@PhDThesis{	  itlic:2001-002,
  author	= {Johan Steensland},
  title		= {Domain-based partitioning for parallel {SAMR}
		  applications},
  school	= {Department of Information Technology, Uppsala University},
  department	= {Division of Scientific Computing},
  year		= {2001},
  number	= {2001-002},
  type		= {Licentiate thesis},
  month		= mar,
  abstract	= {This thesis presents a study of domain-based partitioning
		  techniques for dynamic structured grid hierarchies,
		  occuring in structured adaptive mesh refinement (SAMR)
		  methods. Such methods for obtaining the numerical solution
		  to partial differential equations yield highly advantageous
		  ratios for cost/accuracy as compared to methods based upon
		  static uniform approximations. Distributed implementations
		  of these techniques have the potential for enabling
		  realistic simulations of complex systems. These
		  implementations however, present significant challenges in
		  dynamic data-distribution and load balancing. That is, when
		  SAMR is executed on a parallel computer, the work load will
		  change dynamically. Thus, there is need for
		  \textit{dynamic} load balancing in order to efficiently
		  utilize the resourses of the parallel computer. Inverse
		  space-filling curve partitioning (ISP) is appealing for
		  load balancing in parallel SAMR, because of its speed. In
		  this work, ISP is considered as \textit{part} of a
		  partitioning approach, which combines structured and
		  unstructured techniques.
		  
		  Various design decisions for the structured partitioning
		  are considered. Different design choices lead to graphs
		  with different properties. One objective is to investigate
		  how these differences affect the behavior of ISP. This
		  thesis contributes by identifying certain design choices as
		  being advantageous, and by presenting four new partitioning
		  algorithms that correspond to these design decisions.
		  
		  An experimental comparison of dynamic partitioning
		  techniques for \textit{blockwise} parallel structured
		  adaptive mesh refinement applications is presented. It is
		  shown that an ISP-based technique can compete with other
		  approaches for certain classes of applications. Moreover,
		  an extended experimental characterization of dynamic
		  partitioning\-/load-balancing techniques for
		  \textit{general} adaptive grid hierarchies is presented.
		  Techniques studied include newly proposed as well as
		  existing approaches. It was found that two of the proposed
		  algorithms were particularly useful: pBD-ISP for the more
		  communication dominated applications, and G-MISP+SP for the
		  computation dominated applications.
		  
		  Policies for the automatic selection of partitioner based
		  on application and system state are outlined.
		  Recommendations for appropriate partitioning techniques,
		  given application and system state, are given. The overall
		  motivation is the formulation of policies required to drive
		  a \textit{dynamically adaptive} meta-partitioner for SAMR
		  grid hierarchies capable of selecting the most appropriate
		  partitioning strategy at runtime, based on current
		  application and system state. Such a partitioner may
		  significantly decrease application execution time.}
}