Performance of MIMD Parallel Computing Systems for Irregular Algorithms
Keywords Researchers
Scalability study, irregular problems, benchmarking, load balancing, contention. Dr. Thierry Cornu (project leader) Michel Pahud (Ph.D. student).
Project period Funding Agency
July 1995 - Sept 1998. This project is funded by the Swiss National Science Foundation (Schwerpunkt Programm - Informatik grants # 42391.94/1 and # 50611.97/1).
In few years the performance prediction domain for multiprocessing machines has evolved greatly. Numerous models for predicting performance have been invented for conformable parallel programs. When the program is irregular certain problems still remain because the prediction model must to take into account:
  • variations of performance due to the irregularity of the data structure
  • the fact that the time for the introduction of the code comprised in one or several loops can vary from one repetition to the next
  • the difference between the time of execution of competing process.
On the communication level the model must be able to account for performance loss due to the contention phenomenon, as well as take into account the volume of data exchanged.
In the PERFO project we developped a new performance prediction model for irregular parallel applications. In the first stage we investigated the problem of contention during the communication phases between processors. This leads us to develop a communication model based on a certain number of measures carried out on the targeted machine. Secondly we studied the way to model irregular calculation. Based on the obtained results we developped a general model of performance prediction for irregular programs. Lastly in order to verify the suitability of this model in the practice we carried out prediction experiments on custom-made parallel irregular programs and then on real life programs. Included among the programs used for these performance validation experiments are:
  • application simulation of wave diffusion in urban areas;
  • optimal networking decomposition algorithm in domains;
  • a genetic algorithm based on the concept of individual islands.
The prediction experiments have essentially been carried out on two different platforms:
  • a Cray- T3D;
  • a network of workstations.
The very satisfying results of the validation experiments have comfirmed the validity of the method. Finally we developed a performance prediction tool in order to simplify the automatic use of this model. This tool has been successfully tested on the application already mentioned.