Performance Evaluation Of The Parallel Fast Multipole Algorithm Using The Optimal Effectiveness Metric

Scalability measurements of parallel applications are of significant interest to the evaluation and characterization of various parallel algorithms, particularly in scientific computing. Previously, several metrics have been proposed and accepted by the community of researchers in parallel algorithm development. However, none of these have all the attributes required by an effective metric for parallel algorithm analysis. Recently, a new performance metric has been introduced: the optimal effectiveness (\Gamma opt ). It exhibits both qualitative and quantitative characteristics. This paper presents the performance evaluation of N-body simulations using the parallelized Fast Multipole Algorithm and two competing versions that include load balancing techniques. Using \Gamma opt , this paper reveals the inherent limitations of existing performance metrics and shows the advantages of employing the cost effectiveness metric for parallel applications. 1. INTRODUCTION Scalability measuremen..