csci2041/public-class-repo/Labs/Lab_15_May_02.md

Lab 15: Parallel Evaluation

CSci 2041: Advanced Programming Principles, Spring 2017

Due: Friday, Mary 5 at 5:00pm. You may be able to complete this work during lab, but it may take a bit more time.

Lab goals.

In this lab you will get a chance to see how to generate parallel code based on the map and fold constructs we've studied in class.

This lab was developed by Nathan Ringo, who has been working in my (Eric's) lab and doing some interesting things with parallel programming in Cilk. Thanks Nathan!

Getting started.

Copy the file Lab_15.tar from the Labs directory in the public class repository into your individual repository. This file should be at the top level - next to all the feedback and assessment files.

Next, type

  tar xf Lab_15.tar

and this should create a Lab_15 directory in which you will do your work.

Next, type

   git add Lab_15

Now Git knows about all the files you'll need to turn in. You'll need to commit and push these later, of course.

Exploring the code.

You'll notice that there are a lot of files in this directory.

It is a working compiler for a small functional language. It includes specifications for a scanner and parser. It includes a definition of the source and target language as well as how to do some of the translation.

Examples

To get a feel for the source language, look at the *.src.txt files in the examples directory.

There you'll find a few programs in the source language. These consist of a sequence of functions (which may be no functions) and a final expression that is evaluated (often calling these functions).

You don't need to write any more example programs.

Run the translator.

Try running some examples. Return to the Lab_15 directory and type

   ./build.sh examples/arithmetic.src.txt

You should see OCaml build the translator, display and compile this program and show the result - which should be 7.

Try it also for funcs.src.txt and mapseq.src.txt.

Also, try fibseq.src.txt. Note how long this takes? When you implement parallel map this parallel version in fib.src.txt should execute faster.

The parallel map in map.src.txt and fib.src.txt and the fold in fold.src.txt are not yet implemented. So don't run these yet.

The source language

Next, navigate to the src directory and look at common.ml.

This file has definition of binary operators that is shared by both the source and target language. It also contains some functions for accessing the environment - but you shouldn't need to use these.

Next, look in the src_lang.ml file. This file defines the Src_lang module (as a file-based module).

Here you see the definition the program syntax, starting with program - indicating that a source language program is a list of functions (func) and an expression (expr).

Functions (func) consist of a name, then a list of parameters (each parameter has a name and a type) and then the expression that is the body of the function.

Expressions and types then follow. These should be mostly self explanatory, but few comments are worthwhile.

• Array creates an array from a list of values
• Call is a function call. Note that functions are just names, as strings.
• Fold takes just a function name and an expression that should be an array.
• Map will map the function (again just a name) across the array expression.
• MapSeq is a sequential version of map. Map will have to be translated into parallel code.

The remainder of the file does some type checking of the code. You need not read this.

The target language

Now take a look at tgt_lang.ml which defines the target language of this translator. Programs written in the source language (as defined in src_lang.md) are translated into the target language (as defined in tgt_lang.md).

The target language is similar to the source in that these programs are also a collection of functions followed by an expression.

(The target language is then translated to C and executed. This was visible when running the build.sh script.)

Expressions are similar but there are some interesting additions

• ArrayGet will access an array (the first expr) at some index (the second expr). Indexing begins at position 0, like in C.
• ArraySize returns the size of an array.
• Block lets statements be written as expressions. A Block expression contains a list of statements that are executed. These are followed by an expression. This expression is then evaluated and the value of this expression is returned as the value of the Block expression.
• Call function calls are the same as before
• Spawn will spawn the evaluation of an expression. But the expression that a Spawn contains should be a Call expression.

Statements are also part of this target language.

• ArraySet is an assignment-like statement that sets the value of an array (the first expr) at an index position (the second expr) to be a new value (the third expr).
• Decl creates a new declaration of a variable using it name, type, and initializing value.
• A For loop declares a new integer index variable (its first string argument) that ranges from the value of the second expr up to 1 LESS THAN the third expr. This lets one write for loops that range over all indices of an array by counting from 0 to the size of the array. The body of the for loop is stmt list.
• Sync is the Cilk sync statement we discussed in class.
• Sleep will delay execution and might be useful in writing slow functions that will exhibit speedup when run in parallel. Without this, some functions are so fast that we don't notice any parallel speedup.

The translation

OK, you should now look at translate.ml. This defines the functions translate, translate_expr, translate_func and a few more.

Some simple cases

You need only worry about translate_expr and the incomplete definition of fold_helper.

First look over translate_expr. It does some type checking of the source language program and translates it to the target language.

The first case of the match translate array expressions. It does this by mapping the translate function over the list of expressions (arr) that are the value that go into the array.

Similarly, translations of BinOp binary operations like Add and Mul are simple too.

Translating Boolean values (Bool) and function calls are also simple.

There are other simple translations later in the file.

Sequential map.

The first interesting translation is for the sequential version map function. This code does some type checking and then at the end generates the Tgt_lang.Block construct that is the translation of MapSeq. This block declares the output array, followed by the for loop that sequentially walks down the array applying the function over array elements. The final expression is just a reference (Var "_map_array") that is the value returned.

Parallel map.

The first task you should complete it to implement the parallel version of the map. This is the Map construct.

It is suggested that you copy the translation for the sequential map and modify it by adding appropriate Spawn and Sync constructs.

When finished, return to the Lab_15 directory and run

   ./build.sh examples/map.src.txt

to run the parallel version of mapseq.src.txt

Note that there is no noticeable speedup since the work to be done is so small.

But you should see a difference between figseq.src.txt and the parallel fib.src.txt.

The fold construct

The next interesting translation is for Fold operations. Here the provided code does some type checking and translates to a function call to the fold_helper function that is defined (partially) at the top of this file. This is what we discussed in class last week. The fold_helper function should implement the parallel execution of a fold function.

There is nothing to do here. Instead you should complete the definition of fold_helper.

This will require some careful consideration. So think about this before you start programming. Ask yourself

• where will the result be stored?

• since there is no assignment statement, how can I use ArraySet to store a single value? Hint: create an array of size 1 and store a temporary result in it.

  To get started, an array of size 1 named out is already declared.

• what do the parameter start and end represent, exactly?

  what values of start and end indicate that the range contains only 1 item?

This part of the lab will be considered as extra credit worth about 1/2 of what a lab is worth.