Informationen zum Seminar
»Theorie paralleler Systeme«

Betreuer: Rolf Wanka, Reinhard Lüling

Themenvergabe

Am Dienstag, d. 31.10.95, um 15:00 Uhr in Raum F1.225 (Gebäude Fürstenallee!).

Ort und Zeit des Seminars

Das Seminar wird in der vorlesungsfreien Zeit im Februar 1996 stattfinden. Näheres wird noch bekanntgegeben.

Themen

1. Verfahren, die selbst im Durchschnitt schlecht sind.
   S. A. Savari. Average case analysis of five two-dimensional bubble sorting algorithms. In Proceedings of the 5th ACM-SPAA, pp. 336-345, 1993.

2. Ein Verfahren, das im Durchschnitt gut ist.
   • D. Ierardi. 2D-Bubblesorting in average time O(sqrt(N lg N)). In Proceedings of the 6th ACM-SPAA, pp. 36-45, 1994.
   • D. Ierardi. A simple 2D-Bubblesort for the mesh with good average case complexity. PS-File

3. Ein Verfahren, das immer gut ist.
   • M. Kutylowski, K. Lorys, B. Oesterdiekhoff, R. Wanka. Fast and feasible periodic sorting networks of constant depth. In Proceedings of the 35th IEEE-FOCS, pp. 369-380, 1994. PS-File
   • M. Kutylowski, K. Lorys, B. Oesterdiekhoff, R. Wanka. Constructing Sorting Networks With Constant Period. PS-File

Was man alles mit dem AKS-Ansatz machen kann.

1. Sortieren auf einem Prozessornetzwerk in logarithmischer Zeit.
   T. Leighton. Tight bounds on the complexity of parallel sorting. IEEE Transaction on Computers, 34:344-354, 1985.

2. Fehlertolerantes Sortieren.
   S. Assaf, E. Upfal. Fault tolerant sorting networks. SIAM Journal on Discrete Mathematics, 4:472-480, 1991.

3. Den Median berechnen.
   N. Pippenger. Selection networks. SIAM Journal on Computing, 20:878-887, 1991.

Lastausgleich

1. Lastausgleich auf Parallelrechnern.
   L. Rudolph, M. Slivkin-Allalouf, E. Upfal. A Simple Load Balancing Scheme for Task Allocation in Parallel Machines. In Proceedings of the 3rd ACM-SPAA, pp. 237-245, 1991.

2. Ein realistisches Lastausgleichsverfahren.
   R. Lüling, B. Monien. A Dynamic Distributed Load Balancing Algorithm with Provable Good Performance. In Proceedings of the 5th ACM-SPAA, pp. 164-173, 1993. PS-File

3. Besonders einfache Verfahren.
   C. Xu, B. Monien, R. Lüling, F. Lau. An Analytical Comparison of Nearest Neighbor Algorithms for Load Balancing in Parallel Computers. In Proceedings of the 9th IPPS, pp. 472-479, 1995. PS-File