Design Methods for Parallel Algorithms |
ter |
|||||
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. |