Многопоточное параллельное программирование

Многопоточное параллельноепрограммированиеЦель работыОсвоение методов и средств построения и реализации многопоточных программ.ВведениеВ настоящее время существуют различные языковые средства представления и реализациипараллельных программ, начиная от низкоуровневых примитивов ОС, специальныхбиблиотек (MPI, PVM и др.), предназначенных для описания и реализациивзаимодействующих параллельных процессов и заканчивая системами параллельногопрограммирования, основанными на высокоуровневых языках представления параллельныхпрограмм.

Примерами последних являются системы функционального параллельногопрограммирования [1, 2], граф-схемного параллельного программирования [3], логическогои объектно-ориентированного параллельного программирования и др.Однако, какая бы парадигма не использовалась для представления параллельных программ,её выполнение сводится к управлению порождающими процессами и взаимодействиямимежду ними.По сути, это использование механизмов организации многокомпонентной параллельнойработы вычислительных машин и систем для описания параллельных программ и процессов.Средства описания параллельных процессов, используемые в MPI и PVM, к примеру,ориентированы в большей степени на вычислительные системы с распределенной памятью.Многопоточное параллельное программирование напротив, пытается воспользоватьсявозможностями более простой организации взаимодействия между процессами,протекающими с использованием общей памяти и разделяемых переменных.Интуитивно, потоки – это в некотором смысле последовательность самостоятельныхдействий (обращений к тем или иным устройствам, независимым вычислениям и др.),взаимодействующих при выполнении программы или, точнее, в рамках процесса ОС,однозначно связанного с выполнением программы.

Потоки – это более простые (почему ихиногда называют легковесными) процессы по сравнению с понятием процесса, которымоперируют ОС.Многопоточное параллельное программирование появилось как реакция на необходимостьэффективного использования многопроцессорных вычислительных систем с общей памятью.К примеру, фирма Intel активно внедряет технологии многопоточного параллельногопрограммирования в связи с выпуском ею многопроцессорных ВС. Отметим, что несмотряна простоту, как самой идеи многопоточного параллельного программирования, так и еёреализацию, многопоточное параллельное программирование требует повышенных усилийот программиста, касающихся обеспечения корректности параллельной программы(однозначности результата её выполнения независимо от временных характеристикиндуцируемых потоков и использования общих переменных), её эффективности (частое"столкновение" потоков при обращении к общим программным и аппаратным ресурсам).1.

Многопоточное программирование: средства и реализацияВ параллельном программировании проектирование программ должно ориентироваться нена выполнение одной задачи в некоторый промежуток времени, а на одновременноевыполнение нескольких задач, на которые предварительно должна быть разбита программа.Главная цель - усовершенствовать программное обеспечение, воспользовавшись принципомпараллельности.Рис.1. Типичная архитектура построения параллельной программы.Средства параллельного программирования позволяют распределить работу программымежду двумя (или больше) процессорами в рамках одного физического или одноговиртуального компьютера. Такую программу можно разбить на процессы (process) илипотоки (thread).

Типичная архитектура построения параллельной программы показана нарис. 1.1.1 Понятие процесса и нитиПараллельность в программе достигается путем разбиения программы на несколькопроцессов или потоков. Несмотря на существование различных вариантов организациилогики программы (например, с помощью объектов или функций), под параллелизмом всеже понимается использование множества процессов и потоков.Процесс (process) — это некоторая часть (единица) работы, создаваемая операционнойсистемой.

Программа может состоять из нескольких процессов. Процесс задается адреснымпространством и идентификатором(id процесса). Процесс состоит из множествавыполняющихся инструкций, размещенных в адресном пространстве этого процесса.Адресное пространство процесса распределяется между инструкциями, данными,принадлежащими процессу, и стеками, обеспечивающими вызовы функций и хранениелокальных переменных.Адресное пространство процесса делится на три логических раздела: текстовый (для кодапрограммы), информационный (для данных программы) и стековый (для стеков программы).Логическая структура процесса показана на рис.

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

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

2.Ресурсы, открытые родительским процессом, немедленно становятся доступными всемпотокам. При этом никакой дополнительной инициализации или подготовки не требуется.Потоки независимы от родителя (создателя) и конкурируют за использование процессора.Создатель процесса или потока управляет своим потомком, т.е.

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

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

На рис. 2 показана схема процесса,который содержит два потока. Как показано на рис. 2, процесс содержит два потока А и В, ихстеки расположены в стековом разделе процесса. Потоки выполняют различные функции:поток А выполняет функцию func1(), а поток В — функцию func2().1.2 Многопоточное программирование.1.2.1 Параллелизм данных (OpenMP)Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMPсистемах в модели общей памяти (shared memory model).

В стандарт OpenMP входятспецификации набора директив компилятора, процедур и переменных среды. До появленияOpenMP не было подходящего стандарта для эффективного программирования на SMPсистемах.Наиболее гибким, переносимым и общепринятым интерфейсом параллельногопрограммирования является MPI (интерфейс передачи сообщений).

Однако модель передачисообщений 1) недостаточно эффективна на SMP-системах; 2) относительно сложна восвоении, так как требует мышления в "невычислительных" терминах. POSIX-интерфейс дляорганизации нитей (Pthreads) поддерживается широко (практически на всех UNIXсистемах), однако по многим причинам не подходит для практического параллельногопрограммирования:••слишком низкий уровень,нет поддержки параллелизма по данным.OpenMP можно рассматривать как высокоуровневую надстройку над Pthreads (илианалогичными библиотеками нитей).

Многие поставщики SMP-архитектур (Microsoft, Intel,Sun, HP, SGI) в своих компиляторах поддерживают спецдирективы дляраспараллеливания циклов. Однако эти наборы директив, как правило, 1) весьмаограничены; 2) несовместимы между собой; в результате чего разработчикам приходитсяраспараллеливать приложение отдельно для каждой платформы. OpenMP является вомногом обобщением и расширением упомянутых наборов директив.За счет идеи "инкрементального распараллеливания" OpenMP идеально подходит дляразработчиков, желающих быстро распараллелить свои вычислительные программы сбольшими параллельными циклами.

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

Директивы OpenMP простоигнорируются последовательным компилятором.Спецификация OpenMP для C/C++, содержит следующую функциональность:••Директивы OpenMP начинаются с комбинации символов "#pragma omp". Директивыможно разделить на 3 категории: определение параллельной секции, разделениеработы, синхронизация. Каждая директива может иметь несколько дополнительных.Компилятор с поддержкой OpenMP определяет макрос "_OPENMP", который можетиспользоваться для условной компиляции отдельных блоков, характерных дляпараллельной версии программы.•••••Распараллеливание применяется к for-циклам, для этого используется директива"#pragma omp for".

В параллельных циклах запрещается использовать операторbreak.Статические (static) переменные, определенные в параллельной области программы,являются общими (shared).Память, выделенная с помощью malloc(), является общей (однако указатель на нееможет быть как общим, так и приватным).Типы и функции OpenMP определены во включаемом файле <omp.h>.Кроме обычных, возможны также "вложенные" (nested) мьютексы - вместологических переменных используются целые числа, и нить, уже захватившаямьютекс, при повторном захвате может увеличить это число.Пример распараллеливания for-цикла в C#pragma omp parallel for private(i)#pragma omp shared(x, y, n)for (i=0; i<n; i++){a = a + x[i];b = b + y[i];}Программная модель OpenMP представляет собой fork-join параллелизм, в котором главныйпоток по необходимости порождает группы потоков, при вхождении программы впараллельные области приложения.1.2.2 Функциональный параллелизм (Posix Threads)Поточно-ориентированная библиотека POSIX (Portable Operating System Interface —интерфейс переносимой операционной системы) содержит набор системных функций,которые в сочетании с языковыми средствами C++ успешно используются для поддержкипараллелизма.