Divide-and-conquer mapping of parallel programs onto hypercube computers

被引：3
|
作者：
Lor, S [1 ]
Shen, H [1 ]
Maheshwari, P [1 ]
机构：
[1] GRIFFITH UNIV,SCH COMP & INFORMAT TECHNOL,BRISBANE,QLD 4111,AUSTRALIA
来源：
JOURNAL OF SYSTEMS ARCHITECTURE | 1997年 / 43卷 / 6-7期
关键词：
graph partitioning; mapping problem; clustering; hypercube; task allocation/assignment; heuristic algorithm;
D O I：
10.1016/S1383-7621(96)00052-5
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Mapping of parallel programs onto parallel computers for efficient execution is a fundamental problem of great significance in parallel processing. This paper describes a heuristic algorithm for mapping arbitrary parallel programs onto hypercube computers using a divide-and-conquer technique. The running time of our algorithm is O(dn(3)), where n is the number of tasks in the parallel program and d is the dimension of the hypercube computer. The algorithm is implemented in C + + and its performance is evaluated through extensive testing and analysis.
引用
收藏
页码：373 / 390
页数：18
相关论文
共 50 条
  • [21] Divide-and-conquer checkpointing for arbitrary programs with no user annotation
    Siskind, Jeffrey Mark
    Pearlmutter, Barak A.
    OPTIMIZATION METHODS & SOFTWARE, 2018, 33 (4-6): : 1288 - 1330
  • [22] A Parallel Skeleton for Divide-and-conquer Unbalanced and Deep Problems
    Martinez, Millan A.
    Fraguela, Basilio B.
    Cabaleiro, Jose C.
    INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING, 2021, 49 (06) : 820 - 845
  • [23] Modeling and simulation of parallel adaptive divide-and-conquer algorithms
    Barros, Fernando J.
    JOURNAL OF SUPERCOMPUTING, 2008, 43 (03): : 241 - 255
  • [24] Satin: Efficient parallel divide-and-conquer in Java']Java
    van Nieuwpoort, RV
    Kielmann, T
    Bal, HE
    EURO-PAR 2000 PARALLEL PROCESSING, PROCEEDINGS, 2000, 1900 : 690 - 699
  • [25] Parallel divide-and-conquer phylogeny reconstruction by maximum likelihood
    Du, Z
    Stamatakis, A
    Lin, F
    Roshan, U
    Nakhleh, L
    HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS, PROCEEDINGS, 2005, 3726 : 776 - 785
  • [26] EFFICIENT PARALLEL DIVIDE-AND-CONQUER FOR A CLASS OF INTERCONNECTION TOPOLOGIES
    WU, IC
    LECTURE NOTES IN COMPUTER SCIENCE, 1991, 557 : 229 - 240
  • [27] A Parallel Skeleton for Divide-and-conquer Unbalanced and Deep Problems
    Millán A. Martínez
    Basilio B. Fraguela
    José C. Cabaleiro
    International Journal of Parallel Programming, 2021, 49 : 820 - 845
  • [28] The divide-and-conquer manifesto
    Dietterich, TG
    ALGORITHMIC LEARNING THEORY, PROCEEDINGS, 2000, 1968 : 13 - 26
  • [29] Modeling and simulation of parallel adaptive divide-and-conquer algorithms
    Fernando J. Barros
    The Journal of Supercomputing, 2008, 43 : 241 - 255
  • [30] CASCADING DIVIDE-AND-CONQUER - A TECHNIQUE FOR DESIGNING PARALLEL ALGORITHMS
    ATALLAH, MJ
    COLE, R
    GOODRICH, MT
    SIAM JOURNAL ON COMPUTING, 1989, 18 (03) : 499 - 532
12345