A Simple Dataflow Interpreter

CMSC 683/691c, Parallel Programming

Project 4: A Simple Dataflow Interpreter

Project Goals

The purpose of this project is to learn more about dataflow scheduling, and to gain hands-on experience programming with threads.

The Project

You are to write an interpreter for a simple low-level dataflow language, "DFL", as defined below. A DFL program is simply an adjacency-list representation of a dataflow graph. Your interpreter will use a fixed set of threads (or processes) to execute the dataflow graph with as much parallelism as possible.

The DFL Language

DFL is a low-level language, and a DFL "program" directly defines a dataflow graph. DFL statements can appear in any order, and have one of three forms

         lval = rval
         lval = lval = rval
         lval = rval op rval

There is one DFL statement per line, and the parts of a statement are separated by one or more spaces. DFL has a limited set of operators, variables and constants

         op   --> [+-*/=~?]
         lval --> var | out | halt
         rval --> var | in | num

Variables

DFL variables var consist of a letter followed by a sequence of zero or more letters or numbers, and are simply names for queues of integers. A variable reference on the left-hand side of an assignment indicates writing to the associated queue, and a variable reference on the right-hand side of an assignment indicates reading from the associated queue. Variables can appear at most once on the right-hand side of an assignment statement; thus we need an explicit "copy" operator for sharing a value.

The variables "in", "out", and "halt" have special meanings. "in" is used only on the right-hand side of a statement, and reads integers from stdin or from the specified file. "out" and "halt" are used only on the left-hand side of a statement. "out" writes integers to stdout, and "halt", when assigned any value, ends the computation--any statements on the ready queue are executed, but no further statements are added to the ready queue, any remaining values in the "out" queue are written to stdout, and the interpreter terminates.

Constants

DFL constants num are integers, and can appear only on the right-hand side of a statement. A constant reference in a statement has the effect of writing the value to the associated buffer exactly once.

Operators

In general, a DFL statement bi = bj op bk has the effect of reading values from queues bj and bk, performing op on those values, and writing the result to queue bi. DFL defines the following binary operators

The binary operators {+, -, *, /} have the usual meanings for integers
The "=" operator, as part of the statement bi = bj = bk is a double assignment or `copy' command, and has the effect of reading a value from buffer bk and writing it to buffers bi and bj
The "~" operator is an equality test. The statement bi = bj ~ bk writes a 1 to buffer bi if bj and bk are equal, and a 0 otherwise
The "?" is a "gate" or control operator. The statement bi = bj ? bk reads buffers bj and bk. If bj is zero the values bj and bk are discarded; if bj is non-zero, the value from bk is written to buffer bi

An example program

The following is a simple DFL program to factor an odd number by trial division. The variable names don't have any particular meaning here; they are simply labels for edges in the dataflow graph. (Variables in this example are all of the form a0-z9 for backward compatibility with the first version of DFL.)

a1 = 1
a5 = a1 = a1
a2 = 0
a6 = a2 + a5
a2 = a7 = a6
a3 = 2
a8 = a3 = a3
c5 = a7 * a8
a4 = 1
a9 = a4 = a4
c3 = c5 + a9
b5 = b6 = c3
b1 = in 
b2 = b1 = b1
b9 = b3 = b2
b8 = b7 = b6
b4 = b3 / b5
c6 = b4 * b7
c1 = b9 ~ c6
c2 = c1 ? b8
halt = out = c2

The associated dataflow graph of the program may make its function more obvious.

Program Execution

As the program is read and parsed a record is created for each statement of the form bi = bj op bk a record is created consisting of

the queues for bj and bk
a code for the operation op.
the name of (or a pointer to) the queue for bi

For assignments of the form bi = bj a record is created consisting of

the queue for bj
the name of (or a pointer to) the queue bi

Execution begins when all the program statements have been read and each lval (buffer write) has been paired with an rval (buffer address). Statement records become ready when their associated input queue(s) are non-empty and output queue(s) are not full.

A ready statement-record is executed by removing values from input queues, performing the specified operation, and writing the resulting value to the specified output queue. Ready statement-records can be queued for execution, and can be executed in any order, or in parallel by a set of threads. After execution, a statement-record may or may not still be ready for execution again, depending on the state of the associated queues.

These execution rules give "static dataflow," as discussed by your text. For greater concurrency, if both buffers of a statement-record have several values, we would like to process these values in parallel, while keeping the output values in order. (You don't have to do that for this project, though!)

Running your interpreter

Your interpreter should read the DFL program's filename and the name of an optional data-file from the command line:

                   dfl program [datafile]

"program" is the name of the DFL program file, and "datafile" is an optional file of integers, to be read by the "in" variable. ("in" reads from stdin, if no file is specified.)

Discussion

The hardest part of the project is probably parsing the program and building an internal representation of the dataflow graph; and dealing with i/o can also be messy. An example parser that does this, taken from a working (as far as I can tell, but no guarantees) demo, is available; this is a grungy hack, and in retrospect it would have been far simpler to use "lex" or similar tools to build the internal representation of the dataflow graph, and to use an array of token buffers, separate from the statement records. You don't have to use this code, but it's there if you want to look at it.

If you can get the project to work without threads, as a single process, it shouldn't be too difficult to add the code for threads. There are a number of ways to manage the threads. For example, you can have a single "dispatcher" handing off tasks (ready statements) to a set of threads, or you can simply divide up the statements among the threads. The latter approach may not give the greatest theoretical parallelism, but it eliminates the need for a separate dispatcher, which can be a major bottleneck. Be careful to restrict i/o to a single thread.