Parallel Algorithms for Hierarchical Memory Multiprocessors

该项目涉及并行计算机扩展模型上的并行算法的设计和分析。需要开发能够准确反映并行计算机体系结构和操作系统机制的机器，并分析它们对并行算法设计和性能的影响。要建模的特征包括分层存储结构、并行I/O子系统组织和同步机制。解决这些问题的合适范例是基于使用具有粗粒度并行性的分区算法。该范例区分了与算法和体系结构相关的开销，易于进行定量分析，并提供了一个框架，用于将解决方案扩展到细粒度系统，以及从共享内存到松散耦合的分布式内存系统的跨模型。该项目通过对并行体系结构的适当建模、对这些扩展模型的并行算法设计和分析以及在实际和模拟的并行机上的验证，对该范例进行了系统的研究。

This project concerns the design and analysis of parallel algorithms on extended models of parallel computers. Abstract machines that accurately reflect architectural and operating system mechanisms of parallel computers need to be developed, and their impact on the design and the performance of parallel algorithms analyzed. Features to be modeled include hierarchical storage structures, parallel I/O subsystem organizations, and synchronization mechanisms. An appropriate paradigm addressing these issues is based on using partitioning algorithms with coarse-grained parallelism. This paradigm distinguishes between algorithmic and architecture related overheads, is amenable to quantitative analysis, and provides a framework for scaling solutions to fine-grained systems, as well as across models from shared-memory to loosely-coupled, distributed- memory systems. The project involves a systematic investigation of the paradigm, by appropriate modeling of parallel architectures, parallel algorithm design and analysis on these extended models, and validation on actual and simulated parallel machines.