Министерство образования и науки Российской Федерации
Московский физико-технический институт
(государственный университет)
УТВЕРЖДАЮ
Проректор по учебной работе
___________ Ю. А. Самарский
«___» _______________ 2011 г.
ПРОГРАММА
по курсу: теория и практика многопоточного программирования (базовый)
по направлению: 010600
факультеты: ФУПМ
кафедра: ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ ИНФОРМАТИКИ
курс: 3
семестр: 6 экзамен 6 семестр
лекции: 34 час.
ВСЕГО ЧАСОВ: 34
Программу составил: профессор, д.ф.-м.н., А.Г. Тормасов
Программа обсуждена
на заседании кафедры
теоретической и прикладной
информатики
11 мая 2011 г.
Заведующий кафедрой, А.Г. Тормасов
профессорПрограмма курса
Обзор содержания курса, цели, задачи. Использованные источники.
Оборудование и основные сведения о работе. Обзор стандартной архитектуры современных компьютеров. CPU, потоки исполнения, планирование исполнения и контекстные переключения, interconnect. Связность памяти и разные типы многопроцессорных систем (SMP, NUMA), ее влияние на работу программ. Кэши процессора разных типов и линии кэша (cache line), когерентность кэшей, MESI protocol (modified exclusive shared invalid). False sharing.
Система команд. Упорядоченность операций, видимость результатов операции, и неопределенность последовательности записи-чтения данных (relaxed memory consistency), ключ volatile. Атомарность операции, атомарное чтение и запись. Атомарные примитивы, используемые для организации процедур синхронизации.
Языки программирования и работа порожденного кода в условиях современных многопоточных систем с разделяемой памятью. Причины условий гонок (race conditions) и других проблем параллельного программирования с точки зрения оборудования. Модель программирования и синхронизации, встроенная в язык (Java, C). Потоки, «безопасность для исполнения в параллельных потоках», локальные объекты потока и др.
Некоторые понятия, используемые при разработке параллельных программ. Уровни абстракции, которыми мыслит программист, и корректность программ. Время, простые временные отметки и ограниченные во времени отметки времени. О вероятностях и ошибках.
Общие проблемы параллельного программирования. Проблемы, возникающие при работе с разделяемой памятью. Разделяемые объекты и синхронизация. Синхронизация выполнения кода и синхронизация обращения к данным. Явная и неявная синхронизация. Синхронизация путем обеспечения условий неизменности. Ожидание. Пример ошибки параллельной программы, связанной с «окружением», а не с синхронизацией - АВА.
Типовые аппаратно-реализованные примитивы синхронизации. “Cборка” более сложных объектов синхронизации из более простых – композиция алгоритмов. Проблемы стандартных средств организации параллельного доступа (стандартных блокировок, примитивов типа Compare and Set, объединения примитивов).
Формальное описание программ с использованием понятий событий, «истории», сериализованной истории, эквивалентности, легальности, линеаризации. Композиционность свойств. Теоремы о композиционности и неблокируемости линеаризуемости. Условный прогресс. Свобода от ожидания и свобода от блокировок. Представления о работе платформы, которыми руководствуется программист при написании программ. Согласованность по периодам покоя, упорядоченная согласованность. Взаимоотношения понятий.
Задача о консенсусе (согласии). Использование примитивов синхронизации для решения задачи консенсуса. Использование понятия “валентности” для доказательства. Задача о соглашении для k-набора.
Некоторые свободные от блокировок соисполняемые примитивы и их число консенсуса. Регистры как самые простые блоки для построения сложных объектов (обычные, безопасные, атомарные). Атомарный снимок памяти (снапшет). Очередь типа FIFO, стек LIFO, двусторонние очереди double ended queue, очереди с приоритетами, наборы set. Множественное присваивание. Чтение-модификация-запись. Сравнение с обменом. Расширенная очередь. Теорема о максимальной “мощности” примитива CAS.
Теорема об эквивалентности примитивов с одинаковым числом консенсуса. Теорема о числе консенсуса атомарных операций чтения и записи и невозможности синхронизации при использовании только их. Теорема о неулучшаемости числа консенсуса путем комбинирования. Алгоритм булочной и связанные с ним вопросы консенсуса.
Консенсус в системе со сбоями. Теорема Фишера, Линч и Патерсона о невозможности консенсуса в системе со сбоями (FLP impossibility). Конструктивное доказательство теоремы FLP через понятия t-устойчивого консенсуса и равности. Надежность иерархии консенсуса и недетерминистические объекты.
Неблокирующие алгоритмы и их роль в современном программировании. Проблемы неблокирующих алгоритмов. Неблокирующие алгоритмы, использованные в ядре Linux - krefs, seqlocks, ring buffer, RCU. Неблокирующие стек Трейбера и очередь Михаэля. Алгоритм Деккера. Вероятностная структура – список с пропусками skip list. Неблокирующая хэш таблица с открытой адресацией.
Использование конечных автоматов для разработки и анализа неблокирующих алгоритмов. Пример конечного автомата с «всегда корректными» состояниями для создания неблокирующей хэш таблицы и доказательства ее корректности.
Методика анализа процесса соисполнения асинхронных параллельных алгоритмов. Разрешенные и не разрешенные условия гонок в программах. Условия корректности алгоритмов. Машинный анализ алгоритмов.
Литература
В. А. Серебряков, М. П. Галочкин, Д. Р. Гончар, М. Г. Фуругян. Теория и реализация языков программирования. Серия: Естественные науки. Математика. Информатика. Издательство: МЗ Пресс, 2006 г. , 352 стр. ISBN 94073-094-9.
Карпов В. А., Карпов В. Е., Коньков К. А. Основы операционных систем: Курс лекций: Учеб. пособие для вузов. Издательство: Открытые системы, Интернет-Университет Информационных Технологий - ИНТУИТ.РУ, 2005 г.
Коньков Константин. Устройство и функционирование ОС Windows. Практикум к курсу "Операционные системы. Издательство: БИНОМ. Лаборатория знаний, Интернет-Университет Информационных Технологий - ИНТУИТ.РУ, 2008 г. ISBN: 5-94774-827-4 ISBN13: 978-5-94774-827-7, 207 стр.
Herlihy, Maurice; Shavit, Nir The Art of Multiprocessor Programming 2008. 508 p. Morgan Kaufmann ISBN-13: 9780123705914
М. Руссинович, Д. Соломон Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP, Windows 2000. Мастер-класс. Серия: Мастер-класс Издательства: Питер, Русская Редакция, 2005 г. 992 стр. ISBN 5-467-01174-7, 5-7502-0085-X, 0-7356-1917-4
Intel 64 and IA-32 Architectures Software Developer’s Manual. Volume 3A: System Programming Guide, Part 1. http://www.intel.com/design/processor/manuals/253668.pdf
Memory Model for Multithreaded C++ Hans-J. BoehmHP Labs Other participants:Andrei Alexandrescu, Peter Buhr, Kevlin Henney, BenHutchings, Doug Lea, Maged Michael, Bill Pugh http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/mmissues.pdf
Страуструп Б. Язык программирования C++. Третье издание, – М.: БИНОМ, 1999.
Использование языка Java для разработки параллельных приложений / Б.И.Илюшкин http://www.csa.ru/CSA/tutor/javathread.html
Timothy G. Mattson, Beverly A. Sanders, Berna L. Massingill. Patterns for Parallel Programming (Software Patterns Series) ISBN 0321228111. Addison-Wesley, 2005.
Shameem Akhter, Jason Roberts. Multi-Core Programming. Increasing Performance through Software Multithreading. Intel Press, 2006. ISBN 0-9764832-4-6.
Click, C., A Fast Lock-Free Hash Table. JavaOne 2007 conference, 2007(Session TS-2862): p. 1-48. http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
Software transactional memory / N. Shavit, D. Touitou // Distributed Computing. - 1997. - 10, 2. - 99-116.
Atomic snapshots of shared memory / Y. Afek, H. Attiya, D. Dolevи др. // Journal of the ACM (JACM. - 1993. - 40, 4.
Not Your Father's Von Neumann Machine: A Crash Course in Modern Hardware / C. Click, B. Goetz // JavaOne. - 2008.
What every programmer should know about memory / U. Drepper // Eklektix, Inc., Október. - 2007.
Impossibility of distributed consensus with one faulty process / M. Fischer, N. Lynch, M. Paterson // Journal of the ACM (JACM. - 1985. - 32, 2.
On the inherent weakness of conditional synchronization primitives / F. Fich, D. Hendler, N. Shavit // Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. - 2004. - - 80-87.
A constructive proof for FLP / H. Völzer // Information Processing Letters. - 2004. - 92, 2. - 83-87.
A wait-free sorting algorithm / N. Shavit, E. Upfal, A. Zemach // Theory of Computing Systems. - 2001. - 34, 6. - 519-544.
Bounded concurrency time-stamp systems are constructible / D. Dolev, N. Shavit // - 1989. - - 7.
|
