СКИПОД ответы на билеты (1127807), страница 11

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

Текст из файла (страница 11)

[править] Синхронизация параллельных процессов.

[2]

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

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

В MPI также возможна синхронизация между парами процессов при помощи синхронных (небуферизированных) send/receive.

[править] Алгоритм Деккера

wikipedia:ru:Алгоритм Деккера

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

Процессы объявляют о намерении войти в критическую секцию; это проверяется внешним циклом «while». Если другой процесс не заявил о таком намерении, в критическую секцию можно безопасно войти (вне зависимости от того, чья сейчас очередь). Взаимное исключение всё равно будет гарантировано, так как ни один из процессов не может войти в критическую секцию до установки этого флага (подразумевается, что, по крайней мере, один процесс войдёт в цикл «while»). Это также гарантирует продвижение, так как не будет ожидания процесса, оставившего «намерение» войти в критическую секцию. В ином случае, если переменная другого процесса была установлена, входят в цикл «while» и переменная turn будет показывать, кому разрешено войти в критическую секцию. Процесс, чья очередь не наступила, оставляет намерение войти в критическую секцию до тех пор, пока не придёт его очередь (внутренний цикл «while»). Процесс, чья очередь пришла, выйдет из цикла «while» и войдёт в критическую секцию.

Алгоритм Деккера гарантирует взаимное исключение, невозможность возникновения deadlock или starvation. Рассмотрим, почему справедливо последнее свойство. Предположим, что p0 остался внутри цикла «while flag[1]» навсегда. Поскольку взаимная блокировка произойти не может, рано или поздно p1 достигнет своей критической секции и установит turn = 0 (значение turn будет оставаться постоянным пока p0 не продвигается). p0 выйдет из внутреннего цикла «while turn ≠ 0» (если он там находился). После этого он присвоит flag[0] значение true и будет ждать, пока flag[1] примет значение false (так как turn = 0, он никогда не выполняет действия в цикле «while»). В следующий раз когда p1 попытается войти в критическую секцию, он будет вынужден исполнить действия в цикле «while flag[0]». В частности, он присвоит flag[1] значение false и будет исполнять цикл «while turn ≠ 1» (так как turn остаётся равной 0). Когда в следующий раз управление перейдёт к p0, он выйдет из цикла «while flag[1]» и войдёт в критическую секцию.

Если модифицировать алгоритм так, чтобы действия в цикле «while flag[1]» выполнялись без проверки условия «turn = 0», то появится возможность starvation. Таким образом, все шаги алгоритма являются необходимыми.

[править] Алгоритм банкира

wikipedia:Banker's algorithm

Ресурсы выдаются процессу, если их хватит для завершения. По частям раздавать нет смысла.

[править] Исполняемые комментарии в языках программирования.

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

[править] Система Open MP.

OpenMP (Open Multi-Processing) это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с единой памятью на языках C, C++ и Fortran.

Разработку спецификации OpenMP ведут несколько крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB).

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

Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка — прагм. Например, участок кода на языке Fortran, который должен исполняться несколькими потоками, каждый из которых имеет свою копию переменной N, предваряется следующей директивой: !$OMP PARALLEL PRIVATE(N)

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

Ключевыми элементами OpenMP являются

• конструкции для создания потоков (директива parallel),

• конструкции распределения работы между потоками (директивы DO/for и section),

• конструкции для управления работой с данными (выражения shared и private),

• конструкции для синхронизации потоков (директивы critical, atomic и barrier),

• процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num),

• переменные окружения (например, OMP_NUM_THREADS).

Ниже приведены примеры программ с использованием директив OpenMP: Fortran 77

В этой программе на языке Fortran создается заранее неизвестное число потоков (оно определяется переменной окружения OMP_NUM_THREADS перед запуском программы), каждый из которых выводит приветствие вместе со своим номером. Главный поток (имеющий номер 0) также выводит общее число потоков, но только после того, как все они «пройдут» директиву BARRIER.

PROGRAM HELLO

INTEGER ID, NTHRDS

INTEGER OMP_GET_THREAD_NUM, OMP_GET_NUM_THREADS

C$OMP PARALLEL PRIVATE(ID)

ID = OMP_GET_THREAD_NUM()

PRINT *, 'HELLO WORLD FROM THREAD', ID

C$OMP BARRIER

IF ( ID .EQ. 0 ) THEN

NTHRDS = OMP_GET_NUM_THREADS()

PRINT *, 'THERE ARE', NTHRDS, 'THREADS'

END IF

C$OMP END PARALLEL

END

В этой программе на языке С два вектора (a и b) складываются параллельно десятью потоками.

#include <stdio.h>

#include <omp.h>

#define N 100

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

{

float a[N], b[N], c[N];

int i;

omp_set_dynamic(0); // запретить библиотеке openmp менять число потоков во время исполнения

omp_set_num_threads(10); // установить число потоков в 10

// инициализируем векторы

for (i = 0; i < N; i++)

{

a[i] = i * 1.0;

b[i] = i * 2.0;

}

// вычисляем сумму векторов

#pragma omp parallel shared(a, b, c) private(i)

{

#pragma omp for

for (i = 0; i < N; i++)

c[i] = a[i] + b[i];

}

printf ("%f\n", c[10]);

return 0;

}

OpenMP поддерживается многими коммерческими компиляторами.

1. Компиляторы Sun Studio поддерживают официальную спецификацию — OpenMP 2.5 [2] - с улучшенной производительностью под ОС Solaris; поддержка Linux запланирована на следующий релиз.

2. Visual C++ 2005 поддерживает OpenMP в редакциях Professional и Team System [3].

3. GCC 4.2 поддерживает OpenMP, а некоторые дистрибутивы (такие как Fedora Core 5 gcc) включили поддержку в свои версии GCC 4.1.

4. Intel C Compiler

5. IBM XL compiler

6. PGI (Portland group)

7. Pathscale

8. HP

[править] Пакет MPI.

Проект стандарта MPI (Message Passing Interface) представляет собой стандартный набор библиотечных интерфейсов для передачи сообщений.

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

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

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

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

[править] Язык Фортран-GNS.

http://www.keldysh.ru/papers/2006/prep08/prep2006_08.html

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

Характеристики

Список файлов ответов (шпаргалок)