An Introduction to the Partitioned Global Address Space (PGAS) Programming Model

Introduction The Rise of the 'Multicore' MachinesWhile Moore's Law continues to predict the doubling of transistors on an integrated circuit every 18 months, performance and power considerations have forced chip designers to embrace multi-core processors in place of higher frequency uni-core processors. As desktop and high-performance computing architectures tend towards distributed collections of multi-core nodesWe can view a multi-core processor and its associated memory as a traditional symmetric multiprocessing (SMP) node., a new parallel programming paradigm is required to fully exploit the complex distributed and shared-memory hierarchies of these evolutionary systems. Recently, a programming model has been developed that has the potential to exploit the best features of this distributed shared-memory architecture. Not only does this model promise improved runtime performance on distributed clusters of SMPs, its data and execution semantics support increased programmer productivity. This model is called the Partitioned Global Address Space (PGAS) model.

A Brief Review of Conventional Parallel Programming Models Shared-Memory ModelThe shared-memory programming model typically exploits a shared memory system, where any memory location is directly accessible by any of the computing processes (i.e. there is a single global address space). This programming model is similar in some respects to the sequential single-processor programming model with the addition of new constructs for synchronising multiple access to shared variables and memory locations.

Shared-Memory Architecture and Programming Model The shared-memory architecture and programming model is illustrated in Figure 1. In this model any processing element (PE) can make a reference to any memory address within the global address space. The memory request is forwarded through an interconnection network to memory, with the result returned back, via the network, to the PE. Typically, a shared-memory system will implement a multi-threaded programming model, where each processing element executes program thread. Currently, OpenMP and Pthreads are the two application programming interfaces (API) predominantly used to implement multi-threaded applications on shared-memory systems. Which of the following properties of the shared-memory programming model (e.g using OpenMP) are generally true: (a) It's a simpler programming model than the programming models for distributed-memory systems (b) Provides precise control over data locality and processor affinity (c) Supports finer-grain parallelism e.g., loop-level parallelism (d) Supports incremental parallelization (e) Shared-memory programming bugs are easier to track down (a) TRUE - It's a simpler programming model than the programming models for distributed-memory systems Arguably, a single global address space simplifies memory references (e.g. array and variable references) within the program code, akin to the sequential programming model. (b) FALSE - Provides precise control over data locality and processor affinity Generally shared-memory programming models provide little or no support for data placement and processor association. (c) TRUE - Supports finer-grain parallelism e.g., loop-level parallelism Generally with a multi-threaded based programming language, program loops can be parallelized by executing independent iterations on different threads. In OpenMP this can be accomplished with the PARALLEL DO directive:


!$OMP DO SCHEDULE(DYNAMIC,CHUNK)
      DO I = 1, N
        C(I) = A(I) + B(I)
        WRITE(*,100) TID,I,C(I)
 100    FORMAT(' Thread',I2,': C(',I3,')=',F8.2)
      ENDDO
!$OMP END DO NOWAIT

(d) TRUE - Supports incremental parallelization As illustrated in the example above, individual code segments can be parallelized by simply wrapping them in OpenMP directives. (e) FALSE - Shared-memory programming bugs are easier to track down Shared-memory programming bugs involving synchronization and data races can be very difficult to trace. Distributed-Memory ModelThe distributed-memory programming model exploits a distributed-memory system where each processor maintains its own local memory and has no direct knowledge about another processor's memory (a "share nothing" approach). For data to be shared, it must be passed from one processor to another as a message. Data that resides on the local memory of a processor can be accessed much more quickly than data that resides on another processor.

Distributed-Memory Architecture and Programming ModelThe distributed-memory architecture and programming model is illustrated in Figure 2. If a processing element (PE) requires data from another PE to continue its execution, it must request the data. The request is made by sending a message, through the interconnection network, to the destination PE. When the data is available on the destination PE it is returned within a message, through the interconnection network, to the requesting PE. Typically, a distributed-memory system will implement a message-passing programming model, where processing elements communicate data by sending and receiving messages. Currently, MPI is the de facto standard specification for implementing message-passing on distributed-memory systems. MPI programs generally follow a Single Program Multiple Data (SPMD) programming style. Which of the following properties of the distributed-memory programming model (using MPI) are generally true: (a) For many architectures, it can result in near-optimal performance (b) Provides precise control over data locality and processor affinity (c) Allows natural mapping of algorithms to implementation (d) Supports incremental parallelization (e) Runs on most parallel platforms (a) TRUE - For many architectures, it can result in near-optimal performance (b) TRUE - Provides precise control over data locality and processor affinity Each MPI process has direct access to its local memory for reading and writing data values. Accessing local data is more efficient than accessing data on a remote process. (e) TRUE - Runs on most parallel platforms

The Partitioned Global Address Space (PGAS) ModelThe 'Best' of Both WorldsIdeally a successful parallel programming model should hope to marry the performance and data locality (partitioning) features of MPI with the programmability and data referencing simplicity of a shared-memory (global address space) model.The PGAS programming model aims to achieve these characteristics by providing:a local-view programming style (which differentiates between local and remote data partitions) a global address space (which is directly accessible by any process) compiler-introduced communication to resolve remote references one-sided communication for improved inter-process performance support for distributed data structures

PGAS Programming ModelThe PGAS programming model is illustrated in Figure 3. In this model variables and arrays can be either shared or local. Each process has private memory for local data items and shared memory for globally shared data values. While the shared-memory is partitioned among the cooperating processes (each process will contribute memory to to the shared global memory), a process can directly access any data item within the global address space with a single address. Greater performance is achieved when a process accesses data which is held locally (whether in its private memory or a partition of the global address space). In Figure 3, five data objects have been declared within the PGAS programming model: Each process has declared a private copy of variable x Process 2 has declared a shared variable y A shared array A is distributed across the global address spaceEach instance of variable x can directly write and read values to/from the global address space. Likewise an address in the global address space can be directly read or written to from another address within the global address space.Typically, PGAS language compilers generate the necessary communication during program compilation.PGAS Programming LanguagesCurrently there are three (3) PGAS programming languages that are becoming commonplace on modern computing systems: Unified Parallel C (UPC) Co-Array Fortran (CAF) TitaniumMatrix Multiplication with UPC, CAF and TitaniumFor your curiosity, the following code examples illustrate some of the PGAS language features provided by UPC, CAF and Titanium respectively. For each language, a primitive matrix multiplication operation has been implemented.


#include <upc_relaxed.h>

// a and c are blocked shared matrices, initialization is not currently implemented
shared [N*P /THREADS] int a[N][P], c[N][M];
shared[M/THREADS] int b[P][M];
int b_local[P][M];

void main (void) {
  int i, j , l; // private variables
  upc_memget(b_local, b, P*M*sizeof(int));

  upc_forall(i = 0 ; i<N ; i++; &c[i][0]) {
    for (j=0 ; j<M ;j++) {
      c[i][j] = 0;
      for (l= 0 ; l<P ; l++) c[i][j] += a[i][l]*b_local[l][j];
    }
  }
}Matrix Multiplication in UPC


real,dimension(n,n)[p,*] :: a,b,c

do k=1,n
  do q=1,p
    c(i,j) = c(i,j) + a(i,k)[myP, q]*b(k,j)[q,myQ]
  end do
end do
Matrix Multiplication in Co-Array Fortran


public static void matMul(double [2d] a,
                          double [2d] b,
                          double [2d] c) {

  foreach (ij in c.domain()) {
    double [1d] aRowi = a.slice(1, ij[1]);
    double [1d] bColj = b.slice(2, ij[2]);

      foreach (k in aRowi.domain()) {
        c[ij] += aRowi[k] * bColj[k];
      }
  }
}
Matrix Multiplication in Titanium

The Asynchronous Partitioned Global Address Space ModelWithin the U.S., the DARPA HPCS project has the goal to raise high-performance computing (HPC) user productivity by a factor of 10 by the year 2010.Productivity = Performance + Programmability + Portability + RobustnessAs part of this project two novel parallel programming languages are being funded for development, with the aim of improving programmer productivity on next-generation computing architectures. The two languages under development are: X10 ChapelBoth these languages implement an asynchronous partitioned global address space (APGAS) programming model; a term originally coined within the X10 language project. The APGAS model extends the PGAS programming model by providing a richer execution framework than the SPMD style generally used by the traditional PGAS languages. In particular, asynchrony is achieved by:permitting each node to execute multiple tasks from a task pool permitting nodes to invoke work on other nodes This example illustrates asynchronous task creation in Chapel using Chapel's Locales concept.

// Chapel programs begin running on locale 0 by default
var x, y: real;         // allocate x and y on locale 0

x=1;y=2;

begin on Locales(1) {   // asynchronously create task on locale 1
  var z: real;          // allocate z on locale 1
  writeln(x.locale.id); // print “0”
  writeln(z.locale.id); // print “1”
  z = x + y;            // requires “get” for x and y
  writeln(z);
}Asynchronous Task Creation in Chapel

This example illustrates asynchronous task creation in X10 using X10's async concept.


// global dist. array
final double a[D] =  …;  
final int k = …;

async ( a.distribution[99] ) { 
    // executed at A[99]’s place
    atomic a[99] = k; 
}
Asynchronous Task Creation in X10

Chapel and X10 provide many more high-level language features to improve programmer productivity during the development of parallel applications. These features will be explored in further detail in separate modules. If you are interested in learning more about the next-generation parallel programming languages X10 and Chapel, please view the following video and audio introductions, presented by the technical leads of each project. An Audio Introduction to X10 by Vijay Saraswat (IBM)

You can download the transcript of the audio presentation here. A Video Introduction to Chapel by Brad Chamberlain (Cray Inc.) Google Seattle Conference on Scalability 2008: Chapel - Productive Parallel Programming at Scale.