This project is concerned with the design of algorithms and programming environments for parallel computer systems containing large numbers of interconnected processors. The goals are to develop some of the generic algorithmic techniques that users of such systems will require, to determine what primitive operations should be included in a high-level parallel programming language, and to solve some of the algorithmic problems that will arise in the implementation of such primitive operations. The operations of particular interest relate to set-oriented data structures and combinatorial search. The approach to the efficient implementation of these operations uses ideas from randomized load balancing, parallel tree search and dynamic tree embedding. In order to support high-level parallel programming, efficient algorithms for sorting in the presence of faulty processors, message routing and synchronization control are also investigated.
