A study of average-case speedup and scalability of parallel computations on static networks

K. Li; Y. Pan; H. Shen; S. Q. Zheng

doi:10.1016/S0895-7177(99)00083-7

A study of average-case speedup and scalability of parallel computations on static networks

K. Li, Y. Pan, H. Shen, S. Q. Zheng

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

A parallel system consists of a parallel algorithm and a parallel machine that supports the implementation of the algorithm. The scalability of a parallel system is a measure of its capability to increase speedup in proportion to the number of processors, or its capability to keep a constant efficiency as the number of processors increases. The present paper is devoted to the investigation of the average-case scalability of parallel algorithms executing on multicomputers with symmetric static networks, including the completely connected network, ring, hypercube, and torus. In particular, we characterize the communication overhead such that the expected efficiency can be kept at certain constant level, and that the number of tasks grows at the rate Θ(P log P).

Original language	English
Pages (from-to)	83-94
Number of pages	12
Journal	Mathematical and Computer Modelling
Volume	29
Issue number	9
DOIs	https://doi.org/10.1016/S0895-7177(99)00083-7
Publication status	Published - May 1999
Externally published	Yes

Keywords

Communication cost
Completely connected network
Efficiency
Execution time
Hypercube
Performance analysis
Random parallel program
Ring
Scalability
Speedup
Torus

Access to Document

10.1016/S0895-7177(99)00083-7

Cite this

@article{6ef89c4bcdf549dfb6d808963a58d041,

title = "A study of average-case speedup and scalability of parallel computations on static networks",

abstract = "A parallel system consists of a parallel algorithm and a parallel machine that supports the implementation of the algorithm. The scalability of a parallel system is a measure of its capability to increase speedup in proportion to the number of processors, or its capability to keep a constant efficiency as the number of processors increases. The present paper is devoted to the investigation of the average-case scalability of parallel algorithms executing on multicomputers with symmetric static networks, including the completely connected network, ring, hypercube, and torus. In particular, we characterize the communication overhead such that the expected efficiency can be kept at certain constant level, and that the number of tasks grows at the rate Θ(P log P).",

keywords = "Communication cost, Completely connected network, Efficiency, Execution time, Hypercube, Performance analysis, Random parallel program, Ring, Scalability, Speedup, Torus",

author = "K. Li and Y. Pan and H. Shen and Zheng, {S. Q.}",

note = "Funding Information: *Author to whom all correspondence should be addressed. K. Li was supported by National Aeronautics and Space Administration and the State University of New York through the NASA/U mversity Joint Venture in Space Science Program under Grant NAGS-1313, and the 1996 NASA/ASEE S ummer Faculty Fellowship Program. tY. Pan was supported by the National Science Foundation under Grant CCR-9211621, the Air Force Avionics Laboratory, Wright Laboratory, Dayton, OH, under Grant F33615-C-2218, and an Ohio Board of Regents Investment Fund Competition Grant. $H. Shen was supported by the Australian Research Council under its Large Research Grant (199698) A849602031. **S. Q. Zheng was supported by the National Science Foundation under Grant ECS-9626215, and Louisiana Grant LEQSF (1996-99)-RD-A-16.",

year = "1999",

month = may,

doi = "10.1016/S0895-7177(99)00083-7",

language = "English",

volume = "29",

pages = "83--94",

journal = "Mathematical and Computer Modelling",

issn = "0895-7177",

publisher = "Elsevier Ltd.",

number = "9",

}

TY - JOUR

T1 - A study of average-case speedup and scalability of parallel computations on static networks

AU - Li, K.

AU - Pan, Y.

AU - Shen, H.

AU - Zheng, S. Q.

N1 - Funding Information: *Author to whom all correspondence should be addressed. K. Li was supported by National Aeronautics and Space Administration and the State University of New York through the NASA/U mversity Joint Venture in Space Science Program under Grant NAGS-1313, and the 1996 NASA/ASEE S ummer Faculty Fellowship Program. tY. Pan was supported by the National Science Foundation under Grant CCR-9211621, the Air Force Avionics Laboratory, Wright Laboratory, Dayton, OH, under Grant F33615-C-2218, and an Ohio Board of Regents Investment Fund Competition Grant. $H. Shen was supported by the Australian Research Council under its Large Research Grant (199698) A849602031. **S. Q. Zheng was supported by the National Science Foundation under Grant ECS-9626215, and Louisiana Grant LEQSF (1996-99)-RD-A-16.

PY - 1999/5

Y1 - 1999/5

N2 - A parallel system consists of a parallel algorithm and a parallel machine that supports the implementation of the algorithm. The scalability of a parallel system is a measure of its capability to increase speedup in proportion to the number of processors, or its capability to keep a constant efficiency as the number of processors increases. The present paper is devoted to the investigation of the average-case scalability of parallel algorithms executing on multicomputers with symmetric static networks, including the completely connected network, ring, hypercube, and torus. In particular, we characterize the communication overhead such that the expected efficiency can be kept at certain constant level, and that the number of tasks grows at the rate Θ(P log P).

AB - A parallel system consists of a parallel algorithm and a parallel machine that supports the implementation of the algorithm. The scalability of a parallel system is a measure of its capability to increase speedup in proportion to the number of processors, or its capability to keep a constant efficiency as the number of processors increases. The present paper is devoted to the investigation of the average-case scalability of parallel algorithms executing on multicomputers with symmetric static networks, including the completely connected network, ring, hypercube, and torus. In particular, we characterize the communication overhead such that the expected efficiency can be kept at certain constant level, and that the number of tasks grows at the rate Θ(P log P).

KW - Communication cost

KW - Completely connected network

KW - Efficiency

KW - Execution time

KW - Hypercube

KW - Performance analysis

KW - Random parallel program

KW - Ring

KW - Scalability

KW - Speedup

KW - Torus

UR - http://www.scopus.com/inward/record.url?scp=0033136105&partnerID=8YFLogxK

U2 - 10.1016/S0895-7177(99)00083-7

DO - 10.1016/S0895-7177(99)00083-7

M3 - Article

AN - SCOPUS:0033136105

SN - 0895-7177

VL - 29

SP - 83

EP - 94

JO - Mathematical and Computer Modelling

JF - Mathematical and Computer Modelling

IS - 9

ER -

A study of average-case speedup and scalability of parallel computations on static networks

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this