A framework for automated software partitioning and mapping for distributed multiprocessors

One of the major impediments to the widespread use of large-scale, distributed memory multiprocessors is the difficulty of efficiently partitioning and mapping application algorithms onto these machines so as to extract a large portion of the machines´ peak performance. In this paper, we present the preliminary accomplishments of an ongoing effort aimed at automating the complex tasks of software partitioning and mapping during the: system definition phase of application development for distributed memory multiprocessors. We describe a technique called the Augmented Task Dependency Graph (ATDG) for representing the high-level design of the application software. The ATDG allows one to express functional parallelism as well as data parallelism in a manner that facilitates automated partitioning and mapping. We propose a new strategy for searching through the possible space of design choices for partitioning and mapping. The proposed approach, called hierarchical hybrid search, organizes the search space as a hierarchy of sub-spaces. It permits the use of different search techniques for searching through different search sub-spaces. Examples of search techniques that could be employed in the proposed approach include hill-climbing, simulated annealing, and genetic algorithms