- •1.Вычислительные процессы. Формальная модель. Свойства процесса.
- •2.Система процессов. Независимые процессы. Взаимодействие процессов.
- •3. Классы параллельных вс.
- •4.Отображение системы процессов. Синхронизация.
- •5.Показатели параллельных вс и вычислений.
- •6.Модель вычислений в виде графа "операции-операнды".
- •7.Схема параллельного выполнения алгоритма.
- •8.Определение времени выполнения параллельного алгоритма.
- •9.Теоретические оценки времени выполнения параллельных алгоритмов.
- •10.Показатели эффективности параллельного алгоритма.
- •11.Оценка максимально достижимого параллелизма. Анализ масштабируемости параллельных вычислений.
- •12.Процессы и потоки.
- •13. Закон Амдала.
- •14.Mpi: Стандарт mpi. Общие понятия. Области связи и коммуникаторы.
- •15.Общие процедуры mpi: Инициализация, Завершение.
- •16.Общие процедуры mpi: Определение общего числа параллельных процессов в группе. Определение номера процесса в группе.
- •17.Mpi: Прием/передача сообщений между отдельными процессами.
- •18.Mpi: Групповые (коллективные) взаимодействия. Рассылка целого сообщения процессам. Сборка данных от процессов.
- •19.Mpi: Групповые (коллективные) взаимодействия: Рассылка частей сообщения процессам. Сборка частей сообщения с процессов.
- •20.Mpi: Функции поддержки распределенных операций: Выполнение глобальных операций с возвратом результатов в главный процесс. Выполнение глобальных операций с возвратом результатов во все процессы.
- •21.Mpi: Синхронизация процессов.
- •22.OpenMp: Общие понятия. Область применения.
- •23.Директивы OpenMp: Директивы для определения параллельной области.
- •24.OpenMp: Директивы для распределения вычислений внутри параллельной области: Директива for.
- •25.OpenMp: Директивы для распределения вычислений внутри параллельной области: Директива sections.
- •26.OpenMp: Директивы для распределения вычислений внутри параллельной области: Объединение директив parallel и for (sections).
- •27.Классическая задача об обедающих философах.
- •28.Задача «читатели и писатели».
- •29.Язык параллельного программирования Okkam: основные конструкции и приемы программирования.
- •30.Язык параллельного программирования Linda: основные конструкции и приемы программирования.
- •31.Язык параллельного программирования Ada: основные конструкции и приемы программирования.
25.OpenMp: Директивы для распределения вычислений внутри параллельной области: Директива sections.
Директива single.
Параллелизм на уровне независимых фрагментов оформляется в OpenMP с помощью директивы SECTIONS : END SECTIONS:
!$OMP SECTIONS
< фрагмент 1>
!$OMP SECTIONS
< фрагмент 2>
!$OMP SECTIONS
< фрагмент 3>
!$OMP END SECTIONS
В данном примере программист описал, что все три фрагмента информационно независимы, и их можно исполнять в любом порядке, в частности, параллельно друг другу. Каждый из таких фрагментов будет выполнен какой-либо одной нитью.
Если в параллельной секции какой-то участок кода должен быть выполнен лишь один раз (такая ситуация иногда возникает, например, при работе с общими переменными), то его нужно поставить между директивами SINGLE : END SINGLE. Такой участок кода будет выполнен нитью, первой дошедшей до данной точки программы.
26.OpenMp: Директивы для распределения вычислений внутри параллельной области: Объединение директив parallel и for (sections).
Следует отметить, что если в блоке директивы parallel нет ничего, кроме директивы for, то обе директивы можно объединить в одну
#include <omp.h>
#define NMAX 1000
main () {
int i, j, sum;
float a[NMAX][NMAX];
<инициализация данных>
#pragma omp parallel for shared(a) \
private(i,j,sum)
{
for (i=0; i < NMAX; i++) {
sum = 0;
for (j=0; j < NMAX; j++)
sum += a[i][j];
printf ("Сумма строки %d равна %f\n",i,sum);
} /* Завершение параллельного фрагмента */
}
Пример использования объединенной директивы parallel for
Параметрами директивы for являются:
schedule (type [,chunk])
ordered
nowait
private (list)
shared (list)
firstprivate (list)
lastprivate (list)
reduction (operator: list)
так же, как и для директивы for, в случае, когда в блоке директивы parallel присутствует только директива sections, то данные директивы могут быть объединены.
total = 0;
#pragma omp parallel sections shared(a,b) \
private(i,j)
{
/* Вычисление сумм строк и общей суммы */
for (i=0; i < NMAX; i++) {
sum = 0;
for (j=i; j < NMAX; j++)
sum += a[i][j];
printf ("Сумма строки %d равна %f\n",i,sum);
total = total + sum;
}
#pragma omp section
/* Копирование матрицы */
for (i=0; i < NMAX; i++) {
for (j=i; j < NMAX; j++)
b[i][j] = a[i][j];
}
} /* Завершение параллельного фрагмента */
printf ("Общая сумма матрицы равна %f\n",total);
Пример использования объединенной директивы parallel sections
27.Классическая задача об обедающих философах.
За круглым столом расставлены пять стульев, на каждом из которых сидит определенный философ .
В центре стола – большое блюдо спагетти, а на столе лежат пять вилок (B1..B5) – каждая между двумя соседними тарелками. Каждый философ может находиться только в двух состояниях – либо он размышляет, либо ест спагетти. Начать думать философу ничто не мешает. Но чтобы начать есть, философу нужны две вилки: одна в правой руке, другая в левой. Закончив еду, философ кладет вилки слева и справа от своей тарелки и опять начинает размышлять до тех пор, пока снова не проголодается.
Существует множество различных формулировок данной задачи, в одной из которых философы интерпретируются как процессы, а вилки – как ресурсы. Задача «обедающие философы» удобна для изучения тупиковых ситуаций в системах параллельных процессов.
4. Задача об обедающих философах.
Пять философов сидят за круглым столом. Между ними по вилке. Каждый ест двумя вилками. Каждый некоторе время думает, затем пытается поесть. Нужно смоделировать их поведение. Программа должна избегать ситуации, когда все голодны, но каждый взял по вилке – сл-но ни один не может взять обе вилки.
Цикл будет такой
While True do
Begin
// думаем
sleep(random(1000));
//берем вилки
// едим
sleep(random(1000));
//отдаем вилки
end;
Каждая вилка – семафор (или критическая секция).можно завести массив семафоров. Чтобы не было взаимной блокировки, нужно чтобы были философы которые сначала берут правую вилку и были, которые берут левую. Например, четные и нечетные.
В представленной задаче имеются две опасные ситуации: ситуация голодной смерти и ситуации голодания отдельного философа. Ситуация голодной смерти возникает в случае, когда философы одновременно проголодаются и одновременно попытаются взять, например, свою левую вилку. В данном случае возникает тупиковая ситуация, так как никто из них не может начать есть, не имея второй вилки. Для исключения ситуации голодной смерти были предложены различные стратегии распределения вилок.
Ситуация голодания возникает в случае заговора двух соседей слева и справа против философа, в отношении которого строятся козни. Заговорщики поочередно забирают вилки то слева, то справа от него. Такие согласованные действия злоумышленников приводят жертву к вынужденному голоданию, так как он никогда не может воспользоваться обеими вилками.
