"Babes-Bolyai" University of Cluj-Napoca
Faculty of Mathematics and Computer Science

Design Methods for Parallel Algorithms
Code
Semes-
ter
Hours: C+S+L
Credits
Type
Section
MI097
7
2+0+2
6
optional
Informatică
MI097
7
2+0+2
6
optional
Matematică-Informatică
Teaching Staff in Charge
Lect. NICULESCU Virginia, Ph.D., vniculescu@cs.ubbcluj.ro
Aims
1. To know fundametal notions of parallel programming.
2. To know and use some formal methods for parallel programs development.
3. To implement parallel algorithms using MPI language and Java threads.
Content
This course covers theoretical foundations of parallel algorithms. The emphasis of this course is on the design and analysis of parallel algorithms.
Parallel algorithms are presented with emphasis on linear algebra applications, FFTs, graph, searching and sorting algorithms.

1. Fundamental notions about parallel programming:
- Parallel systems classifications
- Processors interconnection networks
- Parallel programs performance evaluation
2.General principles for parallel programs construction: methodical design, partitioning, communication, agglomeration, mapping.
3.A method based on imperative programming:
- Parameterized processes,
- Data distributions,
- Derivation from specifications.
4. Methods based on functional programming:
- Bird-Meertens Formalism,
- PowerList, ParList, PList theories.
Laboratory
Parallel programs development using:
- Java Threads,
- Message Passing Interface (MPI).
References
1. Ian Foster, Designing and Building Parallel Programs, Addison-Wesley 1995.
2. L.D. Loyens, A Design Method for Parallel Programs, PhD. Thesis, University of Eindhoven, 1992.
3. J. Kornerup. PList: Taking PowerLists Beyond Base Two. CMPP'98 First International WorkShop on Constructive Methods for Parallel Programming, MIP-9805, May 1998.
4. J. Misra. PowerList: A structure for parallel recursion.ACM Transactions on Programming Languages and Systems, 16(6):1737-1767, November 1994.
5. D. Skillicorn, Foundations of Parallel Programming, Cambridge International Series on Parallel Computations, 1994.
6. D.B. Skillicorn, D. Talia. Models and Languages for Parallel Computation. ACM Computer Surveys, 30(2) pg.123-136, June 1998.
7. V. Niculescu, Modele de elaborare a algoritmilor paraleli, PhD. Thesis, Univ. Babes-Bolyai, 2002.
Assessment
An average between the laboratory grade and the final exam grade.