Design and Analysis of Parallel Algorithms, 7.5 Credits

Contents

Part 1, theory, 4.5 credits
The course covers design, analysis, implementation and evaluation of algorithms for scalable architectures, and basic communication operations; Methods of problem-partitioning (eg blocking of 2-dimensional data structures), performance measures for the analysis of cost and scalability; Fundamental parallel algorithms for numeric and non-numerical problems in basic linear algebra for dense and sparse matrices (matrix multiplication, transpose, and direct and iterative methods for solving systems of linear equations), a number of the most common sorting algorithms, graph theory (minimum spanning tree, shortest path, transitive closure, connected components and algorithms for sparse graphs), search in discrete optimization (depth-first, best-first, and relevant algorithms for dynamic load balancing and termination detection), dynamic programming (monadic and polyadic problems, such as shortest path and the knappack problem) and fast Fourier transforms (FFTs).

Part 2, laboratory, 3 credits
In the laboratory part some of the theories and techniques discussed in the theoretical part are put into practice. This part consists of a series of mandatory laboratory assignments.

Expected learning outcomes

After having completed the course the student will be able to:

• Explain and derive the complexity of algorithms for basic and collective communication operations
• Apply different methods and performance measures to analyze algorithms with respect to cost and scalability, including using the so-called iso-efficiency function.
• Describe the basic methods of problem and data partitioning for efficient memory utilization and minimization of communication costs in parallel computers, such as recursive blocked and tiled algorithms for dense matrices and hybrid data layouts.
• Perform design and analysis of parallel algorithms in some of the fields mentioned under contents
• Use and be familiar with standard software in numerical linear algebra such as BLAS, LAPACK, and ScaLAPACK

Required Knowledge

Univ:To be addmitted you must have 60-ECTS-credits in Computing Science or 2 years of completed studies, in both cases including Scientific Computing (5DV005) and Parallel Computer Systems (5DV011) or equivalent.
Proficiency in English equivalent to Swedish upper secondary course English A (IELTS (Academic) with a minimum overall score of 5.5 and no individual score below 5.0. TOEFL PBT (Paper-based Test) with a minimum total score of 530 and a minimum TWE score of 4. TOEFL iBT (Internet-based Test) with a minimum total score of 72 and a minimum score of 17 on the Writing Section).
Where the language of instruction is Swedish, applicants must prove proficiency in Swedish to the level required for basic eligibility for higher studies.

Form of instruction

Education consists of lectures and mandatory computer based assignments. In addition to scheduled activities, individual work with the material is also required.

Examination modes

The examination consists of a written exam in Part 1 and by grading the mandatory computer-based assignments in Part 2. In Part 1, the grades given are Fail (U), Pass (3), Pass with Mark (4), or Pass with Distinction (5). In Part 2 the grades given are Fail (U) or Pass (G). On the course as a whole, the grades given are Fail (U), Pass (3), Pass with Mark (4), or Pass with Distinction (5). In order to pass the course completely all mandatory parts must be passed as well. The final grade of the course is a summary assessment of the results and decided only after all mandatory parts are passed.  A student who has passed an examination may not be re-examined.

For all students who do not pass the regular examination there are additional opportunities to do the examination. A student who has taken two tests for a course or segment of a course, without passing, has the right to have another examiner appointed, unless there exist special reasons (Higher Education Ordinance Chapter 6, section 22). Requests for new examiners are made to the head of the Department of Computing Science.

Other regulations

Transfer of credits
This course may not be used towards a degree, in whole or in part, simultaneously with another course of similar content. If in doubt, consult the student counselors at the Department of Computing Science and / or program director of your program.

Transfer of credits is considered individually (see the University Code of Rules and regulations for transfer of credits). An application for transfer of credits is made on a special form and should be submitted to the Faculty of Science and Technology, Umeå University.