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

You can download the current release of the library from here.

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

License

This code and documentation is copyright by the authors and Imperial College. The software is provided for evaluation purposes.

If you wish to use the software for any practical purpose, permission must be gained from Paul Kelly.

No charge will be made to academic and research users of this version of the software.

Authors and Contributors

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

Installation

The library cannot sensibly be distributed in binary form, as it needs to invoke your compiler at runtime. Instead, you need to expand the tarball on your machine and recompile. This works on Linux, and also on Windows using the Cygwin package. See the "INSTALL" file in the distribution - basically, run a setup script and then run make.

System Requirements

The distribution has been tested under various recent Linux distributions (using gcc 3.3,3.4,4.0,4.1), and Windows XP with Cygwin (using gcc 3.x). If you have the Intel C/C++ compiler installed as well, this can be invoked at runtime.

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.

Problems

• Email Michael Mellor (mrm99@doc.ic.ac.uk)