Algorithmics for Parallel Computation

本项目研究并行计算的算法。这项工作有两个主要方面：1.开发并行算法设计范例的核心，并针对主要应用领域中出现的问题设计并行算法。这方面的前期工作只是第一阶段，还有很多工作要做。该项目从算法和数据结构方面研究了并行算法的许多基本问题，从算法角度研究了概率算法和随机化算法。算法研究的具体领域包括针对计算几何、模式识别和编程语言中的关键问题的并行算法。在这方面，为计算机视觉、可重定向编译器的构建、分子生物学和重写系统等应用领域的并行算法开发基本技术和设计范例是至关重要的。2.研究并行计算模型到并行体系结构的映射原理。必须更好地理解将并行算法映射到现有和新兴技术上，以便对并行计算的机会和限制有新的见解。在算法方面，这需要开发通用技术来处理同步、内存粒度(以及一般的内存访问)和通信负载等问题。

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.