Analytical performance prediction of parallel systems
Dawkins, William Price
Sinclair, James B.
Doctor of Philosophy
The need for more computing power for many computer applications has increased beyond the capabilities of traditional von Neumann architectures. This has generated interest in using parallel computers to improve processing power. Because of the high cost of implementing parallel computers, accurate and efficient tools are needed to predict the performance of parallel computer designs to determine which designs should be built. This thesis presents an analytical technique for predicting the performance of parallel algorithms realized on parallel architectures. The technique models arbitrary non-deterministic task execution times, explicit precedence constraints, resource contention, and a variety of resource scheduling policies. The program model used by this technique is a task graph. The nodes of a task graph represent parts of a parallel algorithm that require service from resources. The edges connecting nodes represent precedence constraints. Each task is assigned a random variable representing its execution time. The technique approximates arbitrarily distributed task execution time random variables with simple random variables. The different sequences of events that can occur due to resource contention are represented in a sequencing tree. A fully constructed sequencing tree represents all the possible sequences of events that can occur during the execution of a task graph. The technique allows the user to trade accuracy for efficiency by basing performance predictions on partial constructions of the sequencing trees. The technique is implemented in a program called ES. ES predicts both the mean and standard deviation of the execution time of a task graph representing a parallel algorithm. ES predictions are compared to predictions of simulations and timings of real parallel algorithms executing on a real parallel computer. Two mergesort algorithms were implemented on a hypercube multicomputer. ES estimates of the mean execution times of these algorithms differ by at most 7.0% from the mean execution times measured on the hypercube. ES estimates of the execution time of an FFT algorithm are compared to estimates obtained from execution-driven simulations. The ES estimates are within $\pm$0.15% of the estimates predicted by simulation.
Computer science; Electronics; Electrical engineering