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
相关论文
共 25 条
  • [21] Parallel clustering of high dimensional data by integrating multi-objective genetic algorithm with divide and conquer
    Ozyer, Tansel
    Alhajj, Reda
    APPLIED INTELLIGENCE, 2009, 31 (03) : 318 - 331
  • [22] MAPPING PARALLEL PROGRAMS INTO HIERARCHICAL DISTRIBUTED COMPUTER SYSTEMS
    Khoroshevsky, Victor G.
    Kurnosov, Mikhail G.
    ICSOFT 2009: PROCEEDINGS OF THE 4TH INTERNATIONAL CONFERENCE ON SOFTWARE AND DATA TECHNOLOGIES, VOL 2, 2009, : 123 - 128
  • [23] AN EFFICIENT ALGORITHM FOR MAPPING VLSI CIRCUIT SIMULATION PROGRAMS ONTO MULTIPROCESSORS
    SELVAKUMAR, S
    MURTHY, CSR
    PARALLEL COMPUTING, 1991, 17 (09) : 1009 - 1016
  • [24] An Agglomeration Strategy for the Parallel Processes Mapping onto a Distributed Computing Architecture
    Catana-Salazar, Juan C.
    Ortega-Arjona, Jorge L.
    HIGH PERFORMANCE COMPUTER APPLICATIONS, 2016, 595 : 201 - 212
  • [25] Mapping Parallel Programs to Heterogeneous CPU/GPU Architectures using a Monte Carlo Tree Search
    Goli, Mehdi
    McCall, John
    Brown, Christopher
    Janjic, Vladimir
    Hammond, Kevin
    2013 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2013, : 2932 - 2939
123