Algorithms and Abstractions for Mapping Parallel Algorithms to Parallel Architectures

将并行算法映射到并行架构的算法和抽象

• 批准号: 9108528
• 负责人: Bella Bose
• 金额: $ 30.59万
• 依托单位: Oregon Advanced Computing Institute
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-01-01 至 1995-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9108528&HistoricalAwards=false
• 关键词: Algorithms; Abstractions; Mapping; Parallel; Architectures

Lo The problem of mapping parallel algorithms to parallel architectures involves the assignment of tasks in the parallel computation to processors and the routing of messages through the interconnection network. This research utilizes information about the regularity present in both the computation and the interconnection network for efficient mapping. It focuses on the design, implementation, and testing of mapping algorithms for three target architectures: the mesh, hypercube, and deBruijn network. In addition, it develops a graph description language and an underlying graph theoretic model to support mapping. The model captures information about the static and temporal structure of the computation, while the language enables the user to express this information in a natural and compact notation. This research represents a step in the evolution toward automatic mapping. It paves the way for the compiler to play an increasing important role as a source of information for the mapper.

将并行算法映射到并行体系结构的问题涉及到将并行计算中的任务分配给处理器以及通过互连网络的消息路由。本研究利用计算和互连网络中存在的规律性信息进行有效的映射。它侧重于三种目标体系结构的映射算法的设计、实现和测试：网格、超立方体和deBruijn网络。此外，还开发了图描述语言和支持映射的底层图论模型。该模型捕获有关计算的静态和时态结构的信息，而该语言使用户能够以自然和紧凑的符号表示这些信息。这项研究代表了向自动映射进化的一步。它为编译器作为映射器的信息源发挥越来越重要的作用铺平了道路。