DidaWiki

The final SPM project is structured in 5 different alternatives. Students should agree which one they want to choose with the Professor before actually starting to implement the project.

Game of Life has already been assigned as a kind of mid term homework to be implemented using low level threading mechanisms. The first alternative project consists in implementing a game of life application working on differently sized matrixes with one of the existing structured parallel programming frameworks discussed within the course (FastFlow or Skandium) and in comparing the results achieved with the thread and framework based versions in terms of performance.

StreamCluster is an application computing a clustering algorithm over data coming from an input stream. Data clustering is used in a variety of different applications and basically consists in grouping the incoming data in such a way all belong to a given cluster (group of data) with a given centroid item.

We will consider here the application already provided in the parsec benchmark suite (see the Parsec web site). The application is provided as C source code. Different parallelisations of the code exist (e.g. using TBB in parsec, or OpenMP and Cuda in the Rodinia benchmark suite). The student must develop a parallel version of the application using FastFlow.

N-queens is the well known problem of placing n queens on an n by n chess board in such a way there is no pair of queens on the same column, on the same row or on the same diagonal. Two versions of the program must be developed:

• one only using low level mechanisms (e.g. threads or processes) and one using one the structured parallel programming frameworks discussed in the course (FastFlow or Skandium).

Micro-mdf is a minimalist parallel programming framework supporting execution of macro data flow graphs. In particular, it must support the following features:

• data flow instructions with instruction and graph id, pointer to the function to be computed, input token and output destination placeholders and a missing input token counter
• a graph repository, suitable to host several graphs of data flow instructions
• a streamer, generating a type stream of tokens directed to the first instruction of some data flow graph, and instantiating in the graph repository a new copy (with a new graph id) of a data flow graph with the token properly assigned to the graph first instruction
• a drainer, processing each final token, i.e. each token produced while executing the graph in the graph repository with special destination output
• an interpreter looking for the fireable instruction in the graph repository and processing them up to the point no other fireable instructions are present and the streamer already terminated its operation.

Students are encourage to propose and discuss with the professor different alternatives, possibly individuated because of personal interests, subjects already tackled in other courses etc.

In order to be considered valid alternatives:

• either the alternative consist in parallelizing and existing and well known application/kernel/algorithm by means of one of the structured parallel programming frameworks discussed in the course
• or the alternative consist in implementing a new (alternative) pattern using either the low level mechanisms discussed in the initial part of the course or integrating the new pattern in one

of the existing frameworks.

We will take into account the following possibilities:

Alternative implementation frameworks may be taken into account in some cases (including OpenMP, MPI, CUDA, OpenCL, scripting languages) depending on the student knowledge and to be agreed with the professor.

A valid project is the result of the execution of an ordered set of steps:

1. the student must agree the subject with the professor, and the pairing student-project has to be published on the project assignment table (agreement should go through an email to the professor with subject “SPM project”)
2. the project design has to be completed and agreed again with the professor
3. the project implementation has to be completed, debugged and validated
4. the project (source code, sample input files and report describing what has been actually produced) has to be submitted by one of the exam terms via email to professor email account
5. the project has be demonstrated (on a text terminal) and discussed with the professor

Project code should be delivered to the professor email account as a compressed archive (.zip or .tar.gz)

The project report is a PDF document of no more than 10 pages explaining:

• what has actually been implemented in the project
• possible major design choices
• a short manual detailing how the project may be compiled and tested from the sources
• experimental results validating design and performances

More in detail:

• experiment results should show scalability, speedup and efficiency of the implementation(s) as well as the difference among the measured values and the expected ones (according to the performance models)
• the short user manual should be detailed enough to enable me to run tests with your software (what should I compile, how, which are the parameters to use to launch experiments, how can I vary parallelism degree, which input files do I need, where are they)
• the major design choices should be exposed at high level of abstraction, mentioning the patterns used, the policies adopted, if the case, particular algorithms or data types used, etc. It is not required to specify the known parts of the assignments (e.g. I don't want to see space wasted to explain GOL rules or NQ problem description)
• at the very beginning, please state clearly in a single sentence the problem solved, the programming framework(s) used, their version (if significant) and the architecture(s) used to run the experiments.

This project is valid for all the exam terms in A.Y. 2015/2016.