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.