Параллельное программирование

Оглавление

1.Теория параллельного программирования………………………………………………2

2.Open MP. Что это такое?.................................................................................6

3. Проблемы параллельного программирования………………………………………..9

4. Интерфейс MPI…………………………………………………………………………………………..12

5.Выводы………………………………………………………………………………………………………..14

Параллельное  программирование.

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

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

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

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

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

Предпосылкой  для распараллеливания выражений  служит тот факт, что входящие в  них операции и функции удовлетворяют  некоторым соотношениям, индуцирующим на всем множестве выражений отношение эквивалентности по результатам (например, для арифметических операций - ассоциативность, коммутативность, дистрибутивность). Задача распараллеливания состоит в построении по заданному выражению Е эквивалентного выражения E', которое может быть исполнено за наименьшее число параллельных шагов, где параллельный шаг - это совокупность действий, выполняемых одновременно на разных вычислителях (процессорах). Напр., выражение преобразуется в эквивалентное выражение, исполнение которого осуществляется за 3 параллельных шага. Отношение числа параллельных шагов исполнения к числу последовательных шагов называется ускорением распараллеливания. Любое арифметическое выражение с поперандами может быть вычислено параллельно за О(log n).шагов с использованием п процессоров. Относительная простота алгоритмов распараллеливания выражений позволяет реализовать их автоматически в ЭВМ с помощью специальных программ или аппаратными средствами.

Большее ускорение  может быть получено за счет распараллеливания  обработки структурных данных. В  алгоритмических языках типа алгол или фортран выражения над структурными данными программируются с помощью операторов цикла вида FOR I=A, В, С,DO S, где I - целочисленный параметр цикла,  А - его начальное значение,  В - конечное значение,  С - шаг изменения параметра, S - тело цикла, задающее действия, выполнимые на одном шаге итерации. Для распараллеливания системы вложенных циклов рассматривается n-мерное целочисленное пространство итераций с координатными осями I1, I2, . . ., In. Выполнение K 1-й итерации по параметру Il, K2-й итерации но параметру I2, . . ., К п-й итерации по параметру I п  изображается точкой (K1, . . .,  К n).этого пространства. В пространстве итераций ищется семейство поверхностей, удовлетворяющих условию: все итерации ( К 1, . . ., К  п), лежащие на любой из этих поверхностей, могут выполняться параллельно. Для программного представления параллельной обработки структурных данных необходимы специальные языковые средства. С этой целью разработаны модификации существующих языков программирования (в основном - фортрана), в которые вводятся параллельные операторы циклов, например, вида:

 FOR ALL (I, J, K)/[1:N; 1:L; 1:M],

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

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

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

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

Наиболее  известными и простыми программными механизмами синхронизации являются семафоры и события. Семафор - это  специальная управляющая переменная, принимающая целочисленные значения. Семафор обычно связан с некоторым конфликтным ресурсом. К семафору применимы только две операции Р и V. Если в ходе исполнения процесса встретится операция P(s), где s - семафор, то процесс может продолжаться с уменьшением значения s на 1 только в том случае, когда значение s положительно; в противном случае он приостанавливается и занимает место в очереди q(s).процессов, ждущих соответствующего ресурса. Операция V увеличивает значение s на 1 и возобновляет первый в очереди q(s).процесс.

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

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

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

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

Что такое  OpenMP?

Первая спецификация компилятора OpenMP (Open specifications for Multi-Processing), являющегося развитием провального и ныне забытого проекта ANSI X3H5, появилась в 1997 году и предназначалась для одного из древнейших языков программирования Fortran, на котором некогда было написано большинство "серьезных" вычислительных приложений. В 1998 году появились варианты OpenMP для языков C/C++; стандарт прижился, получил распространение и к настоящему моменту дорос до версии 2.5. Поддержка спецификации есть во всех компиляторах Intel, начиная с шестой версии (OpenMP 2.0 - с восьмой); в компиляторе Microsoft C/C++, начиная с Visual Studio 2005; буквально на днях стало известно о худо-бедно стандартизованном OpenMP-расширении для GCC[OpenMP для GNU-систем, разумеется, существовал и раньше. Но проект GOMP (GNU OpenMP), обеспечивающий полноценное встраивание поддержки OpenMP непосредственно в GCC, появился только сейчас. 18 ноября пришло сообщение о готовности встроить GOMP в свежие билды GCC - ждем с нетерпением! Для линуксоидов, конечно, вручную параллелить код для pthreads - дело привычное, однако полноценная поддержка OpenMP со стороны GNU Project полностью устранит проблему портирования параллельных приложений между ОС, использующими разные модели потоков].

OpenMP идеально портируется. Он не привязывается к особенностям операционной системы и позволяет создавать переносимые приложения, использующие потоки и объекты синхронизации. Вдобавок большинство OpenMP-директив являются (в терминологии С/C++) "прагмами" (#pragma), а потому попросту игнорируются не понимающим их компилятором[Кстати, программисты, учтите: поддержку OpenMP зачастую требуется явно включать ключом в компиляторе! И еще: далеко не все возможности OpenMP сводятся к прагмам], который генерирует из OpenMP-программ вполне корректные, хотя и однопоточные приложения.

OpenMP позволяет работать на нескольких уровнях - либо задавать низкоуровневые объекты вручную, либо указывать, какие переменные являются "общими" и требуют синхронизации, передоверяя собственно синхронизацию компилятору. Благодаря OpenMP программист может вручную определять в коде программы атомные операции.

На мой  взгляд, этих качеств более чем  достаточно, чтобы OpenMP стал таким же стандартом для параллельного программирования, которым является C/C++ для программирования обычного.

Недостатков у OpenMP два. Первый - только сейчас появляющаяся поддержка сообщества Open Source. Второй - относительно жесткая модель программирования, навязываемая программисту[К примеру, совсем не очевидно, как заставить OpenMP-программу работать в режиме "системы массового обслуживания", когда некий "главный" поток принимает поступающие извне задания (скажем, запрос к БД или обращение с веб-серверу) по отдельным потокам. А вручную подобная система делается элементарно].

OpenMP

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

…

# ВыполниЭтотУчастокКодаПараллельно

Действие

…

а компилятор пытается по его замечаниям сориентироваться. Скажем, встретив указание "разбей этот цикл по двум потокам" перед кодом, в котором перебором по всем объектам вычисляется физика и AI, компилятор пробует сгенерировать такой  код, в котором будет действительно  ровно два потока, каждый из них  будет выполнять примерно половину общего объема работы. Язык замечаний в OpenMP развит хорошо, и на нем можно внятно растолковывать те или иные особенности исполнения данного участка программы, добиваясь нужного эффекта[OpenMP позволяет делать практически все то же самое, что доступно пользователю при работе непосредственно с операционной системой, и даже немного больше (вплоть до определения атомных операций над участками кода)]. А можно и не растолковывать, положившись целиком на компилятор - к начинающим OpenMP весьма либерален. Прибавьте сюда поддержку этого начинания корпорацией Intel, являющейся одним из ведущих производителей компиляторов для своих CPU, - и вам станет понятно, почему OpenMP превратился в стандарт де-факто, ожидающий утверждения в комитете по стандартизации ANSI.

Проблемы  параллельного программирования.

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

Грабли первые, самые простые и очевидные, - это  необходимость балансировки загрузки потоков. Скажем, если один поток считает  физику, другой - AI, а третий выводит  на экран текущую сцену, то вполне возможно, что первые два потока управятся со своими делами гораздо  раньше третьего[В играх со сложной графикой так обычно и происходит - "графическая" подсистема тормозит все остальное] и будут вынуждены его дожидаться. И если вычисления в первом потоке составляют 90% общего объема работы, а во втором - 10%, то больше чем 11-процентного увеличения производительности мы от программы не дождемся.

Замечание из этой же серии: если 80% программного кода поддаются распараллеливанию, а 20% - нет, то получить больше 40% прироста производительности от добавления второго ядра (равно  как и более чем пятикратный  выигрыш при любом числе процессоров) невозможно. Прибавьте сюда принципиально  неразделимые ресурсы - например, оперативную  память[Если программу тормозила в первую очередь она и если 90% времени CPU ожидал, пока в кэш не будет залита очередная порция данных, то установка двух процессоров приведет в лучшем случае к тому, что каждый из CPU будет простаивать 95% времени, а выигрыш в быстродействии составит… 5%], - и сразу станет ясно, почему выжать из двухъядерного процессора двукратное превосходство в производительности даже в специализированных программах удается через раз, а в среднем все ограничивается 40–80%. Это не проблема, а скорее, особенность параллельного программирования; тем не менее следует помнить, что параллельность - отнюдь не панацея и что от порядка распределения данных по потокам может зависеть многое.

Грабли вторые - существование разделяемых между  потоками данных. Представим простейшую модельную ситуацию, когда танк попадает под обстрел во время ремонта. В текущий тик времени "в  танк ударила болванка, вот-вот рванет боекомплект" - с танка снимается 70 единиц "здоровья", гибнет водитель и выходит из строя двигатель. Но в тот же тик механику, вторую минуту заменяющему разбитый трак, удается-таки справиться со своей задачей, поэтому танку добавляется 10 единиц "здоровья" и снимаются все ранее полученные повреждения[Знаю, что звучит дико, но в играх и не такое бывает]. И если все происходит действительно одновременно, то окончательное состояние танка получается недетерминированным - у него с равной вероятностью может и убавиться 70 очков, и прибавиться 10; могут и сохраниться все прежние повреждения, и бесследно сгинуть новые - все зависит только от того, "кто последний" записывал "правильные" по его мнению данные в область памяти, соответствующую танку. Вполне может получиться так, что, к примеру, 70 единиц жизни с танка снимут, а повреждения будут устранены. Или наоборот. И это еще в лучшем случае: а что будет, если в ходе попадания той болванки игра посчитает танк уничтоженным и сотрет его из памяти, а тут откуда ни возьмись прибежит механик и заявит, что несуществующему танку нужно прибавить 10 единиц "здоровья"? Катастрофа и вылет программы!

Поэтому для  защиты разделяемых между несколькими  потоками переменных в параллельных программах вводятся специальные объекты  синхронизации, которые позволяют  заблокировать изменение того или  иного объекта двумя потоками одновременно. Делается это примерно так: объект[Объект синхронизации, но вместе с ним - и весь объект (тот же наш игровой танк, например), который этот объект синхронизации защищает] отдается какому-то одному конкретному потоку, а другие желающие получить объект в пользование ставятся в очередь и ждут, пока нужный объект не освободится. Программисты, забывающие это сделать, как раз и наступают на те самые вторые грабли, обладающие пренеприятным свойством незаметно ломать программу. И ломать так, что она обрушивается не в момент "поломки", а минуты через три, когда "сомнительное место" давным-давно затерялось в пучинах кода, причем происходит это каждый раз в новом месте и в новое время.

Грабли третьи: если недостаточное количество объектов синхронизации - зло, ибо программист  рискует заполучить время от времени  глючащую программу, то переизбыток этих объектов - жуткие вериги на шее проекта. Пусть, скажем, практически любой из наших объектов может изменять игровую землю и стремится получить ее для себя. Поскольку принадлежать двум объектам одновременно земля не сможет, то находится она в каждый момент времени только у одного объекта. Который и будет обрабатываться, а всем остальным потокам придется терпеливо ожидать своей очереди. Получится вот такая картинка (рис. 3), где параллельными вычислениями и не пахнет. С этим успешно борются, беря блокировку ровно на то время, пока она действительно необходима (прочитать состояние земли, проверить его и записать новое состояние), но тогда возникают новые грабли - дедлоки. Предположим, что мы угодили снарядом в землю совсем рядышком от стоящего на ней танка. Пострадала и земля, и танк. Программа добросовестно определяет, что, где и как требуется изменить (поменять рельеф земли и изменить "жизни" у танка), берет первый объект синхронизации "на землю", тянется ко второму объекту синхронизации "на танк"… и тут же виснет. В чем дело? Оказывается, этот танк ждет, когда освободится земля, чтобы внести в нее свои изменения. И пока он земли не дождется, он не отдаст блокировку на самого себя, которая нужна потоку, который "держит" блокировку на ту самую землю. Считаете, что подобный дедлок - надуманная штука? Значит, вы никогда не занимались параллельным программированием: подобные ситуации здесь возникают если не на каждом шагу, то, по крайней мере, очень часто. Еще одна ситуация того же рода - один из потоков взял блокировку на что-то, но забыл освободить, а сторонний поток некстати решил это что-то проверить. Отсюда вытекает второе золотое правило "параллельного" программиста - никогда не пытаться обладать двумя объектами одновременно и тщательно проверять, что все однажды взятые объекты своевременно освобождаются.

Неплохой  джентльменский набор, не правда ли? А  сколько занятных вопросов связано  с работой в "параллельном" режиме стандартных библиотек! К  примеру, функция GetHostByAddr в стандартном программном интерфейсе Microsoft, активно использующаяся сетевыми программами, одно время грешила тем, что при ее повторных вызовах с разными адресами из разных потоков выдавала обоим потокам указатель на одну и ту же структуру данных, хотя запрашивали они совсем разное. И если производитель клятвенно заверяет вас, что его библиотека совсем-совсем, ну честно-честно является thread-safe[Безопасной для использования в параллельном режиме], - вспомните, что даже Microsoft нет-нет да и ошибается, модифицируя продукт с десятилетней историей. А о трудности отыскания подобных глюков красноречиво свидетельствует то, сколько потребовалось времени, чтобы GetHostByAddr выловить[Исправили его в Windows XP SP1. Сколько лет он жил никем не замеченный, одному богу известно].

Интерфейс MPI.

Еще один стандарт де-факто в мире параллельных вычислений - пакет MPI (Message Passing Interface), тоже разрабатывавшийся как универсальное средство облегчения жизни разработчику параллельного ПО. Только устроено оно совсем иначе, нежели OpenMP, и ориентировано в основном для других, "более возвышенных" целей.

Идея MPI заключается  в следующем. OpenMP (да и многие другие системы для разработки параллельного ПО) ориентируется на так называемые системы с общей памятью, когда на компьютере запущена всего одна программа (точнее, один процесс), но внутри этого процесса "живет" несколько потоков исполнения, каждому из которых доступна вся память процесса, а стало быть, и все его данные. MPI исходит из другой предпосылки: на компьютере запущено много-много программ (процессов), которые друг с другом напрямую общаться не могут и вынуждены устанавливать контакт через специальные окна или даже внешние каналы связи. Называется все это IPC (Inter-Process Communication) и, как вы уже, наверное, догадались, сильно изменяется от компьютера к компьютеру и от операционной системе к операционной системе. А MPI - попытка стандартизировать связь между процессами, предоставив всем желающим удобную модель запуска на нескольких процессорах тех программ, которые будут коллективно обрабатывать данные, и обеспечивая "почтовые пересылки" между этими программами. Вот и весь Message Passing Interface.

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

Впрочем, при  желании можно использовать MPI и  для обычных двухъядерных процессоров или двухпроцессорных систем - "вотчины" проектов OpenMP. Но, конечно, MPI для таких целей "тяжеловат", - как в плане быстроты исполнения программного кода, которому, в отличие от его OMP-коллег, приходится еще и оплачивать "накладные расходы" на канал связи, так и в плане высокой сложности разработки MPI-приложений. Последние, правда, лишены большинства тех "граблей", которые существуют для обычных систем с распределенной памятью; но зато для написания соответствующего кода от программиста требуется четкое мышление, позволяющее в деталях продумать систему обмена информацией между процессами.

Отладка параллельных приложений

Не говоря даже о том, что когда в программе запущен не один, а несколько потоков, то пошаговая отладка превращается в настоящий кошмар: контрольные точки "ловят" все треды подряд, а шаг одного потока запросто может сопровождаться полусотней шагов соседнего. Главная проблема в отладке параллельных приложений заключается в том, что возникающие там неполадки уникальны. Зачастую они связаны со случайным совпадением каких-то событий в "жизни" слабо связанных друг с другом потоков, а потому проявляются, как говорится, в соответствии с текущей фазой луны, - возникнут раз-другой и бесследно исчезнут. Мало того, иногда присутствие "наблюдателя" (отладочных средств) изменяет результат измерений, поскольку слегка перестраивает "свойства окружающей среды", - вот и вылавливай после этого какой-нибудь плавающий глюк, обусловленный параллельностью.

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

Выводы.

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

Список литературы:

1. Журнал "Компьютерра"
2. http://www.computerra.ru/242551/
3. http://www.viva64.com/ru/t/0038/
4. http://www.intuit.ru/department/se/parallprog/
5. http://it.sander.su/parallel_coding.php