Shared Memory Workshop   

0368-3500-07/08

Winter Semester סמסטר א תשס"ו 2005

Classes: Sunday, Dan David  118, 15:00-17:00

Basic Requirements from all projects:

•   Well documented and usable:

All project must

·         be usable by others after you finish it and after you have left the university.  The code should be well documented and explained with accompanying documents.

·         A PRD, (Product Requirement Document) in which you define the project, from very high level goals and specification to more detailed explanation of inputs, outputs, output windows (if graphics is involved) and expected behavior under different conditions and inputs.

• Schedule:

·         Nov 29:  First version of the PRD is due November 29.

·         Dec 13:  Detailed project Design Document is due.

·         Dec 27:  Begin implementation.

·         Jan 24:  Presentation of first version of the project. 

·         March 6:  Final project ready.

·         March 21: Projects are submitted after all corrections, bug fixes.

•    Presentation:  Projects must have convenient and easy to use presentation of the results, usually with graphical presentation (when ever appropriate).  If necessary the project will have other easy to use outputs.  Think of the users that will have to use the project.

• Groups:  Projects may be done in groups of 2 or 3 students. 

• Programming Language:   Preferably projects will be written in the C programming language.

Suggested Project

Simulation and performance measurements of multi processor shared memory algorithms

In this project you have to write lock-free multi-threaded programs for one of the following data structures and to evaluate their performances on a 4 processor Sun machine.  (or other architectures as will be discussed in class)  The data structure is one of the following: 

Hash table with link lists,

FIFO Queue,

Priority queue.  

Look at http://www.cs.tau.ac.il/~shanir/multiprocessor-synch-2003/ for more details on multi threaded programming.  For programming the Sun machine look here. 

What you have to learn and cope with:

1. Understanding POSIX threads e.g., here.

2. Creating threads, setting their attributes properly, setting the scheduling type.

3. Synchronizing threads to start simultaneously at the same time.

4. Timing the threads, measuring their execution time.

5. Sometimes it's necessary to bind threads to processors.

6. Generating statistics without impacting the execution - by using thread local storage.

7. Using random numbers (not calling rand()).

8. Writing benchmark scripts and analyzing the results, optimizing the parameters