2019/2020 - Паралелно програмиране (Софтуерно инженерство)

Анотация

Целта на учебната дисциплина е придобиване на теоретични знания и практически умения в областта на паралелното програмиране. Това включва – съвременни паралелни изчислителни архитектури (CPU, GPGPU и др.), йерархия на паметта и архитектури на паметта на паралелните компютри (споделена, разпределена и разпределена-споделена памет; UMA, NUMA, COMA и др.), различни видове паралелизъм (ILP, Data paralelism, SMT, SpMT, Preemptive и Cooperative многозадачност, нишки, задачи и др.), и др. Разглеждат се някои важни теоретични аспекти на паралелните алгоритми, техният анализ, даннови и контролни зависимости, възможни проблеми (мъртва хватка, жива хватка, трудна скалируемост, глад за ресурси, съперничество и др.). Разгледани са също и подходи за дизайн и анализ на паралелни програми (Шаблони, Fork-Join, Map-Reduce, Неблокиращи алгоритми и структури данни и др.). Лекциите включват множество примери и дават някои основни сведения за езиците, библиотеките и API за паралелно програмиране (например Boost.Thread, Cilk, CUDA, C++ AMP, MPI, OpenMP, OpenCL, OpenHMPP, OpenACC, PLINQ, TBB и др.).

Упражненията са проектно базирани и дават възможност на студентите да се запознаят с практическите проблеми и начините им на решаване чрез средствата на паралелното програмиране.

КОНСПЕКТ

Изисквания към проекта

Всеки студент трябва да разработи проект по Паралелно програмиране. Проекта представлява преработка на съществуващ "непаралелен" (примерен) проект до проект използващ различни техники от паралелното програмиране. Всеки може да избере една от следните задачи с различна степен на сложност:

  1. Умножение на две големи матрици (0-20 точки);
  2. Визуализация на 3D сцени с помощта на Ray-tracing (0-40 точки);

Вие можете да:

  • използвате произволен език за програмиране;
  • използвате произволна среда за разработка;
  • използвате произволна операционната система;
  • използвате произволни методи и библиотеки за паралелно програмиране;
  • използвате примерните проекти (дадени в помощните материали), като основа за създаване на собствен проект или като пример за непаралелна реализация на съответната задача;
  • обсъждате проблема, изискванията и материалите с всеки;

Вие НЕ можете да:

  • използвате проекти (или части от тях) създадени от други лица за целите на този курс, включително създадени в предишни учебни години;
  • използвате проекти (или части от тях) създадени от други лица за сходни цели;
  • използвате код, който не сте реализирали собственоръчно (с изключение на код от примерните проекти);

Критерии за оценяване

Оценката на проект се формира по формулата: (20 + Брой точки)/10. Закръглява се до цяла оценка (по общоприетите правила). Оценката се получава на практическата част от изпита при представен проект. Всеки който получи 3.00 или повече на практическата част има право да се яви на теоретичната част на изпита (тест носещ общо до 40 точки). Оценката от теория се формира по същата формула, както тази от практическата част. Крайната оценка от изпита се формира като средно аритметично от двете оценки (практическа и от теория). Ако една от оценките е слаб, то студента трябва да се явяви на поправка.

Работа през семестъра и предаване на проекта

Всеки судент е длъжен да работи по проекта си през семестъра. Работата задължително става с използването на SVN сървъра на ФМИ (повече информация за достъпа и начина на използването на тази система за контрол на версиите вижте сайта на сървъра тук). Всеки студент ще получи име и парола за достъп до своето SVN хранилище (repository) на първото упражнение.

Очаква се в хранилището да бъдат качени всички съществени промени от началото на развитие на проекта до окончателното му завършване. Всеки решава дали да изпраща промените (commit) си в сървъра по-често или по-рядко, но задължително по всеки проект трябва да има поне 4 commit-а в течение на семестъра: В началото при съзадване на празен проект (или съответния стартов проект от помощните материали, ако такъв ще бъде използван), през 5-та седмица на триместъра, през 8-ма седмица и 10-та седмица (за задочно обучение пропорционално от първото занятие до деня преди изпита). Състоянието на проекта в тези версии може да окаже влияние върху общия брой на точките, които ще получите. От 10-та седмица до изпита всеки може да продължи работата си по проекта и съответно да продължава да качва промени в хранилището.

Очаква се проекта да се намира в подпапка trunk/PPProject на SVN хранилището. Той трябва да е във вид готов за сваляне и компилация. Проекти не отговарящи на това изискване няма да бъдат проверявани и оценявани.

Проектите подлежат и ще бъдат проверявани автоматично и ръчно. Автоматичната проверка включва (но не се ограничава само до) използване на системи за автоматизирана проверка за плагиатство (т.е. преписване от ваши колеги и/или от чужди проекти в Интернет). Ръчната проверка представлява преглед и експерементиране с проекта от страна на преподавател. При установяване на плагиатство или съмнение за такова точките на съответните студенти ще бъдат драстично намалени (пропорционално на процента на "взаимстваните" части от код), в допълнение на това ще бъде публикуван списък с провинилите се студенти, както и ще се вземат всички други мерки в съответствие с Регламента за реакция при нечестни прояви.

Литература

  • Peter Pacheco, An Introduction to Parallel Programming, Morgan Kaufmann, 2011, 392 pages, ISBN: 0-123-74260-9.
  • Victor Pankratius, Ali-Reza Adl-Tabatabai, Walter Tichy, Fundamentals of Multicore Software Development, CRC Press, 2011, 330 pages, ISBN 1-439-81273-X.
  • David B. Kirk, Wen-mei W. Hwu, Programming Massively Parallel Processors: A Hands-on Approach (Third Edition), Morgan Kaufmann, 2016, 576 pages, ISBN: 0-128-11986-1.
  • Brian Goetz, Java Concurrency in Practice, Addison-Wesley Professional, 2006, 432 pages, ISBN: 0-321-34960-1.
  • Thomas Rauber, Gudula Rünger, Parallel Programming: for Multicore and Cluster Systems (Second Edition), Springer, 2013, ISBN: 3-642-43806-7.
  • Bertil Schmidt, Jorge Gonzalez-Dominguez, Christian Hundt, Moritz Schlarb, Parallel Programming: Concepts and Practice, Morgan Kaufmann, 2017, ISBN: 0-128-49890-0.
  • Duane Storti, Mete Yurtoglu, CUDA for Engineers: An Introduction to High-Performance Parallel Computing, Addison-Wesley Professional, 2015, 352 pages, ISBN: 0-134-17741-X.
  • Michael McCool, James Reinders, Arch Robison, Structured Parallel Programming: Patterns for Efficient Computation, Morgan Kaufmann, 2012, 432 pages, ISBN: 0-124-15993-1.
  • Mihcael J. Quinn, Parallel programming in C with MPI and OpenMP, McGraw Hill Education, 2017, 544 pages, ISBN: 0-070-58201-7.
  • ED. Pavan Balaji, Programming Models for Parallel Computing (Scientific and Engineering Computation), The MIT Press, 2015, 488 pages, ISBN: 0-262-52881-9.
  • Stephen Cleary, Concurrency in C# Cookbook: Asynchronous, Parallel, and Multithreaded Programming, O'Reilly Media, 2014, 208 pages, ISBN: 1-449-36756-9.
  • Riccardo Terrell, Concurrency in .NET: Modern patterns of concurrent and parallel programming, Manning Publications, 2018, 568 pages, ISBN: 978-1617292996.
  • и други.

Помощни материали