[MPI Logo] HEIGHT=84 WIDTH=142 [InfoLogo] HEIGHT=84 WIDTH=142

Parallel and Distributed Algorithms
Summer 02

When many processors cooperate to jointly solve a problem we get a potential for higher performance and a wider range of applications in networks of computers. In this lecture on parallel and distributed algorithms you learn how to design algorithms that can take advantage of parallel processors and can cope with the added difficulties of coordinating a network of computers. The emphasis is on efficient algorithms that are both theoretically interesting and practically relevant. The lecture is roughly divided in two parts. In Part A, we study basic models, the implementation of primitives and simple algorithmic techniques that are demonstrated using toy applications but can be used in a wide spectrum of real world applications. Part A will somewhat resemble the content of an earlier lecture. In Part B, we study selected advanced topics like, e.g., stability and performance aspects of packet routing, online data management in networks, and randomized load allocation schemes.

[InfoLogo] HEIGHT=84 WIDTH=142

Preliminary Overview

Prerequisites

Basic Algorithms and Data Structures, e.g., from Info V.

Further Information

Lectures: Wednesday 14:00-16:00 Geb.: 45, Room: HS 001
Lecturers
Privatdozent Dr. Peter Sanders, Geb.46 R.308, sanders@mpi-sb.mpg.de
Dr. Berthold Vöcking, Geb.46, R.319, voecking@mpi-sb.mpg.de

Topics of Lectures

Challenges and Topics for Diplomarbeiten

Literature

See also, Semesterapparat AG1 in the MPII Library
1
S. G. Akl. Parallel Computation: Models and Methods. Prentice-Hall, 1997. Chapter 12.

2
J. Jájá. An Introduction to Parallel Algorithms. Addison Wesley, 1992.

3
S. L. Johnsson and C. T. Ho. Optimum broadcasting and personalized communication in hypercubes. IEEE Transactions on Computers, 38(9):1249-1268, 1989.

4
V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing. Design and Analysis of Algorithms. Benjamin/Cummings, 1994.

5
T. Leighton. Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, 1992.

6
P. Sanders and J. Sibeyn. A Bandwidth Latency Tradeoff for Broadcast and Reduction. In 6th Euro-Par, number 1900 in LNCS, pages 918-926. Springer ©, 2000.

7
P. Sanders and R. Solis-Oba. How Helpers Hasten h-Relations. In 8th European Symposium on Algorithms (ESA), number 1879 in LNCS, pages 392-402, 2000. final paper.

8
P. Sanders and T. Worsch. Parallele Programmierung mit MPI - ein Praktikum. Logos Verlag Berlin, 1997. ISBN 3-931216-76-4.

begin:vcard n:Vöcking;Berthold tel;fax:+49 +681 +9325 199 tel;home:+49 +681 +910 2277 tel;work:+49 +681 +932 5119 x-mozilla-html:FALSE url:http://www.mpi-sb.mpg.de org:MPI für Informatik version:2.1 email;internet:voecking@mpi-sb.mpg.de adr;quoted-printable:;;Stuhlsatzenhausweg 85=0D=0A;66123 Saarbrücken;;; x-mozilla-cpt:;-26152 fn:Berthold Voecking end:vcard This is a multi-part message in MIME format. --------------4CFAC215B9E2D93FD72C2796 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hallo Peter, im Anhang findest Du eine ueberarbeitete Version unserer Hompage fuer die Vorlesung "Parallele Algorithmen". -- Berthold --------------4CFAC215B9E2D93FD72C2796 Content-Type: text/html; charset=us-ascii; name="index.html" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="index.html" [MPI Logo] HEIGHT=84 WIDTH=142 [InfoLogo] HEIGHT=84 WIDTH=142

Parallel and Distributed Algorithms
Summer 02

When many processors cooperate to jointly solve a problem we get a potential for higher performance and a wider range of applications in networks of computers. In this lecture on parallel and distributed algorithms you learn how to design algorithms that can take advantage of parallel processors and can cope with the added difficulties of coordinating a network of computers. The emphasis is on efficient algorithms that are both theoretically interesting and practically relevant. The lecture is roughly divided in two parts. In Part A, we study basic models, the implementation of primitives and simple algorithmic techniques that are demonstrated using toy applications but can be used in a wide spectrum of real world applications. Part A will somewhat resemble the content of an earlier lecture. In Part B, we study selected advanced topics like, e.g., stability and performance aspects of packet routing, online data management in networks, and randomized load allocation schemes.

[InfoLogo] HEIGHT=84 WIDTH=142

Preliminary Overview

Prerequisites

Basic Algorithms and Data Structures, e.g., from Info V.

Further Information

Lectures: Wednesday 14:00-16:00 Geb.: 45, Room: HS 001
Lecturers
Privatdozent Dr. Peter Sanders, Geb.46 R.308, sanders@mpi-sb.mpg.de
Dr. Berthold Vöcking, Geb.46, R.319, voecking@mpi-sb.mpg.de

Topics of Lectures

Challenges and Topics for Diplomarbeiten

Literature

See also, Semesterapparat AG1 in the MPII Library
1
S. G. Akl. Parallel Computation: Models and Methods. Prentice-Hall, 1997. Chapter 12.

2
J. Jájá. An Introduction to Parallel Algorithms. Addison Wesley, 1992.

3
S. L. Johnsson and C. T. Ho. Optimum broadcasting and personalized communication in hypercubes. IEEE Transactions on Computers, 38(9):1249-1268, 1989.

4
V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing. Design and Analysis of Algorithms. Benjamin/Cummings, 1994.

5
T. Leighton. Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, 1992.

6
P. Sanders and J. Sibeyn. A Bandwidth Latency Tradeoff for Broadcast and Reduction. In 6th Euro-Par, number 1900 in LNCS, pages 918-926. Springer ©, 2000.

7
P. Sanders and R. Solis-Oba. How Helpers Hasten h-Relations. In 8th European Symposium on Algorithms (ESA), number 1879 in LNCS, pages 392-402, 2000. final paper.

8
P. Sanders and T. Worsch. Parallele Programmierung mit MPI - ein Praktikum. Logos Verlag Berlin, 1997. ISBN 3-931216-76-4.

--------------4CFAC215B9E2D93FD72C2796 Content-Type: text/x-vcard; charset=us-ascii; name="voecking.vcf" Content-Transfer-Encoding: 7bit Content-Description: Card for Berthold Vöcking Content-Disposition: attachment; filename="voecking.vcf" begin:vcard n:Vöcking;Berthold tel;fax:+49 +681 +9325 199 tel;home:+49 +681 +910 2277 tel;work:+49 +681 +932 5119 x-mozilla-html:FALSE url:http://www.mpi-sb.mpg.de org:MPI für Informatik version:2.1 email;internet:voecking@mpi-sb.mpg.de adr;quoted-printable:;;Stuhlsatzenhausweg 85=0D=0A;66123 Saarbrücken;;; x-mozilla-cpt:;-26152 fn:Berthold Voecking end:vcard --------------4CFAC215B9E2D93FD72C2796--