CSE 260 Project ideas

• A hybrid, MPI+OpenMP or CUDA implementation of a stencil method in 3 dimensions. Your baseline is a hybrid MPI+OpenMP implementation. Experiment with different partitionings and note their affect on performance.
  Carefully optimize for locality, using techniques explored in these papers:
  • S. Kamil et al., "An auto-tuning framework for parallel multicore stencil computations," Proc. IPDPS, pp.1-12 (2012)
    
  • K. Datta et al., "Optimization and Performance Modeling of Stencil Computations on Modern Microprocessors," SIAM Review,, 50(1):129-159 (2009).
  Options for Groups of 3:
  1. Overlap communication with computation.
  2. MPI + CUDA

• Multigrid (MPI or CUDA). Multigrid is a multi-level method that uses a progression of meshes to accelerate the solution of equations. A numerical analysis background is a plus for this project. Only groups of 3 may attempt the CUDA implementation. Reference material includes
  • Multigrid notes, by Jim Demmel.
  • Multigrid tutorial slides by William Briggs
  • MG NET, a repository for information related to multigrid, multilevel, multiscale, aggregation, defect correction, and domain decomposition methods.

  If implementing multigrid in MPI, keep in mind that a well-tuned 3D multigrid code will spending most of its running time at the finest level mesh, so you'll want to be able to ascribe computational costs on a per-level basis. At some point, the mesh will become sufficiently coarse that you will need to perform all computation on a single core. There simply isn't enough work to keep processors busy doing computation and communication overheads will be too high to be able to reduce the running time via parallelism.

  More generally, as you recurse to coarser levels, reduce the amount of parallelism incrementally. The reason why is that as the levels get coarser, there will be less and less computational work per core, and the communication overhead can become a problem. This strategy makes the communication patterns more interesting; when you coarsen a mesh you must send it to a subset of processors that will work at the next coarse level, and similarly, when you perform coarse grid correction you'll distribute the data to a larger subset of processors before projecting the coarsened data onto a finer mesh.

  For MPI-based projects: a simple strategy for reducing parallelism is to just use 1/8 the number of processors at the next coarsest level, and to increase the number of processors by 8 as you drop a level. You can experiment with other strategies if your communication overheads are too high.

• Communication avoiding matrix multiplication (MPI). If working in a team of 3, implement communication overlap as well. See the following paper for details: Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms, by Edgar Solomonik and James Demmel, UCB/EECS-2011-10, February 2011, or consult the Berkeley Bebop project web site: http://bebop.cs.berkeley.edu/#pubs
• Algorithm based fault tolerance (ABFT). At high levels of performance, e.g. Exascale, hardware failures are expected. Build a fault tolerant MPI implementation of matrix multiply or a Poisson solver (Poisson's method or multigrid) that will run to completion (and produce the correct result) in the presence of repeated hardware failures. See the following references. As noted in Chen and Dongarra, Cannon's algorithm is not suitable, as the checksum relationship in the input checksum matrices is not maintained in the middle of the computation though it is at the end.
  • Kuang-Hua Huang and J. A. Abraham. Algorithm-Based Fault Tolerance for Matrix Operations, IEEE Trans. Comput., C-33(6):518-528, June 1984. Seminal work in ABFT.
  • Zizhong Chen and Jack Dongarra. Algorithm-Based Fault Tolerance for Fail-Stop Failures, IEEE Trans. Parallel Distrib. Sys. 19(12):1628-1641, December 2008.
  • G. Bosilca, R. Delmas, J. Dongarra and J. Langou. Algorithm-based fault tolerance applied to high performance computing. J. Parallel Distrib. Comput. 69(4):410-416 (April 2009). Presents the implementation stratetgy.
  • A. Roy-Chowdhury, N. Bellas and P. Banerjee. Algorithm-based error-detection schemes for iterative solution of partial differential equations, IEEE Trans. on Comput. 45(4):394-407, Apr 1996.
  • J. Hursey and R. L. Graham. Building a Fault Tolerant MPI Application: A Ring Communication Example, IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), pp.1549-1556, 16-20 May 2011.
• 3D Fast Fourier Transform (MPI). The Fast Fourier Transform is widely used in signal processing and also in solving numerical problems. Implement the 3D Fast Fourier transform either in MPI or in CUDA. Use a 2D data decomposition if implementing in MPI. Only groups of 2 may attempt the CUDA implementation. Groups of 3 should also overlap communication with computation in their MPI implementation.
• Particle simulation (MPI, MPI+OpenMP). Various inefficient implementations are available
  The provided implementation won't scale; you'll need to geographically sort the particles into a mesh to avoid O(N²) searches for neighbors. You'll also have to balance the workloads, likely using a cyclic mapping. These techniques are described in Lectures 14 and 15 given in CSE 260, Fall 2009. There is also a reader on Load balancing and Data Decomposition (the link to the fall 2009 reader is broken). Note that, you may adjust the block size of the block cyclic decomposition to reduce the communication overhead at the cost of increased load imbalance, so there is a tradeoff between the two sources of inefficiency. Show that you can scale to 64 cores. Groups of 3 should implement recursive coordinate bisection to balance the workloads and compare with cyclic mapping.

  To learn more about how to manage load balancing and partitiong, read this paper that is based on my dissertation: "Programming Abstractions for Dynamically Partitioning and Coordinating Localized Scientific Calculations Running on Multiprocessors," SIAM J. on Scientific and Statistical Computing, 12(145):145-157, January 1991.

  You'll note that the particles are given an initial random distribution. Thus, the load imbalance will be low. To make life more interesting, distribute the particles, say, within the upper quadrant. This will ensure that particles are unbalance.

Maintained by [Sun Oct 21 19:25:51 PDT 2012]