Параллельные вычисления и многопоточное программирование

Параллельные вычисления и многопоточное
программирование

2-е издание, исправленное

Биллиг В.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Параллельные вычисления и многопоточное программирование/ В.А. Биллиг - М.: Национальный
Открытый Университет “ИНТУИТ”, 2016

Данный учебный курс представляет введение в параллельное и многопоточное программирование.
Он знакомит читателя с общими свойствами параллельных вычислений, моделью параллельных
вычислений и ее характеристиками.
Рассматриваются основы построения параллельных алгоритмов, обсуждаются проблемы
параллельных вычислений при их выполнении на многоядерных компьютерах с общей памятью –
гонка данных, клинч, проблемы синхронизации и блокировки. Все примеры программ, приведенные
в данном курсе, написаны на языке C# с использованием средств параллельного программирования.
В курсе обсуждаются средства, включенные в состав библиотеки классов FCL (Framework Class
Library), начиная от класса Thread, описывающего потоки, до класса Parallel, включенного в TPL
(Task Parallel Library).

(c) ООО “ИНТУИТ.РУ”, -2016
(c) Биллиг В.А., -2016

3

Введение

Предисловие

Around 2000 it became clear that the future of programming goes through parallelism. But
concurrent programming remains hard, and many programmers do not understand the
fundamental concepts.

This is not for lack of literature: there are many books on concurrency, Some are very long,
some are very theoretical. This one is a different kind of book: concise and practical, giving
the reader a concrete grasp of thread-based programming in the C# programming language.
For its size, it surveys a remarkable set of problems and techniques, from how to parallelize
numerical applications to how to avoid data races, from operating system processes to
semaphores and monitors.

Professor Vladimir Billig, who already has authored so many books on programming topics,
and translations of other people’s books, has produced with Параллельные вычисления и
многопоточное программирование a highly useful and usable book, full of well-crafted
examples. It deserves to be widely known and will introduce many programmers to the
challenges and beauty of parallel programming.

Bertrand Meyer, professor of ETH University

В последние 10 -15 лет пришло ясное осознание того, что будущее программирования
неразрывно связано с параллелизмом. Но параллельное программирование – трудное
дело, и для многих программистов фундаментальные концепции остаются
непонятными.

И дело не в отсутствии литературы: есть много книг, посвященных параллельным
вычислениям, некоторые весьма объемные, другие – изобилуют теоретическими
выкладками. Данная книга является примером другого вида: лаконичная и практичная,
она дает читателю конкретное понимание программирования, основанного на потоках,
при создании программ на языке C#.

В небольшой по объему книге рассматривается значительное множество важных
проблем и методов, начиная от того, как распараллеливать вычислительные задачи, до
рассмотрения гонки данных, от процессов операционной системы до семафоров и
мониторов.

Профессор Владимир Биллиг, который является автором многих книг по
программированию, также как и переводчиком книг других авторов, создав
“Параллельные вычисления и многопоточное программирование”, представил еще
одну весьма полезную, широко применимую книгу, с хорошо продуманными
примерами. Она заслуживает широкого распространения и познакомит многих
программистов с вызовами и красотой параллельного программированияю

Бертран Мейер, профессор университета ETH, Цюрих

4

РЕЦЕНЗИЯ на книгу В.А.Биллига “Параллельные вычисления и многопоточное
программирование”

С большим удовольствием прочитал эту книгу.

Во-первых, тема параллельного программирования сегодня очень актуальна.

Во-вторых, хороших книг на эту тему пока слишком мало.

Ну и, наконец, еще меньше книг, действительно полезных практикам. Книгу
В.А.Биллига можно читать, чтобы познакомиться с основными теоретическими
положениями, но, на мой взгляд, основной интерес представляют многочисленные
примеры. Это полноценные программы, по которым можно осваивать средства
параллелизма в языке С#.

Автор проделал громадную работу, не просто написав несколько примеров, но проведя
подробные исследования. Ему удалось найти “темные” места в реализации фирмы
Микрософт, он сравнивал эффективность применения разных вариантов
распараллеливания, и некоторые результаты оказались просто неожиданными.

Читатель, внимательно изучивший данную книгу, получит бесценный опыт и знания,
которые без этой книги пришлось бы по крупицам собирать в объемной фирменной
документации. Я по себе знаю, как это трудно.

Рекомендую книгу В.А.Биллига к публикации и использованию в качестве учебника
для всех вузов, где преподается программирование на серьезном уровне.

Зав. кафедрой системного программирования СПбГУ,доктор физ.-мат. наук, профессор
А.Н.Терехов

Мир современных компьютеров это многопроцессорный мир. Рассматривая широкий
спектр разнообразных компьютеров, на одном конце спектра можно видеть наиболее
мощные компьютеры - суперкомпьютеры, занимающие целые здания, на другом компьютеры, окружающие человека, - смартфоны, планшеты, ноутбуки.

У одного из лучших на данный момент суперкомпьютера Sequoia число ядер более
полутора миллионов. Выпускаемые сегодня смартфоны имеют не менее двух ядер.
Фирмы, производящие процессоры, переходят от выпуска процессоров с несколькими
ядрами - до 8 ядер у процессора, к выпуску процессоров со многими ядрами - от 64
ядер у процессора. В ближайшие 10 лет можно ожидать, что домашний компьютер с
числом ядер 64 или 128 станет обычным явлением.

Рост числа ядер означает, что продолжается гонка за быстродействие компьютера.
Быстродействие суперкомпьютера Sequoia составляет 20 петафлоп, быстродействие
самого мощного в нашей стране суперкомпьютера Ломоносов, установленного в МГУ,
превосходит один петафлоп. В ближайшие 5 - 7 лет появятся компьютеры с
экзафлопной производительностью, что означает увеличение быстродействия еще в
тысячу раз. Такой компьютер в секунду способен выполнить 1018 операций.

5

Громадность этого числа плохо укладывается в человеческом сознании. До сих пор все
изобретения человечества позволяли увеличить его способности максимум на 4 - 5
порядков. Человек способен бежать со скоростью 0,01 км/сек. Предположим, что нам
удастся создать ракеты, летящие с максимально возможной скоростью, - скоростью
света - 300 000 км/сек. В этом случае скорость таких ракет превзойдет скорость
человека всего на 8 порядков. Компьютеры способны увеличить вычислительные
способности человека на 18 порядков.

В чем суть гонки за быстродействие компьютера? Ответ прост. Мощности
современных компьютеров не хватает для задач, требующих решения. Возникает
некоторый парадокс. Чем более сложные задачи решаются на компьютерах, тем
больше появляется новых задач, для которых мощности существующих компьютеров
уже не хватает.

Задачи, требующие сегодня экзафлопных компьютеров, крайне важны. Они
определяют инновационное развитие общества. Это задачи, связанные с изучением
человека и окружающего его мира - моделирование мозга, создание новых лекарств,
экологические прогнозы, генная инженерия. Пожалуй, нет ни одной области науки и
техники, начиная от сугубо инженерных дисциплин, кончая гуманитарными науками,
историей и другими, где бы ни были поставлены задачи, требующие сложных
компьютерных вычислений, превосходящие возможности компьютеров, на которых
решаются эти задачи. Это справедливо для всего спектра мира компьютеров, начиная с
мобильных устройств.

Мир компьютерных программ начинает меняться вслед за изменением мира
компьютеров. Многопроцессорность компьютеров требует перехода к параллельным
вычислениям, переходу к качественно новому программированию.

Представьте себе, как изменится игра в футбол, если в игре будет не один мяч, а три
мяча. Представьте себе вратаря, в ворота которого одновременно летят три мяча, - гол
неизбежен. Насколько же усложняется задача программиста, которому требуется
написать эффективную программу для компьютера с сотней процессоров. Ему
необходимо написать такую программу, чтобы все сто процессоров в каждый момент
времени выполняли различные фрагменты кода этой программы, чтобы вычисления
были синхронизированы, чтобы в нужные времена процессоры обменивались
информацией, чтобы действия одного процессора не вступали в конфликт с
действиями других процессоров. Задача эта более сложная, чем игра в футбол с тремя
мячами, или задача дирижера, управляющего оркестром.

Обучение программированию, выработка алгоритмического мышления - сложная
задача. Обучение параллельному программированию еще более сложная задача,
поскольку в параллельном программировании появляется ряд новых проблем, не
свойственных последовательному программированию. Прежде всего, необходимо
решать проблему синхронизации одновременно протекающих процессов. Для
многоядерных компьютеров с общей памятью - память представляет общий ресурс,
доступный всем параллельным процессам. В этом случае необходимо уметь
справляться с проблемой “гонки данных”, когда несколько процессов одновременно
пытаются получить доступ к одному и тому же элементу памяти, пытаясь прочитать

6

или произвести запись нового содержимого в элемент памяти. Пытаясь справиться с
гонкой данных, блокируя доступ к критической секции кода, можно попасть в еще
худшую ситуацию клинча, когда выполнение прекращается из-за взаимной блокировки
процессов. При создании программ для кластеров - компьютеров с раздельной
памятью, объединенных линиями связи для обмена сообщениями, центральной
проблемой становится проблема “Map - Reduce” - проблема распределения данных
между компьютерами кластера и сбора результатов вычислений, произведенных
каждым компьютером. При необходимости передачи данных большого объема вполне
может оказаться, что время, требуемое на передачу данных, съест весь выигрыш,
достигнутый за счет одновременных вычислений на компьютерах кластера.

Переход от последовательных алгоритмов к алгоритмам, допускающим
распараллеливание, построение программ, реализующим реальное распараллеливание,
является сложным делом. Не менее сложным делом является отладка этих программ,
доказательство корректности их работы. Для параллельных программ возможна
ситуация, когда тест, запущенный на одних и тех же данных, дает разные результаты
из-за изменения порядка параллельно протекающих вычислений. Когда работает
параллельный цикл, то все или некоторые итерации цикла выполняются параллельно,
при этом определенный порядок их выполнения не гарантируется. Увеличение
размерности задачи в параллельном мире может гораздо чаще, чем в последовательном
мире, приводить к непредсказуемым результатам.

Работы над созданием языков параллельного программирования ведутся уже давно,
задолго до появления многопроцессорных компьютеров в современном смысле этого
слова. Можно вспомнить язык APL, появившийся в 60-х годах прошлого столетия,
язык Occam и многие другие специализированные языки. Сегодня большинство
современных языков в том или ином виде включают средства, позволяющие
разрабатывать параллельные программы. Теоретические разработки в этом
направлении продолжаются. Следует, однако, признать, что оптимальное решение,
подходящее для разработки параллельных программ для разных типов компьютеров,
для разных алгоритмов, еще не найдено. Несомненно, что широкий переход к
многопроцессорным, многоядерным компьютерам будет способствовать развитию
параллельного программирования.

Данный учебный курс представляет введение в параллельное и многопоточное
программирование. Он знакомит читателя с общими свойствами параллельных
вычислений, моделью параллельных вычислений и ее характеристиками.
Рассматриваются основы построения параллельных алгоритмов, обсуждаются
проблемы параллельных вычислений при их выполнении на многоядерных
компьютерах с общей памятью - гонка данных, клинч, проблемы синхронизации и
блокировки.

В первую очередь курс предназначен для программистов, создающих программы на
языке C#. Все примеры программ, приведенные в данном курсе, написаны на этом
языке с использованием средств параллельного программирования. В курсе
обсуждаются средства, включенные в состав библиотеки классов FCL (Framework Class
Library), начиная от класса Thread, описывающего потоки, до класса Parallel,
включенного в TPL (Task Parallel Library).

7

Следует отметить, что за последние несколько лет появились хорошие учебники,
созданные в России и посвященные параллельному программированию. Большая
заслуга в этом консорциума университетов по суперкомпьютерным технологиям, по
инициативе которого написан ряд учебников, разосланных во многие университеты
страны. Различные учебные материалы по параллельному программированию
доступны в интернете, прежде всего, следует упомянуть такие сайты как: ссылка:
intuit.ru - http://intuit.ru, ссылка: parallel.ru - http://parallel.ru.

8

Параллельные вычисления

Лекция расскажет какие преимущества есть у параллельных вычислений, и какие
проблемы ждут программиста при создании программ, ориентированных на
параллельные вычисления.

Мир параллельных вычислений

Первый вопрос, на который следует дать ответ, - какие вычисления программы на
компьютере следует называть параллельными. Но это не единственный вопрос, на
который хотелось бы получить ответ. Не менее важно понять, зачем вообще
переходить из простого, хорошо знакомого, понятного мира последовательных
вычислений к сложному для понимания миру параллельных вычислений. Какие
преимущества есть у параллельных вычислений, и какие проблемы ждут программиста
при создании программ, ориентированных на параллельные вычисления. Чтобы
ответить на эти вопросы, давайте совершим небольшой экскурс в историю развития
компьютеров.

Первые компьютеры были построены в соответствии с принципами,
сформулированными Фон-Нейманом. Они имели три главных компонента - память,
процессор и некоторый набор внешних устройств, обеспечивающих ввод и вывод
информации.

Память была многоуровневой и для первых компьютеров содержала внешнюю память
и внутреннюю память - оперативную и регистровую. Внешняя память (на магнитных
лентах, перфокартах, дисках) позволяла сохранять программы и данные вне
зависимости от того, включен компьютер или нет. Внутренняя память хранила
информацию только на период сеанса работы с компьютером. При отключении
компьютера содержимое внутренней памяти исчезало.

Для того чтобы программа могла быть выполнена на компьютере, она должна была
быть загружена в оперативную память. Хранилась она там точно также как и данные,
обрабатываемые этой программой. Принцип хранимой в памяти программы - один из
главных принципов Фон-Неймановских компьютеров.

Регистровая память использовалась в момент выполнения вычислений. Прежде, чем
выполнить некоторую операцию над данными, данные должны быть размещены на
регистрах. Этот самый быстрый вид памяти обеспечивал необходимое быстродействие
при выполнении операций над данными.

Выполнение всех операций - операций над данными и операций по управлению
процессом вычислений - осуществлял процессор. Процессор компьютера обладал
определенным набором команд. Этот набор был достаточно универсальным, чтобы
вычислить любую потенциально вычислимую функцию. С другой стороны этот набор
обеспечивал относительную простоту написания программ человеком.

Программы для первых компьютеров представляли последовательность команд,
входящих в допустимый набор команд процессора. Выполнение программы на

9

компьютере осуществлялось достаточно просто. В каждый момент времени на
компьютере выполнялась одна программа. Процессор, в соответствии с программой,
последовательно выполнял одну команду за другой. Все ресурсы компьютера - память,
время процессора, все устройства - были в полном распоряжении программы, и ничто
не могло вмешаться в ее работу (не считая конечно человека). Параллелизма не было и
в помине.

Такая идиллия продолжалась недолго по причине неэффективного использования
ресурсов крайне дорогих в те времена компьютеров. Компьютеры тогда не
выключались, - одна программа сменяла другую.

Достаточно скоро у компьютера наряду с процессором, который стал называться
центральным процессором, появились дополнительные процессоры, в первую очередь
специализированные процессоры устройств ввода-вывода информации, отвечающие за
выполнение наиболее медленных команд. Это дало возможность организации
пакетного режима выполнения программ, когда на компьютере одновременно
выполнялись несколько программ - одна программа могла печатать результаты работы,
другая - выполняться, третья - вводить необходимые ей данные, например с магнитной
ленты или другого внешнего носителя.

Революционным шагом было появление в 1964 году операционной системы фирмы
IBM - OS 360. Появившаяся у компьютера операционная система стала его
полновластным хозяином - распорядителем всех его ресурсов. Теперь программа
пользователя могла быть выполнена только под управлением операционной системы.
Операционная система позволяла решить две важные задачи - с одной стороны
обеспечить необходимый сервис всем программам, одновременно выполняемым на
компьютере, с другой - эффективно использовать и распределять существующие
ресурсы между программами, претендующими на эти ресурсы. Появление
операционных систем привело к переходу от однопрограммного режима работы к
мультипрограммному, когда на одном компьютере одновременно выполняются
несколько программ. Мультипрограммирование это еще не параллельное
программирование, но это шаг в направлении параллельных вычислений.

Мультипрограммирование - параллельное выполнение нескольких программ.
Мультипрограммирование позволяет уменьшить общее время их выполнения.
Под параллельными вычислениями понимается параллельное выполнение одной и той
же программы. Параллельные вычисления позволяют уменьшить время выполнения
одной программы.

Заметим, что наличие у компьютера нескольких процессоров является необходимым
условием для мультипрограммирования. Существование операционной системы,
организующей взаимную работу процессоров, достаточно для реализации
мультипрограммирования. Для параллельных вычислений накладывается
дополнительное требование - это требование к самой программе, - программа должна
допускать возможность распараллеливания вычислений.

Появление операционной системы означало, что компьютер нельзя рассматривать
только как “железо” (память, процессоры, другие устройства). Теперь у него две

10