Optimization of PRAM-Programs with Input-Dependent Memory Access

. There exist transformations of PRAM programs with predictable communication behavior to existing architectures. We extend the class of tractable programs to those with communication depending on the input. First, we define this class of programs. Second, we give source code transformations to simplify the programs and to eliminate indirect addresses and conditionals. Third, we show how to derive the communication behavior statically. Fourth, we show how to compute the mapping at compile time. Finally, we give upper time bounds for execution on existing architectures. 1 Introduction In sequential computing the step from programming in machine code to programming in machine independent high level languages has been done for decades. Although high level programming languages are available for parallel machines todays parallel programs highly depend on the architectures they are planed to run on. Designing efficient parallel programs is a difficult task that can be performed by speciali..