Informationen zur Vorlesung »Parallele Sortiernetzwerke«
Hier kann man mir eine
E-Mail schicken.
Ort und Zeit
Vorlesung: Donnerstags, 16:01 Uhr - 17:30 Uhr in Hörsaal D1
Übung: Donnerstags, 17:30 Uhr - 18:15 Uhr in Hörsaal D1
Übungszettel
Stichworte zu den einzelnen Vorlesungen
- 19.04.: Komparatoren, das 0-1-Prinzip, Odd-Even Merge Sort
- 27.04.: Bitonic Sort, korrespondierende Prozessornetzwerke,
die (mehrdimensionalen) Gitter-Netzwerke
- 04.05.: Index-Schemata, Shearsort auf dem zweidimensionalen
Gitter
- 11.05.: Shearsort mit 2er-Potenz-Breite, mehrdimensionales
Shearsort
- 18.05.: Schnelles Sortieren auf mehrdimensionalen Gittern
ohne und mit Routing
(Zeit: O(d²mlog m)
bzw. O(d²m))
- 01.06.: Einführung in das AKS-Sortiernetzwerk
Literaturhinweise
Bücher
- D. E. Knuth.
The Art of Computer Programming, Volume 3: Sorting and
Searching.
Addison-Wesley, Reading, Massachusetts, 1973.
- F. T. Leighton.
Introduction to Parallel Algorithms and Architectures: Arrays ·
Trees · Hypercubes.
Morgan Kaufmann Publishers, San Mateo, CA, 1992.
- I. Parberry.
Parallel Complexity Theory.
Pitman/Wiley, London, New York, Toronto, 1987.
- R. Wanka.
Paralleles Sortieren auf mehrdimensionalen Gittern.
Dissertation, Universität-GH Paderborn, 1994.
Aufsätze
- M. Kutylowski and R. Wanka.
Periodic
Sorting on Two-Dimensional Meshes.
Parallel Processing Letters, 2:213-220, 1992.
- R. Wanka.
Fast
General Sorting on Meshes of Arbitrary Dimension Without Routing.
Forschungsbericht Nr. 87, August 1991, Universität-GH Paderborn,
Fachbereich 17.
- K. E. Batcher.
Sorting networks and their applications.
In AFIPS Conf. Proc. 32, pp. 307-314, 1968.
- I. D. Scherson and S. Sen.
Parallel sorting in two-dimensional VLSI models of computation.
IEEE Transactions on Computers, 38:238-249, 1989.
- M. S. Paterson.
Improved sorting networks with O(log n) depth.
Algorithmica, 5:75-92, 1990.
Rolf Wanka
(email:
wanka@uni-paderborn.de)