240 lines
8.7 KiB
Markdown
240 lines
8.7 KiB
Markdown
# 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.
|