Treffer: Average-Case Analysis of Isospeed Scalability of Parallel Computations on Multiprocessors.

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 ... (PlogP), where P is the number of processors, so that a constant average-speed can be maintained. Furthermore, ...(logP/log P') is the highest isospeed scalability achievable. 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... [ABSTRACT FROM AUTHOR]

Copyright of International Journal of High Speed Computing is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)