Dynamic Scheduling N-Body Simulations in Distributed Memory Architectures 



                           Ioana Banicescu

        Department of Computer Science -  Mississippi State University 
                               and 
              NSF ERC for Computational Field Simulation  

                              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
recent experiments on a IBM-SP2 and a 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 applications. Future work 
will be dedicated to extensions of this method, and to new techniques that 
could improve performance of scientific applications on parallel machines.



  Biographical Sketch:
  -------------------

  Ioana Banicescu received the Diploma in Electronics and Telecommunications
from Polytechnic Institute, Bucharest - Romania, and her MS and Ph.D.
degrees in Computer Science from Polytechnic University, New York in 
1991 and 1996, respectively. Currently, she is an assistant professor in
the Department of Computer Science at Mississippi State University
(1996 - present), and a research faculty member at the National Science 
Foundation Engineering Center (NSF ERC) for Computational Field Simulation.

  Dr. Banicescu's interests range from theoretical to experimental research
in parallel algorithms and scientific computing, with an emphasis on 
algorithms for irregular problems, dynamic scheduling, load balancing and
performance analysis.  As a research faculty member at the NSF ERC she has 
been involved in collaborative work with a few computational scientists in 
the development of a dynamic scheduling methodology for an effective, 
scalable parallelization of computational field simulation problems.

Currently, Dr. Banicescu is working to extend the study of recent dynamic 
scheduling strategies used in scientific computing with new and competitive 
methods and to evaluate their effectiveness on an analytical and experimental 
basis (using a recently proposed predictive performance metric).  This work is 
essential especially for applications where none of the existing techniques 
accommodate the unpredictable behavior of simulations.



			Brief Overview of Research Work
				Ioana Banicescu

My research background is in parallel algorithms and scientific
computing with an emphasis on algorithms for irregular problems, dynamic 
scheduling, load balancing, and performance analysis.  My topics of interest 
in the past and present range from theoretical to experimental research.
 
During my doctoral dissertation, my concentration area was parallel 
algorithms for irregular problems.  More specifically I studied the 
parallelization of the hierarchical N-body methods in order to improve 
their performance on parallel machines.  I proposed applying a new dynamic 
scheduling algorithm, based on a probabilistic analysis, to a class of N-body 
problem solutions to significantly improve their performance on parallel 
machines via load balancing and data locality.  The resulting algorithm has 
been successfully implemented on a KSR-1 at the Cornell Theory Center, and 
proved to be extremely competitive over other recently proposed techniques 
(i.e., up to 53% improvement over other techniques).  I demonstrated the 
importance of using the new proposed technique in the hierarchical N-body 
methods and the significance of extending the application of this techniques 
to a wider class of scientific applications.  

During the first year of my faculty appointment in the Department of
Computer Science, I worked to experimentally extend the application of 
the proposed dynamic scheduling strategy from distributed memory shared 
address space to a distributed memory message passing architecture. Thus, 
the effectiveness of the strategy was demonstrated in both programming 
paradigms.  The proposed work was successfully accomplished with the help 
of graduate students and implemented at the Maui High Performance Computing 
Center.  As a research faculty member at the NSF ERC (NSF Engineering Research 
Center for Computational Field Simulation), I have been involved in 
collaborative work with a few computational scientists in the development of 
a dynamic scheduling methodology for an effective, scalable parallelization of 
computational field simulation problems.  

Currently, I am working to extend the study of recent dynamic scheduling
strategies used in scientific computing with new and competitive methods
and to evaluate their effectiveness on an analytical and experimental basis
(using a recently proposed predictive performance metric).  This work is 
essential especially for applications where none of the existing techniques 
accommodate the unpredictable behavior of simulations.

Additional details can be found at http://www.cs.msstate.edu/~ioana