Fastmap: a distributed scheme for mapping large scale applications onto computational grids

Abstract

Many large and complex computational applications can be modeled as irregular graphs and are typically characterized by a large number of vertices and edges. This paper proposes a new and fast mapping heuristic, called FastMap, to map this class of applications onto heterogeneous metacomputing platforms such as computational grids. While previous approaches have delved into graph partitioning of the application, we attempt to solve this problem from the clustering perspective. We exploit a hierarchical resource management infrastructure on the grid to distribute the overhead of mapping among a tree of schedulers and develop a scheme that proves to be almost linear in its scalability. Furthermore, we optimize on the result of the mapping with the help of a genetic algorithm at each scheduler node. Our experiments include a 50,000-node application graph from NASA and several other synthetically-generated graphs with as many as 100,000 vertices. Comparisons with another heterogeneous partitioner, MiniMax, show an improvement factor of over 100 on the mapping time, yet with superior quality mapping.