@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",
}