Parallele Algorithmen

Ein Schlüsselproblem beim parallelen Rechnen in großen Prozessornetzwerken ist die effiziente Kommunikation der Prozessoren untereinander. Wir haben, hauptsächlich für Gitternetzwerke, verschiedene Fragestellungen unter (relativ einfachen) Annahmen untersucht, z.B.

• Sortieren von Schlüsseln, die auf den Netzwerken verteilt sind
• statisches Realisieren von vorgegebenen Permutationen von Paketen
• Verschicken von Einzel- und Mehrfachnachrichten (randomisiert und deterministisch)
• Permutationsrouting auf Busstrukturen bzw. rekonfigurierbaren Netzwerken
• Laufzeitverhalten vs. Größe der lokalen Speicher (Ziel: Hot-Potato-Routing)
• Praxistauglichkeit der Verfahren

In Zukunft wollen wir uns noch intensiver um praxistaugliche Verfahren bemühen, dabei auch Aspekte wie Fehlertoleranz untersuchen, sowie Algorithmen aus anderen Bereichen (z.B. der Bildverarbeitung) effizient auf Gitternetzwerke übertragen.

Veröffentlichungen

M. Kaufmann, H. Schröder, J. F. Sibeyn: "Asymptotically Optimal and Practical Routing on Reconfigurable Meshes", Special Issue of 'Parallel Processing Letters', Vol. 5(1) , pp. 81-95, 1995.

M. Kaufmann, J. F. Sibeyn, T. Suel: "Beyond the Bisection Bound: Fast Ranking and Counting on Meshes", Proc. 3rd European Symposium on Algorithms (ESA '95), LNCS 979, Springer Verlag, pp. 75-88, 1995.

B. Chlebus, M. Kaufmann, J. F. Sibeyn: "Deterministic Permutation Routing on Meshes", Journal of Algorithms 22, pp. 111-141, 1997.

M. Kaufmann, R. Raman, J. F. Sibeyn: "Randomized Routing on Meshes with Buses", Algorithmica 18, pp. 417-444, 1997.

M. Kaufmann, U. Meyer, J. F. Sibeyn: "Matrix Transpose on Meshes: Theory and Practice", Computers and Artificial Intelligence, Vol. 16, pp. 107-140, 1997.