Министерство образования Российской Федерации
Московский физико-технический институт
(государственный университет)
УТВЕРЖДАЮ
Проректор по учебной работе
__________ Ю. А. Самарский
«____» ____________ 2011 г.
П Р О Г Р А М М А
по курсу Параллельное программирование многопоточных систем с разделяемой памятью (базовый)
по направлению 010600
факультет ФУПМ
кафедра ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ ИНФОРМАТИКИ
курс 4 Экзамен – 8 сем.
семестр 7, 8 Задания – 2
практические занятия – 132 часа Контрольные работы – 1
ВСЕГО ЧАСОВ: 132
Программу составил профессор, д.ф.-м.н. А.Г. Тормасов
Программа обсуждена
на заседании кафедры
теоретической и прикладной
информатики
11 мая 2011 года.
Заведующий кафедрой А.Г. Тормасов
Семестр 7.
1. Методики измерения времени выполнения программ.
1.1 Измерение времени выполнения программы. Технические приёмы. Использование RDTSC.
1.2 Различные механизмы измерения времени исполнения программ и оценка их области применения.
1.3 Точность измерения, валидность результатов, влияние процесса измерения на измеряемый процесс.
1.4 Простейшие примеры замеров времени для мультипоточных программ.
1.5 Лабораторная работа “Измерение времени”.
2. Архитектура CPU.
2.1 Кеш. Кеши первого, второго, третьего уровней (L1, L2, L3- кеши). Разбор примеров работы.
2.2 Hyperthreading и кеши первого уровня.
2.3 Разбор на простых примерах понятий когерентность, гранулярность, неправильное разделение (false sharing), cacheline.
2.4 Механизмы кэширования данных процессором, влияние неправильного разделения линии кэша процессора на производительность программы. Пример о неправильном разделении и связь с cacheline.
2.5 Лабораторная работа “Кэш процессора и неправильное разделение”.
3. Атомарность исполнения.
3.1 Понятие атомарности, атомарность исполнения, атомарные регистры.
3.2 Разбор задачи о замене атомарных регистров обычными для алгоритма взаимного исключения Петерсона.
3.3 Понятие барьера памяти, барьер чтения и барьер записи. Реализация алгоритма Петерсона без барьеров памяти.
3.4 Влияние барьеров на производительность. Барьеры для высокой и низкой нагрузки на примерах.
3.5 Лабораторная работа “Порядок выполнения команд и барьеры памяти”
4. Модель памяти.
4.1 Атомарность и RMW-операции на простых примерах. Операции копирования по полслова, exchange, compare_exchange и другие.
4.2 Видимость. Различные архитектуры и когерентность кеша.
4.3 Упорядоченность. Связь с барьерами.
4.4 Фомальный язык. История исполнения, периоды покоя, упорядоченная согласованность, линеаризуемость.
4.5 Задачи о связи истории исполнения с согласовании по периодам покоя.
4.6 Лабораторная работа “Атомарность”.
5. Проблемы многопоточных программ.
5.1 Синхронизация, разбор типовых примеров для реальных программ.
5.2 Различные способы синхронизации: критические секции, семафоры, счётчики ссылок, кольцевой буфер.
6. Вычислительные многопоточные задачи.
6.1 Коммуникация, балансировка нагрузки, масштабируемость. Вычислительные задачи.
6.2 Написание многопоточной программы, в которой потоки коммуницируют через общую память и с помощью объектов синхронизации.
7. Понятия свободы.
7.1 Соотношения между понятиями, примеры свободных программ.
7.2 Свобода от блокировки, свобода от ожидания, ограниченность от ожидания.
7.3 Задача о связи истории исполнения и понятий свободы.
Семестр 8
8. Неблокирующие алгоритмы.
8.1 Понятние неблокируемости. Неблокирующие алгоритмы. Примеры алгоритмов.
8.2 Разбор примеров: очередь Майкла-Скотта, неблокирующий список.
9. Определение консенсуса и связанные с этим понятия.
9.1 Существенность всех компонент определения. Что должно выполняться всегда, и что можно использовать для опровержения и доказательства?
9.2 Методика доказательства, использующая понятие валентности, критические состояния.
9.3 Задачи о коненсусе для различных условий, задача про число консенсуса для модифицированного CAS.
10. Композиция алгоритмов для решения более сложных задач.
10.1 Методика доказательства задачи о числе консенсуса для RMW регистра с функцией модификации с возможностью перезаписи или коммутативной.
10.2 Более нетривиальные задачи о консенсусе, задача о StickyBit.
11. Проблемы неблокирующих алгоритмов
11.1 Проблема ABA.
11.2 Проблемы, связанные с неблокирующими алгоритмами. Сложность. Доказательство корректности.
11.3 Лабораторная работа “Проблема ABA”.
12. Взаимное исключение. Ожидание и отложенное ожидание.
12.1 Взаимное исключение, spin lock, monitor lock, mutex.
12.2 Изучение и сравнение различных способов ожидания входа в критическую секцию.
12.3 Лабораторная работа «Взаимное исключение. Ожидание и отложенное ожидание».
13. Побочные эффекты взаимного исключения.
13.1 Ознакомление с основными побочными средства синхронизации.
13.2 Взаимная блокировка, инверсия приоритета, конвоирование.
13.3 Лабораторная работа “Взаимное исключение. Побочные эффекты.”
14. Оптимистический подход к синхронизации
14.1 SeqLock, RWLock. Область их применения.
14.2 Read-Copy-Update (RCU) как альтернатива RWLock, оценка области его применения.
14.3 Лабораторная работа “SeqLock как пример оптимистического подхода”.
14.4 Лабораторная работа “RCU как альтернатива RWLock”.
15. Параллельное программирование с помощью Fastflow
15.1 Библиотека Fastflow, оценка пределов ее эффективности.
15.2 Лабораторная работа “Параллельное программирование с помощью Fastflow”.
Литература
1. System Deadlocks/ E. Coffman, M. Elphick, A. Shoshani // Computing Surveys (CSUR. - 1971. - 3, 2.
2. Wait-free synchronization/ M. Herlihy // ACM Transactions on Programming Languages and …. - 1991. -
3. Obstruction-free synchronization: Double-ended queues as an example/ M. Herlihy, V. Luchangco, M. Moir // International Conference on Distributed Computing Systems. - 2003. - 23, - 522-529.
4. The art of multiprocessor programming/ M. Herlihy, N. Shavit // - 2008. - - 508.
5. Multiprocessing / Wikipedia // - - 2011Feb.http://en.wikipedia.org/wiki/Multiprocessing
6. Rdtsc / Wikipedia // - - 2011http://ru.wikipedia.org/wiki/Rdtsc
7. Теория и реализация языков программирования / В.А. Серебряков, М.П. Галочкин, Д.Р. Гончар и др. - Москва: МЗ Пресс, 2006. - 352 стр.
8. Multi-core programming : increasing performance through software multi-threading / S. Akhter, J. Roberts - Hillsboro, OR: Intel Press, 2006.
9. Алгоритмы + структуры данных - программы / Н. Вирт - М.: Мир, 1985. - 406 с.
10. Внутреннее устройство Microsoft® Windows® : Windows Server™ 2003, Windows XP и Windows 2000 / М. Руссинович, Д. Соломон - 4-е изд. - Москва [и др.]: Русская ред. Питер, 2008. - 968 с.
11. Современные операционные системы = Modern operating systems / Э. Таненбаум - 2. изд. - М. [и др.]: Питер, 2002. - 1037 с.
Задание
(срок сдачи 12-17 апреля)
Задача 1
Докажите, что если бинарный консенсус, используя атомарные регистры, невозможен для n потоков, то тогда он невозможен и для k значений, где k>2.
Задача 2
Класс приблизительного соглашения для двух потоков с заданным значением ε, определяется следующим образом. Пусть даны два потока А и В, каждый вызывает методы decide(xa) и decide(xb), где xa and xb – действительные числа. Методы возвращают, в свою очередь, действительные числа ya и yb ,причем обозначения ya и yb лежат в закрытом интервале [min(xa, xb), max(xa, xb)], и |ya − yb| <= ε для ε > 0. Заметим, что этот объект не является детерминистическим. Каким числом консенсуса обладает объект приблизительного соглашения?
Задача 3
Предложите свободную от ожидания реализацию объекта множественного присваивания для 3 ячеек памяти и двух потоков Assign_2_3, использующий 3 стандартных объекта CAS (предоставляющих методы CAS и get).
Задача4
Доказать, что каждый n-потоковый протокол консенсуса имеет бивалентное начальное состояние.
Задача 5
Покажите, что массив размером log2m объектов типа StickyBit вместе с атомарными регистрами чтения-записи могут решить задачу о свободном от ожидания консенсусе для любого количества потоков, где количество различных входных значений равно ровно m.
Задача 6
Определение операции CAS - compareAndSet() возвращает булевское значение, которое описывает тот факт, что значение в памяти было завершено. Строгоговоря, в таком случае этот метод не является RMW (чтение-модификация-запись), так как для RMW метода он должен возвращать старое значение ячейки. Используя объект, реализующий методы get() и описанный выше compareAndSet(), реализовать новый объект, предоставляющий линеаризуемый метод rmwCAS(), который возвращает текущее значение регистра вместо булевского значения.
Задача 7
Рассмотрим систему потоков, которая использует технологию передачи сообщений для обмена информацией.
Пусть в ней существует n процессоров P0..Pn-1, объединенных в кольцо, где Pi отсылает сообщения только «вперед», Pi+1 mod n. Сообщения всегда доставляются в порядке FIFO. Каждый процессор имеет собственную копию разделяемого регистра.
Работа регистра устроена следующим образом:
Для чтения регистра процессор читает копию из своей локальной памяти
Для отправки сообщения процессор Pi запускает вызов write() с значением v для регистра х: “Pi: write v to x” процессору Pi+1 mod n.
Если Pi получает сообщение “Pj: write v to x” и i != j, то он записывает v в свою локальную копию х, и переправляет сообщение Pi+1 mod n.
Если Pi получает сообщение “Pi: write v to x”, то он записывает v в свою локальную копию х, и удаляет сообщение. Вызов write считается законченным.
Докажите или опровергните следующие утверждения:
При условии, что вызовы write() никогда не перекрываются (упорядочены), реализованный в системе регистр является
При условии, что вызовы write() могут перекрыватся для разных процессоров, реализованный в системе регистр является
Задача 8
Пусть заданы 3 потока A, B, C, каждый со своим MRSW регистром XA, XB, XC соответственно. В каждый регистр можно писать одному потоку, и двум другим можно читать.
Также для любой пары потоков задан разделяемый RMWR регистр, который предоставляет только методы CAS и get – RAB для A и B, RBС для B и C и RAC для A и C, соответственно. Только тот поток, который разделяет регистр, может вызывать его методы.
Предложите протокол консенсуса, или докажите его невозможность.
Задача 9
Рассмотрим систему потоков, которая использует технологию передачи сообщений для обмена информацией. Пусть в ней определен режим широковещательной передачи сообщений типа А (то есть, один поток отправляет сообщения всем потокам), который гарантирует, что
каждый работающий поток получит все сообщения. Если поток P отправляет сообщение M1, а затем, M2, то каждый поток получит сообщение M1перед сообщением M2.
Разные потоки могут получить сообщения от разных потоков в произвольном порядке.
Предложите протокол консенсуса для такой системы, или докажите его невозможность.
Задача 10
Рассмотрим систему потоков, которая использует технологию передачи сообщений для обмена информацией.
Пусть в ней определен режим широковещательной передачи сообщений типа В (то есть, один поток отправляет сообщения всем потокам), который гарантирует, что каждый работающий поток получит все сообщения.
Если поток P отправляет сообщение M1, и поток Q отправляет сообщение M2, то каждый поток получит сообщения M1 и M2 в одном и том же порядке.
Предложите протокол консенсуса для такой системы, или докажите его невозможность.
Задача 11
Объект группового консенсуса может решить проблему консенсуса, если не более 2 различных значений будет предложено всеми участниками. Его поведение при большем количестве входных значений неопределено. Предложите методику решения задачи консенсуса для n потоков, с вплоть до n разных входных значений, используя объекты группового консенсуса.
Задача 12
Опишем класс тринарных объектов. Каждый объект имеет 3 состояния – 0, 1 и 2.Начальное состояние объекта - 2.Объект предоставляет обычные методы типа CAS и get.
Предложите протокол, который использует один такой регистр для решения задачи бинарного (входные значения только 0 или 1) консенсуса для n потоков.
Задача 13
Можно ли использовать множество тринарных объектов консенсуса (возможно, с другими атомарными регистрами чтения-записи) для решения задачи свободного от ожидания консенсуса для n потоков, если диапазон входных значений потоков находится в диапазоне 0..2K-1, для К>1.
Задача 14
Предложите решение предыдущей задачи с числом тринарных регистров О(n).
Задача15
Предложите решение предыдущей задачи с числом тринарных регистров О(K).
Лабораторные работы
Порядок выполнения команд и барьеры памяти
Цель работы
Убедиться в наличии возможности изменения порядка выполнения комманд на процессорах x86. Научиться пользоваться барьерами памяти для предотвращения изменения порядка выполнения команд.
Принадлежности
Блокировка Петерсона в "классическом" виде (без использования барьеров).
Ход работы
1. Перестановка команд из-за оптимизации кода компилятором.
Написать программу, состоящую из двух потоков, один из которых крутится в цикле до тех пор, пока значение разделяемой переменной равно 0, а второй устанавливает значение этой переменной в 1. Проверить, что произойдет, если разделяемая переменная не помечена спецификатором volatile.
2. Перестановка команд процессором.
Написать программу состоящую из двух потоков. Первый поток инициализирует некоторую структуру данных и записывает указатель на нее в разделяемую переменную, начальное значение которой равно NULL. Второй поток крутится в цикле до тех пор, пока значение разделяемой равно NULL, затем считывает значение полей структуры. Не расставляя барьеров памяти, запустить несколько раз программу и убедиться, что возможна ситуация, когда второй поток считает неинициализированные поля структуры. Расставить корректно барьеры памяти в программе.
3. Написать программу, состоящую из двух потоков, параллельно увеличивающих значение разделяемой переменной. В качестве средства синхронизации воспользоваться предоставленной блокировкой Петерсона. Запустить программу и убедиться в некорректности результата. Расставить барьеры в коде блокировки Петерсона и убедиться в корректности расстановки барьеров с помощью написанной программы.
Кэш процессора и неправильное разделение
Цель работы
Ознакомиться с механизмом кэширования данных процессором. Изучить влияние неправильного разделения линии кэша процессора на производительность программы.
Принадлежности
Средства измерения времени.
Простая, хорошо распараллеливаемая программа, подверженная проблеме неправильного разделения. Например, это может быть программа, которая параллельно подсчитывает число нечетных чисел в матрице, причем каждый поток хранит свой промежуточный итог в ячейке разделяемого массива.
Ход работы
1. Убедиться в наличии механизма кэширования данных процессором. Для этого написать однопоточную программу, которая считывает каждый n-й элемент массива (n – задается пользователем), и построить зависимость времени исполнения от числа n. Из полученных результатов оценить размер линии кэша процессора.
2. Продемонстрировать неправильное разделение. Для этого написать многопоточную программу, каждый поток которой модифицирует ячейку разделяемого массива под номером i·n, где i – номер потока, n – задается пользователем. Построить зависимость времени исполнения от максимального числа потоков при n=1 и при n, равном размеру линии кэша процессора. Объяснить результат. Проверить, изменится ли результат при n=1, если только один поток будет модифицировать значение своей ячейки массива, а остальные лишь читать свои ячейки.
3. Измерить время исполнения предоставленной программы. Объяснить, почему программа не распараллеливается, и исправить ошибку.
Измерение времени
Цель работы
Исследовать различные механизмы измерения времени исполнения программ. Оценить их область применения.
Принадлежности
1. Два механизма измерения времени: с помощью средств ОС и с помощью аппаратной инструкции RDTSC.
2. Различные функции, время исполнения которых необходимо будет измерить.
Ход работы
1. Измерить время исполнения кода, объем которого невелик (несколько десятков инструкций), с помощью обоих механизмов. Объяснить результат.
2. Измерить время исполнения кода большого объема (который выполняется несколько секунд) с помощью обоих механизмов. Объяснить результат.
3. С помощью инструкции RDTSC измерить время выполнения небольшой периодически повторяющейся функции, работающей с данными в памяти (например, вычисление произведения нескольких элементов массива). Объяснить, почему время исполнения первых циклов отличается от времени исполнения последующих циклов.
4. Измерить время исполнения непосредственно операций измерения времени.
5. Корректно (получить как можно более точный результат) измерить время исполнения различных функций: часто используемые инструкции (деление, умножение и т.д.); за - данная небольшая функция; заданная большая функция; заданная небольшая периодически повторяющаяся функция, работающая с данными в памяти.
6. Удалить из кода измерения времени с помощью инструкции RDTSC барьеры памяти и измерить время исполнения произвольной небольшой функции. Объяснить результат.
7. Измерить время исполнения заданной функции с помощью обоих механизмов в виртуальной машине. Сравнить результат.
Атомарность
Цель работы
Ознакомиться с основными атомарными примитивами, оценить их скорость и масштабируемость.
Принадлежности
1. Средства измерения времени.
2. Библиотека атомарных примитивов.
Ход работы
1. Написать программу, состоящую из двух потоков, параллельно изменяющих разделяемую ячейку памяти с помощью неатомарных эквивалентов FAA, CAS, DCAS. Объяснить результат некорректного поведения программы.
2. Заменить неатомарные эквиваленты атомарными операциями. Убедиться в корректности результата.
3. Написать Spinlock типа TAS и TTAS. Сравнить их пропускные способности.
4. Вычислить точно количество тактов, которые процессор тратит на атомарные операции FAA, CAS, DCAS и их неатомарные эквиваленты.
5. Написать многопоточную программу, каждый поток которой работает на отдельном процессоре и изменяет с помощью атомарной инструкции FAA или CAS некоторую переменную. Изменяя число потоков от одного до максимально возможного, сравнить время исполнения программы в случаях, когда все потоки изменяют одну и ту же переменную; соседние элементы массива; элементы массива, расстояние между которыми не меньше размера линии кэша процессора (Цель – убедиться в том, что на процессорах типа x86, начиная с Pentium Pro, атомарная операция не приводит к блокировке всей шины памяти, а лишь блокирует соответствующую линию кэша процессора).
Проблема ABA
Цель работы
Изучить проблему ABA как возможное последствие применения атомарной операции CAS.
Принадлежности
1. Средства измерения времени.
2. Несколько классов на языке C++, реализующих указатель, к которому можно применять атомарную операцию CAS. Различие между классами заключается в том, что один из них подвержен проблеме ABA, а другие ее каким-либо образом избегают.
3. Неблокирующий стек Трейбера, который может использовать один из вышеупомянутых классов.
4. Псевдокод какой-либо неблокирующей структуры данных (Это может быть очередь Майкла-Скотта или неблокирующий список).
Ход работы
1. Написать многопоточную программу, каждый поток исполнения которой добавляет/удаляет элементы из стека Трейбера, использующего подверженный проблеме ABA атомарный примитив CAS. Подсчитав элементы стека после исполнения программы, убедиться в существовании проблемы ABA.
2. Запустить ту же многопоточную программу, что и в пункте 1, но уже с использованием "безопасного" примитива CAS. Убедиться в корректности работы программы.
3. Сравнить время исполнения обычного и "безопасного" атомарного примитива CAS.
4. Реализовать на языке C неблокирующую структуру на основе представленного псевдокода. Убедиться в корректности реализации.
Взаимное исключение. Ожидание и отложенное ожидание
Цель работы
Изучить и сравнить различные способы ожидания входа в критическую секцию.
Принадлежности
1. Средства измерения времени.
2. Spinlock типа TTAS с использованием Backoff и без, MonitorLock.
Ход работы
1. Написать программу, состоящую из двух потоков, работающих на одном процессоре.
Каждый поток, например, увеличивает значение разделяемой переменной, пользуясь взаимным исключением для обеспечения синхронизации доступа. Сравнить время исполнения программы при использовании SpinLock и MonitorLock в качестве средства синхронизации.
2. Написать программу, состоящую из двух потоков, работающих на разных процессорах. Каждый поток, например, увеличивает значение разделяемой переменной, пользуясь взаимным исключением для обеспечения синхронизации доступа. Сравнить время исполнения программы при использовании SpinLock и MonitorLock в качестве средства синхронизации в случаях, когда объем кода, исполняемого в критической секции невелик, и когда в критической секции исполняется большой объем кода.
3. Написать программу, состоящую из двух потоков, работающих на разных процессорах. Каждый поток извлекает работу из общего списка работ, синхронизация в котором производится с помощью взаимного исключения, выполняет эту работу, затем приступает к следующей работе и т.д., причем работы выполняются параллельно, а время выполнения работы пропорционально ее размеру. Реализовать взаимное исключение в этой программе с помощью SpinLock, SpinLock с Backoff и MonitorLock. Сравнить время исполнения написанной программы при разных размерах работ (В случае, когда в списке много маленьких работ, использование SpinLock с Backoff должно дать наилучший результат).
Взаимное исключение. Побочные эффекты
Цель работы
Ознакомиться с основными побочными эффектами использования взаимного исключения как средства синхронизации, такими как взаимная блокировка, инверсия приоритета и конвоирование.
Принадлежности
1. Средства измерения времени.
2. SpinLock, MonitorLock.
3. Неблокирующая очередь Майкла-Скотта, неблокирующий стек Трейбера.
4. Программа, подверженная взаимной блокировке из-за неправильного порядка взятия вложенных блокировок.
5. Программа, подверженная инверсии приоритета. Программа состоит из потока-передатчика пакетов, потока-приемника пакетов с высоким приоритетом, потока-обработчика пакетов с низким приоритетом и из одного или более потоков с средним приоритетом. Поток-передатчик передает пакеты, например, через pipe. Поток-приемник получает пакет, посылает уведомление потоку-передатчику о том, что пакет принят, помещает пакет в очередь подлежащих обработке пакетов, защищенную с помощью MonitorLock, затем приступает к следующему пакету. Если поток-передатчик не получает уведомление от потока-приемника в течение некоторого периода времени, он посылает этот пакет снова. Поток-обработчик по одному извлекает пакеты из очереди подлежащих обработке пакетов, и обрабатывает их. Остальные потоки делают какую- либо свою работу (например, просто крутятся в цикле, исчерпывая свой квант времени).
6. Программа, подверженная конвоированию. Программа запускает заданное количество потоков с одинаковым приоритетом. Каждый поток вставляет заданное количество элементов в общий стек, защищенный с помощью MonitorLock, затем извлекает из стека столько же элементов. Между операциями над стеком поток делает какую-либо свою локальную работу (например, крутится в цикле заданное количество раз).
Ход работы
1. Взаимная блокировка.
Запустить программу, подверженную взаимной блокировке. Объяснить и исправить ошибку.
2. Инверсия приоритета.
a) Запустить программу, подверженную инверсии приоритета. Измерить время исполнения программы и подсчитать число повторно отправленных пакетов.
b) Проверить, изменится ли результат при замене SpinLock на MonitorLock.
c) Изменить код так, чтобы при захвате MonitorLock приоритет низкоприоритетного потока повышался, а при освобождении понижался. Измерить время исполнения программы и подсчитать число повторно отправленных пакетов.
d) Заменить блокирующую очередь на неблокирующую очередь Майкла-Скотта. Измерить время исполнения программы и подсчитать число повторно отправленных пакетов.
e) Сравнить и объяснить результаты полученные выше.
3. Конвоирование.
a) Запустить программу, подверженную конвоированию. Измерить время исполнения программы.
b) Проверить, изменится ли результат при замене SpinLock на MonitorLock.
c) Изменить код так, чтобы перед захватом MonitorLock приоритет потока повышался, а после захвата понижался. Измерить время исполнения программы.
d) Заменить блокирующий стек на неблокирующий стек Трейбера. Измерить время исполнения программы.
e) Сравнить и объяснить результаты полученные выше.
SeqLock как пример оптимистического подхода
Цель работы
Ознакомиться с оптимистическим подходом синхронизации на примере Seqlock. Оценить область его применения.
Принадлежности
1. Средства измерения времени.
2. SpinLock, RWLock, SeqLock.
3. Простая программа, использующая SeqLock для синхронизации доступа к структуре, содержащей указатели. Например, это может быть программа, работающая с связным списком, "защищенным" с помощью SeqLock.
Ход работы
1. Написать многопоточную программу, имитирующую отсчет времени. На одном процессоре запускается поток-писатель, который с некоторой периодичностью увеличивает счетчик времени, состоящий из нескольких (двух-четырех) слов (например, секунды, миллисекунды). На остальных процессорах запускаются потоки-читатели, считывающие некоторое количество раз значение времени. Сравнить время исполнения про- граммы при использовании разных примитивов синхронизации.
2. Увеличив время чтения структуры, попытаться добиться активной блокировки при использовании SeqLock для синхронизации. Сравнить в этом случае эффективность разных примитивов синхронизации.
3. Увеличив число писателей и частоту записей разделяемой структуры, попытаться добиться активной блокировки при использовании SeqLock для синхронизации. Срав- нить в этом случае эффективность разных примитивов синхронизации.
4. Запустить предоставленную программу и объяснить возникающую ошибку.
Read-Copy-Update (RCU) как альтернатива RWLock
Цель работы
Ознакомиться с механизмом RCU как с неблокирующей альтернативой RWLock. Оценить область его применения.
Принадлежности
1. Средства измерения времени.
2. SpinLock, RWLock, механизм RCU.
3. Двусвязный список, не пригодный для конкурентного использования.
4. Программа для тестирования параллельной работы с двусвязным списком. Программа создает заданное количество потоков, часть из которых только читают список, а остальные случайным образом модифицируют его. Отношение числа читателей к числу писателей задается пользователем. Измеряется время исполнения программы, а также средний, медианный и максимальный расход памяти.
Ход работы
1. Сделать предоставленный двусвязный список пригодным для конкурентного использования с помощью (a) SpinLock, (b) RWLock, (c) механизма RCU.
2. Запустить предоставленную программу для тестирования двусвязного списка, защищенного различными механизмами синхронизации. Построить зависимость времени исполнения от отношения числа потоков-читателей к числу потоков-писателей.
3. Запустить предоставленную программу для тестирования двусвязного списка, защищенного с помощью механизма RCU. Построить зависимость расхода памяти от отношения числа потоков-читателей к числу потоков-писателей при разных временах чтения данных в критической секции RCU.
Параллельное программирование с помощью Fastflow
Цель работы
Ознакомиться с библиотекой Fastflow, оценить пределы ее эффективности.
Принадлежности
1. Средства измерения времени.
2. Два варианта библиотеки Fastflow: оригинальная и с использованием для передачи данных блокирующей очереди вместо неблокирующей SRSW очереди.
3. Программа, демонстрирующая использование библиотеки Fastflow (например, программа сложения матриц).
Ход работы
1. С помощью предоставленного примера написать программу параллельного умножения матриц с использованием библиотеки Fastflow.
2. Найти размер матрицы, время умножения которой на одном процессоре совпадает с временем умножения на нескольких процессорах. Из полученного результата оценить время передачи данных между потоками.
3. Так же как и в пункте 2, найти время передачи данных между потоками в случае, когда для передачи данных используется блокирующая очередь.
|
