Архитектура современного компьютера

параллелизма по данным HPF
Модель с общей памятью OpenMP.

которых имеет собственное локальное адресное пространство

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

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

Обобщение и стандартизация различных библиотек передачи сообщений привели в 1993 году к разработке стандарта MPI (Message Passing Interface).

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

для реализации

------------------------------------------------------------
В настоящее время практически не существует реализаций MPI, в которых в полной мере обеспечивается совмещение обменов с вычислениями.
------------------------------------------------------------

неподъемным для полной реализации.

Предусматривается развитие в следующих направлениях:

Динамическое создание и уничтожение процессов

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

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

явная передача сообщений или явная синхронизация

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

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

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

специфицировать общие данные и упорядочивать доступ к ним с помощью средств синхронизации

Появление большого количества языков программирования, реализующих данную концепцию, например Modula-2, ADA

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

Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMP-системах (SSMP,ccNUMA, etc.) в модели общей памяти (shared memory model).

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

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

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

Параллельная программа представляет собой систему нитей (threads), взаимодействующих посредством общих переменных и примитивов синхронизации.
Нить — легковесный процесс, имеющий с другими нитями общие ресурсы, включая общую оперативную память.
Эта модель может использоваться только на многопроцессорных системах с общей памятью или с DSM (Distributed Shared Memory — распределенная общая память)

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

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

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

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

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

На каждом уровне вложенности циклов тела циклов могут выполняться независимо друг от друга. Чтобы распараллелить приведенный код вставим прагму #pragma omp parallel for перед самым внешним циклом, так как это даст наибольший выигрыш в производительности. В распараллеленном цикле переменные array, array1, array2 и dim являются общими для потоков, а переменные i, j, k являются частными для каждого потока. Приведенный выше код теперь становится таким:

for (i = 0; i < dim; i++)
{ for (j = 0; j < dim; j++)
{ for (k = 0; k < dim; k++)
{array[i][j] += array1[i][k] * array2[k][j];}
}
}

#pragma omp parallel for shared(array, array1, array2, dim) private(i, j, k)
for (i = 0; i < dim; i++)
{ for (j = 0; j < dim; j++)
{ for (k = 0; k < dim; k++)
{array[ii[j] = array1[i][k] * array2[k][jj;}
}
}

ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ OPENMP

message;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &n);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (rank= =0)
{ printf (“\n Hello from process %3d”, rank);
for (i=1;i { MPI_Recv(&message,1,MPI_INT, MPI_ANY_SOURCE,MPI_ANY_TAG,MPI_COMM_WORLD, &Status);
printf (“\n Hello from process %3d”, message);
}
}
else MPI_Send(&rank,1,MPI_INT, 0,0,MPI_COMM_WORLD);
MPI_Finalize ();
Return 0;
}

myrank,np,I,n,y,s1,s2,x(20),a(10),b(10),m=n/2;
File *dat,*res;
dat=fopen(“d: ,”r”);
res=fopen(“d: “,”w”);
MPI_Init(&argc,&argv);
MPI_Status status;
MPI_Comm_size(MPI_COMM_WORLD,&np);
MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
If (myrank==0)
{ //input array X from file
………..
//Divide array X into two arrays A and B
For (i=0; I{A[i]=X[i];
B[i]=X[i+n/2];
}
m=n/2;
MPI_Send(A[0],m,MPI_INT,1,98,MPI_COMM_WORLD);
MPI_Send(B[0],m,MPI_INT,2,99,MPI_COMM_WORLD);
MPI_Recv(S1,1,MPI_INT,1,97,MPI_COMM_WORLD, MPI_Status *status);