merk@mtu.edu
Dave Strenskistren@cray.com
All major HPC vendors currently have some UPC development project and there are two university based open source development efforts. UPC and CoArray Fortran are available on the X1 as a compiler options. In the case of UPC it is cc (-h upc). No other vendor has direct support for GAS, Global Address Space, programming models. The effort at Michigan Tech has been to provide a reference implementation of the current specification that would be as platform independent as possible. It is based on an EDG source to source frontend and the a runtime system, currently using MPI, that is being developed at Michigan Tech. Berkeley's publicly available implementation of UPC is part of a bigger effort including GasNet, which provides support for partitioned shared memory on various architectures including clusters, and Titanium, which provides partitioned shared memory on top of java.
UPC provides the user with "partitioned shared memory" and a generic SPMD programming model. The "single program" is referred to as a "thread". In some implementations a thread is a full UNIX process. The current specification does not allow a thread to spawning new threads. The number of threads in an execution is given by the reserved word THREADS. This number can be set at runtime by the program that launches the parallel run, for example aprun, or it can be fixed at compile time. The word MYTHREAD is the reserved word for a thread's identity. One can treat MYTHREAD as int in the range 0, 1, ..., THREADS-1. There is currently no notion of subsets of threads like communicators in MPI.
One of the design philosophies is that UPC should be a minimal extension to C. The developers jokingly once put the "UPC documentation kit" on a business card. A more realistic indication of it complexity is that the UPC section in the C and C++ Reference Manual for the X1 is only 19 pages long. [2] In addition, this minimal philosophy implies that individual threads behave like C programs. The extensions to handle shared memory and to control the interaction among threads should't interfere with the way one thinks about an individual thread.
Before we discuss the UPC commands, there are two issues involving the shared memory that cause some difficulty.
The idea of partitioned shared memory is not new, but we have adopted the new term in attempt to distinguish it from the many other types of shared memory systems built from physically distributed memory. Simply put, if one declares a variable as shared then all the threads have access to it. There is no restriction on mechanism that preforms the access. By default, variables are local---there is no
shared with global scope or one must have a pointer to a shared space that is allocated at runtime. In addition, partition shared memory introduces the notion of the
Affinity is one of the key ideas in UPC. It is one of the things that distinguishes it from other shared memory programming facilities, for example OpenMP. From an application research point of view, this notion of affinity gives us a way to experiment with two layers of a (shared) memory hierarchy. (This assumes that the multiple layers from registers to cache local memory are better managed by the compiler and the ILP mechanisms.) It also allows a programmer to abstractly control locality and by partitioning programs memory use, the programmer can expose parallelism in a natural way. Affinity usually corresponds with references that are "local" to node on which the thread is running and there is usually a corresponding penalty in latency and bandwidth for off-affinity references. This is much more significant on Beowulf cluster than on an X1. Our ability to handle affinity will determine whether or not we can efficiently run applications on multiple architectures.
To declare a variable as shared one uses the keyword shared as a type qualifier. For example given the declaration
shared float x;any thread can read or write the value of
x with statements like y=x; or x=5;. As an example of how affinity is controlled consider the following declarations:
shared float X[N]; shared [1] float Y[N]; shared [BLOCK] float Z[N];The data distribution for
A and B are the same. These have a
A[i] is i % THREADS. This is also referred to as the round robin distribution. The Z array is blocked with blocking factor BLOCK. In this case Z[0],z[1],...,Z[BLOCK-1] have affinity to thread 0, Z[BLOCK],z[BLOCK+1],...,Z[2*BLOCK-1] have affinity to thread 1, etc. For matrices, the declarations:
shared [1] float A[THREADS][THREADS]; shared [THREADS] float B[THREADS][THREADS];gives
A a column striped distribution and B a row striped distribution. It is clear that if THREADS divides the order of the matrix, then the right choice of blocking factor will produce any row or column, blocked or striped distribution.
Finally note that controlling the blocking factor on arrays is the only control of the data distribution that UPC provides. There is some debate on this point. Having more flexibility in data (affinity) distributions might help application developers. It might also hurt performance. Currently, if you want a more complicated data layout, you have to do the addressing arithmetic yourself. Some programmer dislike this, others like the fact that it is explicit and hence they have complete control over the distribution.
The other subtle point in UPC is the shared memory consistency model. UPC has two modes strict and relaxed. The UPC specification defines strict and relaxed as follows:
It is important that these models are well understood, because we want to have UPC programs that behave the same across multiple platforms. The relax model allows for out of order execution, caching and prefetching of non-affinity references. We hope this will allow us compensate for a lower bandwidth, high latency network to give good performance on some applications across multiple platforms. We also need precise understand of the memory model as we introduce additional features that like collective operations and parallel IO.
On the other hand, any UPC program can be executed with only strict references. There may be a loss in performance potential, but it will execute correctly. For this reason, memory models are one of the last things to cover when introducing new students to parallel computing with UPC. Most introductory work can be done using the relaxed memory model and upc_barriers (which are actually a split phase barriers) to synchronize the threads and upc_lock, upc_unlock pairs to protect critical sections. The difficulty with the memory model is seldom the programmer's intuition, rather the legal constraints placed on the implementors and developers.
A colleague is writing a UPC program to find maximal cliques in a random graph. This is a backtracking algorithm that he converted from his serial C program that he runs on a Linux workstation. This work is being done on a T3E running Carlson's original UPC implementation. The amount of speedup his able to obtain is minimal still because of load balancing issues. The algorithm uses a lexicographic trick to dramatically prune the backtrack tree. Unfortunately, the resulting tree is dramatically skewed, which leads to the load balancing issues. Current research is focused on better ways to prune the tree and better work queues to handle the load imbalance.
In this case, simply the fact that he tried to write a parallel program is a major accomplishment. We credit this to the fact he has access to a T3E, hence significant potential speedup and language which allowed him to incrementally convert his program to a parallel program.
In our parallel algorithms course this spring we used UPC and MPI on a Beowulf cluster as the example language for shared memory and message passing programming, respectively. We used the cluster because: 1) the other machines were tied up with research projects, 2) we wanted the experience of working in an environment that is readily available in the university community, and 3) performance didn't matter. The algorithms that we covered in class were first presented abstractly, from a mathematical or application point of view. Then the serial algorithm was usually presented in C pseudo code. Finally the shared memory and message codes were discussed.
Consider an easy grid based algorithm like solving heat equation on a thin plate. The serial version look like:
while( notdone ){
for( j=1; j < N-1; j++ ){
for( i=1; i < N-1; i++ ){
new_u[i][j] = 0.25*(u[i-1[j]+u[i+1][j]+u[i][j-1]+u[i][j+1]);
}
}
< u[i][j] = new_u[i][j] for all i,j >
< check if done >
}
Now if we use a blocked row distribution by declaring u and new_u shared as follows:
shared [ N/THREADS* N] float u[N][N], new_u[N][N];Then the main loop look like
while( notdone ){
for( j=1; j < N-1; j++ ){
if( upc_threadof( u[0][j] ) == MYTHREAD ){
for( i=1; i < N-1; i++ ){
new_u[i][j] = 0.25*(u[i-1[j]+u[i+1][j]+u[i][j-1]+u[i][j+1]);
}
}
}
< u[i][j] = new_u[i][j] for all i,j in my block>
< check if done: compute l2 norm and allreduce >
}
Domain Decomposition problems like this are easy because in most cases we simply do the same thing except we only do it on the cells for which we have affinity. There are a few collective operations that are required like the allreduce needed to compute the norm, but most of the code is the same. Many students questioned these assignments because they thought they were missing something---the assignments were to easy. It is also easy because we ignore the performance hit of the off-affinity references along the boundary between threads. To address the performance issue, one could turn this into the UPC version of a message passing program by moving the arrays into local memory, setting up shared arrays for the ghostcells and using upc_memcpy to move the ghostcells arrays in bulk. This supports the argument that you can incrementally write a UPC program, as oppose to an MPI which one to do all the memory management and all the messages before anything will run. This also introduces some of the performance differences between UPC on a cluster on a real shared memory machine like the X1.
Every major HPC vendor either has or is working on support for UPC.
UPC will work better on better hardware. In this case better means hardware that has high bandwidth, low latency memory systems and mechanisms for fine-grain synchronization. Since many MPI programs don't require these capabilities, there is often a cost/performance penalty for running MPI programs on such machines. This is has been a problem in high performance computing for the last several years.
UPC programs can be developed incrementally. This lowers the break-down threshold required to convince people to try parallel programming. In addition, the fact that one can also incrementally tune the performance of a UPC program presents a path from algorithm development and research on high-end systems to more cost effective reproduction code on cluster based systems. The Beowulf community often forgets that that the algorithms that run well in the low bandwidth, high latency cluster environment were first developed on machines that were much more forgiving from a latency, bandwidth, and locality perspective. "One first finds the algorithm and then one finds a way to make it latency tolerant." Having UPC on the full spectrum of machines from the X1 to Beowulf clusters facilitates this migration of algorithm from high-end systems to less expense systems. This can increase the productivity of the entire organization.
[2] Cray C and C++ Reference Manual (S-2179-52), April 2004.
http://cray.com
[3] W. Kuchera and C. Wallace, "The UPC Memory Model: Problems and Prospects",, IPDPS, 2004.
[4] T.El-Ghazawi and F.Cantonnet, "UPC Performance and Potential: A NPB Experimental Study", SC2002.
[5] "UPC Collective Operations Specifications", UPC Consortium, http://www.gwu.edu/~upc/pubs.html