Программа по курсу: теория и практика многопоточного программирования




Скачать 56.33 Kb.
НазваниеПрограмма по курсу: теория и практика многопоточного программирования
Дата публикации14.05.2014
Размер56.33 Kb.
ТипПрограмма
literature-edu.ru > Физика > Программа
Министерство образования и науки Российской Федерации

Московский физико-технический институт

(государственный университет)
УТВЕРЖДАЮ

Проректор по учебной работе

___________ Ю. А. Самарский

«___» _______________ 2011 г.

ПРОГРАММА
по курсу: теория и практика многопоточного программирования (базовый)

по направлению: 010600

факультеты: ФУПМ

кафедра: ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ ИНФОРМАТИКИ

курс: 3

семестр: 6 экзамен 6 семестр

лекции: 34 час.
ВСЕГО ЧАСОВ: 34
Программу составил: профессор, д.ф.-м.н., А.Г. Тормасов
Программа обсуждена

на заседании кафедры

теоретической и прикладной

информатики

11 мая 2011 г.
Заведующий кафедрой, А.Г. Тормасов

профессорПрограмма курса


  1. Обзор содержания курса, цели, задачи. Использованные источники.

  2. Оборудование и основные сведения о работе. Обзор стандартной архитектуры современных компьютеров. CPU, потоки исполнения, планирование исполнения и контекстные переключения, interconnect. Связность памяти и разные типы многопроцессорных систем (SMP, NUMA), ее влияние на работу программ. Кэши процессора разных типов и линии кэша (cache line), когерентность кэшей, MESI protocol (modified exclusive shared invalid). False sharing.

  3. Система команд. Упорядоченность операций, видимость результатов операции, и неопределенность последовательности записи-чтения данных (relaxed memory consistency), ключ volatile. Атомарность операции, атомарное чтение и запись. Атомарные примитивы, используемые для организации процедур синхронизации.

  4. Языки программирования и работа порожденного кода в условиях современных многопоточных систем с разделяемой памятью. Причины условий гонок (race conditions) и других проблем параллельного программирования с точки зрения оборудования. Модель программирования и синхронизации, встроенная в язык (Java, C). Потоки, «безопасность для исполнения в параллельных потоках», локальные объекты потока и др.

  5. Некоторые понятия, используемые при разработке параллельных программ. Уровни абстракции, которыми мыслит программист, и корректность программ. Время, простые временные отметки и ограниченные во времени отметки времени. О вероятностях и ошибках.

  6. Общие проблемы параллельного программирования. Проблемы, возникающие при работе с разделяемой памятью. Разделяемые объекты и синхронизация. Синхронизация выполнения кода и синхронизация обращения к данным. Явная и неявная синхронизация. Синхронизация путем обеспечения условий неизменности. Ожидание. Пример ошибки параллельной программы, связанной с «окружением», а не с синхронизацией - АВА.

  7. Типовые аппаратно-реализованные примитивы синхронизации. “Cборка” более сложных объектов синхронизации из более простых – композиция алгоритмов. Проблемы стандартных средств организации параллельного доступа (стандартных блокировок, примитивов типа Compare and Set, объединения примитивов).

  8. Формальное описание программ с использованием понятий событий, «истории», сериализованной истории, эквивалентности, легальности, линеаризации. Композиционность свойств. Теоремы о композиционности и неблокируемости линеаризуемости. Условный прогресс. Свобода от ожидания и свобода от блокировок. Представления о работе платформы, которыми руководствуется программист при написании программ. Согласованность по периодам покоя, упорядоченная согласованность. Взаимоотношения понятий.

  9. Задача о консенсусе (согласии). Использование примитивов синхронизации для решения задачи консенсуса. Использование понятия “валентности” для доказательства. Задача о соглашении для k-набора.

  10. Некоторые свободные от блокировок соисполняемые примитивы и их число консенсуса. Регистры как самые простые блоки для построения сложных объектов (обычные, безопасные, атомарные). Атомарный снимок памяти (снапшет). Очередь типа FIFO, стек LIFO, двусторонние очереди double ended queue, очереди с приоритетами, наборы set. Множественное присваивание. Чтение-модификация-запись. Сравнение с обменом. Расширенная очередь. Теорема о максимальной “мощности” примитива CAS.

  11. Теорема об эквивалентности примитивов с одинаковым числом консенсуса. Теорема о числе консенсуса атомарных операций чтения и записи и невозможности синхронизации при использовании только их. Теорема о неулучшаемости числа консенсуса путем комбинирования. Алгоритм булочной и связанные с ним вопросы консенсуса.

  12. Консенсус в системе со сбоями. Теорема Фишера, Линч и Патерсона о невозможности консенсуса в системе со сбоями (FLP impossibility). Конструктивное доказательство теоремы FLP через понятия t-устойчивого консенсуса и равности. Надежность иерархии консенсуса и недетерминистические объекты.

  13. Неблокирующие алгоритмы и их роль в современном программировании. Проблемы неблокирующих алгоритмов. Неблокирующие алгоритмы, использованные в ядре Linux - krefs, seqlocks, ring buffer, RCU. Неблокирующие стек Трейбера и очередь Михаэля. Алгоритм Деккера. Вероятностная структура – список с пропусками skip list. Неблокирующая хэш таблица с открытой адресацией.

  14. Использование конечных автоматов для разработки и анализа неблокирующих алгоритмов. Пример конечного автомата с «всегда корректными» состояниями для создания неблокирующей хэш таблицы и доказательства ее корректности.

  15. Методика анализа процесса соисполнения асинхронных параллельных алгоритмов. Разрешенные и не разрешенные условия гонок в программах. Условия корректности алгоритмов. Машинный анализ алгоритмов.


Литература

  1. В. А. Серебряков, М. П. Галочкин, Д. Р. Гончар, М. Г. Фуругян. Теория и реализация языков программирования. Серия: Естественные науки. Математика. Информатика. Издательство: МЗ Пресс, 2006 г. , 352 стр. ISBN   94073-094-9.

  2. Карпов В. А., Карпов В. Е., Коньков К. А. Основы операционных систем: Курс лекций: Учеб. пособие для вузов. Издательство: Открытые системы, Интернет-Университет Информационных Технологий - ИНТУИТ.РУ, 2005 г.

  3. Коньков Константин. Устройство и функционирование ОС Windows. Практикум к курсу "Операционные системы. Издательство: БИНОМ. Лаборатория знаний, Интернет-Университет Информационных Технологий - ИНТУИТ.РУ, 2008 г. ISBN: 5-94774-827-4 ISBN13: 978-5-94774-827-7, 207 стр.

  4. Herlihy, Maurice; Shavit, Nir The Art of Multiprocessor Programming 2008. 508 p. Morgan Kaufmann ISBN-13: 9780123705914

  5. М. Руссинович, Д. Соломон Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP, Windows 2000. Мастер-класс. Серия: Мастер-класс Издательства: Питер, Русская Редакция, 2005 г. 992 стр. ISBN 5-467-01174-7, 5-7502-0085-X, 0-7356-1917-4

  6. 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

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

  8. Страуструп Б. Язык программирования C++. Третье издание, – М.: БИНОМ, 1999.

  9. Использование языка Java для разработки параллельных приложений / Б.И.Илюшкин http://www.csa.ru/CSA/tutor/javathread.html

  10. Timothy G. Mattson, Beverly A. Sanders, Berna L. Massingill. Patterns for Parallel Programming (Software Patterns Series) ISBN   0321228111. Addison-Wesley, 2005.

  11. Shameem Akhter, Jason Roberts. Multi-Core Programming. Increasing Performance through Software Multithreading. Intel Press, 2006. ISBN 0-9764832-4-6.

  12. 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

  13. Software transactional memory / N. Shavit, D. Touitou // Distributed Computing. - 1997. - 10, 2. - 99-116.

  14. Atomic snapshots of shared memory / Y. Afek, H. Attiya, D. Dolevи др. // Journal of the ACM (JACM. - 1993. - 40, 4.

  15. Not Your Father's Von Neumann Machine: A Crash Course in Modern Hardware / C. Click, B. Goetz // JavaOne. - 2008.

  16. What every programmer should know about memory / U. Drepper // Eklektix, Inc., Október. - 2007.

  17. Impossibility of distributed consensus with one faulty process / M. Fischer, N. Lynch, M. Paterson // Journal of the ACM (JACM. - 1985. - 32, 2.

  18. 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.

  19. A constructive proof for FLP / H. Völzer // Information Processing Letters. - 2004. - 92, 2. - 83-87.

  20. A wait-free sorting algorithm / N. Shavit, E. Upfal, A. Zemach // Theory of Computing Systems. - 2001. - 34, 6. - 519-544.

  21. Bounded concurrency time-stamp systems are constructible‎ / D. Dolev, N. Shavit // - 1989. - - 7.

Добавить документ в свой блог или на сайт

Похожие:

Программа по курсу: теория и практика многопоточного программирования iconРабочая программа по курсу «основы Программирования на языке ассемблер»
Программа предназначена для обучения основам программирования на языке низкого уровня Ассемблере учащихся средних школ, учреждений...

Программа по курсу: теория и практика многопоточного программирования iconКонспект лекций доцента и. А. Волковой по курсу «системы программирования»
Система программирования – комплекс программных инструментов и библиотек, который поддерживает создание и существование программного...

Программа по курсу: теория и практика многопоточного программирования iconТеория и практика общения с новыми детьми
Г27 Энциклопедия Индиго: Теория и практика общения с Новыми Детьми / Пер с нем. — М.: Ооо издательство «София», 2007. — 288 с

Программа по курсу: теория и практика многопоточного программирования iconТеория и практика профессионального самоопределения
Пряжников Н. С. Теория и практика профессионального самоопределения. Учебное пособие. – М.: Мгппи, 1999. – 97 с

Программа по курсу: теория и практика многопоточного программирования iconТестология гуманитариям Теория и практика учебного тестирования
Войтов А. Г. Тестология гуманитариям. Теория и практика учебного тестирования. 2-е перераб изд., руководство педагогам гуманитарных,...

Программа по курсу: теория и практика многопоточного программирования iconПряжников Н. С. Профессиональное самоопределение: теория и практика...
Пряжников Н. С. Профессиональное самоопределение: теория и практика. – М.: «Академия», 2007. – с

Программа по курсу: теория и практика многопоточного программирования iconСамотаев И. Джон Дж. Мэрфи Технический анализ фьючерсных рынков: теория и практика
Технический анализ фьючерсных рынков: теория и практика. М.: Сокол, 1996. 592с

Программа по курсу: теория и практика многопоточного программирования iconБ. И. Белый тест роршаха. Практика и теория под редакцией Л. Н. Собчик «каскад»
Б43 Тест Роршаха. Практика и теория / Под ред. Л. Н. Собчик. — Спб.: Ооо «Каскад», 2005. 240 с

Программа по курсу: теория и практика многопоточного программирования iconОсновная образовательная программа высшего профессионального образования...
Предназначение Основной образовательной программы высшего профессионального образования (ооп впо) бакалавриата, реализуемой Кыргызско-Российским...

Программа по курсу: теория и практика многопоточного программирования iconПедагогическая практика Педагогическая практика является частью цикла...
М. 3 Практики и научно-исследовательская работа ооп впо магистратуры по направлению подготовки №032700 «Филология, иностранные языки...

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции