A Network-Topology-Independent Static Task Allocation Strategy for Massively Parallel Computers

Takanobu BABA; Akehito GUNJI; Yoshifumi IWAMOTO

A Network-Topology-Independent Static Task Allocation Strategy for Massively Parallel Computers

Takanobu BABA, Akehito GUNJI, Yoshifumi IWAMOTO

Full Text Views

0

Cite this

Summary :

A network-topology-independent static task allocation strategy has been designed and implemented for massively parallel computers. For mapping a task graph to a processor graph, this strategy evaluates several functions that represent some intuitively feasible properties or the graphs. They include the connectivity with the allocated nodes, distance from the median of a graph, connectivity with candidate nodes, and the number of candidate nodes within a distance. Several greedy strategies are defined to guide the mapping process, utilizing the indicated function values. An allocation system has been designed and implemented based on the allocation strategy. In experiments we have defined about 1000 nodes in task graphs with regular and irregular topologies, and the same order of processors with mesh, tree, and hypercube topologies. The results are summarized as follows. 1) The system can yield 4.0 times better total communication costs than an arbitrary allocation. 2) It is difficult to select a single strategy capable of providing the best solutions for a wide range of task-processor combinations. 3) Comparison with hypercube-topology-dependent research indicates that our topology-independent allocator produces better results than the dependent ones. 4) The order of computaion time of the allocator is experimentally proved to be O (n²) where n represents the number of tasks.

Publication: IEICE TRANSACTIONS on Information Vol.E76-D No.8 pp.870-881

Publication Date: 1993/08/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computer Networks

Cite this

Copy

Takanobu BABA, Akehito GUNJI, Yoshifumi IWAMOTO, "A Network-Topology-Independent Static Task Allocation Strategy for Massively Parallel Computers" in IEICE TRANSACTIONS on Information, vol. E76-D, no. 8, pp. 870-881, August 1993, doi: .
Abstract: A network-topology-independent static task allocation strategy has been designed and implemented for massively parallel computers. For mapping a task graph to a processor graph, this strategy evaluates several functions that represent some intuitively feasible properties or the graphs. They include the connectivity with the allocated nodes, distance from the median of a graph, connectivity with candidate nodes, and the number of candidate nodes within a distance. Several greedy strategies are defined to guide the mapping process, utilizing the indicated function values. An allocation system has been designed and implemented based on the allocation strategy. In experiments we have defined about 1000 nodes in task graphs with regular and irregular topologies, and the same order of processors with mesh, tree, and hypercube topologies. The results are summarized as follows. 1) The system can yield 4.0 times better total communication costs than an arbitrary allocation. 2) It is difficult to select a single strategy capable of providing the best solutions for a wide range of task-processor combinations. 3) Comparison with hypercube-topology-dependent research indicates that our topology-independent allocator produces better results than the dependent ones. 4) The order of computaion time of the allocator is experimentally proved to be O (n²) where n represents the number of tasks.
URL: https://global.ieice.org/en_transactions/information/10.1587/e76-d_8_870/_p

Copy

@ARTICLE{e76-d_8_870,
author={Takanobu BABA, Akehito GUNJI, Yoshifumi IWAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={A Network-Topology-Independent Static Task Allocation Strategy for Massively Parallel Computers},
year={1993},
volume={E76-D},
number={8},
pages={870-881},
abstract={A network-topology-independent static task allocation strategy has been designed and implemented for massively parallel computers. For mapping a task graph to a processor graph, this strategy evaluates several functions that represent some intuitively feasible properties or the graphs. They include the connectivity with the allocated nodes, distance from the median of a graph, connectivity with candidate nodes, and the number of candidate nodes within a distance. Several greedy strategies are defined to guide the mapping process, utilizing the indicated function values. An allocation system has been designed and implemented based on the allocation strategy. In experiments we have defined about 1000 nodes in task graphs with regular and irregular topologies, and the same order of processors with mesh, tree, and hypercube topologies. The results are summarized as follows. 1) The system can yield 4.0 times better total communication costs than an arbitrary allocation. 2) It is difficult to select a single strategy capable of providing the best solutions for a wide range of task-processor combinations. 3) Comparison with hypercube-topology-dependent research indicates that our topology-independent allocator produces better results than the dependent ones. 4) The order of computaion time of the allocator is experimentally proved to be O (n²) where n represents the number of tasks.},
keywords={},
doi={},
ISSN={},
month={August},}

Copy

TY - JOUR
TI - A Network-Topology-Independent Static Task Allocation Strategy for Massively Parallel Computers
T2 - IEICE TRANSACTIONS on Information
SP - 870
EP - 881
AU - Takanobu BABA
AU - Akehito GUNJI
AU - Yoshifumi IWAMOTO
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E76-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 1993
AB - A network-topology-independent static task allocation strategy has been designed and implemented for massively parallel computers. For mapping a task graph to a processor graph, this strategy evaluates several functions that represent some intuitively feasible properties or the graphs. They include the connectivity with the allocated nodes, distance from the median of a graph, connectivity with candidate nodes, and the number of candidate nodes within a distance. Several greedy strategies are defined to guide the mapping process, utilizing the indicated function values. An allocation system has been designed and implemented based on the allocation strategy. In experiments we have defined about 1000 nodes in task graphs with regular and irregular topologies, and the same order of processors with mesh, tree, and hypercube topologies. The results are summarized as follows. 1) The system can yield 4.0 times better total communication costs than an arbitrary allocation. 2) It is difficult to select a single strategy capable of providing the best solutions for a wide range of task-processor combinations. 3) Comparison with hypercube-topology-dependent research indicates that our topology-independent allocator produces better results than the dependent ones. 4) The order of computaion time of the allocator is experimentally proved to be O (n²) where n represents the number of tasks.
ER -