Title :
Predicting the running times of parallel programs by simulation
Author :
Rugina, Radu ; Schauser, Klaus Erik
Author_Institution :
Dept. of Comput. Sci., California Univ., Santa Barbara, CA, USA
fDate :
30 Mar-3 Apr 1998
Abstract :
Predicting the running time of a parallel program is useful for determining the optimal values for the parameters of the implementation and the optimal mapping of data on processors. However deriving an explicit formula for the running time of a certain parallel program is a difficult task. The authors present a new method for the analysis of parallel programs: simulating the execution of parallel programs by following their control flow and by determining, for each processor; the sequence of send and receive operations according to the LogGP model. They developed two algorithms to simulate the LogGP communication between processors and tested them on the blocked parallel version of the Gaussian elimination algorithm on the Meiko CS-2 parallel machine. The implementation showed that the LogGP simulation is able to detect the nonlinear behavior of the program running times, to indicate the differences in running times for different data layouts and to find the local optimal value of the block size with acceptable precision
Keywords :
computational complexity; parallel algorithms; parallel programming; virtual machines; LogGP communication; LogGP model; Meiko CS-2 parallel machine; algorithms; blocked parallel Gaussian elimination algorithm; control flow; data layouts; explicit formula; local optimal block size value; nonlinear behavior detection; optimal data mapping; optimal parameter values; parallel programs; receive operation sequence; running time prediction; send operation sequence; simulation; Algorithm design and analysis; Analytical models; Communication system control; Computational modeling; Computer science; Concurrent computing; Parallel algorithms; Performance analysis; Predictive models; Testing;
Conference_Titel :
Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International ... and Symposium on Parallel and Distributed Processing 1998
Conference_Location :
Orlando, FL
Print_ISBN :
0-8186-8404-6
DOI :
10.1109/IPPS.1998.669996