A method of performance characterization for parallel programs on multicomputers
James Quinlan · 1990
Previous work by Vrsalovic has shown that an analytical model of multiprocessor computation can successfully predict the performance of many algorithms. Each algorithm modeled is in the form of repeated application cycles: each application cycle consists of (1) access to global data and (2) local processing. The model is able to separate the effects of decomposition on performance from the effects of resource utilization. The work in this thesis establishes a similar model for multicomputers which guarantee message delivery in bounded time. By examining the activity graph of a parallel program and its demands on the communications network, a model is constructed that delineates the algorithm's performance range. It is shown that this model is capable of characterizing performance of a number of algorithms. The model's performance prediction is favorably compared to the execution of several algorithms on the Mark III hypercube.