For this assignment, you must use a version control system such as Git or SVN and submit the log file that describes the activity on your repository. We will provide you with an SVN repository hosted by CSUG. Note: if you use Git, you should not host your code on a public repository such as GitHub, as making your code available to others in the class could consitute a violation of academic integrity.
For information on how to get started with SVN there, read
Using
Subversion in the CSUGLab. The repository we allocate for you will
be named cs3110_<netid(s)>. For example,
cs3110_jnf27 or if you have a
partner cs3110_dck10_jnf27 (note that the NetIDs are in
alphabetical order). This repository name is what you should use in
place of project1 in the directions in the link provided
above.
If you use Windows and are unfamiliar with the command line or
Cygwin, there is a graphical SVN client called
Tortoise SVN which
provides convenient context menu access to repositories. If you use
Linux, there is a graphical SVN client called
Rapid SVN. To install it, type
apt-get install rapidsvn from the command prompt. OS X
users can try SC Plugin,
which provides similar functionality to Tortoise. Rapid SVN may also
work depending on your setup. Finally , there is an Eclipse plug-in
called Subclipse that
provides nice integration with SVN repositories. Note that all of
these graphical tools are only alternatives to the powerful
command-line tools, and are not necessary to use version control
effectively.
You will have a lot of flexibility including selecting appropriate data structures, modules, and algorithms to implement your solutions to this problem set. To help you check that you are on the right track, we will hold brief (15-minute) design review meetings. You must schedule a time to meet with a member of the course staff on or before April 5th using the schedule which will be available on CMS. During your meeting, you should explain your design in about 10 minutes, leaving 5 minutes for us to ask you questions. It is a good idea to practice your presentation ahead of time so you can use your time effectively. Please come prepared to describe:
A sequence is an ordered collection of elements. OCaml's
built-in list type is one representation of sequences. In
this problem, you will develop another representation for sequences
that support a number of parallel operations. For example,
the map function will apply a function to all the
elements of the sequence in parallel.
The following table summarizes the most important operations in the sequence module. The work and span columns are described below. The only special case if flatten -- you may use any correct, functional implementation without worrying about the work/span complexity.
| Function | Work | Span | Notes |
|---|---|---|---|
| length | O(1) | O(1) | |
| empty | O(1) | O(1) | |
| cons | O(n) | O(1) | Second argument has length n. |
| singleton | O(1) | O(1) | |
| append | O(n+m) | O(1) | Arguments have length n and m. |
| tabulate | O(n) | O(1) | Argument has length n. |
| nth | O(1) | O(1) | |
| filter | O(n) | O(log n) | Argument has length n. |
| map | O(n) | O(1) | Argument has length n. |
| reduce | O(n) | O(log n) | Argument has length n. |
| repeat | O(n) | O(1) | Second argument is n. |
| flatten | -- | -- | Sum of lengths of lists contained in argument is n. |
| zip | O(min(n,m)) | O(1) | Arguments have length n and m. |
| split | O(n) | O(1) | Argument has length n. |
The work column in the table above captures the total amount
of work done in executing each function on an idealized parallel
machine. The span column captures the length of the longest
path of any execution of any sub-task. To illustrate, Consider the the
familiar map function applied to arguments f
and x1,x2,...,xn. If each invocation of f
can be executed in parallel, the overall execution can be depicted by
the following diagram:
.
/ | \
/ | \
(f x1) (f x2) ... (f xn)
\ | /
\ | /
.
The top dot represents the intial task, which spawns n
sub-tasks that apply f to an element of the sequence and then
complete. The total work performed by map is O(n),
but the span is O(1), since the length of any path in this
graph is bounded by a constant.
You may assume that
let multi_create (f:int -> unit) (n:int) : Thread.t array =
let a = Array.make n (Thread.self ()) in
for i=0 to n-1 do
a.(i) <- Thread.create f i;
done;
a
let multi_join (a:Thread.t array) : unit =
Array.iter Thread.join a
For experts: Array.make is actually performing two tasks: allocation and initialization. Allocation can indeed be peformed in (amortized) constant time. Initialization requires a linear scan in general, but we will ignore that in this problem. For multi_create and multi_join, one can imagine a parallel machine where initializing a thread of execution running the same function on each of its processing units can be done in constant time. Our multi_create lets you do exactly this.
Your task is to build an implementation of sequences that have the
work and span listed above. We have provided a complete interface in
the sequence.mli as well as a reference implementation
based on lists in sequence.ml. This implementation is
only meant to be a guide — it does not have the time
complexities described above, but may be useful for debugging.
To submit: sequence.ml.
The following applications are designed to test out your sequence implementation and illustrate the "Map-Reduce" style of computation.
An inverted
index is a mapping from words to the documents in which they
appear. For example, if we started with the following documents:
Document 1:
OCaml map reduce
fold filter ocamlThe inverted index would look like this:
| word | document |
|---|---|
| ocaml | 1 2 |
| map | 1 |
| reduce | 1 |
| fold | 2 |
| filter | 2 |
To implement this application, you should take a dataset of documents (such
as data/reuters.txt) as input and use the map and reduce operations
to produce an inverted index. Complete the mkindex function
in apps/inverted_index.ml. This function should
accept the name of a data file and print the index to screen. You can print the
final result using Util.print_reduce_results.
For the next application, you will implement apm, a
simple dating service. The files data/profiles.txt
(long) and data/test_profiles.txt (shorter) contain some
randomly generated profiles of fictional people seeking partners for a
romantic relationship in the files. The type of a profile
is Apm.profile. We have supplied code
in apm.ml for parsing data files and printing results to
the console. You must write the matchme function.
This function takes several arguments as a string array: the app name, the data
file, the number of matches requested, and the first and last name of the
client, who should have a profile in the data file. The map step should pair
the client's profile with every other profile in the database and test the match
between them. For each pair, compute a compatibility index, which is
a float between 0. (perfectly incompatible) and 1. (perfectly
compatible). We leave the details of this computation up to you. Please include
comments as to your reasoning; be respectful and don't get too carried away.
The reduce step should use the compatibility index and the corresponding pairs
to create the desired number of matches. The results should then be printed out
the using the supplied print_matches
function. The Util module has some functions for reading in files
and manipulating strings that may be useful.
Here is a sample run of apm using our solution.
------------------------------ Client: Jeremiah Sanford sex: M age: 23 profession: trucker nondrinker nonsmoker has children does not want children prefers a female partner between the ages of 19 and 29 likes classical music and sports 2 best matches: ------------------------------ Compatibility index: 0.691358 Katy Allen sex: F age: 21 profession: trucker nondrinker nonsmoker no children does not want children prefers a male partner between the ages of 18 and 24 likes country music and sports ------------------------------ Compatibility index: 0.691358 Corina Savage sex: F age: 24 profession: trucker nondrinker nonsmoker no children does not want children prefers a male partner between the ages of 18 and 32 likes country music and sports
Complete the matchme and mkindex functions making use
of the parallel map and reduce functionality provided by your Sequence
implementation. You may use your own metric for calculating match
compatibility.
You have also been provide with a Makefile and a buildTopLevel script that will compile the apps into an executable for testing. For example to run the inverted index, run make (on Unix) or build the top level (on Windows) and then run:
./main_apps mkindex data/test1.txtand for A Perfect Match run
./main_apps matchme data/profiles.txt 5 John Doe
Replace main_apps with main_apps.exe for Windows.
DO NOT change any code already provided to you (especially the parsing functions in apm.ml). Make sure you place any additional functions you write in your submission files.
To submit: apm.ml and inverted_index.ml.
An n-body simulation models the movement of objects in space due to the gravitational forces acting between them. There is a straightforward O(n^2) algorithm that computes the movement of each object by calculating the interactions with every other object. Your task in this problem will be to implement a more efficient algorithm that approximates an n-body simulation. Your solution will build on the code for parallel sequences developed in Part 3.
In an n-body simulation, we are given a collection of n objects or bodies, each possessing a mass, location, and velocity. The goal of the simulation is to compute, for each time step, the new positions and velocities for each body based on the gravitational forces acting on each.
Assume that we have a module Plane that defines
representations for scalar values, two-dimensional points, vectors,
and common functions such as Euclidean distance (implementing such a
module will be a part of this problem). Using Plane, we
can define a type that represent the mass, position, and velocity of a
body,
type mass = Plane.scalar type location = Plane.point type velocity = Plane.vector type body = mass * location * velocityand a function
acc that calculates the acceleration of
one body on another:
val acceleration : body -> body -> Plane.vector
To understand how the acceleration function works, we need to
review a few basic facts from physics. Recall that force is equal to
mass times acceleration (F = m × a) and the gravitational
force between objects with masses m and n separated by
distance d is given by (G × m × n) / d²
where G is the gravitational constant. Putting these two
equations together, and solving for a, we have that the
magnitude of the acceleration vector due to gravity for the object
with mass n is G × m / d²; the direction of
the acceleration vector is the same as the direction of the unit
vector between the objects. Note that this calculation assumes that
the objects do not collide. We will make this simplifying assumption
throughout this problem.
Using acceleration and the functions from
the Sequence module, we can then define a
function accelerations that computes the accelerations on
each of the bodies in the simulation:
val accelerations : body Sequence.t -> Plane.vector Sequence.tFinally, we update the position p and velocity v of each body to p + v + a/2 and v + a respectively, where a is the
Plane.vector in the sequence
returned by accelerations.
make_simulation that creates a
stream to represent a simulation. We will use the following datatype
(which is essentially a lazy list) to represent streams :
type 'a stream = Nil | Cons of 'a * (unit -> 'a stream)The helper functions we have provided for running simulations (discussed next) will access these streams and give you a way to test your code on simple examples.
We have provided several modules, helper functions, test cases, and a
graphical interface that may be useful while developing your
solution. The function run_simulation
in Main_nbody can be used to generate "transcripts" of
simulations. The module Test_nbody defines the initial
values for several simulations. The Java
application bouncy.jar (depicted in the image above) can
be used to animate a simulations using a transcript.
Your task for the first part of this problem is to implement the
naive n-body algorithm. In particular, you will need to
implement plane.ml and fill in the missing functions
in naive_nbody.ml.
To submit: plane.ml and naive_nbody.ml.
The Barnes-Hut algorithm provides a way to approximate an n-body simulation, while dramatically decreasing its cost. The insight behind the algorithm is that the gravitational forces between objects separated by large distances are weak, so they can be approximated without affecting the fidelity of the overall simulation very much.
The algorithm works by grouping bodies into regions and
using a fixed threshold θ to determine if it should perform the
exact acceleration calculation for the each body in the
region, or if it should merely approximate acceleration
using a pseudobody that represents aggregate information about
all of the bodies contained in the region. This dramatically reduces
the time needed to perform large simulations — asymptotically,
from O(n^2) to O(n log n).
To represent regions, we will use bounding boxes comprising two points:
type bbox = {north_west:Plane.point; south_east:Plane.point}
To represent the decomposition of a collection of bodies into regions,
we will use the following datatype:
type bhtree =
Empty
| Single of body
| Cell of body * bbox * (bhtree Sequence.t)
Intuitively, Empty represents a region with no
bodies; Single(b) represents a region with a single
body b; and Cell(b,bb,qs) represents a
region with pseudobody b, bounding box bb,
and four sub-quadrants qs. The position of the pseudobody
in a Cell is the center of mass (or barycenter) of
all objects in the region. The mass of the pseudobody is the total
mass of all objects. The velocity of the pseudobody can be arbitrary,
as it is not needed for the acceleration calculation. In
your solution, you will likely have to write a function that
decomposes a sequence of n bodies into
a bhtree.
The actual Barnes-Hut simulation works as follows. For each
body b, the algorithm traverses the top-level
bhtree. If it encounters a region with more than one body
— i.e., a Cell node — it checks
whether θ ≥ m / d, where m is the total mass
of the pseudobody associated with the region, and d is the
distance between b and the pseudobody's center of mass. If so,
then it treats the entire region as if it were one large
pseudobody. Otherwise, it recursively performs the computation on the
sub-quadrants of the region. The base cases are the Empty
and Single(b) cases, where the algorithm simply invokes
the acceleration function as in the naive algorithm.
Your task for the second part of this problem is to implement the
Barnes-Hut algorithm. You will need to fill in the missing code
in barnes_hut_nbody.ml.
To submit: barnes_hut_nbody.ml.
This assignment is based on materials developed by Dan Licata (Carnegie Mellon University) and Professor David Bindel.