Informationen zur Vorlesung »Parallele Sortiernetzwerke«

Vorlesung: Donnerstags, 16:01 Uhr - 17:30 Uhr in Hörsaal D1
Übung: Donnerstags, 17:30 Uhr - 18:15 Uhr in Hörsaal D1

• Blatt 1
• Blatt 2
• Blatt 3
• Blatt 4
• Blatt 5
• Blatt 6

• 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

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.