Technical Report Number
In this paper, the N-body simulation problem is considered, its parallel implementation described, its execution time performance is modeled and compared with measured results, and two alternative load balancing algorithms for enhancing performance investigated. Parallel N-body techniques are widely applied in various fields and possess characteristics that challenge the computation and communication capabilities of parallel computing systems and are therefore good candidates for use as parallel benchmarks. Performance models may be used to estimate the performance of an algorithm on a given system, identify performance bottlenecks and study the performance implications of several algorithm are system enhancements. In this paper, we propose a general framework for developing performance models for a class of synchronous iterative algorithms and specilize it for the case of N-body simulation algorithms. We use the model to estimate the performance of two load balancing algorithms.
Govindan, Vasudha and Franklin, Mark A., "The N-body Problem: Distributed System Load Balancing and Performance Evaluation" Report Number: WUCS-93-16 (1993). All Computer Science and Engineering Research.