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 条
  • [1] Spectral clustering for divide-and-conquer graph matching
    Lyzinski, Vince
    Sussman, Daniel L.
    Fishkind, Donniell E.
    Pao, Henry
    Chen, Li
    Vogelstein, Joshua T.
    Park, Youngser
    Priebe, Carey E.
    PARALLEL COMPUTING, 2015, 47 : 70 - 87
  • [2] Divide-and-conquer minimal-cut bisectioning of task graphs
    Lor, S
    Shen, H
    Maheshwari, P
    COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 1996, 11 (04): : 227 - 234
  • [3] Iteratively Divide-and-Conquer Learning for Nonlinear Classification and Ranking
    Wu, Ou
    Mao, Xue
    Hu, Weiming
    ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY, 2018, 9 (02)
  • [4] A divide-and-conquer method for multi-net classifiers
    Frosyniotis, D
    Stafylopatis, A
    Likas, A
    PATTERN ANALYSIS AND APPLICATIONS, 2003, 6 (01) : 32 - 40
  • [5] A Divide-and-Conquer Approach for Minimum Spanning Tree-Based Clustering
    Wang, Xiaochun
    Wang, Xiali
    Wilkes, Mitchell
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2009, 21 (07) : 945 - 958
  • [6] Two provably consistent divide-and-conquer clustering algorithms for large networks
    Mukherjee, Soumendu Sundar
    Sarkar, Purnamrita
    Bickel, Peter J.
    PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2021, 118 (44)
  • [7] Multi - Warehouse Location of Logistics Based on Dijkstra and Divide-and-Conquer Algorithm
    Hou, Donggu
    Zhang, Wei
    2017 10TH INTERNATIONAL SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE AND DESIGN (ISCID), VOL. 1, 2017, : 442 - 447
  • [8] Heuristic algorithm based on a genetic algorithm for mapping parallel programs on hypercube multiprocessors
    Aguilar, J
    COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 2003, 18 (04): : 217 - 221
  • [9] A DIVIDE-AND-CONQUER APPROACH TO LATENT PERCEPTUAL INDEXING OF AUDIO FOR LARGE WEB 2.0 APPLICATIONS
    Sundaram, Shiva
    Narayanan, Shrikanth
    ICME: 2009 IEEE INTERNATIONAL CONFERENCE ON MULTIMEDIA AND EXPO, VOLS 1-3, 2009, : 466 - +
  • [10] MAPPING SINGLE AND MULTIPLE MULTILEVEL STRUCTURES ONTO THE HYPERCUBE
    ZIAVRAS, SG
    IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES, 1993, 140 (02): : 115 - 118
123