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 条
  • [41] A divide-and-conquer method with approximate Fermi levels for parallel computations
    Yoshikawa, Takeshi
    Nakai, Hiromi
    THEORETICAL CHEMISTRY ACCOUNTS, 2015, 134 (05)
  • [42] Parallel skeletons for Divide-and-Conquer and Branch-and-Bound techniques
    Dorta, I
    León, C
    Rodríguez, C
    Rojas, A
    ELEVENTH EUROMICRO CONFERENCE ON PARALLEL, DISTRIBUTED AND NETWORK-BASED PROCESSING, PROCEEDINGS, 2003, : 292 - 298
  • [43] A parallel processing method of divide-and-conquer and a highly efficient parallel sorting algorithm
    Huang, Minghe
    Zhong, Cuixiang
    Dai, Liping
    Lei, Gang
    DCABES 2006 Proceedings, Vols 1 and 2, 2006, : 86 - 88
  • [44] ON THE BALANCED DIVIDE-AND-CONQUER EQUATION
    BATAGELJ, V
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1986, 19 (3-4) : 259 - 266
  • [45] DIVIDE-AND-CONQUER IN PLANAR GEOMETRY
    GUTING, RH
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1986, 18 (3-4) : 247 - 263
  • [46] PIPELINES FOR DIVIDE-AND-CONQUER FUNCTIONS
    DEGUZMAN, IP
    HARRISON, PG
    MEDINA, E
    COMPUTER JOURNAL, 1993, 36 (03): : 254 - 268
  • [47] DIVIDE-AND-CONQUER YOUR DATABASE
    LIVINGSTON, D
    SYSTEMS INTEGRATION BUSINESS, 1991, 24 (05): : 43 - 45
  • [48] A divide-and-conquer discretization algorithm
    Min, F
    Xie, LJ
    Liu, QH
    Cai, HB
    FUZZY SYSTEMS AND KNOWLEDGE DISCOVERY, PT 1, PROCEEDINGS, 2005, 3613 : 1277 - 1286
  • [49] PRUNING DIVIDE-AND-CONQUER NETWORKS
    ROMANIUK, SG
    NETWORK-COMPUTATION IN NEURAL SYSTEMS, 1993, 4 (04) : 481 - 494
  • [50] CUTTING HYPERPLANES FOR DIVIDE-AND-CONQUER
    CHAZELLE, B
    DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (02) : 145 - 158
12345