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 条
  • [1] Divide-and-conquer algorithms on the hypercube
    Mayr, EW
    Werchner, R
    THEORETICAL COMPUTER SCIENCE, 1996, 162 (02) : 283 - 296
  • [2] Automatic inversion generates divide-and-conquer parallel programs
    Morita, Kazutaka
    Morihata, Akimasa
    Matsuzaki, Kiminori
    Hu, Zhenjiang
    Takeichi, Masato
    ACM SIGPLAN NOTICES, 2007, 42 (06) : 146 - 155
  • [3] Automatic Inversion Generates Divide-and-Conquer Parallel Programs
    Morita, Kazutaka
    Morihata, Akimasa
    Matsuzaki, Kiminori
    Hu, Zhenjiang
    Takeichi, Masato
    PLDI'07: PROCEEDINGS OF THE 2007 ACM SIGPLAN CONFERENCE ON PROGRAMMING LANGUAGE DESIGN AND IMPLEMENTATION, 2007, : 146 - 155
  • [4] DIVIDE-AND-CONQUER FOR PARALLEL PROCESSING
    HOROWITZ, E
    ZORAT, A
    IEEE TRANSACTIONS ON COMPUTERS, 1983, 32 (06) : 582 - 585
  • [5] Automated transformation of sequential divide-and-conquer algorithms into parallel programs
    Freisleben, B
    Kielmann, T
    COMPUTERS AND ARTIFICIAL INTELLIGENCE, 1995, 14 (06): : 579 - 596
  • [6] Mapping parallel programs onto hypercube computers to minimize link-contention degree
    Chan, KL
    Shen, H
    1996 IEEE SECOND INTERNATIONAL CONFERENCE ON ALGORITHMS & ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP'96, PROCEEDINGS OF, 1996, : 44 - 52
  • [7] DIVIDE-AND-CONQUER AND PARALLEL GRAPH REDUCTION
    RABHI, FA
    MANSON, GA
    PARALLEL COMPUTING, 1991, 17 (2-3) : 189 - 205
  • [8] REVERSE SCHEDULING - AN EFFECTIVE METHOD FOR SCHEDULING TASKS OF PARALLEL PROGRAMS EMPLOYING A DIVIDE-AND-CONQUER STRATEGY ONTO MULTIPROCESSORS
    SREENIVAS, A
    MURTHY, KNB
    MURTHY, CSR
    MICROPROCESSORS AND MICROSYSTEMS, 1994, 18 (04) : 187 - 192
  • [9] Generating synchronization statements in divide-and-conquer programs
    Hijma, Pieter
    van Nieuwpoort, Rob V.
    Jacobs, Ceriel J. H.
    Bal, Henri E.
    PARALLEL COMPUTING, 2012, 38 (1-2) : 75 - 89
  • [10] Parallel divide-and-conquer scheme for Delaunay triangulation
    Chen, MB
    Chuang, TR
    Wu, JJ
    NINTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, PROCEEDINGS, 2002, : 571 - 576
12345