This project investigates algorithmics for parallel computation. There are two thrusts to this work: 1. The development of a core of parallel algorithmic design paradigms and the designing of parallel algorithms for problems arising in major application domains. Prior work in this area is only a first stage and much remains to be done. This project studies many unresolved issues fundamental to parallel algorithms from an algorithmic and data structures, along with probabilistic and randomized algorithms from an algorithmic perspective. Specific areas for algorithmic research include parallel algorithms for key problems from computational geometry, pattern recognition, and programming languages. In this connection, it is crucial to develop fundamental techniques and design paradigms for parallel algorithms in application areas such as computer vision, construction of retargetable compilers, molecular biology, and rewriting systems. 2. The investigation of principles for mapping parallel models of computation onto parallel architectures. The mapping of parallel algorithms onto available and emerging technologies has to be better understood so as to gain new insights into the opportunities and constraints of parallel computing. On the algorithmic side, this calls for developing general techniques for coping with problems like synchrony, memory granularity (and memory access, in general), and communication load.
