ШПОРА1

Параллелизм за счет нескольких процессов

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

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

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

Применение параллелизма для повышения производительности

Многопроцессорные системы существуют уже десятки лет, но до недавнего времени они использовались исключительно в суперком­пьютерах, больших ЭВМ и крупных серверах. Однако ныне произ­водители микропроцессоров предпочитают делать процессоры с 2, 4, 16 и более ядрами на одном кристалле, а не наращивать произво­дительность одного ядра. Поэтому все большее распространение по­лучают настольные компьютеры и даже встраиваемые устройства с многоядерными процессорами. Увеличение вычислительной мощи, в этом случае связано не с тем, что каждая отдельная задача работа­ет быстрее, а с тем, что несколько задач исполняются параллельно.

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

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

Когда параллелизм вреден?

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

Кроме того, прирост производительности может оказаться мень­ше ожидаемого: с запуском потоков связаны неустранимые наклад­ные расходы, потому что ОС должна выделить ресурсы ядра и память для стека и сообщить о новом потоке планировщику, а на все это тре­буется время. Если задача, исполняемая в отдельном потоке, завер­шается быстро, то может оказаться, что в общем времени ее работы доминируют именно накладные расходы на запуск потока, поэтому производительность приложения в целом может оказаться хуже, чем если бы задача исполнялась в уже имеющемся потоке.

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

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

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

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

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

Тем самым, для параллельного выполнения в алгоритмах решения вычислительных задач достаточно выделять только крупные независимые части расчетов, что, в свою очередь, снижает сложность построения параллельных методов вычислений и уменьшает потоки передаваемых данных между компьютерами кластера. Вместе с этим следует отметить, что организация взаимодействия вычислительных узлов кластера при помощи передачи сообщений обычно приводит к значительным временным задержкам, и это накладывает дополнительные ограничения на тип разрабатываемых параллельных алгоритмов и программ. Отдельные исследователи обращают особое внимание на отличие понятия кластера от сети компьютеров. Для построения локальной компьютерной сети, как правило, используют более простые сети передачи данных (порядка 100 Мбит/сек). Компьютеры сети обычно более рассредоточены, и пользователи могут применять их для выполнения каких-либо дополнительных работ.

Однопроцессорные системы

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

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

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

Существует три способа запустить задачу в приложениях, составленных на языке программирования C. Во-первых, можно использовать фукнцию CreateThread XE "CreateThread" , которая входит в программный интерфейс операционной системы Microsoft Windows NT. Этот способ предоставляет наибольшие возможности по управлению запущенными задачами, позволяя, в частности, присваивать запущенным задачам атрибуты защиты и создавать задачи в приостановленном состоянии.

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

В-третьих, можно запустить задачу при помощи функции beginthreadex XE.

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

Показатели эффективности параллельного алгоритма.

Ускорение, получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется как отношение времени решения задач на скалярной ЭВМ к времени выполнения параллельного алгоритма.

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

При практическом применении данных показателей для оценки эффективности параллельных вычислений следует учитывать следующие два важные момента:

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

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

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

Методы синхронизации вычислений и обмена сообщениями.

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

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

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

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

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

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

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

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

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

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

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

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

Требования к критическим секциям:

1. В любой момент времени только один процесс должен находиться в своей критической секции;

2. Ни один процесс не должен бесконечно долго находиться в своей критической секции;

3. Ни один процесс не должен бесконечно долго ожидать разрешение на вход в свою критическую секцию. В частности:

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

5. Если два процесса хотят войти в свои критические секции, то принятие решения о том, кто первым войдет в критическую секцию, не должно быть бесконечно долгим;

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

Атомарный доступ семейства Interlocked функций

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

Атомарные операции – это группа особых функций, названия которых начинаются с префикса Interlocked, позволяет выполнить операцию так что её выполнение не может быть прервано другим потоком. Работа interlocked функций зависит от того какая используется платформа. На x86-процессорах они выдают по шине аппаратный сигнал, закрывая для других процессоров конкретный адрес памяти. Являются высокопроизводительными операциями по атомарному обновлению значения размером dword или pointer.

function InterlockedIncrement( var Addend: Integer ): Integer; stdcall; Функция увеличивает переменную Addend на 1.

function InterlockedDecrement( var Addend: Integer ): Integer; stdcall; Функция уменьшает переменную Addend на 1.

function InterlockedExchange( var Target: Integer; Value: Integer ): Integer; stdcall; Функция записывает в переменную Target значение Value и возвращает предыдущее значение Target

function InterlockedCompareExchange( var Destination: Pointer; Exchange: Pointer; Comperand: Pointer ): Pointer; stdcall; Функция сравнивает значения Destination и Comperand. Если они совпадают, значение Exchange записывается в Destination. Функция возвращает начальное значение Destination.

function InterlockedExchangeAdd( Addend: PLongint; Value: Longint ): Longint; stdcall; Функция добавляет к переменной, на которую указывает Addend значение Value и возвращает начальное значение Addend.

Синхронизация потоков с использованием объектов ядра

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

Ядро операционной системы

Ядро – центральная часть операционной системы, управляющая выполнение процессов, ресурсами вычислительной системы и предоставляющая процессам координированный доступ к этим ресурсам. Основными ресурсами являются: процессорное время, память, устройство ввода-вывода.

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

Объекты ядра не создаются для каждого процесса отдельно. Если два процесса пытаются создать каждый по одному экземпляру одного и того же объекта ядра, то первый действительно создаст его, а второй будет подключен к уже созданному. Для того, чтобы создать объект ядра, приложение должно вызвать соответствующая функцию winApi. Имена функций создающих объекты ядра стандартны: имя состоит из префикса create, за которым следует полное либо сокращенное имя объекта ядра. В числе параметров функции создания объекта ядра всегда имеется параметр. Этот параметр определяет из каких процессов может быть доступен создаваемый объект ядра. Функция создания объекта ядра возвращает значение описателя объекта(handle).

Каждый объект ядра имеет счётчик числа пользователей. Если программа создаёт новый объект ядра, то ОС создаст его и установит счётчик =1. Если же при попытке создать объект ядра он сущ, счётчик увелич на единицу. Когда программа перестаёт нуждаться в объекте ядра, она должна вызвать api функцию close handle, передав ей в качестве параметра handle объекта. Вызов close handle приводит к тому, что счётчик числа пользователей объекта уменьшается на единицу. Если счётчик становится равным 0, то ОС автоматически удаляет объект.

ПП использованием OpenMP

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

Важные положительные моменты этой технологии:

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

2. Сложность разработки параллельной программы с использованием OpenMP в значительной степени согласуется со сложностью решаемой задачи.

В случае синхронизации потока слэш-процессов, каждый из объектов может находиться либо в свободном, либо в занятом состоянии – non-single stand. Переход из одного состояния в другой осуществляется по правилам, определенным для каждого из объектов ядра. Например объект ядра процесс сразу после создания всегда находится в занятом состоянии. В момент завершения процесса операционная система автоматически освобождает его объект ядра "процесс", и он навсегда остается в этом состоянии.

Объект ядра "процесс" пребывает в занятом состоянии, пока выполняется сопоставленный с ним процесс, и переходит в свободное состояние, когда процесс завершается. Внутри этого объекта поддерживается булева переменная, которая при создании объекта инициализируется как FALSE ("занято"). По окончании работы процесса операционная система меняет значение этой переменной на TRUE, сообщая тем самым, что объект свободен.

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

Wait-функция

В случае ошибки процедура возвращает WAIT_FAILED, а подробности поможет узнать GetLastError. В случае успеха возвращается WAIT_OBJECT_0, если мы дождались перехода объекта в сигнальное состояние, и WAIT_TIMEOUT, если отвалились по таймауту. Также мы можем получить WAIT_ABANDONED. Это происходит в случае, если нить, державшая мьютекс, завершилась, не освободив его. В этом случае мьютекс становится залочен текущей нитью, но целостность данных, доступ к которым ограничивался мьютексом, по понятным причинам находится под вопросом.

Основы технологии OpenMP

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

Количество потоков определяется в начале выполнения параллельных фрагментов программы и обычно совпадает с количеством имеющихся вычислительных элементов в системе; изменение количества создаваемых потоков может быть выполнено при помощи целого ряда средств OpenMP. Все потоки в параллельных фрагментах программы последовательно перенумерованы от 0 до np–1, где np есть общее количество потоков. Номер потока также может быть получен при помощи функции OpenMP.

Организация взаимодействия параллельных потоков.

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

В OpenMP взаимоисключение может быть организовано при помощи неделимых (atomic) операций, механизма критических секций (critical sections) или специального типа семафоров – замков (locks).

Основные понятия параллельной программы: фрагмент, область, секция

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

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

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

Параллельная секция (parallel section) – часть параллельного фрагмента, выделяемая для параллельного выполнения при помощи директивы section

Пп на основе mpi - massage passing interface

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

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

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

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

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

Основные понятия и определения.

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

Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода. Данный программный код, представленный в виде исполняемой программы, должен быть доступен в момент запуска параллельной программы на всех используемых процессорах. Исходный программный код для исполняемой программы разрабатывается на алгоритмических языках C или Fortran с применением той или иной реализации библиотеки MPI.

Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI -программ и в ходе вычислений не может меняться без применения специальных, но редко задействуемых средств динамического порождения процессов и управления ими, появившихся в стандарте MPI версии 2.0. Все процессы программы последовательно перенумерованы от 0 до p-1, где p есть общее количество процессов. Номер процесса именуется рангом процесса.

Программа 5.2. Параллельная программа суммирования числовых значений

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include "mpi.h"

int main(int argc, char* argv[]){

double x[100], TotalSum, ProcSum = 0.0;

int ProcRank, ProcNum, N=100, k, i1, i2;

MPI_Status Status;

// Инициализация

MPI_Init(&argc,&argv);

MPI_Comm_size(MPI_COMM_WORLD,&ProcNum);

MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank);

// Подготовка данных

if ( ProcRank == 0 ) DataInitialization(x,N);

// Рассылка данных на все процессы

MPI_Bcast(x, N, MPI_DOUBLE, 0, MPI_COMM_WORLD);

// Вычисление частичной суммы на каждом из процессов

// на каждом процессе суммируются элементы вектора x от i1 до i2

k = N / ProcNum;

i1 = k * ProcRank;

i2 = k * ( ProcRank + 1 );

if ( ProcRank == ProcNum-1 ) i2 = N;

for ( int i = i1; i < i2; i++ )

ProcSum = ProcSum + x[i];

// Сборка частичных сумм на процессе с рангом 0

if ( ProcRank == 0 ) {

TotalSum = ProcSum;

for ( int i=1; i < ProcNum; i++ ) {

MPI_Recv(&ProcSum,1,MPI_DOUBLE,MPI_ANY_SOURCE,0, MPI_COMM_WORLD, &Status);

TotalSum = TotalSum + ProcSum;

}

}

else // Все процессы отсылают свои частичные суммы

MPI_Send(&ProcSum, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);

// Вывод результата

if ( ProcRank == 0 )

printf("\nTotal Sum = %10.2f",TotalSum);

MPI_Finalize();

return 0;

}