Multi-tier Programming

Multi-tier parallelism is an effective solution to enhancing machine performance, and is typically delivered as an interconnected collection of Symmetric Multiprocessors (SMPs). Several vendors support multi-tier parallelism, including Sun Microsystems, Compaq, IBM, and Cray/SGI.

What characterizes multi-tier computing? The presence of multiple levels or modes of locality. For example Alpern, Carter, and Ferrante, identify the PMH model with the goal of unifying the treatment of the multiple levels of the physical parallel memory hierarchy.

Multi-tier locality is not necessarily restricted to multi-tier hardware, since multi-tier locality may be logical rather than physical. For example, coupled multidisciplinary applications employ task parallelism, and may divide a single parallel computer into processor subsets with each set used to solve a different piece of the problem. The pieces are computed in parallel, communicating information across their common boundaries. Parallelism also exists within the pieces, which may communicate by passing message or shared memory. Too, some applications such as structured adaptive mesh refinement have a more elaborate computational structure, which is dynamic and data-dependent.


  • We have investgiated a formalism for multi-tier programming using the KeLP system developed jointly with former student Stephen J. Fink. Results are described in the following papers
  • S. B. Baden and D. Shalit, "Performance tradeoffs in multi-tier formulation of a finite difference method," in  Proc. 2001 International Conference on Computational Science,  San Francisco, CA , May 2001.
  • S. B. Baden and S. J. Fink A Programming Methodology for Dual-tier Multicomputers . IEEE Transactions on Software Engineering, 26(3): 212-26, March 2000.
  • Scott B. Baden and Stephen J. Fink, Communication overlap in multi-tier parallel algorithms, Conf. Proc. SC '98, Orlando FL, November 1998.
  • Stephen J. Fink A Programming Model for Block-Structured Scientific Calculations on SMP Clusters , Ph. D. Dissertation, June 1998.
  • Runtime Support for Multi-Tier Programming of Block-Structured Applications on SMP Clusters, S. J. Fink and S. B. Baden, Lecture Notes in Computer Science, Volume 1343, edited by Y. Ishikawa et al., Springer Verlag, 1997, pp. 1-8. Proc. 1997 International Scientific Computing in Object-Oriented Parallel Environments Conference (ISCOPE '97), Marina del Ray, California, December 1997.
  • This system treats hardware-supported multi-tier parallelism and also provides building blocks for supporting task parallelism in multidisciplinary applications.  To download the software and documentation click  HERE .
  • In some applications, it is useful to invoke HPF from an explicit SPMD layer, such that multiple data parallel contexts are simultaneously active. We refer to such a model as multi data parallelism (MDP) . Click HERE for more information about MDP.

  • Maintained by Daniel Shalit. Last modified: Thurs Nov 1 06:20:28 PST 2001