π-calculus, Session Types research at Imperial College
This paper presents a code generation framework for type-safe and deadlock-free Message Passing Interface (MPI) programs. The code generation process starts with the definition of the global topology using a protocol specification language based on parameterised multiparty session types (MPST). An MPI parallel program backbone is automatically generated from the global specification. The backbone code can then be merged with the sequential code describing the application behaviour, resulting in a complete MPI program. This merging process is fully automated through the use of an aspect-oriented compilation approach. In this way, programmers only need to supply the intended communication protocol and provide sequential code to automatically obtain parallelised programs that are guaranteed free from communication mismatch, type errors or deadlocks. The code generation framework also integrates an optimisation method that overlaps communication and computation, and can derive not only representative parallel programs with common parallel patterns (such as ring and stencil), but also distributed applications from any MPST protocols. We show that our tool generates efficient and scalable MPI applications, and improves productivity of programmers. For instance, our benchmarks involving representative parallel and application-specific patterns speed up sequential execution by up to 31 times and reduce programming effort by an average of 39%.
Protocol (Pabble) | Backbone (C/MPI) | Diagram |
---|---|---|
ring pipeline | Backbone | |
stencil | Backbone | |
scatter-gather | Backbone | |
master-worker | Backbone | |
all-to-all | Backbone | |
fft64 | Backbone | Repeated for 64 processes with r=5 |
The Overall benchmark compares the performance of all the applications we evaluated in our framework. The range of protocols used by the implementations are both from the repository and custom. All implementations are spawned with 64 processes (maximum available on our target cluster), this provides a common environment to compare the speedup of each implementation.
The Nbody benchmark compares the performance of N-body simulation implemented in the Ring protocol and shows how it scales with an increasing number of parallel process. As a parallel algorithm very suitable for our communication-computation overlapping using asynchronous optimisation we described in our paper, we show the impact on performance when we utilise the optimisation technique.
The Solver benchmark compare the performance of a Linear Equation Solver implemented in a custom, wraparound mesh protocol (see below). The aim of this benchmark is to show the flexibility of our framework which uses a used-specified protocol not in the protocol repository above.
module custom;
const N = 2..max;
global protocol Solver(role Worker[1..N][1..N], group Col={Worker[1..N][1]}) {
rec Converge {
BeforeRing() from __self to __self;
Ring(double) from Worker[i:1..N][j:1..N-1] to Worker[i][j+1];
Ring(double) from Worker[i:1..N][N] to Worker[i][1];
AfterRing() from __self to __self;
// Vertical propagation
Propagate(double) from Col to Col;
continue Converge;
}
}
The MapReduce benchmark compares 2 different applications, AdPredictor and Word Count, that share the scatter-gather protocol with 2 different set of kernel.
Pre-compiled packages for Debian/Ubuntu Linux: libsesstype libesesstype-dev libscribble libscribble-dev pabble-mpi
$ scribble-tool /path/to/protocol.spr --codegen --project ProjectionRole | pabble-mpi-tool -
@inproceedings{NCY2015, author = {Nicholas Ng and Jose G.F. Coutinho and Nobuko Yoshida}, title = {{Protocols by Default: Safe MPI Code Generation based on Session Types}}, booktitle = {24th International Conference on Compiler Construction}, series = {LNCS}, volume = {9031}, pages = {212--232}, publisher = {Springer}, year = 2015 }
@inproceedings{NCY2015, author = {Nicholas Ng and Jose G.F. Coutinho and Nobuko Yoshida}, title = {{Protocols by Default: Safe MPI Code Generation based on Session Types}}, booktitle = {24th International Conference on Compiler Construction}, series = {LNCS}, volume = {9031}, pages = {212--232}, publisher = {Springer}, doi = "10.1007/978-3-662-46663-6_11", year = 2015 }