Algorithms and Abstractions for Mapping Parallel Algorithms to 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.