Мiнiстерство освiти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Лабораторна робота №4
з диципліни: «Паралельні і розподілені обчислення»
на тему: «МОЖЛИВОСТІ ВИКОРИСТАННЯ ПАРАЛЕЛЬНИХ АЛГОРИТМІВ»
МЕТА РОБОТИ. Дослідити можливості розв’язання різноманітних задач за допомогою паралельних алгоритмів. Навчитися виділяти незалежні гілки обчислень та виконувати їх паралельно.
Завдання:
5,
19
Запропонувати та відобразити алгоритм реалізації гри “LIFE”. Гра моделює життя деякої колонії живих клітин, які виживають, розмножуються або гинуть згідно наступних умов. Клітина виживає, якщо вона має двох або трьох сусідів з восьми можливих. Якщо у клітини лише один сусід, або немає жодного, то вона гине (від ізоляції). Якщо клітина має більше трьох сусідів, то вона гине (від перенаселення). В будь-якій порожній позиції, яка має рівно трьох сусідів у наступному поколінні з’являється нова клітина. Гра повинна починатися з довільної кількості клітин, що розташовані в ігровому полі випадковим чином (інтерактивний режим задавання вхідних даних) – так звана початкова популяція. Програма повинна коректно завершувати роботу у таких випадках: а).загинула вся популяція, б) на вимогу користувача.
Аналіз задачі та опис незалежних подій.
В даній задачі у нас є залежність по ресурсах, зокрема залежність одних «клітин від інших», тому розпаралелити даний алгоритм не можливо. В даній задачі для кожної комірки матриці – «Клітини» аналізуються сусіди, якщо в порожньої комірки є більше трьох сусіді в ній вона ініціалізується «1», якщо в інціаізованої «1» комірки – більше 3 сусідів вона помирає. Виходячи з цього опису можна сказати, що результат роботи на кожному кроці залежить від існуючих сусідів комірки і це створює конфлікт за ресурсами. Даний алгоритм є повністю послідовним.
5. Текст програми
#include <stdio.h>
#define WIDTH 20
#define HEIGHT 20
void init(int board[][WIDTH], int rows) {
int x, y;
for (y = 0; y < rows; y++)
for (x = 0; x < WIDTH; x++)
board[y][x] = 0;
board[10][10] = 1;
board[10][11] = 1;
board[10][12] = 1;
board[11][10] = 1;
board[11][11] = 1;
board[11][12] = 1;
board[12][10] = 1;
board[12][11] = 1;
board[12][12] = 1;
}
int print(int *board, int rows, int cols)
{
int x, y;
char c;
int ex=0;
for (y = 0; y < rows; y++) {
for (x = 0; x < cols; x++) {
if (*(board + y*cols + x) == 1)
{
printf("%c", 2);
ex = 1;
}
else
printf("%c", 177);
}
printf("\n");
}
if (ex == 0)
return 0;
else
ex = 0;
printf("Press any key to continue or \'q\' - exit:\n");
c=getchar();
if(c == 'q')
return 0;
else
return 1;
}
int count_neighbors(int board[][WIDTH], int rows,
int y, int x)
{
int i, j;
int result = 0;
for (i = -1; i <= 1; i++)
if ((y+i >= 0) && (y+i < rows))
for (j = -1; j <= 1; j++)
if ((x+j >= 0) && (x+j < WIDTH))
if ((i != 0) || (j != 0))
result += board[y+i][x+j];
return result;
}
void step(int board[][WIDTH], int rows) {
int x, y;
int neighbors[HEIGHT][WIDTH];
for (y = 0; y < rows; y++)
for (x = 0; x < WIDTH; x++)
neighbors[y][x] = count_neighbors(board, rows, y, x);
for (y = 0; y < rows; y++)
for (x = 0; x < WIDTH; x++)
if (board[y][x] == 1) {
if (neighbors[y][x] < 2)
board[y][x] = 0;
else if (neighbors[y][x] > 3)
board[y][x] = 0;
}
else {
if (neighbors[y][x] == 3)
board[y][x] = 1;
}
}
int main(void) {
int exit = 1;
int board[HEIGHT][WIDTH];
init(board, HEIGHT);
while (exit) {
exit = print((int*)board, HEIGHT, WIDTH);
step(board, HEIGHT);
}
return 0;
}
6. Результати виконання програми
Висновок
В роботі я використав послідовний алгоритм, який описує гру “Life”. В результаті аналізу задачі я вияснив, що в даному алгоритмі є конфлікт за ресурсами і тому даний алгоритм ...
