Matching algorithms with parallel architectures: a quantitative approach

The purpose of this paper is to assess the match between algorithms and MIMD parallel architectures from the perspective of resource requirements and resource supplies. In the Extended Evaluation Framework, three figures of merit (FOM₁, FOM₂ and FOM₃) are proposed as measures of the match. FOM₁ shows the time average of the sum of weighted resource to requirement ratios, FOM₂ gives the percentage of resource surplus time during the total execution time, and FOM₃ predicts the minimum actual execution time subject to the availability of limited resources. A parallel matrix multiplication algorithm is used to exemplify how the matching process is carried out. Also presented are experiments conducted on the Sequent Symmetry multiprocessor to examine the accuracy of the modeling process. Results show that measurements are in good agreement with predictions. The Extended Evaluation Framework will help users to determine what parallel architecture is best matched with the algorithm, assist algorithm designers to develop new and improve old algorithms, and provide a platform for assessing the effects that different data allocations and processor assignments can have on combinations of algorithms and architectures