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 条

[31] DIVIDE-AND-CONQUER ORTHOGONALITY PRINCIPLE FOR PARALLEL OPTIMIZATIONS IN TSP
SZU, H
FOO, S
NEUROCOMPUTING, 1995, 8 (03) : 249 - 261
[32] Divide-and-Conquer Fusion
Chan, Ryan S. Y.
Pollock, Murray
Johansen, Adam M.
Roberts, Gareth O.
JOURNAL OF MACHINE LEARNING RESEARCH, 2023, 24
[33] HEADINGS, OR DIVIDE-AND-CONQUER
DOLLE, R
JOURNAL OF ENVIRONMENTAL HEALTH, 1990, 53 (03) : 56 - 56
[34] MULTIDIMENSIONAL DIVIDE-AND-CONQUER
BENTLEY, JL
COMMUNICATIONS OF THE ACM, 1980, 23 (04) : 214 - 229
[35] CLUSTER-PARTITIONING APPROACHES TO MAPPING PARALLEL PROGRAMS ONTO A HYPERCUBE
SADAYAPPAN, P
ERCAL, F
LECTURE NOTES IN COMPUTER SCIENCE, 1988, 297 : 475 - 497
[36] An Efficient Parallel Divide-and-Conquer Algorithm for Generalized Matrix Multiplication
Eagan, John
Herdman, Marc
Vaughn, Christian
Bean, Nathaniel
Kern, Sarah
Pirouz, Matin
2023 IEEE 13TH ANNUAL COMPUTING AND COMMUNICATION WORKSHOP AND CONFERENCE, CCWC, 2023, : 442 - 449
[37] A parallel symmetric block-tridiagonal divide-and-conquer algorithm
Bai, Yihua
Ward, Robert C.
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2007, 33 (04):
[38] A divide-and-conquer method with approximate Fermi levels for parallel computations
Takeshi Yoshikawa
Hiromi Nakai
Theoretical Chemistry Accounts, 2015, 134
[39] A PARALLEL DIVIDE-AND-CONQUER ALGORITHM FOR FINDING MINIMUM ENERGY TRAJECTORIES
Leandro, Carlos
Ambrosio, Jorge
PROCEEDINGS OF THE 7TH INTERNATIONAL CONFERENCE ON MECHANICS AND MATERIALS IN DESIGN (M2D2017), 2017, : 155 - 156
[40] Parallel implementation of divide-and-conquer semiempirical quantum chemistry calculations
Pan, W
Lee, TS
Yang, WT
JOURNAL OF COMPUTATIONAL CHEMISTRY, 1998, 19 (09) : 1101 - 1109

← 1 2 3 4 5 →