Summer 02

- Parallel Machines and their Models
- Logical and physical interconnection Networks
- Fundamental communication operations: Routing, Broadcasting, Synchronization, Reduction, Gathering Scattering, Prefix Sums,...
- Sorting
- Parallel data structures
- Graph algorithms
- Mutual simulation between parallel models
- Load balancing
- Data management in networks

- 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

- April 10: Models
- April 17: The relation between parallel algorithms and circuits. Reduction, Prefix, Addition, Multiplication. Main source: Leighton92, Section 1.2, 2.3
- April 24: Collective communication. Main source: KumarEtAl, Chapter 3
- Mai 2: Advanced Broadcasting algorithms. Sources: SandersSibeyn2000, JohnsonHo 1989
- Mai 8: Routing h-relations offline. This needs bipartite edge coloring as a subroutine. This needs list ranking as a subroutine. Sources: SandersSolis-Oba2000, JaJa Section 3.1
- Mai 15: Load balancing: Master-Worker, Round Robin, Work Stealing (The book by Sanders and Worsch and the PhD Thesis of Sanders
- Mai 22: Load balancing by random allocation
- Mai 29: Parallel Linear Algebra; in particular Matrix-Vector-Multiplication
- June 5: Load balancing by balanced random allocation
- June 12/19: Off-line routing on meshes and permutation networks (Source: Annexstein, Baumslag, SPAA 1990)
- June 26: On-line randomized Routing on the Butterfly (Source: Leighton 92, Section 3.4.4, 3.4.5)
- July 3: Parallel Programming with MPI and Posix Threads. Source: MPI Standard, the book by Sanders and Worsch.
- July 10:

**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"

Summer 02

- Parallel Machines and their Models
- Logical and physical interconnection Networks
- Fundamental communication operations: Routing, Broadcasting, Synchronization, Reduction, Gathering Scattering, Prefix Sums,...
- Sorting
- Parallel data structures
- Graph algorithms
- Mutual simulation between parallel models
- Load balancing
- Data management in networks

- 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

- April 10: Models
- April 17: The relation between parallel algorithms and circuits. Reduction, Prefix, Addition, Multiplication. Main source: Leighton92, Section 1.2, 2.3
- April 24: Collective communication. Main source: KumarEtAl, Chapter 3
- Mai 2: Advanced Broadcasting algorithms. Sources: SandersSibeyn2000, JohnsonHo 1989
- Mai 8: Routing h-relations offline. This needs bipartite edge coloring as a subroutine. This needs list ranking as a subroutine. Sources: SandersSolis-Oba2000, JaJa Section 3.1
- Mai 15: Load balancing: Master-Worker, Round Robin, Work Stealing (The book by Sanders and Worsch and the PhD Thesis of Sanders
- Mai 22: Load balancing by random allocation
- Mai 29: Parallel Linear Algebra; in particular Matrix-Vector-Multiplication
- June 5: Load balancing by balanced random allocation
- June 12/19: Off-line routing on meshes and permutation networks (Source: Annexstein, Baumslag, SPAA 1990)
- June 26: On-line randomized Routing on the Butterfly (Source: Leighton 92, Section 3.4.4, 3.4.5)
- July 3: Parallel Programming with MPI and Posix Threads. Source: MPI Standard, the book by Sanders and Worsch.
- July 10:

**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--