SEMINAR

ABSTRACT

N-body simulations arise in many areas of science, ranging from astrophysics to molecular biology. Although N-body algorithms are computationally intensive and amenable to parallel execution, performance gains are difficult to obtain due to load imbalances caused by the irregular distribution of bodies. In general, there is a tension between balancing processor loads and maintaining locality, as the re-assignment of work may necessitate access to remote data. Fractiling is a dynamic scheduling scheme that simultaneously balances processor loads and maintains locality by exploiting the self-similarity properties of fractals. Fractiling is based on a probabilistic analysis, and thus, it accommodates load imbalances caused by predictable phenomena, such as irregular data as well as unpredictable phenomena, such as data-access latency and operation system interference. In this talk, I will report on experiments on a IBM-SP2 and SuperMSPARC, where performance of N-body simulation codes were improved by as much as 52% by fractiling. Performance improvements were obtained on uniform and nonuniform distribution of bodies, underscoring the need for a scheduling scheme that accommodates application as well as system induced execution time variance.

Performance gains with Fractiling on N-body simulations leads us to believe that the method can improve the performance of a large class of parallel computational field simulation (CFS) applications. Future work will be dedicated to new probabilistic methods that could improve performance of scientific applications on parallel machines.

WHERE: TEC 340

WHEN(day): Friday, May 8th, 1998

WHEN(time): 2:00 PM

EVERYBODY IS INVITED