Н с. лабораторії паралельних та розподілених обчислень Інституту кібернетики ім. В. М. Глушкова нан україни Всього годин 16 Лекційних 10 Практичних 2 Самостійна робота 4 Програма

Parallel Programming

Викладач: к.ф.-м.н. Ющенко Руслан Андрійович

с.н.с. лабораторії паралельних та розподілених обчислень

Інституту кібернетики ім. В. М. Глушкова НАН України

Всього годин – 16

Лекційних – 10

Практичних – 2

Самостійна робота – 4

Програма курсу
За основу спецкурсу взяті матеріали лекцій дисципліни «Паралельні обчислення» факультету інформатики Національного університету «Києво-Могилянська академія» [1]. Метою курсу є ознайомлення студентів з основними поняттями паралельних обчислювальних систем, а також методами паралельного програмування.

Проектування послідовних програм спирається на узагальнену архітектуру фон Неймана. Для паралельних програм не існує єдиної архітектури, більше того, такі архітектури постійно змінюються. Тому проектування та дослідження паралельних програм можна виконувати тільки спираючись на деяку архітектуру паралельного комп’ютера. Можна виділити три основних підходи паралельного програмування, пов’язані з певною архітектурою паралельних комп’ютерів:

1. Синхронізація в системах зі спільною пам’яттю («POSIX Thread» та «OpenMP»).

2. Обмін повідомленнями в системах з розподіленою пам’яттю («MPI»).

3. Асинхронне виконання на прискорювачі («kernel offload» в «CUDA» та «OpenCL»).

На перших двох заняттях спецкурсу розглядаються основні теоретичні передумови паралелізму, моделі паралельних комп’ютерів та методи дослідження ефективності паралельних алгоритмів і програм. З третього по шосте заняття розглядаються інструменти та технології паралельного програмування. Починаючи зі знайомства з проблемою доступу до спільних ресурсів та засобами синхронізації, на заняттях приділено увагу розгляду розповсюдженої технології програмування на паралельних комп’ютерах зі спільною пам’яттю «OpenMP» та технології програмування на великих комп’ютерах кластерної архітектури «MPI».

Джерелом лекційного матеріалу курсу є семінари та доповіді учасників проекту «ParLab» [2], паралельних обчислень в UC Berkeley, курс CS162 «Operating System Programming» [3]; курси NCSA University of Illinois «Multilevel Parallel Programming» [5], «Introduction to OpenMP» [6] та «Introduction to MPI» [7]; та власні конспекти з інших джерел.

Рекомендована література

Більш поглиблені знання можна отримати з наступних джерел

• 
  Blaise Barney «Introduction to Parallel Computing», Lawrence Livermore National Laboratory [8].
  
• 
  E. Minty, R. Davey, A.Simpson, D. Henty «Decomposing The Potentially Parallel».
  
• 
  Maurice Herlihy, Nir Shavit «The Art of Multiprocessor Programming».
  

Детальний перелік занять

День 1

1. 
   Паралелізм та паралельні комп’ютери
   
   1. 
      Паралельні комп’ютери, класифікації архітектур (Фліна та інші);
      
   2. 
      загальні властивості паралелізму поняття графу потоку даних;
      
   3. 
      формальні критерії коректності: поняття послідовної узгодженості, лінеарізованості;
      
   4. 
      приклади застосувань.
      

2. 
   Оцінка ефективності паралельних програм
   
   1. 
      Закони Амдала та Густавсона-Барсиса;
      
   2. 
      оцінка ефективності паралельних алгоритмів;
      
   3. 
      метрика Карпа-Флата;
      
   4. 
      оцінка досягнутої ефективності паралельних програм;
      
   5. 
      патерни паралельного програмування.
      

3. 
   Процеси, нитки, синхронізація
   
   1. 
      Процеси, потоки та нитки;
      
   2. 
      віртуальна пам’ять та ізоляція;
      
   3. 
      проблема доступу до спільних ресурсів;
      
   4. 
      атомарні операції та замки;
      
   5. 
      паралельні структури даних «lock-free».
      

4. 
   Синхронізація (продовження), OpenMP
   
   1. 
      Семафори та монітори;
      
   2. 
      патерни «виробник-споживач» та «читач-письменник»;
      
   3. 
      дедлоки, методи їх детекції та усунення;
      
   4. 
      основи OpenMP.
      

День 3

5. 
   Основи програмування на паралельних комп’ютерах з розподіленою пам’яттю
   
   1. 
      Основи інтерфейсу обміну повідомленнями (MPI);
      
   2. 
      огляд систем на основі черг повідомлень (Message Queues);
      
   3. 
      умови задачі акустичного моделювання, яку будемо розв’язувати на наступному занятті.
      

6. 
   Практичне заняття
   
   1. 
      Завдання полягає у розпаралеленні послідовної програми моделювання акустичних хвиль у двовимірному просторі
      (моделювання експерименту SOFAR Евінга і Бреховських);
      
   2. 
      для виконання завдання необхідно бути знайомими з мовами програмування «C» та/або «С++»;
      
   3. 
      використовуючи інструменти MPI та, можливо, OpenMP;
      
   4. 
      виконання експериментів на кластері «СКІТ-4».
      

1. 
   https://sites.google.com/site/parcomp2012/lectures
   
2. 
   https://parlab.eecs.berkeley.edu/
   
3. 
   https://www.youtube.com/playlist?list=PL-XXv-cvA_iBDyz-ba4yDskqMDY6A1w_c
   
4. 
   https://inst.eecs.berkeley.edu/~cs162/sp15/
   
5. 
   https://www.citutor.org/login.php?course=3
   
6. 
   https://www.citutor.org/login.php?course=24
   
7. 
   https://www.citutor.org/login.php?course=21
   
8. 
   https://computing.llnl.gov/tutorials/parallel_comp/
   
9. 
   https://computing.llnl.gov/tutorials/openMP/
   
10. 
    https://computing.llnl.gov/tutorials/mpi/