Show simple item record

dc.contributor.advisor Sinclair, James B.
dc.creatorDawkins, William Price
dc.date.accessioned 2009-06-04T00:00:14Z
dc.date.available 2009-06-04T00:00:14Z
dc.date.issued 1993
dc.identifier.citation Dawkins, William Price. "Analytical performance prediction of parallel systems." (1993) Diss., Rice University. https://hdl.handle.net/1911/16615.
dc.identifier.urihttps://hdl.handle.net/1911/16615
dc.description.abstract 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.
dc.format.extent 112 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectComputer science
Electronics
Electrical engineering
dc.title Analytical performance prediction of parallel systems
dc.type Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record