Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs
F Pellegrini, J Roman - … Conference and Exhibition HPCN EUROPE 1996 …, 1996 - Springer
F Pellegrini, J Roman
High-Performance Computing and Networking: International Conference and …, 1996•SpringerThe combinatorial optimization problem of assigning the communicating processes of a
parallel program onto a parallel machine so as to minimize its overall execution time is
called static mapping. This paper presents Scotch, a software package for static mapping
based on the recursive bipartitioning of both the source process graph and the target
architecture graph. Scotch can map any weighted source graph onto any weighted target
graph in a time linear in the number of source edges and logarithmic in the number of target …
parallel program onto a parallel machine so as to minimize its overall execution time is
called static mapping. This paper presents Scotch, a software package for static mapping
based on the recursive bipartitioning of both the source process graph and the target
architecture graph. Scotch can map any weighted source graph onto any weighted target
graph in a time linear in the number of source edges and logarithmic in the number of target …
Abstract
The combinatorial optimization problem of assigning the communicating processes of a parallel program onto a parallel machine so as to minimize its overall execution time is called static mapping.
This paper presents Scotch, a software package for static mapping based on the recursive bipartitioning of both the source process graph and the target architecture graph. Scotch can map any weighted source graph onto any weighted target graph in a time linear in the number of source edges and logarithmic in the number of target vertices. We give brief descriptions of the algorithm and its bipartitioning methods, and compare its performance to other mapping and partitioning programs.
Springer