×

Average-case analysis of isospeed scalability of parallel computations on multiprocessors. (English) Zbl 0970.68065

Summary: We investigate the average-case speed and scalability of parallel algorithms executing on multiprocessors. Our performance metrics are average-speed and isospeed scalability. For the purpose of average-case performance prediction, we formally define the concepts of average-case average-speed and average-case isospeed scalability. By modeling parallel algorithms on multiprocessors using task precedence graphs, we are mainly interested in the effects of synchronization overhead and load imbalance on the performance of parallel computations. Thus, we focus on the structures of parallel computations, whose inherent sequential parts are limitations to high performance. Task execution times are treated as random variables, so that we can analyze the average-case performance of parallel computations. For several typical classes of task graphs, including iterative computations, search trees, partitioning algorithms, and diamond dags, we derive the growth rate of the number of tasks as well as isospeed scalability in keeping constant average-speed. In addition to analytical results, extensive numerical data are also demonstrated. An important discovery of our study is that while a parallel computation can be made scalable by increasing the problem size together with the system size, it is actually the amount of parallelism that should scale up with the system size. We also argue that under our probabilistic model of parallel algorithms and the list scheduling strategy, the number of tasks should grow at least at the rate of \(\Theta(P\log P)\), where \(P\) is the number of processors, so that a constant average-speed can be maintained. Furthermore, \(\Theta(\log P/\log P')\) is the highest isospeed scalability achievable.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W10 Parallel algorithms in computer science
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1109/88.242438 · Zbl 05100308 · doi:10.1109/88.242438
[2] DOI: 10.1145/42411.42415 · doi:10.1145/42411.42415
[3] DOI: 10.1145/78607.78614 · doi:10.1145/78607.78614
[4] Kumar V., Proc. International Conference on Supercomputing pp 396– (1991)
[5] Li K., IEEE Transactions on Computers 46 pp 5– (1997)
[6] Li K., Proceedings of 3rd International Conference on Computer Science and Informatics pp 145– (1997)
[7] Li K., Proceedings of 3rd International Conference on Computer Science and Informatics pp 149– (1997)
[8] Li K., Proc. Int’l Conf. Parallel and Distributed Processing Techniques and Applications pp 474– (1996)
[9] Li K., Informatica - An International Journal of Computing and Informatics 21 pp 279– (1997)
[10] DOI: 10.1016/S0895-7177(99)00083-7 · Zbl 0993.68148 · doi:10.1016/S0895-7177(99)00083-7
[11] DOI: 10.1109/71.80193 · Zbl 05106504 · doi:10.1109/71.80193
[12] DOI: 10.1145/102868.102871 · doi:10.1145/102868.102871
[13] DOI: 10.1109/88.481664 · Zbl 05100119 · doi:10.1109/88.481664
[14] DOI: 10.1109/MC.1993.274941 · Zbl 05089615 · doi:10.1109/MC.1993.274941
[15] DOI: 10.1006/jpdc.1993.1087 · Zbl 0800.68228 · doi:10.1006/jpdc.1993.1087
[16] Sun X.-H., IEEE Transactions on Parallel and Distributed Systems 5 pp 6– (1994)
[17] Sun X.-H., IEEE Transactions on Parallel and Distributed Systems 6 pp 11– (1995)
[18] DOI: 10.1109/88.544430 · Zbl 05100471 · doi:10.1109/88.544430
[19] Willebeek-LeMair M., Proceedings of International Conference on Parallel Processing pp 171– (1990)
[20] DOI: 10.1109/32.67575 · Zbl 05113179 · doi:10.1109/32.67575
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.