A RATIONALE FOR MASSIVELY-PARALLEL PROGRAMMING WITH SETS

The rationale for the design of parallel SETL (PSETL), a language for developing massively parallel programs, is given. The language is buil t atop SETL, a very high-level prototyping language based on set theor y. The addition of explicit parallel constructs enables the concise sp ecification of parallel algorithms. Sets and maps (sets of ordered pai rs) are intrinsic components of parallel-algorithm specifications, for instance, there are sets of subtasks to be performed, and maps betwee n subtasks that represent communication patterns. These constructs are easily represented using set-algebra notation. Sets are unordered, so programs are not forced to over-specify control flow. This simplifies both the implementation and the detection of parallelism. Parallel SE TL includes MIMD and SIMD parallel loops over sets, bags and tuples. D ata-parallel and work queue paradigms are supported. There is a hierar chy of communication mechanisms: CRCW shared variables, associatively accessed maps, fetch & PHI, PHI-reductions and PHI-scans. These parall el features are versatile, and yet the loop-constructs and PHI-operati ons admit efficient highly-parallel implementations. To enhance perfor mance and to facilitate verification, program correctness is not allow ed to depend on the relative execution times of MIMD-loop iterates. Th e range of parallel features supported by parallel SETL, and their rel ationship to other languages and models, is discussed. Their implement ation on parallel machines with atomic fetch and PHI instructions is s ketched.