Introduction

The Rise of the 'Multicore' Machines

While 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 nodes1, 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 Model

The 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.

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.

!$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

Distributed-Memory Model

The 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.

The 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.

The Partitioned Global Address Space (PGAS) Model

The 'Best' of Both Worlds

Ideally 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:

The 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.

In Figure 3, five data objects have been declared within the PGAS programming model:

Each 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.

PGAS Programming Languages

Currently there are three (3) PGAS programming languages that are becoming commonplace on modern computing systems:

Matrix Multiplication with UPC, CAF and Titanium

For 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];
    }
  }
}

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

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];
      }
  }
}

The Asynchronous Partitioned Global Address Space Model

Within 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.

As 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:

Both 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:

// 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);
}

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

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

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.