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

Оглавление 

1 

Министерство образования и науки Российской Федерации 
Сибирский  федеральный университет 
 
Федеральное государственное бюджетное учреждение науки 
«Институт вычислительного моделирования 
Сибирского отделения Российской академии наук» 
 
Сибирский научно-образовательный центр  
суперкомпьютерных технологий 
 
 
 
 
Е. Д. Карепова  
 
ОСНОВЫ  МНОГОПОТОЧНОГО 
И  ПАРАЛЛЕЛЬНОГО  
ПРОГРАММИРОВАНИЯ 
 
Допущено УМО по классическому университетскому образованию в качестве учебного пособия для студентов высших 
учебных заведений, обучающихся по направлениям ВПО 
010400 «Прикладная математика и информатика» и 010300 
«Фундаментальная информатика и информационные технологии», 23 марта 2015 г. 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2016 

Оглавление 

2 

УДК 004.272(07) 
ББК 32.973я73 
         К225 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Карепова, Е. Д. 
К225            Основы многопоточного и параллельного программирования : 
учеб. пособие / Е. Д. Карепова. – Красноярск : Сиб. федер. ун-т, 2016. – 
356 с. 
ISBN 978-5-7638-3385-0 
 
Рассматриваются современные подходы к разработке программного обеспечения для высокопроизводительных параллельных вычислительных систем. 
Приводятся общие сведения об архитектурах современных суперкомпьютеров        
и методах их программирования. Описываются особенности ряда популярных 
средств разработки многопоточных и параллельных программ и их использования для эффективного решения научных и прикладных задач.  
Предназначено для студентов, аспирантов, инженеров и исследователей, 
работающих в области прикладной математики, вычислительной физики и высокопроизводительных параллельных вычислений.  
 
Работа выполнена при частичной поддержке Российского научного фонда 
(проект № 14-11-00147) 
 
 
Электронный вариант издания см.: 
http://catalog.sfu-kras.ru 
УДК 004.272(07)  
ББК 32.973я73 
 
ISBN 978-5-7638-3385-0                                                            © Сибирский федеральный  
                                                                                                          университет, 2016 

Оглавление 

3 

 
 
  ОГЛАВЛЕНИЕ 

 
ПРЕДИСЛОВИЕ .................................................................................................. 5 
ВВЕДЕНИЕ .......................................................................................................... 8 
Г л а в а  1.  ОБЗОР  ОБЛАСТИ  ПАРАЛЛЕЛЬНЫХ  ВЫЧИСЛЕНИЙ ..... 10 
1.1. Основные архитектурные особенности построения  
       параллельной вычислительной среды ............................... 10 
1.2. Основные  классы  современных   
       параллельных  компьютеров .............................................. 17 
1.3. Разработка параллельных приложений ............................. 25 
1.4. Программные средства ........................................................ 29 
1.5. Парадигмы параллельных приложений ............................ 34 
Контрольные вопросы и задания .............................................. 51 
Задачи ........................................................................................... 52 
Г л а в а  2.  ПРОБЛЕМЫ  ПРОГРАММИРОВАНИЯ   
ДЛЯ  ВЫЧИСЛИТЕЛЬНЫХ  СИСТЕМ   
С  ОБЩЕЙ  ПАМЯТЬЮ ............................................................ 54 
2.1. Анатомия потока .................................................................. 54 
2.2. Синхронизация потоков. Оператор ожидания .................. 58 
2.3. Взаимное исключение. Задача критической секции ........ 60 
2.4. Сигнализирующие события. Барьерная  
       синхронизация ...................................................................... 65 
2.5. Семафоры .............................................................................. 73 
2.6. Мониторы ............................................................................. 85 
Контрольные вопросы и задания .............................................. 91 
Задачи ........................................................................................... 93 
Г л а в а  3.  УПРАВЛЕНИЕ  ПОТОКАМИ  
С  ПОМОЩЬЮ  ФУНКЦИЙ  WinAPI ..................................... 95 
3.1. Объекты ядра ........................................................................ 95 
3.2. Процессы ............................................................................. 101 
3.3. Потоки ................................................................................. 108 
3.4. Синхронизация потоков в пользовательском режиме ... 113  
3.5. Синхронизация потоков с помощью объектов ядра ...... 120 
3.6. Проблемы условной синхронизации ............................... 128  
3.7. Проецируемые в память файлы ........................................ 138 
3.8. Совместный доступ процессов  
       к данным через механизм проецирования ...................... 144  
Контрольные вопросы и задания ............................................ 146 
Задачи ......................................................................................... 147 

Оглавление 

4 

Г л а в а  4.  ТЕХНОЛОГИЯ  ПРОГРАММИРОВАНИЯ  OpenMP ............ 153 
4.1. Программная модель OpenMP .......................................... 153 
4.2. Модель памяти OpenMP .................................................... 156 
4.3. Среда выполнения OpenMP-программы ......................... 158 
4.4.  Директива omp parallel ..................................................... 164  
4.5. Распределение работы в параллельной области  
       по нитям .............................................................................. 171 
4.6. Директивы синхронизации ............................................... 191 
4.7. Переменные среды и функции времени выполнения .... 204 
4.8. Спецификации стандарта OpenMP v. 4.0 ........................ 210 
4.9. Оптимизация программ OpenMP ..................................... 212  
4.10. Ограничения OpenMP...................................................... 213  
Контрольные вопросы и задания ............................................ 215 
Задачи ......................................................................................... 215 
Г л а в а  5.  СОГЛАСОВАННОЕ   
ПАРАЛЛЕЛЬНОЕ  ПРОГРАММИРОВАНИЕ ...................... 221 
5.1. Проблемы программирования  
       для вычислительных систем  
       с распределенной памятью ............................................... 221 
5.2. Оценка эффективности параллельных алгоритмов ....... 225 
5.3. Реализация базовых алгоритмов  
       вычислительной математики ............................................ 248 
5.4. Проблемы выбора эффективной  
       параллельной реализации ................................................. 272 
Контрольные вопросы и задания ............................................ 289 
Г л а в а  6.  ОСНОВЫ  ТЕХНОЛОГИИ   
ПРОГРАММИРОВАНИЯ  MPI ............................................... 291 
6.1. Архитектурная парадигма MPI ........................................ 291 
6.2. Обрамляющие и информационные функции MPI .......... 293 
6.3. MPI и крупноблочное распараллеливание ...................... 294 
6.4. Организация вычислений .................................................. 300 
6.5. Организация взаимодействий процессов ........................ 311 
6.6. Повышение эффективности MPI-программ .................... 335 
Контрольные вопросы и задания ............................................ 338 
Задачи ......................................................................................... 340 
БИБЛИОГРАФИЧЕСКИЙ  СПИСОК .......................................................... 347 

Предисловие 

5 

 
 
  ПРЕДИСЛОВИЕ 

 
 
Предлагаемое учебное пособие содержит материал для  
базового курса «Параллельное программирование», который охватывает 
широкий круг вопросов, связанных с высокопроизводительными вычислениями, а также отражает содержание нескольких спецкурсов, которые на 
протяжении ряда лет читаются автором в Институте математики и фундаментальной информатики Сибирского федерального университета и аспирантуре Института вычислительного моделирования СО РАН.  
Пособие можно разделить на три части: общие аспекты параллельного 
программирования; программирование для параллельных вычислительных 
систем (ПВС) с общей памятью; программирование для систем с распределенной памятью. В каждой части сначала обсуждаются проблемы, порождаемые архитектурой соответствующей вычислительной системы (ВС), 
теоретические основы решения этих проблем, затем подробно рассматривается языковая реализация всех базовых механизмов. Как теоретический, так 
и практический материал проиллюстрирован большим количеством примеров, многие из которых давно уже стали классикой параллельного программирования. 
В первой главе рассматриваются основные особенности параллельного программирования. Приводится краткая классификация основных  
видов архитектур ПВС, и подчеркивается необходимость использования 
разнообразных методов написания параллельных программ в зависимости 
от типа архитектуры. Здесь же дан краткий перечень существующих программных средств, методов написания параллельных программ, а также 
факторов, определяющих те или иные приемы распараллеливания. 
Во второй главе более подробно описываются особенности разработки программ для ПВС с общей памятью. Дается определение потока, 
рассматриваются основные состояния, в которых может находиться поток. 
Приводятся сведения о создании параллельных потоков и методах решения проблем, порождаемых необходимостью их синхронизации (взаимного исключения, барьерной синхронизации, условного ожидания), вводятся 
основные синхропримитивы, используемые при многопоточном программировании. Подробно рассмотрено использование семафоров и мониторов. 
Обсуждаются способы решения классических задач многопоточного программирования (задачи о критической секции, кольцевом буфере, философах, читателях и писателях).  

Предисловие 

6 

Третья глава посвящена практическому применению потоков для 
операционной системы Windows с использованием WinAPI. Дается общее 
понятие объекта ядра ОС Windows, процесса и потока. Приводится описание общей структуры создаваемой многопоточной программы. Обсуждаются особенности реализации проблемы взаимного исключения потоков 
одного процесса, т. е. потоков, находящихся в общем адресном пространстве 
(синхронизация в пользовательском режиме), и общий случай синхронизации потоков, относящихся, может быть, к разным процессам, с помощью 
объектов ядра. Рассмотрен один из простых механизмов организации связи 
между потоками разных процессов, например, для обмена данными. Автор 
благодарит аспиранта Г. А. Федорова за помощь в отборе материала и отладке кода ряда примеров. 
Технология OpenMP создания параллельных программ для ВС с общей памятью обсуждается в четвертой главе. В отличие от реализации 
многопоточности в языке Си с помощью функций WinAPI, или библиотек 
Pthread, или Qt библиотека OpenMP в большей степени рассчитана               
на прикладного программиста, позволяя быстро создавать короткие и простые 
многопоточные приложения с помощью директив компилятора из последовательного кода. Знание основ технологии OpenMP полезно еще и по той 
причине, что ее современные реализации обеспечивают поддержку программирования для комбинированных ПВС, содержащих как общую, так  
и распределенную память. 
Общие сведения о разработке параллельных программ для систем           
с распределенной памятью на основе механизма передачи сообщений       
приводятся в пятой главе. Кратко обсуждаются вопросы, связанные с исследованием информационных зависимостей и оценками внутреннего         
параллелизма алгоритмов, даются понятия ускорения, эффективности, 
масштабируемости. На ряде примеров показаны различные стратегии использования вычислительных ресурсов ПВС, взаимодействующих между 
собой через механизм передачи сообщений. Рассмотрены достоинства            
и недостатки каждого из подходов. Описаны двухточечные и коллективные взаимодействия процессов, подходы к оценке времени, необходимого 
на передачу сообщений в кластерных системах. В конце главы рассмотрены основные задачи вычислительной математики и схемы возможных          
параллельных алгоритмов для их решения. 
В шестой главе рассмотрены основы программирования для ВС           
с распределенной памятью с помощью библиотеки MPI, которая соответствует всем требованиям одноименного стандарта средств организации  
передачи сообщений (message passing interface – MPI). Описана архитектурная парадигма MPI, ее связь с крупноблочным распараллеливанием. 
Обсуждаются  вопросы организации вычислений (использование комму

Предисловие 

7 

никаторов, производных типов, виртуальных топологий) и взаимодействий 
процессов (двухточечные и коллективные обмены, операции приведения           
и барьерной синхронизации). Отметим, что хотя в тексте и приведены синтаксис и характеристика большинства функций MPI для языка Си, главу не 
следует рассматривать как описание стандарта MPI. Все вводимые концепции, понятия и методы проиллюстрированы примерами. Автор благодарит А. В. Малышева за предоставленный материал и полезные обсуждения по теме главы. 
Знания и навыки, полученные при изучении курса, позволяют            
в дальнейшем перейти к более детальному освоению инструментальных 
средств разработки параллельных программ и методов эффективного распараллеливания практических и научных задач. 
Базовый курс «Параллельное программирование» читается в Институте математики и фундаментальной информатики Сибирского федерального университета в течение восьми лет. В это же время автором читались 
и более узконаправленные спецкурсы и курсы для магистрантов и аспирантов, материалы которых также включены в пособие.  
Следует отметить, что при разработке курса и подготовке настоящего 
учебного пособия автором использовались, прежде всего, учебные пособия 
и монографии [1, 2, 9–14, 25–27, 34, 35, 48], материалы по параллельному 
программированию, представленные на порталах [77, 82], а также электронный курс [68] «Многопроцессорные вычислительные системы и параллельное  программирование», разработанный под руководством профессора В. П. Гергеля в Нижегородском госуниверситете им. Н. И. Лобачевского.  
Автор благодарит за полезные обсуждения члена-корреспондента 
РАН В. В. Шайдурова, профессора А. В. Старченко, профессора А. И. Легалова, Д. А. Кузьмина, а также признателен за помощь и участие Андрею Малышеву, Юрию Шанько, Георгию Федорову, Екатерине Дементьевой и Марине Вдовенко.  
Работа выполнена при частичной поддержке Российского научного 
фонда (проект № 14-11-00147). 

Введение 

8 

  
 
  ВВЕДЕНИЕ 

 
 
Сегодня многопоточное и параллельное программирование применяется не только для научных вычислений, но и в повседневных 
областях человеческой деятельности. Это обуславливается массовым переходом производителей микропроцессоров на многоядерные архитектуры. 
Любой современный персональный компьютер является параллельной вычислительной системой, а многие приложения – суть многопроцессные 
(или многопоточные). Многие научные и промышленные предприятия        
используют для повседневных нужд высокопроизводительные вычислительные системы, состоящие из десятков тысяч процессорных узлов.  
Очевидно, что при разработке параллельных программ необходимо 
применять методы, обеспечивающие эффективное использование предоставляемых вычислительных ресурсов. Однако разнообразие архитектур 
ПВС привело к тому, что в настоящее время не существует языка, позволяющего создавать программы, легко и эффективно переносимые с одной         
архитектуры на другую.  
Первоначально виделось, что использование языков последовательного программирования обеспечит универсальный путь для написания      
параллельных приложений. Однако быстро выяснилось, что такой подход 
обладает рядом недостатков: 
● Прямое распараллеливание последовательных программ часто не 
обеспечивает достижения приемлемого уровня параллелизма из-за ограничений, обусловленных принципиально последовательными реализациями 
алгоритмов и стереотипами последовательного мышления. 
● В большинстве языковых средств для реализации параллелизма 
необходимо явно формировать все параллельные фрагменты и следить            
за корректной синхронизацией процессов. 
● Допустимость использования в языках «ручного» управления           
памятью может привести к конфликтам между процессами в борьбе за общий ресурс. 
● Разработанные программы оказываются жестко привязанными               
к конкретной архитектуре или к семейству архитектур (дальнейшая смена 
поколений вычислительных систем или появление новых, более эффективных, архитектур ведут к потере разработанного ПО и/или необходимости его переработки, что не раз случалось на различных этапах развития 
программирования). 
● Существует излишняя детализация ведения вычислений, поскольку 
кроме управления, связанного с непосредственным преобразованием дан

Введение 

9 

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

Г л а в а  1.  Обзор области параллельных вычислений 

10 

 
Г л а в а  1   ОБЗОР  ОБЛАСТИ  
  ПАРАЛЛЕЛЬНЫХ  ВЫЧИСЛЕНИЙ 

 
 
 
В главе обсуждается широкий круг тем, связанных с параллельным программированием. Рассмотрены принципы, положенные          
в основу параллельной обработки данных, проблемы классификации современных суперкомпьютеров, особенности их архитектуры. Изложены 
вопросы, связанные с проектированием параллельных приложений, описаны 
и проиллюстрированы на классических примерах их главные парадигмы.  
 
 
1.1. Основные  архитектурные особенности  
построения параллельной вычислительной среды 
 
Следуя [9], выделим два основных фактора, определяющих бурное 
развитие вычислительной техники на пути увеличения производительности вычислительных систем, уменьшения их размеров, а также расширения круга решаемых задач: 1) развитие элементной базы; 2) совершенствование архитектуры.  
Сравним характеристики (табл. 1.1) одного из первых компьютеров 
мира – EDSAC, появившегося в 1949 году в Кембридже, – и одного процессора современного суперкомпьютера Roadrunner1, инсталлированного            
в 2008 году в Лос-Аламосской национальной лаборатории (США).  
За 60 лет тактовая частота процессора выросла в тысячи раз, а производительность увеличилась в сотни миллионов. Ясно, что основное увеличение производительности обусловлено не наращиванием мощности процессора, а использованием новых решений в архитектуре компьютеров.    
Архитектуру однопроцессорного компьютера принято называть        
архитектурой фон Неймана (рис. 1.1). Она была логичным решением2 проблемы создания первой электронной машины с запоминаемой программой 
                                           
1 Суперкомпьютер Roadrunner создан компанией IBM для Министерства энергетики США и установлен в Лос-Аламосской национальной лаборатории в НьюМексико, США. Roadrunner первым в мире преодолел на тесте Linpack рубеж производительности в 1 PFlop/s.  
2 В 1948–1950 гг. в Советском Союзе независимо от Джона фон Неймона под 
руководством Сергея Александровича Лебедева была разработана и реализована 
МЭСМ (малая электронная счетная машина), основанная на сходных идейных и архитектурных принципах.