Курс «Теория и практика многопоточного программирования»


Оглавление (нажмите, чтобы открыть):

Программа по курсу: теория и практика многопоточного программирования ( базовый ) по направлению

Дата 17.06.2015
Размер 56,33 Kb.
Тип Программа
Министерство образования и науки Российской Федерации

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

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

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

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

«___» _______________ 2011 г.

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

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

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

семестр: 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. Методика анализа процесса соисполнения асинхронных параллельных алгоритмов. Разрешенные и не разрешенные условия гонок в программах. Условия корректности алгоритмов. Машинный анализ алгоритмов.

ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ — PowerPoint PPT Presentation

ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ. Тема 7 Синхронизация при помощи примитивов. Общие проблемы средств организации параллельного доступа. Д.ф.-м.н., профессор А.Г. Тормасов Базовая кафедра «Теоретическая и Прикладная Информатика», МФТИ. Тема.

ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ

Download Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author. While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server.

Presentation Transcript

ТЕОРИЯ И ПРАКТИКАМНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 7 Синхронизация при помощи примитивов. Общие проблемы средств организации параллельного доступа. Д.ф.-м.н., профессор А.Г. Тормасов Базовая кафедра «Теоретическая и Прикладная Информатика», МФТИ

Тема • Типовые аппаратно реализованные примитивы синхронизации • “Cборка” более сложных объектов синхронизации из более простых • Проблемы стандартных средств организации параллельного доступа • стандартных блокировок • примитивов типа Compare and Set • объединения примитивов. Теоретическая и Прикладная Информатика, МФТИ

От простого к сложному • Можно ли из простых синхронизационных объектов получить сложные? • Может быть, да? • Например, в ядре Windows можно пользоваться множеством примитивов • И все они организованы на платформе x86! Теоретическая и Прикладная Информатика, МФТИ

Примитивы Windows 7 • Mutex • FastMutex • FastMutexUnsafe • GuardedMutex • CriticalRegion • GuardedRegion • ExecutiveResource • Event • Semaphore • ExecutiveSpinLock • QueuedSpinLock • InterruptSpinLock • Timer • ConditionVariable • SlimReaderWriterLock • InitOnceInitialization Теоретическая и Прикладная Информатика, МФТИ


Примитивы • все они «собраны» из каких то других операций • критическая секция (CriticalRegion) реализуется через одну ячейку и атомарную операцию Compare-And-Set. • из каких низкоуровненвых «аппаратных» примитивов можно собрать более высокоуровневые? • сколько памяти для этого потребуется? • Пример нестандартного применения – распределенная файловая система, объединенная одной SCSI шиной. Теоретическая и Прикладная Информатика, МФТИ

Что делать? • проанализировать примитивы и алгоритмы • ввести классификацию • какие алгоритмы можно реализовать какими примитивами • Об этом – при обсуждении задачи о консенсусе • Могут ли много «слабых» примитивов сложным алгоритмом корректно решить задачу, требующую хотя бы один более «сильный» примитив Теоретическая и Прикладная Информатика, МФТИ

«Сборка» алгоритмов • Можно ли собрать один алгоритм из другого? Что такое «собрать»? • Пусть существует релизация алгоритма в виде программы. • Будем считать, что внутри программы (кода функций и модулей) есть обращения (вызовы, синхронные или асинхронные) к одному или нескольким экземплярам синхронизационных объектов через соответствующий АПИ (без каких либо «прямых доступов к переменной» и других нарушений инкапсуляции). • Алгоритм «собран» из синхронизационных объектов • Так же, естественно, мы можем утверждать, что алгоритм реализует какой либо синхронизационный примитив, или, в более общем случае, решает какую то задачу, используя синхронизационные объекты. • Фактически, это композиция объектов Теоретическая и Прикладная Информатика, МФТИ

Проблемы стандартных средств • Как обычно решаются задачи, возникающие при написании параллельных программ? • Синхронизационные примитивы, которые поставляет аппаратная платформа • Атомарные операции типа Compare and Swap и их родственники • Разнообразные блокировки, построенные на их основе Теоретическая и Прикладная Информатика, МФТИ

Проблемы стандартных блокировок • Взаимная блокировка (тупик, deadlock) Оба процесса хотят взять А и В Процесс1 Процесс2 Захватывает А Захватывает В Пытается захватить В Пытается захватить А и ждет его освобождения! и ждет его освобождения! Теоретическая и Прикладная Информатика, МФТИ

Условия Коффмана • Условия, при которых наступает взаимная блокировка (Коффман, 1971) • Условие взаимного исключения, то есть ресурс не может в один момент времени быть использован более чем одним потоком, • Условие удержания и ожидания, то есть поток захватывает какие то ресурсы и ожидает, когда сможет захватить еще ресурсы, не освобождая уже захваченные, • Условие неперераспределяемости, или невозможности принудительного освобождения уже захваченного ресурса кем либо, кроме захватившего его потока, • Условие взаимного кругового ожидания, или существования «круга», в котором каждый участник ждет одного или более ресурсов, захваченных другими участниками «круга». Теоретическая и Прикладная Информатика, МФТИ

Проблемы стандартных блокировок • Инверсия приоритета • низкоприоритетный поток захватил блокировку и перестал получать кванты • Высокоприоритетный, ожидающий блокировки, эффективно понижает приоритет • Конвоирование • «медленно» исполняющийся поток, периодически захватывающий блокировку • Высокоприоритетный поток, который периодически ожидает освобождения блокировки • В результате быстрый поток тащится со средней скоростью медленного (конвоирует) Теоретическая и Прикладная Информатика, МФТИ

Проблемы CAS • крайняя сложность в разработке • Например, обход проблемы работы только с 1 словом • Как ни странно, аппаратный DCAS не спасает • высокий уровень накладных расходов • Блокировки шины • Сложные вычислительно алгоритмы Теоретическая и Прикладная Информатика, МФТИ

Проблемы композиции • Крайне сложная и неприятная в решении проблема • пример – атомарное переписывание с одного счета на другой • Более сложный пример – переполнение хэш таблиц • Надо переписать элемент из старой в новую • Как быть с выполняемой операцией? • Элемент временно невидим • Элемент в двух экземплярах • Заблокировать обе таблицы на время переписи! • Обе таблицы – неблокирующие • Зато алгоритм переписи – блокирующий в худшем смысле Теоретическая и Прикладная Информатика, МФТИ

Как решать проблемы? • Никто не знает, как организовать сложную программную структуру с большим количеством блокировок • Привлекать высококвалифицированных инженеров (дорого!) • Создается какой то набор соглашений • не являются частью программы, а находятся исключительно в голове программиста • описываются обычно в документации к программе/комментариях Теоретическая и Прикладная Информатика, МФТИ

Выводы • Для реализации всегда используются только аппаратные примитивные операции • Практически всегда алгоритмы синхронизации являются композицией из других алгоритмов • Создание композиционных алгоритмов – крайне сложная задача, «хорошие» составляющие могут дать «плохой» алгоритм • Все используемые стандартные подходы имеют свои весьма сложные в решении проблемы Теоретическая и Прикладная Информатика, МФТИ

ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ

    Алексей Оловенников 8 месяцев назад Просмотров:

1 ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 11 Свойства примитивов по отношению к числам консенсуса Д.ф.-м.н., профессор А.Г. Тормасов Базовая кафедра «Теоретическая и Прикладная Информатика», МФТИ

2 Тема Теорема об эквивалентности примитивов с одинаковым числом консенсуса. Теорема о числе консенсуса атомарных операций чтения и записи и невозможности синхронизации при использовании только их. «тонкие отличия» числа консенсуса и решения задач синхронизации Теорема о неулучшаемости числа консенсуса путем комбинирования. Теоретическая и Прикладная Информатика, МФТИ 2

3 Универсальность консенсуса Обсудили что нельзя сделать из других примитивов А что можно? А что такое одинаковость числа консенсуса? Теорема. Любой объект с числом консенсуса n в системе из n потоков можно реализовать, используя один или более экземпляров любого другого объекта с тем же числом консенсуса n несколько экземпляров атомарных регистров типа чтениезапись (опционально) Теоретическая и Прикладная Информатика, МФТИ 3

4 Универсальность консенсуса произвольный примитив синхронизации можно реализовать через любой другой примитив синхронизации одинаковой с ним силы! Доказательство создадим алгоритм: реализует объект (выбранного примитива) реализация является корректной реализация является ограниченной от ожидания Теоретическая и Прикладная Информатика, МФТИ 4

5 Конструируемый объект последовательный объект в его начальном состоянии «журнал операций» объекта последовательность вызовов в виде односвязного списка, каждый элемент описывает вызов метода объекта с параметрами Read-only Исполнение в потоке Добавляет описание метода который надо исполнить в голову Создает приватную копию данных и исполняет все методы из списка Возвращает результат исполнения последней операции Теоретическая и Прикладная Информатика, МФТИ 5

6 Конструируемый объект Сделаем сконструированный объект соисполняемым для вызова любого потока Создадим элемент списка для выполнения метода Решим задачу о консенсусе n потоков (по условию всегда можно) используя ЛЮБОЙ примитив с числом n (!) Победитель делает свою копию и добавляет элемент в вершину и вычисляет ответ Это соисполнимо, так как все операции только чтение, модификаций ни объектов ни списков нет Полученное, по конструкции, свободно от ожидания Теоретическая и Прикладная Информатика, МФТИ 6

7 Число консенсуса регистров Теорема. Используя только атомарные операции чтения и записи, невозможно решить задачу консенсуса для двух и более потоков Число консенсуса атомарных чтения/записи: 1 ТОЛЬКО детерминированные объекты и системы! Доказательство от «противного» — пусть существуют 2 процесса, решающих задачу консенсуса для 2 потоков 0 и 1 Теоретическая и Прикладная Информатика, МФТИ 7

8 Доказательство По лемме будет существовать критическое состояние. Выберем нумерацию потоков так, что после критического все ходы потока 0 ведут в 0-валентное состояние все ходы потока 1 ведут в 1-валентное состояние Рассмотрим все возможные варианты один поток читает (а второй делает что угодно) Поток 0 собирается читать нашу ячейку Поток 1 делает что угодно (читает или пишет) оба потока пишут в разные регистры (r0 и r1 соответственно) оба потока пишут в один и тот же регистр r Теоретическая и Прикладная Информатика, МФТИ 8

9 Поток 0 читает (Поток 1 может читать или писать в тот же или другой регистр) Левая ветка поток 1 делает 1 ход, переводя в 1-валентное состояние, и работает соло, оканчивая решением 1. Правая ветка поток 0 делает ход, переводя в 0-валентное состояние, и оканчивает решением 0. поток 1 также, после первого хода, работает соло и должен решить что 0. Но для потока 1 оба состояния неотличимы при одинаковых условиях он обязан получить два разных решения! Теоретическая и Прикладная Информатика, МФТИ 9

10 Потоки пишут в разные регистры (Поток 0 пишет в r0 и поток 1 пишет в r1) Левая ветка поток 0 сначала пишет в r0, переводя в 0-валентное состояние, и поток 1 пишет в r1, оканчивая решением 0. Правая ветка поток 1 сначала пишет в r1, переводя в 1-валентное состояние, и поток 0 пишет в r0, оканчивая решением 1. Но для потоков оба состояния неотличимы, так как они не знают кто сделал первый ход при одинаковых условиях опять обязаны получиться два разных решения! Теоретическая и Прикладная Информатика, МФТИ 10


11 Потоки пишут в один регистр (Оба потока пишут в регистр r) Левая ветка поток 0 сначала пишет в r, переводя в 0-валентное состояние, и затем поток 1 пишет в r, оканчивая решением 0. Правая ветка поток 1 сначала пишет в r, переводя в 1-валентное состояние, и затем поток работает соло, оканчивая решением 1. Но для потока 1 оба состояния неотличимы, так как содержание регистра r затерто после записи и он не знает, делал ли поток 0 первый ход при разных начальных условиях обязаны получиться одинаковые решения! Теоретическая и Прикладная Информатика, МФТИ 11

12 Число консенсуса регистров Следствие. Построение любого свободного от ожидания объекта с числом консенсуса более 1, которое использует только операции атомарного чтения и записи, невозможно. Комбинируя операции чтения и записи, построить, например, FIFO очередь, нельзя Теоретическая и Прикладная Информатика, МФТИ 12

13 Неулучшаемость консенсуса Теорема. Если X имеет число консенсуса n, и Y имеет число консенсуса m, и m 14 Неулучшаемость консенсуса Мы имеем набор вызовов для объекта X набор вызовов для объекта Y причем X может быть реализовано через Y есть некоторая композиция вызовов , которая реализует протокол, и использует данные объектов Y! Итого, у нас есть новый объект, в каком то смысле эквивалентный Y — та же память, тоже свободный от ожидания, с другим набором вызовов, и решает задачу консенсуса для n>m! Но Y по определению ее решить не может. Противоречие. Теоретическая и Прикладная Информатика, МФТИ 14

15 Консенсус панацея? Является ли решение задачи консенсуса синонимом возможности решения задач организации корректного синхронного доступа к данным, и наоборот? Задача о соглашении для k-набора продемонстрировала, что число консенсуса не полностью характеризует вычислительную мощность объекта. Существует понятие «надежности» иерархии, согласно которому нельзя сконструировать объект из более высокого уровня иерархии через низкоуровневые (См теорему о невозможности). Иерархия консенсуса не является надежной для недетерминистических (асинхронных) объектов. Более того, есть задачи и их решения, не попадающие под определение консенсуса (в основном, изза несоответствия требованию свободы от ожидания), но решающие практические задачи. Теоретическая и Прикладная Информатика, МФТИ 15

16 Алгоритм булочной // Пример реализации алгоритма Лампорта // использует лексикографическое сравнение пар // (num[i],i) 0) && ((num[j] 0) ; > > > Теоретическая и Прикладная Информатика, МФТИ 16

17 Алгоритм булочной Лемма Алгоритм булочной является свободным от взаимной блокировки Доказательство: ожидающий поток имеет уникальную пару значений (num[i],i), то есть не ждет другого потока Лемма Алгоритм булочной является «честным» (обслуживает в порядке прихода) Доказательство: если «тамбур» (см текст) i предшествует j, то билет i меньше, так как write i (num[i]) read j (num[i]) write j (num[j]) read j (choosing[i]) то есть j заблокировано пока choosing[i] равно TRUE. NB Любой алгоритм, являющийся свободным от взаимной блокировки и являющийся «честным», также является свободным от зависаний. Лемма Алгоритм булочной удовлетворяет условиям взаимного исключения в критической секции. Доказательство (самостоятельно). Теоретическая и Прикладная Информатика, МФТИ 17

18 Алгоритм булочной Прост, элегантен, обладает честностью, обладает свободой от взаимной блокировки, обладает уникальным свойством работать корректно даже с «небезопасными» регистрами при параллельном чтении-записи (!) Но требует n раздельных ячеек, где n максимальное значение соисполнимых потоков! Можно доказать, что не существует другого алгоритма использующего только чтение-запись, со свободой от взаимной блокировки, требующего меньшего размера памяти! Но, как обсуждалось, число консенсуса чтения-записи 1, так как же быть с алгоритмом булочной Лампорта. (для самостоятельного обдумывания) Теоретическая и Прикладная Информатика, МФТИ 18

19 Выводы Рассмотрели отношения примитивов друг к другу при помощи анализа их на число консенсуса Все примитивы одного уровня одинаковы, их не улучшить! Доказали число консенсуса для чтения-записи основополагающее утверждение для всей теории Начали анализировать «тонкие отличия» числа консенсуса и решения задач синхронизации в общем Невозможность решения задачи о консенсусе не есть невозможность организации синхронизации Практические ограничения не только сложность решения задачи, но и объем памяти, нужной для работы алгоритма Часто легче сделать менее «свободный» но более эффективный алгоритм Теоретическая и Прикладная Информатика, МФТИ 19

ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 1 Введение Д. ф.- м. н., профессор А. Г. Тормасов Базовая Кафедра « Теоретическая и Прикладная Информатика. — презентация

Презентация была опубликована 6 лет назад пользователемtormasov.com

Похожие презентации

Презентация на тему: » ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 1 Введение Д. ф.- м. н., профессор А. Г. Тормасов Базовая Кафедра « Теоретическая и Прикладная Информатика.» — Транскрипт:

1 ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 1 Введение Д. ф.- м. н., профессор А. Г. Тормасов Базовая Кафедра « Теоретическая и Прикладная Информатика », МФТИ

больше мощность -> больше потерь на тепло – и как отдавать тепло ?) Скорость света ( скоро будет так, что за один такт сигнал уже не успевает передаться » title=»Почему . Производители процессоров « уткнулись в множество стен »: Мощность ( выше частота –> больше мощность -> больше потерь на тепло – и как отдавать тепло ?) Скорость света ( скоро будет так, что за один такт сигнал уже не успевает передаться » > 2 Почему . Производители процессоров « уткнулись в множество стен »: Мощность ( выше частота –> больше мощность -> больше потерь на тепло – и как отдавать тепло ?) Скорость света ( скоро будет так, что за один такт сигнал уже не успевает передаться с одного конца ЦПУ на другой !) Скорость памяти ( тормозит выполнение программ, часто количество промахов кэша определяет производительность !) Умозрительное исполнение ограничено ( сложность растет экспоненциально с глубиной ) 2 Теоретическая и Прикладная Информатика, МФТИ больше мощность -> больше потерь на тепло – и как отдавать тепло ?) Скорость света ( скоро будет так, что за один такт сигнал уже не успевает передаться «> больше мощность -> больше потерь на тепло – и как отдавать тепло ?) Скорость света ( скоро будет так, что за один такт сигнал уже не успевает передаться с одного конца ЦПУ на другой !) Скорость памяти ( тормозит выполнение программ, часто количество промахов кэша определяет производительность !) Умозрительное исполнение ограничено ( сложность растет экспоненциально с глубиной ) 2 Теоретическая и Прикладная Информатика, МФТИ»> больше мощность -> больше потерь на тепло – и как отдавать тепло ?) Скорость света ( скоро будет так, что за один такт сигнал уже не успевает передаться » title=»Почему . Производители процессоров « уткнулись в множество стен »: Мощность ( выше частота –> больше мощность -> больше потерь на тепло – и как отдавать тепло ?) Скорость света ( скоро будет так, что за один такт сигнал уже не успевает передаться «>

RISC Типичный современный компьютер : Много быстрых ядер и гиперпотоков Много кэшей разного уро» title=»А потому, что. Решение : « потроха наружу », и пусть программист заботится о производительности ! Примерно так же как во времена начала перехода CISC -> RISC Типичный современный компьютер : Много быстрых ядер и гиперпотоков Много кэшей разного уро» > 3 А потому, что. Решение : « потроха наружу », и пусть программист заботится о производительности ! Примерно так же как во времена начала перехода CISC -> RISC Типичный современный компьютер : Много быстрых ядер и гиперпотоков Много кэшей разного уровня Медленная память ( штраф за обращение !) Написание программы в « традиционном » последовательном стиле на 16 потоковой системе приведет к тому, что … от полной мощности системы ваша программа может получить уже около 1/16

5- 6%! Теоретическая и Прикладная Информатика, МФТИ 3 RISC Типичный современный компьютер : Много быстрых ядер и гиперпотоков Много кэшей разного уро»> RISC Типичный современный компьютер : Много быстрых ядер и гиперпотоков Много кэшей разного уровня Медленная память ( штраф за обращение !) Написание программы в « традиционном » последовательном стиле на 16 потоковой системе приведет к тому, что … от полной мощности системы ваша программа может получить уже около 1/16

5- 6%! Теоретическая и Прикладная Информатика, МФТИ 3″> RISC Типичный современный компьютер : Много быстрых ядер и гиперпотоков Много кэшей разного уро» title=»А потому, что. Решение : « потроха наружу », и пусть программист заботится о производительности ! Примерно так же как во времена начала перехода CISC -> RISC Типичный современный компьютер : Много быстрых ядер и гиперпотоков Много кэшей разного уро»>

4 парадигма Традиционная : последовательная Я один на машине Мне никто не мешает Думаю только о правильности алгоритма Современная : параллельная Меня на машине много ( много потоков ) Мне мешает ОС, другие программы, я сам и тд Думаю и о корректности работы алгоритма в многопоточном окружении Думаю и об общей скорости работы алгоритма, задействованных устройствах, попадании в кэши и тд Практически вся рассматриваемая « математика » появилась в XXI веке ! 4 Теоретическая и Прикладная Информатика, МФТИ

5 До курса : Умею программировать ( слегка ) Знаю язык С Знаю на уровне прикладного программиста Аппаратуру ОС и АПИ системных вызовов Базовые синхронизационные вызовы Знаю что такое машина Тьюринга 5 Теоретическая и Прикладная Информатика, МФТИ

6 Содержание курса « Аппаратура » Классика параллельного программирования ( небольшая ее часть, не претендуя на замену других традиционных курсов ПП ) Теория ( математика ): теоремы, доказательства, анализ алгоритмов ( на корректность, производительность, иногдп в лучшем, в худшем, в среднем. ) Практика ( программирование ): написание реально работающих программ, исследование поведения алгоритмов под нагрузкой ( отдельные занятия ) Все вместе : работа с неблокирующими алгоритмами в программах 6 Теоретическая и Прикладная Информатика, МФТИ

7 Содержание курса Основы архитектуры современных микрокомпьютерных систем Только те сведения, которые влияют на производительность программ Способы явного и неявного программного манипулирования компонентами аппаратуры Аппаратура, система команд и языки программирования ( С — подобные ) Акцент на архитектуру x86 Некоторые необычные понятия параллельного программирования Уровни абстракции, не — существование « а на самом деле. » Атомарность Время Корректность Специфика работы с разделяемой памятью Общие проблемы параллельности и частные проблемы раздельного доступа Методы организации синхронного доступа 7 Теоретическая и Прикладная Информатика, МФТИ

8 Содержание курса Математика параллельного программирования Некоторые математические аппараты, применяемые для анализа и моделирования параллельных программ Формализация понятий История, завершенность, сериализованность, линеаризованность, легальность и тд Прогресс, условный и безусловный Сравнение примитивов друг с другом, относительная мощность Использование задачи о консенсусе для сравнения примитивов синхронизации Числа консенсуса для типовых примитивов 8 Теоретическая и Прикладная Информатика, МФТИ

9 Содержание курса Свобода – наша цель Свободные, свободные от блокировок, свободные от ожидания и с ограниченным от ожидания прогрессом Эффективность разных свободных алгоритмов Невозможность – наш ограничитель Невозможно улучшить примитив Невозможно решить задачу о консенсусе инструкциями чтения записи Невозможно решить задачу о консенсусе для системы со сбоями Невозможно … Но ! Невозможно решить точно не означает нерешаемо ! Пример : Ethernet 9 Теоретическая и Прикладная Информатика, МФТИ

10 Содержание курса Неблокирующие алгоритмы – наше будущее ? Существующие алгоритмы Когда можно применять, и зачем Как реализовать Как создать новый Упражнения и задание (TBD) 10 Теоретическая и Прикладная Информатика, МФТИ

11 После курса : Уметь анализировать работу параллельных потоков, использующих общую ( разделяемую ) память Понимать проблемы и терминологию параллельного программирования, математический аппарат, применяемый для описания и анализа Знать современные подходы к организации параллельных вычислений, в том числе высокопроизводительных Знать ограничения алгоритмики и не заниматься « квадратурой круга » или изобретением велосипеда Уметь создавать эффективные параллельные алгоритмы и понимать, когда их применение оправдано 11 Теоретическая и Прикладная Информатика, МФТИ


12 Дополнения Источники, на базе которых появился курс Потребность в новых алгоритмах и программах Книга Шафита, Херлихая и курсы на ее основе Недостатки имеющихся источников ( слишком « молодая » тема ) Личный опыт программирования и написания высокопроизводительных программ ( как следствие – использование С и x86 для примеров ) Литература Увы, почти вся англоязычная, причем большинство в виде « зубодробительных » научных статей Готовится пособие по курсу ( уже выпущена часть про аппаратуру ) Практические занятия Задание со списком задач (TBD) Практикум – реализация и анализ какого либо алгоритма Дополнение к курсу в виде библиотеки неблокирующих алгоритмов Комментарии, ошибки в материалах, предложения – welcome! 12 Теоретическая и Прикладная Информатика, МФТИ

13 НИР На кафедре информатики МФТИ ведется работа по методам анализа неблокирующих алгоритмов Можно ли построить автоматический метод анализа алгоритмов на корректность и отсутствие неразрешенных гонок ( сейчас это крайне сложно, например, анализ неблокирующей хеш таблицы на корректность методом машинной верификации занял 2 года !). Новые подходы к неблокирующим алгоритмам, не использующим блокировки шины (CAS) и барьеры Защищены ( к. ф.- м. н.) 2 первые диссертации по этим темам Желающие заниматься – welcome! 13 Теоретическая и Прикладная Информатика, МФТИ

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

Название Программа по курсу: теория и практика многопоточного программирования
Дата публикации 14.05.2014
Размер 56.33 Kb.
Тип Программа

literature-edu.ru > Физика > Программа

Министерство образования и науки Российской Федерации

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

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

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

«___» _______________ 2011 г.

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

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

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

семестр: 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. Методика анализа процесса соисполнения асинхронных параллельных алгоритмов. Разрешенные и не разрешенные условия гонок в программах. Условия корректности алгоритмов. Машинный анализ алгоритмов.

ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ

Published on
18-Mar-2020

. 11 . .-. .. , . . . — PowerPoint PPT Presentation

11 ..-. .. , . . . 2 , ? ?. n n , n — () , 3 ! : ( ) , 4 , Read-only , 5 n ( ) n (!) , , , , , 6 . , /: 1 ! — 2 , 2 0 1 , 7 . , 0 0- 1 1- ( ) 0 1 ( ) (r0 r1 ) r

, 8 0 ( 1 ) 1 1 , 1- , , 1. 0 , 0- , 0. 1 , , 0. 1 ! , 9

( 0 r0 1 r1) 0 r0, 0- , 1 r1, 0. 1 r1, 1- , 0 r0, 1. , ! , 10

( r) 0 r, 0- , 1 r, 0. 1 r, 1- , , 1. 1 , r , 0 ! , 11


. 1, , . , , , FIFO , , 12 . X n, Y m, m m! Y . . , 14 ? , ? k- , . , ( ). () . , , ( , ), . , 15 , 16// ivo > 0) && ((num[j] 0) ; > >>// // // (num[i],i)

ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 5 Некоторые понятия, используемые при разработке параллельных программ Д. ф.- м. н., профессор А.

Published by Modified over 4 years ago

Similar presentations

Presentation on theme: «ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 5 Некоторые понятия, используемые при разработке параллельных программ Д. ф.- м. н., профессор А.»— Presentation transcript:

1 ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 5 Некоторые понятия, используемые при разработке параллельных программ Д. ф.- м. н., профессор А. Г. Тормасов Базовая кафедра « Теоретическая и Прикладная Информатика », МФТИ

2 Тема Некоторые понятия, используемые при разработке параллельных программ. Уровни абстракции, которыми мыслит программист, и корректность программ. Время, простые временные отметки и ограниченные во времени отметки времени. О вероятностях и ошибках. 2 Теоретическая и Прикладная Информатика, МФТИ

3 Модель исполнения Программист, пишущий программу, имеет « в голове » модель того как она будет исполняться Эта модель эволюционирует Когда то были инженеры, которые « знают как течет ток в процессоре » Когда то были инженеры — математики, которые знают как дифурами, переложенными на набор модулей и функций фортран, описывается задача Сейчас есть программисты, оперирующие понятиями объекты, методы, связи и тд в исполняемой программе ( забыв о подпрограммах и модулях ) Часть программистов манипулирует понятиями « распределенной веб — объектной системы » и тд Теоретическая и Прикладная Информатика, МФТИ 3

4 Модель исполнения Типичная современня модель исполнения параллельных программ : 1.“ мой код исполняется одним процессором в одиночестве без перерывов ” 2.Операторы исполняются последовательно один за другим, « целиком » ( псевдоатомарно ) 3.Если несколько процессоров, то поделим код на куски, где опять см пп 1,2! Теоретическая и Прикладная Информатика, МФТИ 4

5 Но почему ? А потому, что. Свели задачу к известной ( старая история про то « как программист кипятит чайник »?) А как по другому то ? А по другому то сверхсложно, недоступно обычному программисту — инженеру ! Теоретическая и Прикладная Информатика, МФТИ 5

6 Как ? Для этого « изобрели » множество процедур, гарантирующих исполнение кода « в одиночестве » ( разновидности критических секций по сути своей ) будем называть их « примитивами синхронизации » Примитив потому что обычно неделим Их стало очень много ( в ядре Windows 7 – 16 типов !) Технически они все используют примерно один и тот же набор низкоуровневых операций платформы ( х 86) Теоретическая и Прикладная Информатика, МФТИ 6

7 Примитивы Согласно теореме об эквивалентности примитивов с одинаковым числом консенсуса ( которая будет доказана далее ), любой из них может быть реализован через любые другие примитивы одного уровня консенсуса Их существование – исключительно удобство уровня абстракции, которым пользуется программист Для повышения эффективности, но, в первую очередь, для уменьшения ошибок и приближения « модели апи » к « модели программы » Теоретическая и Прикладная Информатика, МФТИ 7

8 Корректность программ Одно из самых основных понятий остается одинаковым с самых давних времен – корректность « Программа должна быть правильной » ?! Теоретическая и Прикладная Информатика, МФТИ 8

9 « корректно работающая программа » Что это такое ? При каких условиях ? Если сломался ЦПУ, должна ли программа работать ? А на борту космического корабля ? Будет ли корректна программа, дающие разные ответы в одинаковых условиях ? Теоретическая и Прикладная Информатика, МФТИ 9

10 « корректно работающая программа » Если выбранный ( и закодированный ) алгоритм не всегда работает так как мы ожидали – программа корректна ? Мы просто не предусмотрели всех вариантов ! – наша ошибка ? Предусмотреть все варианты невозможно математически ? Условно — корректная программа RSA алгоритм базируется на задаче нахождения простых чисел, и на невозможности ее стабильного решения за какое то время Недавно новый результат в фундаментальной математике уменьшил перебор на 2-3 порядка ! Заменить ключи 768 бит на 2048 бит. На момент написания – корректна, но потом. Один из вариантов задачи корректности программ в математической постановке будет рассмотрен при рассказе об оценке наличия неразрешенных условий гонок Теоретическая и Прикладная Информатика, МФТИ 10

11 Время как одна из абстракций Одновременно сложное и простое понятие, о котором знают все Понятие события и отношение Одно событие раньше другого Эти события – одновременны Есть « абсолютное знание » с точки зрения которого это правильно или нет А если нет такого ? Теоретическая и Прикладная Информатика, МФТИ 11

12 Отношения и порядок А какая инструкция сейчас исполняется ? Умозрительное исполнение Неатомарность большинства инструкций Что есть окончание работы команды ? Например, Последний такт процессора Время попадания результата в кэш ( который из них ) Время попадания результата в память Видимость результата соседним процессором Теоретическая и Прикладная Информатика, МФТИ 12

13 Отношения и порядок Последовательность записей в память может меняться процессором ! А одновременно ли исполняются две эти инструкции ? Если мы не знаем когда она кончается, то. А влияет ли исполнение этой инструкции на вот эту ? Ключевой вопрос – взаимовлияние ! Теоретическая и Прикладная Информатика, МФТИ 13

14 Наблюдаемая упорядоченность Результат действия одних инструкций по отношению к состоянию других инструкций Даже если мы можем « измерить » все оборудование, не поможет « знать точно состояние ячейки »! Скорее, не просто « может быть так », а « так является » Команды « наблюдения » влияют на наблюдаемые Совсем как в квантовой механике Процесс измерения меняет измеряемую величину ? Измеряемое явление не существует до момента измерения ! Теоретическая и Прикладная Информатика, МФТИ 14

15 Наше время Последовательность операций внутри одного потока как последовательность переданных на исполнение CPU команд Общее время все потоки разделяют одно и тоже понятие времени В дальнейшем понятие времени будет формализовано Теоретическая и Прикладная Информатика, МФТИ 15

16 Временные отметки (TS) Один из важных приемов – используется во множестве алгоритмов « в какой то степени уникальное » значение счетчика « монотонно » растет Пример : время, прошедшее с какого то момента Теоретическая и Прикладная Информатика, МФТИ 16

17 Временные отметки TS_instance CreateTS(); Создает экземпляр временной метки TS_value GetTSvalue(TS_instance); получает новое значение временной метки ( и, обычно, инкрементирует ее экземпляр ) int CompareTSvalues(TS_value, TS_value); сравнивает два значения Изменение внутреннего счетчика По запросу Постоянно меняющееся значение ( например, RDTSC) Обычно целое слово (4 байта ) Теоретическая и Прикладная Информатика, МФТИ 17

18 Временные отметки Пример – счетчик в алгоритме булочной Проблемы Переполнение (Y2K – проблема 2000 года ) Точность Калибровка (RDTSC) Гарантии уникальности Теоретическая и Прикладная Информатика, МФТИ 18

19 Ограниченные отметки Как избежать проблем переполнения ? получить такие значения счетчиков, которые можно сравнивать всегда Есть сложные реализации, с гарантией Пример – реализация с ограничением схемы использования Сканирование – чтение отметки другого потока Самопометка – выставка себе большей метки Только последовательно ( упорядоченно ) Теоретическая и Прикладная Информатика, МФТИ 19

20 Ограниченные отметки ассиметричный упорядоченный граф ( предшествования ) для представления Ребро от a к b означает что а позднее Нет транзитивности (a→b + b→c != a→c) Метка потока « переползает » по ребрам Теоретическая и Прикладная Информатика, МФТИ 20


21 Ограниченные отметки G есть граф предшествования, и A и B есть его подграфы Определение : А доминирует над B в графе G, если каждая вершина графа A имеет ребра, идущие к каждой вершине графа B. Определение : Операция размножения графа G через H (G o H) есть некоммутативный оператор следующего вида : Заменим каждую вершину графа G копией графа H ( обозначаемой далее H ), причем H доминирует над Hu в G o H, если доминирует над u в G. Определение : граф предшествования для k потоков T k есть : T 1 – единственная вершина ; T 2 – определен выше ; T k = T 2 o T k-1 при к > 2. Используя предложенный граф T k, можно всегда найдти новое место для знака потока, который будет доминировать надо всеми остальными потоками Теоретическая и Прикладная Информатика, МФТИ 21

22 Вероятности и ошибки Можно ли пренебречь маловероятным событием ? неатомарная инкрементация i++ в 2 потоках Мала вероятность совпадения ? На 1 М ошибка

10 раз, несколько раз в секунду ! Теоретическая и Прикладная Информатика, МФТИ 22

23 Вероятности и ошибки Другой пример – сравнение страниц (4 кб ) Можно сравнивать побайтово ( а если их много ?) Можно сгенерировать хеш и сравнить его Второй случай имеет « встроенную » ошибку Для 64 бит хеша с учетом парадокса дня рождения надо сделать 6 сравнений (10 5 байт ) для достижения вероятности совпадения 10 -18, т. е. 1 отказ на 10 23 байт Первый – тоже ! ( ЕСС память ) 1 отказ на 10 20 байт, хотя, возможно, это разные ошибки Теоретическая и Прикладная Информатика, МФТИ 23

24 Выводы Программист использует понятные ему абстракции ( понятия ) в рамках модели исполнения Типовые понятия ( кроме обычных для языка ) включают Корректность программы Время и процесс выполнения кода Наблюдаемый порядок выполнения инструкций, отношения между ними Примитивы синхронизации Для « прямой » работы со временем используются временные отметки Они часто используются для организации параллельных алгоритмов и имеют специфику реализации Типовая модель исполнения для параллельного программирования является продолжением последовательной Чаще всего используется модель « автономного исполнения участков кода » При выборе алгоритмов, в том числе паралельных, необходимо учитывать вероятности и ошибки 24 Теоретическая и Прикладная Информатика, МФТИ

ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ

Published on
31-Dec-2015

. 13 . ..-. .. , . . , — PowerPoint PPT Presentation

13 . -. .. , , , , 2 , Lockless , / , , 3 , , , , 4 : ( ) , , , CAS , , , , ( , ). , 5 , — , L. Lamport, Concurrent reading and writing Communications of the ACM, vol. 20, no. 11, pp. 806811, Nov. 1977 , 6 , . ( ) , 7 , i, , ., , , , . i, , . , i , . , i , . , , , , . , 8 Linux, Linux (2.6)krefs (lockless counters )seqlocks (, )Ring buffer (kfifo.h)RCU (radix tree ) , 9krefs , 10krefsstruct foo < struct kref kref; >;// struct foo *foo;foo = kmalloc(sizeof(*foo),GFP_KERNEL);kref_init(&foo->kref, foo_release);// — kref_get(&foo->kref);kref_put(&foo->kref);// vo >refcount,1); kref->release = release;>struct kref *kref_get(struct kref *kref) < atomic_inc(&kref->refcount); return kref;>down (&disconnect_sem);kref_put(&dev->kref);up(&disconnect_sem);

, 11seqlockssequential lock : , () , , 12seqlocks , 13// // // ! , void write_seqlock(seqlock_t *lock);// void write_tryseqlock(seqlock_t *lock);

// , // RCU , , 0! , 14RCUstruct my_stuff *stuff;

// rcu_read_lock( );stuff = find_the_stuff(args. );do_something_with(stuff);rcu_read_unlock( );

vo >data = v; do < t = S; x->next = t; > while(!CAS(&S,t,x));>vo >next; > while(!CAS(&S,t,x)); return t->data;> , 17 Treiber init . push: x; S; next S; x. 2 4 , CAS . pop . , , 18 , Head Tail.Head , Tail CAS ( ABA)Dequeue , Tail , ( ) , (, ) ( , , ) , 19 struct Pointer < Node *ptr; unsigned int counter;>;

vo >next.ptr = NULL; q->Head = ; q->Tail = ; // > , 20 vo >value = value; x->next.ptr = NULL; while(1) < // ptr+cnt ! Pointer t = q->Tail; Pointer n = t.ptr->next; if (t == q->Tail) // ? < // t ? if (n.ptr == NULL) < // if (CAS(&t.ptr->next, n, )) break; // > else // t — CAS(&q->Tail, t, // . ); > > // — Tail CAS(&q->Tail,t,);> , 21 BOOL dequeue(Queue *q, value_t *pvalue)< while(1) < // Pointer t=q->Tail, h=q->Head, n=h->next; if (h == q->Head) // ? // ? if (h.ptr == t.ptr) < if (n.ptr == NULL) // return FALSE; // , CAS(&q->Tail, t, )); > else // < // , // dequeue *pvalue = n.ptr->value; if (CAS(&q->Head, h, )) break; // . > > // while free(h.ptr); return TRUE;> , 22 FIFO SWSRRCU SWMR ( 2 , , )Fastflow SRSW , , 23 1 boolean flag[2] = ; int turn = 0; // 1

flag[0] = true; while (flag[1] == true) < if (turn != 0) < flag[0] = false; while (turn != 0) ; flag[0] = true; >> // . turn = 1; flag[0] = false; // 2 flag[1] = true; while (flag[0] == true) < if (turn != 1) < flag[1] = false; while (turn != 1) ; flag[1] = true; >> // . turn = 0; flag[0] = false; // , 24 skip list 90% — lookup, 9% — add, 1% — del (AVL, — ) add/del , 90- O(log(n)) , O(n) , 25 skip list , 26025789 skip list ( — 8) , , 27025789 skip list ( 7) , 28025897 skip list ( 7) , 297 skip list ( 7) , , 30025789 skip list i 2i , M. Fomitchev. Lock-free linked lists and skip lists. Masters thesis, York University, October 2003. http://www.cs.yorku.ca/

mikhail. , 31 , , , 32 H. Gao, J. F. Groote, W. H. Hesselink, «Almost Wait-Free Resizable Hashtables,» ipdps, vol. 1, pp.50a, 18th International Parallel and Distributed Processing Symposium (IPDPS’04)126 , 42 insert, find, delete30 getAccess/releaseAccess46 new Table, refresh, migrate, moveContents6 moveElement2 — , 200 , , 33 < getAccess; (find/delete/insert)*; releaseAccess;>, , 34 Gao Chris Purcell and Tim Harris. Non-blocking hashtables with open addressing. Distributed Computing, pages 108121, 2005 , ( !) — — , , 35 , , , , ! Empty busy inserting member , 36 3 inserting , , , , busy CAS member , 37 bool CollisionInBucket(int h, int index)< versionstate temp1(GetBucket(h,index)->vs); if (IsReadableKey((State)temp1.state)) if (Hash(GetBucket(h,index)->key) == h ) < versionstate temp2(GetBucket(h,index)->vs); if (IsReadableKey(temp2.state)) if (temp1.version == temp2.version) return true; > return false;>

2010/2011 — Осенний семестр

Теория и практика многопоточного программирования

Семестровый курс по выбору.

Проходит: по понедельникам в 18:30, первое занятие 20 сентября. Аудитория: 806 КПМ.

Лектор: проф. Тормасов А., д. ф.-м. н., Коротаев К., к. ф.-м. н.

Курс рассчитан на студентов от 2 курса и аспирантов.

Продолжение нового курса «Теория и практика многопоточного программирования», прочитанного весной.

Почему?

За последние 10 лет появились новые многоядерные процессоры, разделы фундаментальной математики, алгоритмы и структуры данных (lockless, вероятностные. )


Зачем?

Понять, как можно создавать эффективно работающие программы в современном многопроцессорном мире.

Кто может участвовать?

Студенты (от 2 курса) и аспиранты, имеющие некоторый опыт в программировании на языке С или аналогичном.

Особенности курса

Теоретическая часть: обсуждение задач и приемов их решения. Предполагается задание (

Практическая часть: написание небольших программ и их практический анализ — производительность, корректность и т. д.

Что развивает курс (данные для «Вектора»)

  • Практика программирования (языки и технологии) (курс сфокусирован на этом)

Информация о развиваемых компетенциях занесена в систему для работы «Вектора». Поскольку занесение информации производится редакторами проекта, а не авторами курсов, информация может быть неполной или даже частично неверной. Если Вы нашли ошибку, напишите нам об этом. См. также подробнее о системе «Вектор» и полный список компетенций.

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

Название Программа по курсу: теория и практика многопоточного программирования
Дата конвертации 06.07.2013
Размер 56.33 Kb.
Тип Программа

Министерство образования и науки Российской Федерации

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

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

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

«___» _______________ 2011 г.

по курсу: теория и практика многопоточного программирования ( базовый )

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

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

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

Программу составил: профессор, д.ф.-м.н., А.Г. Тормасов

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

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

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

  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. Методика анализа процесса соисполнения асинхронных параллельных алгоритмов. Разрешенные и не разрешенные условия гонок в программах. Условия корректности алгоритмов. Машинный анализ алгоритмов.
Мастер Йода рекомендует:  PHP против ASP - делайте ставки, господа!
Добавить комментарий