Pabble protocol description language

Scribble Parameterised Session Types C++

Pabble is a protocol description language, parametric variant of the Scribble language, extended for modelling communication in parallel applications.

Publications

Scribble project
Poster for code generation work

Pabble examples

Pabble protocols: dwarfs

The following Pabble protocols are examples chosen from am evaluation metic for parallel programming models and architectues called dwarfs from UC Berkeley, details available from their CACM article. The article defines six categories of algorithmic patterns (called dwarfs) common in HPC applications: Structured Grid, Dense Matrix, Sparse Matrix, Spectral (FFT), Particle methods, and Unstructured Grid. Each of the protocols below belong to one of the categories.

N-Body simulation

global protocol NBody(role W[0..N]) {
    rec LOOP {
        (float) from Worker[i:0..N-1] to W[i+1];
        (float) from Worker[N] to W[0];
        /* Calculate Velocity */
        continue LOOP; 
    }
    /* Calculate Step */
}

Dynamic load balancing

global protocol LoadBalancing(role Worker[0..N]) {
    rec REPEAT {
        oneof (Worker[i in 1..N]) {
            request() from Worker[i] to Worker[0];
            choice at Worker[0] {
                finish() from Worker[0] to Worker[i];
                foreach (x:1..N except i) {
                    request() from Worker[x] to Worker[0];
                    finish() from Worker[0] to Worker[x]; 
                }
            } or {
                reply() from Worker[0] to Worker[i]; continue REPEAT;
            }
        }
    }
}

Dense matrix-vector multiplication

global protocol DenseMatVec(role Worker[0..N]) {
    // Scatter Matrix A
    foreach (i:1..N) {
        LBound(int) from Worker[0] to Worker[i];
        UBound(int) from Worker[0] to Worker[i];
        Data(double) from Worker[0] to Worker[i];
    }
    // Scatter Vector B
    (double) from Worker[0] to Worker[1..N];
    // --- Perform calculation ---
    // Gather data
    (double) from Worker[1..N] to Worker[0];
}

Sparse matrix-vector multiplication

global protocol SparseMatVec(role PE[0..N]) {
    /* Distribute data */
    (int) from W[0] to W[1..N]; // row_ptr
    (int) from W[0] to W[1..N]; // col_ind
    (double) from W[0] to W[1..N]; // vals
    (double) from W[0] to W[1..N]; // vector
    /* Output vector */
    (double) from W[1..N] to W[0];
}

Fast-Fourier Transformation (FFT)

const N = 3;
global protocol FFT(role W[0..7]) {
    foreach (r:0..N-1) {
        foreach (i:0..2<<N-1) {
            Label(int) from Worker[i] to Worker[i - (i/1<<r)%2 * 1<<(r+1) + 1<<r];
        }
    }
}

Linear Equation Solver

global protocol Solver(role W[1..N][1..N], group Col={W[1..N][1]}) {
    rec CONVERGE {
        Ring(double) from W[i:1..N][j:1..N-1] to W[i][j+1];
        Ring(double) from W[i:1..N][N] to W[i][1];

        // Vertical propagation
        (double) from Col to Col;
        continue CONVERGE; 
    }
}

Monte-Carlo Pi simulation

global protocol MonteCarloPi(role Worker[0..N]) {
    // Calculation per process
    Count(int) from Worker[0] to Worker[1..N];
    Result(double) from Worker[1..N] to Worker[0];
    // Final result calculated at Worker[0];
}