Задача обедающих философов

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

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

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

// Семафоры доступа к вилкам

Semaphore fork[5] = { 1, 1, 1, 1, 1 };

// Поток -философ (для всех философов одинаковый)

Prilosopher(){

// i – номер философа

while (1) { P(fork[i]); // Доступ к левой вилке P(fork[(i+1)%5]); // Доступ к правой вилке <Питание>

// Освобождение вилок

V(fork[i]); V(fork[(i+1)%5])

<Размышление> } }

(выражение (i+1)%5 определяет номер правой вилки, % есть операция получения остатка от целого деления в алгоритмическом языке С).

2. Коллективті мәлімет алмасу функциялары. Редукция мысалдары.

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

- Синхронизацию всех процессов с помощью барьеров (MPI_Barrier);

- Коллективные коммуникационные операции, в число которых входят: рассылка информации от одного процесса всем остальным членам некоторой области связи (MPI_Bcast); сборка (gather) распределенного по процессам массива в один массив с сохранением его в адресном пространстве выделенного (root) процесса (MPI_Gather, MPI_Gatherv); сборка (gather) распределенного массива в один массив с рассылкой его всем процессам некоторой области связи (MPI_Allgather, MPI_Allgatherv); разбиение массива и рассылка его фрагментов (scatter) всем процессам области связи (MPI_Scatter, MPI_Scatterv); совмещенная операция Scatter/Gather (All-to-All), каждый процесс делит данные из своего буфера передачи и разбрасывает фрагменты всем остальным процессам, одновременно собирая фрагменты, посланные другими процессами в свой буфер приема (MPI_Alltoall, MPI_Alltoallv).

- Глобальные вычислительные операции (sum, min, max и др.) над данными, расположенными в адресных пространствах различных процессов: с сохранением результата в адресном пространстве одного процесса (MPI_Reduce); с рассылкой результата всем процессам (MPI_Allreduce); совмещенная операция Reduce/Scatter (MPI_Reduce_scatter); префиксная редукция (MPI_Scan);

Отличительные особенности коллективных операций: 1)Коллективные коммуникации не взаимодействуют с коммуникациями типа точка-точка. 2)Коллективные коммуникации выполняются в режиме с блокировкой. Возврат из подпрограммы в каждом процессе происходит тогда, когда его участие в коллективной операции завершилось, однако это не означает, что другие процессы завершили операцию. 3)Количество получаемых данных должно быть равно количеству посланных данных. 4)Типы элементов посылаемых и получаемых сообщений должны совпадать. 5) Сообщения не имеют идентификаторов.

3. Параллельді векторларды скаляр көбейту программасын жазыңыз

int main(int argc,char **argv)

{

int size,rank,i,n=6;

float *a,*b;

a=new float[n];

b=new float[n];

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

{

a[i]=i+1;

b[i]=i+1;

}

MPI_Status status;

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&rank);

MPI_Comm_size(MPI_COMM_WORLD,&size);

float f=0,s=0,s1=0;

int nachalo,konec,shag;

shag=n/(size-1);

if(rank!=size-1)

{

nachalo=rank*shag;

konec=rank*shag+shag;

for(i=nachalo;i<konec;i++)

s=s+a[i]*b[i];

MPI_Send(&s,1,MPI_FLOAT,size-1,1,MPI_COMM_WORLD);

}

if(rank==size-1){

for(i=0;i<size-1;i++)

{ MPI_Recv(&s,1,MPI_FLOAT,i,1,MPI_COMM_WORLD,&status);

f=f+s; }

printf("%f\n",f);

}

MPI_Finalize();}

Сурак

3. 2 өлшемді Лаплас теңдеуін 2-өлшемді декомпозиция тәсілімен программалау.

1. Қазіргі параллель архитектуралы компьютерлер. Аппараттық бөлімі.

Основным параметром классификации параллельных компьютеров является наличие общей (SMP) или распределенной памяти (MPP). Нечто среднее между SMP и MPP представляют собой NUMA-архитектуры, где память физически распределена, но логически общедоступна. Кластерные системы являются более дешевым вариантом MPP. При поддержке команд обработки векторных данных говорят о векторно-конвейерных процессорах, которые, в свою очередь могут объединяться в PVP-системы с использованием общей или распределенной памяти. Программная часть архитектуры параллельных компьютеров:

1. SISD (Single Instruction Single Data) – единственный поток команд и единственный поток данных. По сути дела это классическая машина фон Неймана. К этому классу относятся все однопроцессорные системы.

2. SIMD (Single Instruction Multiple Data) – единственный поток команд и множественный поток данных. Типичными представителями являются матричные компьютеры, в которых все процессорные элементы выполняют одну и ту же программу, применяемую к своим локальным данным.

3. MISD (Multiple Instruction Single Date) – множественный поток команд и единственный поток данных. М. Флинн не смог привести ни одного примера реально существующей системы, работающей на

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

4. MIMD (Multiple Instruction Multiple Date) – множественный поток команд и множественный поток данных. К этому классу относятся практически все современные многопроцессорные системы.

2. MPI_Cart_create() функциясын қолдану мысалы.

Для создания декартовой топологии (решетки) в MPI предназначена функция: int MPI_Cart_create(MPI_Comm oldcomm, int ndims, int *dims, int *periods, int reorder, MPI_Comm *cartcomm). 1. oldcomm - исходный коммуникатор. 2. ndims - размерность декартовой решетки 3. dims - массив длины ndims, задает количество процессов каждом измерении решетки. 4. periods - массив длины ndims, определяет, является ли решетка периодической вдоль каждого измерения. 5.reorder - параметр допустимости изменения нумерации процессов 6. cartcomm – создаваемый коммуникатор с декартовой топологией процессов.

int dims[3]={0,0,0}, periods[3]={0,0,0},coords[3], ndims=3, reorder=0; ; MPI_Cart_create(MPI_COMM_WORLD,ndims,dims,periods,reorder,&cartcomm);

5 08сурак

3. 3 өлшемді Лаплас теңдеуін 2-өлшемді декомпозиция тәсілімен программалау.

1. Қазіргі параллель архитектуралы компьютерлер. Программалық бөлімі.

2. MPI_Dims_create() функциясын қолдану мысалы.

В декартовой топологии функция MPI_DIMS_CREATE помогает пользователю выбрать выгодное распределение процессов по каждой координате в зависимости от числа процессов в группе и некоторых ограничений, определеных пользователем. Эта функция используется, чтобы распределить все процессы (размер группы MPI_COMM_WORLD) в n-мерную топологическую среду. int MPI_Dims_create(int nnodes, int ndims, int *dims)nnodes количество узлов решетки (целое), ndims число размерностей декартовой решетки(целое), dims - целочисленный массив размера ndims, указывающий количество вершин в каждой размерности.

int dims[2]={0,0},ndims=2;

MPI_Dims_create(size, ndims, dims);

Сурак

3. Санды полиномдылыққа тексеру параллельді программасын жазыңыз.

1. Shared & distributed memory архитектуралары.

Распределенная общая память (DSM - Distributed Shared Memory)

Традиционно распределенные вычисления базируются на модели передачи сообщений, в которой данные передаются от процессора к процессору в виде сообщений. Удаленный вызов процедур фактически является той же самой моделью (или очень близкой). DSM - виртуальное адресное пространство, разделяемое всеми узлами (процессорами) распределенной системы. Программы получают доступ к данным в DSM примерно так же, как они работают с данными в виртуальной памяти традиционных ЭВМ. В системах с DSM данные перемещаются между локальными памятями разных компьютеров аналогично тому, как они перемещаются между оперативной и внешней памятью одного компьютера. Конфигурация — с распределенной разделяемой памятью, представляет собой вариант распределенной памяти. Здесь все узлы, состоящие из одного или нескольких процессоров, подключенных по схеме SMP, используют общее адресное пространство. Отличие этой конфигурации от машины с распределенной памятью в том, что здесь любой процессор может обратиться к любому участку памяти. Однако, время обращения к разным участкам памяти для каждого процессора различно в зависимости от того, где участок физически расположен в кластере. По этой причине такие конфигурации еще называют машинами с неоднородным доступом к памяти NUMA (non-uniform memory access).

NUMA (Non-Uniform Memory Access) – это архитектура совместного доступа к памяти в многопроцессорных системах, в которой время доступа к участку памяти определяется его расположением относительно процессора. Как и в случае с большинством других свойств процессорных систем, невнимание к особенностям архитектуры может привести к ухудшению работы памяти. К счастью, существует возможность нивелировать проблемы в работе, связанные с характерными особенностями NUMA-архитектур и даже использовать некоторые её преимущества для улучшения работы приложений. Это касается привязки потоков к процессорам, распределения памяти с использованием неявных методов, а также применения системных API для привязки ресурсов и перемещения страниц между узлами вычислительной системы.

2. Нүкте-нүкте коммуникациялары. MPI_Bsend(), MPI_Brecv функцияларын қолдану мысалдары.

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

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

int MPI_Bsend(void *buf, int count, MPI_Datatype datatype,int dest, int tag, MPI_Comm comm)

buf-адрес начала расположения пересылаемых данных; count– число пересылаемых элементов; datatype – тип посылаемых элементов; dest–номер процесса-получателя в группе, связанной с коммуникатором comm; tag–идентификатор сообщения (аналог типа сообщения функций nread и nwrite PSE nCUBE2); comm – коммуникатор области связи.

MPI_Bsend(&buffer, buffsize, MPI_INT, 1, TAG, MPI_COMM_WORLD);

Сурак