Static mapping by dual recursive bipartitioning of process architecture graphs
Static mapping by dual recursive bipartitioning of process architecture graphs
复制标题
通过进程架构图的双重递归二分区进行静态映射
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
F. Pellegrini
中科院分区：
文献类型：
--
作者：
F. Pellegrini
将并行程序的通信进程分配到并行机上以最小化其总执行时间的组合优化问题称为静态映射。这个问题一般来说是NP完全问题。我们引入了一种基于源进程图和目标架构图的递归二分的映射算法，其分而治之和模块化方法允许处理许多拓扑和二分启发式。为了说明这一特征，我们提供了超立方体、二元 de Buijn 和二维网格图上的映射结果。<<ETX>>
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 referred to as static mapping. This problem is NP-complete in general. We introduce a mapping algorithm based on the recursive bipartitioning of both the source process graph and the target architecture graph, whose divide and conquer and modular approach allows the handling of many topologies and bipartitioning heuristics. Mapping results on hypercube, binary de Buijn, and bidimensional mesh graphs are presented in order to illustrate this feature.<<ETX>>