Performance characterization of Uniform Parallel C, UPC (Cluster)
UPC is a parallel
programming language currently under development by a consortium that includes
industrial participants. In this project you'll compare the performance
of UPC with equivalent MPI implementations of selected applications.
See the web page for the
UPC Forum.
Dense Matrix factorization (Cluster or Cell)
Matrix factorization is used to solve systems of linear equations. Factorization
is discussed in section 8.3 of the text. Jim Demmel's notes provide a nice
discussion of the Gaussian Elimination algorithm:
http://www.cs.berkeley.edu/~demmel/cs267/lecture12/lecture12.html#link_3
This application requires the use of CYCLIC decomposition to balance the
workloads. Use a 2D block cyclic decomposition, and explore
scalability out to 1024 processors.
On Cell, the implementation is a bit different, see me for the details.
Sharks and fishes (Cluster or Cell)
Sharks and Fishes is a computer simulation designed to mimic the behavior
of moving bodies. There are several variants, and they are described more
fully at the URL
http://www.cs.berkeley.edu/~demmel/cs267/Sharks_and_Fish.
The simplest
version of Sharks and Fish is Conway's game of life
http://www.bitstorm.org/gameoflife.
On the cluster,
you should implement one of the more ambitious versions, e.g. version 5 or
version 6, where the load balancing problem arises.
On Cell a more basic implementation would suffice. See me for the details.
Matching Send/Receive Problem (Cluster)
New
As we know, the message passing model employs two-sided
communication, in which each message there is an explicit sender and recipient.
Thus, for each send there must be a matching receive, and vice versa.
However, it is not possible to perform this analysis statically;
the problem is undecidable.
In this project, you'll write a run time support package
to enable you to run an MPI program and to generate a report
of dynamically
executed, matched send/receive pairs, including their arguments,
and identifying call sites.
3D iterative Poisson solver (Cell)
Iterative solvers are used to solve certain partial differential
equations, and also systems of equations. They are a component of
multigrid (see the multigrid project). Assume that the
input does not fit into Cell’s local store. Orchestrate
DMA transfers, employing triple buffering to overlap
data motion with computation. Optimize the data transfer
geometry and also vectorize the inner loops.
Wavelet compression (Cell)
Implement a wavelet compression algorithm on Cell,
and it apply it to a large data set. See more for the details
including a suggested dataset.
A web page for wavelet resources is posted at
Multigrid is a fast technique for solving certain partial
differential equations, and also to solve systems of equations. It accelerates
the computation performed by RedBlack3D. Report on the effects of reduced parallelism at the coarser levels.
See Jim Demmel's Notes on Multigrid for the details, including numerical issues.
As an option you could compare performance and scalability with that of an an FFT solver.
Comparative performance study of Cell BE against
conventional parallel implementations.
The Cell BE can boost performance for certain applications,
but it incurs high programming overheads compared with
more conventional parallel implementations (MPI, OpenMP, threads, etc.)
In this project at least 3 individuals will collaborate to make cross-platform
comparisons.
I will also consider broader efforts involving more than three persons,
or an organization involving two or more teams.
See me about the details.