Parallel Performance Modeling, Prediction and Tuning Doctoral Thesis

This thesis presents a unified approach to modeling of parallel architectures and algorithms with special emphasis on estimation of obtainable performance. A modeling language and simulator Transim is used for this purpose. Although Transim was designed by its authors just as a transputer simulator for prototyping and performance evaluation of message-passing programs, it is applied to simulations of many different types of parallel architectures and programming paradigms, what is far beyond the originally anticipated applications. The approach is demonstrated on simulations of abstract machine models like PRAM or APRAM as well as commonly used parallel architectures like symmetrical multiprocessors, clusters of workstations and their combinations. Performance tuning of parallel algorithms is undertaken and results of simulations are compared to results obtained on real parallel computers. Presented simulation models also include various synchronization operations found in many parallel algorithms. These models can be used as building blocks of more complex models. Finally performance tuning of communication algorithms has been undertaken, because of the dramatic impact of these algorithms on the overhead of parallel computing. Communication is an indispensable part of any parallel computation and the results are therefore applicable to a wide class of parallel applications running on distributed machines with irregular network topology