Parallel Algorithms and Programs

Today, there is a great variety on parallel algorithms for shared-memory architectures, mainly the PRAM. However, the PRAM model does not take into account properties of realistic architectures. Recently, Culler et al. defined a new more realistic machine model which reflects better the practical behaviour of massively parallel computers. Their LogP model differs from the PRAM in the following points. First, the synchronous execution is dropped. Instead all processors perform their computation asynchronously. Second, there is no shared memory assumption. Instead they consider a communication latency, communication overhead and network bandwith. Finally, the number of processors is fixed and cannot increase with the problem size.

We focus on transformation of parallel algorithms and programs on the PRAM to equivalent LogP-programs.

Recent research of mine:

• W. Zimmermann and H. Kumm: On the Implementation of Virtual Shared Memory in: Programming Models For Massively Parallel Computers, pp. 172-178, IEEE, 1993
• W. Zimmermann and W. Loewe: An Approach to Machine-Independent Parallel Programming in: Parallel Programming: CONPAR 94 - VAPP VI, Lecture Notes in Computer Science 854, pp. 277-288, 1994
• W. Loewe and W. Zimmermann: On Finding Optimal Clusterings of Task Graphs in: Parallel Algorithms/Architecture Synthesis pAs'95, IEEE, pp. 241-247,1995
• W. Loewe and W. Zimmermann: Programming Data-Parallel -- Executing Process-Parallel in: Proc. of the ZEUS'95 Workshop on Parallel Processing and Computation, pp. 50-64,1995
• W. Loewe and W. Zimmermann: Upper Time Bounds for Executing PRAM-Programs on the LogP-Machine in: Proc. of the 9th ACM International Conference on Supercomputing, pp.41-50,1995