| TDDC85 | Advanced parallell programming: Models, languages and algorithm, 7,5 ECTS credits. /Advanced parallell programming: Models, languages and algorithm/ |
|||
OBS! |
Only open for students admitted to the Computer Science Master programme |
|||
Prel. scheduled
hours: |
||||
|
Area of Education: Technology Subject area: Computer Science |
||||
| Advancement level
(G1, G2, A): A
|
||||
| Aim: The course emphasizes fundamental aspects of parallel programming such as parallel architectures and programming models, performance models, parallel complexity classes, parallel algorithmic paradigms, parallelization strategies, scheduling methods, and concepts of parallel programming languages. Practical exercises help to apply the theoretical concepts of the course to solve concrete problems in different parallel programming models. |
||||
| Prerequisites: (valid for students admitted to programmes within which the course is offered) Data structures and algorithms are absolutely required; knowledge in complexity theory and compiler construction is useful. Processprogramming and Parallel Programming are recommended. Programming in C is necessary for the practical exercises. Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshhold requirements for progression within the programme, or corresponding. |
||||
| Organisation: Lectures (usually 2 intensive weeks in february / early march), programming exercises, optional theoretical exercises for self-assessment. |
||||
| Course contents: I. General introduction: Parallel computer architectures (*). II. Basic theory of parallel computation: PRAM model. Time, work, cost. NC. Speedup and Amdahl's Law (*), Self-simulation and Brent's Theorem, Scalability and Gustafssons Law (*). Fundamental PRAM algorithms (reduction, parallel prefix, list ranking). PRAM variants, simulation results and separation theorems. III. PRAM emulations on distributed-memory architectures: Hashed address space, Pipelining and Multithreading. Ranade's massively parallel realization in hardware. IV. Message passing models: Delay model, of McColl, LogP, LogGP. V. Distributed shared memory realizations DSM emulations. Memory consistency models. VI. Concepts of parallel programming languages covering e.g. Fork, BSPlib, MPI (*), OpenMP Linda, ... VII. Parallel algorithmic paradigms and programming problems: Parallel loops, static and dynamic Parallel divide-and-conquer, recursive doubling. asynchronous computations and parallel Synchronous and asynchronous pipelining. parallelism. VIII. Generic parallel programming with environments. Parallel program composition. IX. Compiling for parallel computers: Dependence parallelization, idiom recognition. Speculative X. Optimization of data layout. XI. Clustering and scheduling of tasks. XII. Advanced issues as time permits. |
||||
| Course literature: Keller, Kessler, Träff: Practical PRAM Programming. Wiley Interscience, 2000. ISBN 0-471-35351-5. |
||||
| Examination: | ||||
| Written examination Programming exercise Fork Programming exercise MPI |
3 p 1 p 1 p |
/ / / |
4,5 ECTS 1,5 ECTS 1,5 ECTS |
|
| Grades are given as â?TFailâ?T or â?TPassâ?T. | ||||
Course language is English. Department offering the course: IDA. Director of Studies: Examiner: Course Syllabus in Swedish |
||||
|
|
 |
|||||
| ||||||