Performance analysis of multiple-processor systems
Zarka Cvetanovic · 1986
Analyzing and predicting the performance of multiple-processor systems is a very complex task, since many factors interact to determine system behavior. In this dissertation, we have developed a deterministic model that shows the performance effects of the number of processors, the bandwidth of the interconnection structure, the allocation of subproblems to processors, and the granularity of the task decomposition. Each of these factors impacts cost and performance, but the interaction among them is not well understood at present. We have investigated models for some proposed architectures, including a shared memory parallel architecture and a pipelined dataflow architecture. These architectures are evaluated for some iterative parallel algorithms, such as the FFT and grid computations. The main feature of our approach is that it can model the bursty nature of arrivals at the interconnection network and the effect of different allocations of subproblems to processors. Our results indicate that in an N-processor system, the communication overhead can be reduced by a factor of O(N) by changing the method used to allocate subproblems to processors. If overlap of processing and communication is possible, the communication overhead for the best-case allocation can be reduced by a factor of O(log N). The ratio of processing time to communication time has a significant effect on performance, since it alone can decrease the speedup from O(N) to a constant value. For parallel algorithms where the communication overhead is not fully decomposable among N processors, the speedup approaches the maximum and then decreases as N grows for all values of the bandwidth less than N. Our model can be used to determine the number of processors which, for given bandwidth and problem decomposition, results in the best performance. The methodology applied for predicting performance of algorithms analyzed here can be used to estimate the performance of other parallel programs. The results obtained in this dissertation should provide a basis for designing systems with combinations of these parameters such that the total system design achieves the best possible cost-effectiveness.