Paralelní algoritmy (B4M35PAG), Parallel Algorithms (BE4M35PAG)

Quick links: Seminars, Upload system, Forum, Lecture and Seminar Rooms, Schedule, Academic year time-line.

Why parallel algorithms?

News

Summary

In the introductory lectures, we will focus on general approaches to design of parallel algorithms and their properties important for understanding the fundamental principles of parallel and distributed algorithms. Subsequently, we will talk about fundamental parallel algorithms; typically constituting cornerstones of algorithms for real-world problems. The laboratory exercises will be aimed at hardware platform commonly used in practice (multi-core CPUs, Xeon Phi, …).

Prerequisities

The course requires programming skills in C/C++ and good fundamentals algorithms development.

Lectures

č.	Název přednášky	Materiály
1	Introduction to Parallel Computing	Chapter 2
2	Principles of Parallel Algorithms Design	Chapter 3
3	Basic Communication Operations	Chapter 4
4	Analytical Modeling of Parallel Algorithms	Chapter 5
5	Sorting	Chapter 9, bitonic.cpp.txt
6	Matrix Algorithms	Chapter 8
7	Algorithms for Linear Algebra, TEST	Chapter 8
8	Parallel Accelerators	Parallel Accelerators
9	Graph Algorithms I.	Chapter 10
10	Graph Algorithms II.	Chapter 10
11	Combinatorial Algorithms	Chapter 11
12	Dynamic Programming	Chapter 12
13	Fast Fourier Transform	Chapter 13

There will be a test at lecture #7. The test starts at the beginning of the lecture and takes approximately 30 minutes. It focuses on knowledge from the lectures and seminars already taught. The test is optional and there will not be any extra one.

Clasification and Exam

In this subject, we use points for classification. The points can be awarded as follows:

You can get 21 points for homework assignments (3 assignments, 7 points each)
For semestral work you can get up to 14 points.
Up to 10 points can be gain from the test at the lecture (test is optional)
For the written exam, you can get 45 points.
The oral exam can give you 10 points.

To obtain the assessment (“zápočet” in Czech), it is necessary to get at least 25 points for homework, semestral work and the test at the lecture.

A mandatory condition for obtaining a better grade than “F” is to gain at least 20 points for the written exam. The oral exam is compulsory and the final grade is given by the following table:

points	[0,50)	[50,60)	[60,70)	[70,80)	[80,90)	[90,100]
grade	F	E	D	C	B	A

For the written and oral exam, you will need a pen and few sheets of paper. The exam tests both the knowledge from lectures and seminars.

Literatura

[1] Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar: Introduction to Parallel Computing, Second Edition, Addison Wesley, 2003.

[2] Georg Hager, Gerhard Wellein: Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2011.

[3] James Reinders, Jim Jeffers: Intel Xeon Phi Coprocessor High-Performance Programming, Newnes, 2013.

Table of Contents