МОЖЛИВОСТІ ВИКОРИСТАННЯ ПАРАЛЕЛЬНИХ АЛГОРИТМІВ. Лабораторна робота з Паралельні та розподілені обчислення . Робота № 522141

МОЖЛИВОСТІ ВИКОРИСТАННЯ ПАРАЛЕЛЬНИХ АЛГОРИТМІВ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2013

Тип роботи:

Лабораторна робота

Предмет:

Паралельні та розподілені обчислення

Завантажити

Частина тексту файла (без зображень, графіків і формул):

М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”. В результаті аналізу задачі я вияснив, що в даному алгоритмі є конфлікт за ресурсами і тому даний алгоритм є повністю послідовний.

Лабораторна робота Паралельні та розподілені обчислення

daniel

30.03.2013 22:20

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись