Paradigms for Parallel Algorithm Design

该项目旨在为针对并行算法设计的健壮和高效范例的严格研究计划提供理论基础。该项目涉及广泛的范例：-通用范例，包括用于利用树形结构计算、用于设计并行数据结构和用于并行化递归规范的创新方法-用于脉动体系结构的高级设计技术，包括用于设计与拓扑无关的方案的一般方法--用于计算几何的并行设计方案，包括用于利用对输出敏感的数量的处理器和用于并行遍历几何结构的新方法--用于人工智能的技术，包括符号约束满足网络的高效并行解和语义网络中的并行推理--并行计算的健壮性研究，包括高效测试/修改方案和快速并行验收测试此外，PI打算通过实验验证算法中固有的开销，通过在高级并行编程语言中实现它们。

This project aims to develop a theoretical foundation for a rigorous research program on robust and efficient paradigms for parallel algorithm design. The project addresses a broad spectrum of paradigms: - general paradigms, including innovative methods for exploiting treestructured computations, for designing parallel data structures, and for parallelizing recursive specifications - high-level design techniques for systolic architectures, including general methods for designing schemes that are topology independent - parallel design schemes for computational geometry, including novel methods for utilizing an output-sensitive number of processors and for traversing geometric structures in parallel - techniques for artificial intelligence, including efficient parallel solutions of symbolic constraint satisfaction networks and parallel inference in semantic networks - studies in robustness of parallel computations, including highly efficient testing/modifying schemes and fast parallel acceptance testing In addition, the PIs intend to verify experimentally overhead inherent in algorithms, by implementing them in a high-level parallel programming language.