====== Paralelní algoritmy (B4M35PAG), Parallel Algorithms (BE4M35PAG) ======
Lecturer: [[http://people.ciirc.cvut.cz/suchap| Přemysl Šůcha]]

Lab teachers: [[https://dce.fel.cvut.cz/ing-michal-bouska| Michal Bouška]]

Quick links: [[http://cw.felk.cvut.cz/upload/|UploadSystem]],
[[https://cw.felk.cvut.cz/forum/forum-1604.html|Forum]]



===== Why parallel algorithms? =====

{{pagmotivation.jpg}}

===== 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).

/*===== Restrictions 2020 =====
In accordance with Rector's Order No. 16/2020 (the coronavirus infection risk reduction), the subject will be taught online. Therefore, the primary platform for teaching is Microsoft Teams, specifically team "B201-B4M35PAG - Paralelni algoritmy / Parallel algorithms". Plan "B" is Zoom. In case of any problem with Teams, we will leave a link to the Zoom meeting on Teams. We apologize for any potential problems.
Lectures will be given live at the time specified by the timetable (channel Lectures). Labs are primarily meant as consultations supported by videos (channel Labs).*
===== Prerequisities =====

C/C++, basic Linux skills, algorithms

===== Lectures =====

^ No. ^ Title ^ Notes ^ Handouts ^
| 1 | Introduction to Parallel Computing | |{{:courses:pag:chap2_slides_selected.pdf| Chapter 2}} |
| 2 | Principles of Parallel Algorithms Design | |{{:courses:pag:chap3_slides_selected.pdf| Chapter 3}} |
| 3 | Basic Communication Operations | |{{:courses:pag:chap4_slides_selected.pdf| Chapter 4}} |
| 4 | Analytical Modeling of Parallel Algorithms | | {{:courses:pag:chap5_slides_selected.pdf| Chapter 5}} |
| 5 | Matrix Algorithms | | {{:courses:pag:chap8_slides_selected.pdf| Chapter 8}} |
| 6 | Algorithms for Linear Algebra | | {{:courses:pag:chap8_slides_selected.pdf| Chapter 8}} |
| 7 | Sorting | TEST | {{:courses:pag:chap9_slides_selected.pdf| Chapter 9}} |
| 8 | Parallel Accelerators | | {{:courses:pag:par_accelerators.pdf| Parallel Accelerators}} |
| 9 | Graph Algorithms I. | | {{:courses:pag:chap10_slides_selected.pdf| Chapter 10}} |
| 10 | Graph Algorithms  II. | | {{:courses:pag:chap10_slides_selected.pdf| Chapter 10}} |
| 11 | Combinatorial Algorithms | | {{:courses:pag:chap11_slides_selected.pdf| Chapter 11}} |
| 12 | Dynamic Programming | | {{:courses:pag:chap12_slides_selected.pdf| Chapter 12}} |
| 13 | Fast Fourier Transform | | {{:courses:pag:chap13_slides_selected.pdf| Chapter 13}} |



===== Grading and Exam =====

To get an ungraded assessment the following requirements have to be met:
  * obtain at least 25 from 45 points:
    * 21 points for homework assignments No. 1 to 3 (7 points per assignment)
    * 14 points for a semester project
    * 10  points for the Test
      * The test starts at the beginning of the lecture and takes approximately 30 minutes. It focuses on knowledge from the lectures and labs already taught.


To pass the exam it is necessary to get at least 20 points (maximum 45 points) from the written exam. The oral exam is mandatory and gives 10 points at maximum.

**Extension of deadlines (homework, semestral projects ...) is not possible!** The only exception is a serious health or family issue proven, for example, by a medical certificate. **We also do not award assessments (zápočety) in the examination period**. 

Final grading scale: 

^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 exams, you will need a pen and a few sheets of paper. The exam tests both the knowledge from lectures and seminars.

===== Literature =====

[1] Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar: [[http://www-users.cs.umn.edu/~karypis/parbook/|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.