Добавил:

Studfiles2 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Санкт-Петербургский государственный электротехнический университет "ЛЭТИ"

Предмет:

Параллельное программирование

Файл:

Лабораторная работа 3.doc

Скачиваний:

Добавлен:

01.05.2014

Размер:

86.02 Кб

Скачать

☆

Министерство образование и науки РФ

Санкт-Петербургский государственный электротехнический университет

Дисциплина «Параллельное программирование»

Кафедра МОЭВМ

Лабораторная работа №3 ” Организация вычислений на решетке процессорных элементов ”

Выполнил:

студент гр. 3351

Фонарева С.

Преподаватель:

Красюк В.И.

Санкт-Петербург

2008

Задание

Разработать программу, моделирующую буфер типа FIFO на N сообщений, где N – число процессоров. Программа, как минимум, должна моделировать управляющие сигналы «буфер пуст» и «буфер полон».

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

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

Тестирование программы.

Для тестирования программы:

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

попытка обращения к пустой очереди->вывод сообщения “пуста”.
Попытка добавления нового сообщения в заполненную очередь-> очередь переполнена.

освобождение очереди с контролем правильности последовательности сообщений

Организация работы кольца процессоров

Инициализация кольца из N процессоров происходит согласно следующему алгоритму:

Если это процессор 0:

Создать линк (MakeLink) со следующим процессором 1.
Cоздать линк (GetLink) с предыдущим процессором N-1.

Иначе, если это процессор с номером i (0 < i < N):

Создать линк с предыдущим процессором i-1.
Создать линк со следующим процессором (i+1 mod N).

Постановка сообщения в очередь происходит так:

1. Если это процессор 0:

Получить сообщение, если пуст.
Передать сообщение процессору №1, если он пуст.

2. Иначе если это процессор i (0 < i < N):

Получить сообщение от предыдущего процессора
Если (i < N-1), то передать следующему процессору, если он пуст.

Алгоритм изъятия сообщения из очереди:

1. Если это процессор 0:

Передать следующему процессору команду «вытолкнуть сообщение».
Получить от предыдущего процессора сообщение или извещение о пустоте.

2. Иначе если это процессор i (0 < i < N):

Получить от предыдущего команду «вытолкнуть сообщение»
Если (i < N-1), передать команду следующему, дождаться ответа, передать ему свое сообщение (если есть).
Иначе если i = N-1, передать следующему свое сообщение или извещение о пустоте, сообщить предыдущему что пуст и готов принять новое сообщение.

Программа

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <sys/root.h>

#include <sys/link.h>

#include <sys/sys_rpc.h>

#include <unistd.h>

#define QUERY_EMPTY 1

#define REPLY_FULL 2

#define REPLY_EMPTY 3

#define DATA 4

#define EXIT 5

#define PRINT 6

#define POP 7

#define READY 8

#define BUFFER 128

int ProcID, nProcs, error, bExit = 0, bBusy = 0, bLast = 0;

int MesNumber = 0;

LinkCB_t *NextLink, *PrevLink;

char buffer[BUFFER];

void ToNext(void)

{

int mes = QUERY_EMPTY;

if (!bLast)

{ SendLink(NextLink, (byte*) &mes, sizeof(mes));

RecvLink(NextLink, (byte*) &mes, sizeof(mes));

if (mes == REPLY_EMPTY)

{ SendLink(NextLink, buffer, BUFFER);

bBusy = 0;

}

else

bBusy = 1;

}

else bBusy = 1;

}

void Pop(void)

{

int mes = POP;

if (!bLast)

{

/* to move data*/

SendLink(NextLink, &mes, sizeof(mes));

/* Next - to receive*/

RecvLink(NextLink, &mes, sizeof(mes));

/* Move data, if it is.*/

if (bBusy)

ToNext();

}

else

{ if(bBusy)

{mes = REPLY_FULL;}

else mes =REPLY_EMPTY;

SendLink(NextLink, &mes, sizeof(mes));

if (bBusy)

{ SendLink(NextLink, buffer, BUFFER);

bBusy = 0;

}

mes = READY;

SendLink(PrevLink, &mes, sizeof(mes));

}

void output(void)

{

int mes = PRINT;

if (ID == 0)

printf("\nFIFO :");

if (bBusy)

printf("\nProc %d: %s ", ID, buffer);

SendLink(NextLink, &mes, sizeof(mes));

if (ID == 0)

RecvLink(PrevLink, &mes, sizeof(mes));

if (ID == 0)

printf("\n-FIFO end -");

}

int Put(void)

{

if (!bBusy)

{

sprintf(buffer,"MESSG-%d", MesNumber++);

printf("\nAdd new message: %s", buffer);

ToNext();

output();

return 1;

}

printf("\nFIFO is full");

return 0;

}

int Get(void)

{

char Buffer[BUFFER];

int mes = POP;

int res;

SendLink(NextLink, &mes, sizeof(mes));

/* last element- empty/full */

RecvLink(PrevLink, &mes, sizeof(mes));

res = (mes == REPLY_FULL);

if (res)

RecvLink(PrevLink, Buffer, BUFFER);

printf("\nGet message: %s", res ? Buffer : "FIFO is empty\n");

/* second element-ok */

RecvLink(NextLink, &mes, sizeof(mes));

if (bBusy)

ToNext();

output();

return res;

}

void Test(void)

{ int i;

printf("\n get from empty queue:");

Get();

printf("\nFill the queue");

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

{ Put(); }

printf("\n put message to full queue:");

Put();

printf("\nGet messages from queue:");

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

{ Get(); }

printf("\n get message from empty queue:");

Get();

printf("\ntests finished");

}

int main(void)

{

ID = GET_ROOT()->ProcRoot->MyProcID;

nProcs = GET_ROOT()->ProcRoot->nProcs;

char *FName = "main";

int choice, mes;

if (nProcs < 2)

{

printf("\n\nNot enough processors!!!");

AbortServer(1);

}

bBusy = 0;

bLast = (ID == (nProcs - 1));

if (ID == 0)

{

if ( (NextLink = MakeLink((ID+1)%nProcs, 1, &error)) == NULL )

{

LogError(EC_ERROR, FName, "Failed to make link, Proc0, error code %d.\n",

error);

AbortServer(1);

}

if ( (PrevLink = GetLink(nProcs-1, 1, &error)) == NULL )

{

LogError(EC_ERROR, FName, "Failed to get link, Proc0, error code %d.\n",

error);

AbortServer(1);

}

printf("\nProcessor %d: initialized",ID);

printf("\nStart test:\n", ID);

Test();

mes =EXIT;

SendLink(NextLink, &mes, sizeof(mes));

}

else{

if ( (PrevLink = GetLink(ID-1, 1, &error)) == NULL )

{

LogError(EC_ERROR, FName, "Failed to get link, ProcN, error code %d.\n",

error);

AbortServer(1);

}

if ( (NextLink = MakeLink((ID+1)%nProcs, 1, &error)) == NULL )

{

LogError(EC_ERROR, FName, "Failed to make link, ProcN, error code %d.\n",

error);

AbortServer(1);

}

printf("\nProcessor %d: initialized", ID);

while (!bExit)

{

/* Wait command/query */

RecvLink(PrevLink, &mes, sizeof(mes));

switch (mes)

{

case QUERY_EMPTY:

if (bBusy)

{

mes =REPLY_FULL;

SendLink(PrevLink, &mes, sizeof(mes));

}

else

{

mes =REPLY_EMPTY;

SendLink(PrevLink, &mes, sizeof(mes));

RecvLink(PrevLink, buffer, BUFFER);

ToNext();

}

break;

case POP:

Pop();

break;

case PRINT:

output();

break;

case EXIT:

if (!bLast) SendLink(NextLink, &mes, sizeof(mes));

return;

break;

}

printf("\nProcessor %d: exit", ID);

return 0;

}

Результат запуска программы

bash-2.03$ run -f1 3 2 lab3_try.px

run : Creating 3 * 2 descriptor by calling mkdesc.

start booting server

run : Starting D-Server at opus link 1.

Processor 1: initialized

Prcessr 2: initialized

Processor 3: initialized

Processor 4: initialized

Processor 0: initialized

Processor 5: initialized

Start test:

get from empty queue:

Get message: FIFO is empty

------------ FIFO ------------

---- FIFO end ---

Fill the queue

Add new message: MESSG-0

------------ FIFO ------------

Proc 5: MESSG-0

---- FIFO end ---

Add new message: MESSG-1

------------ FIFO ------------

Proc 4: MESSG-1

Proc 5: MESSG-0

---- FIFO end ---

Add new message: MESSG-2

------------ FIFO ------------

Proc 3: MESSG-2

Proc 4: MESSG-1

Proc 5: MESSG-0

---- FIFO end ---

Add new message: MESSG-3

------------ FIFO ------------

Proc 2: MESSG-3

Proc 3: MESSG-2

Proc 4: MESSG-1

Proc 5: MESSG-0

---- FIFO end ---

Add new message: MESSG-4

------------ FIFO ------------

Proc 1: MESSG-4

Proc 2: MESSG-3

Proc 3: MESSG-2

Proc 4: MESSG-1

Proc 5: MESSG-0

---- FIFO end ---

Add new message: MESSG-5

------------ FIFO ------------

Proc 0: MESSG-5

Proc 1: MESSG-4

Proc 2: MESSG-3

Proc 3: MESSG-2

Proc 4: MESSG-1

Proc 5: MESSG-0

---- FIFO end ---

put message to full queue:

FIFO is full

Get messages from queue:

Get message: MESSG-0

------------ FIFO ------------

Proc 1: MESSG-5

Proc 2: MESSG-4

Proc 3: MESSG-3

Proc 4: MESSG-2

Proc 5: MESSG-1

---- FIFO end ---

Get message: MESSG-1

------------ FIFO ------------

Proc 2: MESSG-5

Proc 3: MESSG-4

Proc 4: MESSG-3

Proc 5: MESSG-2

---- FIFO end ---

Get message: MESSG-2

------------ FIFO ------------

Proc 3: MESSG-5

Prc 4: MESSG-4

Proc 5: MESSG-3

---- FIFO end ---

Get message: MESSG-3

------------ FIFO ------------

Proc 4: MESSG-5

Proc 5: MESSG-4

---- FIFO end ---

Get message: MESSG-4

------------ FIFO ------------

Proc 5: MESSG-5

---- FIFO end ---

Get message: MESSG-5

------------ FIFO ------------

---- FIFO end ---

get message from empty queue:

Get message: FIFO is empty

------------ FIFO ------------

---- FIFO end ---

tests finished

Processor 0: exit

///////////////////////////////////////////////////////////////////

bash-2.03$ run -f1 1 4 lab3_try.px

run : Creating 1 * 4 descriptor by calling mkdesc.

start booting server

run : Starting D-Server at opus link 1.

Processor 1: initialized

Processor 2: initialized

Processor 0: initialized

Processor 3: initialized

Start test:

get from empty queue:

Get message: FIFO is empty

------------ FIFO ------------

---- FIFO end ---

Fill the queue

Add new message: MESSG-0

------------ FIFO ------------

Proc 3: MESSG-0

---- FIFO end ---

Add new message: MESSG-1

------------ FIFO ------------

Proc 2: MESSG-1

Proc 3: MESSG-0

---- FIFO end ---

Add new message: MESSG-2

------------ FIFO ------------

Proc 1: MESSG-2

Proc 2: MESSG-1

Proc 3: MESSG-0

---- FIFO end ---

Add new message: MESSG-3

------------ FIFO ------------

Proc 0: MESSG-3

Proc 1: MESSG-2

Proc 2: MESSG-1

Proc 3: MESSG-0

---- FIFO end ---

put message to full queue:

FIFO is full

Get messages from queue:

Get message: MESSG-0

------------ FIFO ------------

Proc 1: MESSG-3

Proc 2: MESSG-2

Proc 3: MESSG-1

---- FIFO end ---

Get message: MESSG-1

------------ FIFO ------------

Proc 2: MESSG-3

Proc 3: MESSG-2

---- FIFO end ---

Get message: MESSG-2

------------ FIFO ------------

Proc 3: MESSG-3

---- FIFO end ---

Get message: MESSG-3

------------ FIFO ------------

---- FIFO end ---

get message from empty queue:

Get message: FIFO is empty

------------ FIFO ------------

---- FIFO end ---

tests finished

Processor 0: exit

Вывод

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

Соседние файлы в предмете Параллельное программирование

#
01.05.2014594.94 Кб101Архитектура параллельных вычислительных систем.doc
#
01.05.201497.79 Кб12Лабораторная работа 0.doc
#
01.05.2014200.7 Кб14Лабораторная работа 1.doc
#
01.05.201465.02 Кб13Лабораторная работа 2.doc
#
01.05.201486.02 Кб12Лабораторная работа 3.doc
#
01.05.2014888.32 Кб45Ответы на экзаменационные вопросы.doc