Final Project Write-up, Part 4: The Implementation

Frontend

Our language is a modification of the 164 language, so we already had the bytecode interpreter and the grammar. We ended up modifying the bytecode to implement while loops, if statements, and function definitions as bytecode instructions instead of syntactic sugar in terms of conds and lambdas. Each program is compiled just like a 164 program, but instead of feeding the bytecode directly into an interpreter, we first build a dependency graph from the bytecode. Then we send that graph (a dag) into a modified 164 interpreter that simulates parallel execution.

The Core Language

Although we used the 164 grammar and a modified version of the bytecode, our final language differs significantly from the 164 language. To simplify the project, we took away some features included in the 164 language. First, in order to build the dependency graph statically, we eliminated first class functions and lambdas from the language. Therefore, while the 164 language implements if statements and while loops as lambdas, we implement them as separate bytecode instructions. In addition, our language is fully functional, meaning that every variable a function refers to must be passed as an argument. Finally, all mutable variables are passed by value. Lists are passed by reference since mutation of lists is not allowed.

We did not implement objects or structs.

Internal Representation

The program is converted into a dag which is sent to our interpreter. It would be better to have the compiler automatically insert thread operations into the program before final compilation, but for this project we think the representation of the program as a dag is sufficient. Our main goal was to effectively parallelize programs.

Compiler

Each program goes through two stages of compilation: the initial compilation into bytecode (based on the 164 bytecode) and the compilation into a dependency dag. The first compilation is nearly identical to the 164 compilation (except we modified the bytecode to include "def-func", "if-else" and "while" instructions). Compilation into the dag is more complicated and involves 5 dependencies:

1. Each read of a variable depends on the instruction that wrote to it last. We call this a W-R dependency.

2. Writes depend on writes because when we read a variable we want to make sure that we are reading the correct value.

3. A write depends on all previous reads because we want the read of the variable to occur before the write to the variable. Otherwise, we will read an incorrect value.

4. All commands (input/print) must be in order. If the user intends to print "1 2 3", we do not want the program to print "3 2 1". To do this, we look inside functions to see if a "print" or "input" statement is ever possible within the execution of that function. This involves doing a dfs from a print or input node in a function dependency graph to see if it is in the same connected component as the function. If it is, then the function is treated like a command.

We do a similar search to make sure all the functions that a function f may call are defined before f is called.

5. All instructions must precede the return instruction because we do not want the block of code to return before other instructions in the block have completed. For the following code, if the dag does not have the sink edge, then x cannot be guaranteed to be 1 when it is printed.

def x = 0
if (true) {
def y = 0
x = 1
y
}
print x



To create the graph, we walk down the bytecode and calculate the parents based on the bytecode we have already seen.

Interpreter

The interpreter traverses the dag in a random fashion and executes the instruction at each node while ensuring that each instruction gets executed after all its parent instructions have been executed. There is a limitation to our simulation, however. Since a function call is executed as a single instruction, the execution of two function bodies do not interleave, but they can be executed in a different order.

Measuring Parallelism

To measure the amount of parallelism this achieves, we take the ratio of the length of the longest path in this DAG from the sources to sinks to the number of bytecode operations in the program.

Debugging

We debugged our implementation by using GraphViz to visualize the DAG, and, of course, by running programs since the order of the instructions is randomized by the interpreter.