A Metric for Parallel Poly-Algorithm Design

This paper discusses a scalability metric based on the cost effectiveness of parallel algorithms. Unlike other scalability measures, this metric can be used to compare different parallel algorithms and identify specific conditions of problem size and processor allocation that characterize "crossover" points and intervals where one algorithm becomes more cost effective than another. Finally, this paper presents a series of examples to illustrate the measurement methodology in practice. 1 Introduction Consider the development of an algorithm that multiplies matrices. Of the many algorithms that might be employed, two of the most popular methods are the naive algorithm and the Strassen algorithm. Asymptotically, the naive algorithm is O(n 3 ) while the Strassen algorithm is O(n 2:81 ). Although the Strassen algorithm is asymptotically better than the naive algorithm, the setup cost of the Strassen algorithm makes it inefficient for small matrices. An optimal algorithm might employ bo..