StreamIt

Sources

W. Thies, M. Karczmarek, and S. Amarasinghe, “StreamIt: A Language for Streaming Applications,” in Compiler Construction, 2002, pp. 179–196.
MIT, StreamIt Cookbook. 2006.

Motivation for StreamIt

Provide high-level stream abstractions to improve productivity and program robustness within streaming domain
Serve as common machine language for grid-based processors ^[1]

Characteristics of a Streaming Application

Large (virtually infinite) streams of data
Independent filters as basic unit of transformation
Stable computation pattern
Occasional structure modification and side-effects
- e.g. adding filters to clean up high noise; changing cell phone volume
High performance

Program Structure

A program is a composition (via pipelines, split-joins, and feedback loops) of filters into a directed stream graph, connecting inputs to outputs.

Filter

Minimal.str

void->int filter IntSource { (1)
  int x;
  init { x = 0; }            (2)
  work push 1 { push(x++); } (3)
}

1	Specify input and output types; `void` indicates a boundary of program
2	Establishes initial state; will be called implicitly with same arguments passed to constructor
3	Execution step in steady state; `push` adds a single item to filter’s output stream

Pipeline

MovingAverage.str

void->void pipeline MovingAverage {
  add IntSource();                  (1)
  add Averager(10);
  add IntPrinter();
}

int->int filter Averager(int n) {
  work pop 1 push 1 peek n {        (2)
    int sum = 0;
    for (int i = 0; i < n; i++)
      sum += peek(i);               (3)
    push(sum/n);
    pop();                          (4)
  }
}

void->int filter IntSource {
    int x;
    init { x = 0; }
    work push 1 {
	push(x);
	x++;
    }
}

int->void filter IntPrinter {
    work pop 1 { println(pop()); }
}

1	Add filters (connected in order)
2	Specify data rates; `peek(n)` is a maximum rate
3	`peek(0)` returns next item that would be popped
4	`pop` removes a single item from the its input stream

Here’s what it looks like from a higher-level:

The scheduler guarantees that Averager filter not run until its input rates can be met (causes source to be run an additional nine times). The compiler automatically schedules execution of adjacent filters with different push-pop rates.

Split Join

BandPassFilter.str

float->float pipeline BandPassFilter (float rate, float low, float high, int taps) {
  add BPFCore(rate, low, high, taps);
  add Subtracter();
}
float->float splitjoin BPFCore (float rate, float low, float high, int taps) {
  split duplicate;                              (1)
  add LowPassFilter(rate, low, taps, 0);
  add LowPassFilter(rate, high, taps, 0);
  join roundrobin;                              (2)
}
float->float filter Subtracter {
  work pop 2 push 1 {
    push(peek(1) - peek(0));
    pop(); pop();
  }
}

1	Splitter runs some number of children in parallel
2	Round-robin joiner combines outputs from children in order they were added

Here’s what it looks like from a higher-level: bpf

Round-robin can be used as both a splitter and joiner. In the joiner case, roundrobin(1,2,1) specifies that it requires exactly three incoming children, reading one from the first, two from the second, and one from the third.

Feedback Loop

Can consider this an inverted split-join (joiner at the top and splitter at the bottom).
Has exactly two children ("body" and "loop")

EchoProgram.str

float->float feedbackloop Echo
    (int n, float f) {
  join roundrobin(1,1);
  body FloatAdderBypass();          (1)
  loop float->float filter {        (2)
    work pop 1 push 1 {
      push(pop() * f);
    }
  };
  split roundrobin;
  for (int i = 0; i < n; i++)
    enqueue(0);                     (3)
}
float->float filter FloatAdderBypass {
  work pop 2 push 2 {
    push(peek(0) + peek(1));
    push(peek(0));
    pop();
    pop();
  }
}

1	Adds child as `body` part of feedback loop
2	Adds child as `loop` part of feedback loop
3	Pushes item onto input of joiner coming from loop part of feedback loop

Here’s what it looks like from a higher-level: echo

Miscellanea

Data rates can be dynamically or statically allocated
Only datatypes are void, int, float, complex, and bit

1. A story for another day