Abstract
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.