MULTIPLE QUADRATIC-FORMS - A CASE-STUDY IN THE DESIGN OF DATA-PARALLEL ALGORITHMS

Data-parallel implementations of the computationally intensive task of solving multiple quadratic forms (MQFs) have been examined. Coupled a nd uncoupled parallel methods are investigated, where coupling relates to the degree of interaction among the processors. Also, the impact o f partitioning a large MQF problem into smaller non-interacting subtas ks is studied. Trade-offs among the implementations for various data-s ize/machine-size ratios are categorized in terms of complex arithmetic operation counts, communication overhead, and memory storage requirem ents. Furthermore, the impact on performance of the mode of parallelis m used is considered, specifically, SIMD versus MIMD versus SIMD/MIMD mixed-mode. From the complexity analyses, it is shown that none of the algorithms presented in this paper is best for all data-size/machine- size ratios. Thus, to achieve scalability (i.e., good performance as t he number of processors available in a machine increases), instead of using a single algorithm, the approach discussed is to have a set of a lgorithms from which the most appropriate algorithm or combination of algorithms is selected based on the ratio calculated from the scaled m achine size. The analytical results have been verified by experiments on the MasPar MP-1 (SIMD), nCUBE 2 (MIMD), and PASM (mixed-mode) proto type. (C) 1994 Academic Press. Inc.