~ $ cd research/streams-by-annotation && cat README.md

Streams by annotation

A radio, a video decoder, a filter: a program that reads a value, works on it, writes a result, and does it again for ever. Written in C it is a while loop. Run on several cores it should be a pipeline, every stage on a core of its own with the data flowing between them — and the usual way to get there is to throw the C away and write it again in a streaming language.

The stream programming model of the European project ACOTES, which is the compiler I wrote at the Barcelona Supercomputing Center, does it the way OpenMP does loops: the program stays, and the pipeline is written in its margin. What follows are the examples of the poster it was presented with at HiPEAC's summer school in 2008, which I signed with Roger Ferrer, Xavier Martorell and Eduard Ayguadé.

From plain C, one line at a time

A program that turns capitals into small letters:

int main()
{
  char c;

  while (fread(&c, sizeof(c), 1, stdin)) {

    if ('A' <= c && c <= 'Z')
      c= c - 'A' + 'a';

    fwrite(&c, sizeof(c), 1, stdout);
  }
  return 0;
}

First say where the stream is. One line, and the program still runs exactly as it did, because a compiler that does not know the annotation ignores it:

  #pragma acotes taskgroup
  while (fread(&c, sizeof(c), 1, stdin)) {

Then say what the stages are, and what each takes in and gives out:

  #pragma acotes taskgroup
  while (fread(&c, sizeof(c), 1, stdin)) {

    #pragma acotes task input(c) output(c)
    if ('A' <= c && c <= 'Z')
      c= c - 'A' + 'a';

    #pragma acotes task input(c)
    fwrite(&c, sizeof(c), 1, stdout);
  }

That is the whole of it. From input and output the compiler isolates each task's code, works out who feeds whom, and builds the graph:

Three things run at once: the loop reading, the first task converting the character before, the second writing the one before that. Add a suffix, output(c:bp), and the values travel in blocks instead of one at a time, which is where most of the speed of a stream is.

The point of doing it a line at a time is that the program works after every line. It can be debugged serially, the annotations can be switched off, and the code that was already written and trusted is still the code.

A task with a memory

Real filters remember things. A task's variables are its own, and the annotation says how they start and how they end:

  #pragma acotes task input(v) output(o) \
          copyinstate(stats) copyoutstate(stats) \
          initializestate(buff) finalizestate(buff)
  {
    o= compute_buffer(buff, v);
    stats++;
  }

And a filter that needs the last few values does not have to keep them itself. peek gives the task a window on its input stream, so the task stays without state and nothing is copied:

  #pragma acotes task copyinstate(i, a[3]) input(v) output(o)
  {
    #pragma acotes peek(v;a)
    {
      a[2]= a[1];  a[1]= a[0];  a[0]= v;
    }
    o= a[0]*.25 + a[1]*.5 + a[2]*.25;
  }

Splitting a task that is too slow

A pipeline runs at the speed of its slowest stage. When one task is the bottleneck, it is split: team(3) makes three instances of it, a replicator deals the input out among them and a merger puts the results back in order.

  #pragma acotes task team(3) copyinstate(a[3]) inputreplicate(c) output(o)
  {
    #pragma acotes teamreplicate
    h(c, a)

    o= ffd(c, a);
  }

The difficulty is that the task has state, and three copies of a task with state compute three different things. teamreplicate marks the part that updates the state, and that part runs in every instance for every value, so each copy's state stays exactly what the single task's would have been; only the expensive part is shared out. Data parallelism, from a task that was not data-parallel.

A loop that is already in the program can be used the same way: forreplicate(i) turns its iterations into instances, and a port says which elements of an array go to which. And tasks that are not in a pipeline at all — a microphone being played while a keyboard changes the volume — can share a value with async, update and check, the programmer deciding when it is looked at.

What it measured

The prototype compiler and its runtime ran on a machine with four cores. They were a proof that the model could be compiled, not an attempt to be fast, and the numbers should be read that way.

An FM radio written as plain C, annotated, and turned into a stream program by the compiler with nobody drawing the graph by hand: 3.5 times faster on four cores. What held it back was one filter much heavier than the rest, the FFD. Give that one task a team and, in the thesis's words, the radio is able to use effectively all four available cores. A Wi-Fi 802.11a receiver scaled slightly better than the number of cores.

Replicating the FFD alone scaled poorly with the radio's own parameters — the runtime's overhead was larger than the work — and well once the filter was made heavier, as well as the same filter did in StreamIt, the streaming language it was being compared with. Which is the honest summary of the whole model: the same three kinds of parallelism as a language designed for them — task, pipeline and data — from a C program that was never rewritten.

The FM radio, taken from GNU Radio's examples and stripped down to pure serial C, is one of the tools the thesis released. The compiler, its runtime and the tracing library are public, under the GPL.