The TaskGraph Meta-programming Library

The TaskGraph Meta-programming Library is a C++ package that supports

• Run-time code generation - programs that generate code on the fly, then execute it (the first step towards "multi-stage" programming)
• Meta-programming - having built a piece of code, you can apply various transformations to it (such as loop interchange and tiling).

The library is available at on github.

It is presented in a talk and a paper (however this distribution has a tidied and more typesafe design).

Example (from examples/introductory/simpleinterchange)

#include <stdio.h>

#include <stdlib.h>

#include <TaskGraph>

using namespace tg;

typedef TaskGraph<int, int> TG_IntResIntArg;

int main( int argc, char *argv[] ) {

TG_IntResIntArg T;

int n = atoi( argv[1] );

taskgraph( TG_IntResIntArg, T, tuple1(a) ) {

tVar(int, i);

tVar(int, j);

tFor(i, 0, n-1) {

tFor(j, 0, n-1) {

tPrintf("Iteration i=%d, j=%d\n", i, j);

}

}

tReturn(a + n);

}

InterchangeSettings inter;

inter.firstLoop = LoopIdentifier ( 1 );

inter.secondLoop = LoopIdentifier ( 1, 1 );

T.applyOptimisation ( "interchange", &inter );

T.compile( tg::GCC, true );

printf( "T(%d) = %d\n", n, T(n) );

}

If you run this with input 2, it prints:

 
Iteration i=0, j=0
Iteration i=1, j=0
Iteration i=0, j=1
Iteration i=1, j=1
T(2) = 4

At runtime it generates the following code:

 
extern int printf(char *, ...);
extern int taskGraph_0(void **);
 
extern int taskGraph_0(void **params)
 {
 int *a;
 int i;
  int j;
 static char string0_[23] = "Iteration i=%d, j=%d\n";
 
 a = *params;
 for (j = 0; j <= 1; j++)
 {
 for (i = 0; i <= 1; i++)
 {
 printf(string0_, i, j);
 }
 }
 return *a + 2;
 }

The distribution includes examples that demonstrate performance improvements thanks to two Taskgraph features:

· Specialisation:

· Convolution filtering

· Interpreter for simple functional language

· JIT for a RISC instruction set

· Ray tracing

· Transformation:

· Tiling and loop interchange for matrix multiply

· Skewing and tiling for a Gauss-Seidel smoother

· Design-space exploration: searching for optimum tiling factor

There are also some more complex generators, for example producing recursively-tiled loops to walk arrays in Morton order - code that is very hard to write by hand.

Taskgraphs are typed and taskgraph parameters are type-checked.

Authors and Contributors

• Alastair Houghton
• Michael Mellor
• Paul Kelly
• Peter Fordham
• Olav Beckmann
• Konstantinos Spyropoulos
• Peter Collingbourne
• Francis Russell

Getting Started

• Take a look at the examples/introductory/simple directory. Try to run:

  ./addc 1

This should print "T(b) = 2"!

• There are additional examples included in this package, showing various algorithms or techniques that the TaskGraph library is best suited at. They typically contain a C++ implementation of the algorithm or technique, as well as a TaskGraph implementation, for easy comparison of speeds. More details on each example can be found in the examples/README file.