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

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

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ

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

Рік:
2005
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Паралельні та розподілені обчислення

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

Міністерство освіти та науки України Національний університет „Львівська Політехніка” Кафедра ЕОМ ЗВІТ Про виконання лабораторної роботи № 3 з предмету „Паралельні та розподілені обчислення” на тему: „ МОЖЛИВОСТІ ВИКОРИСТАННЯ ПАРАЛЕЛЬНИХ АЛГОРИТМІВ.” м Львів – 2005 Мета: Дослідити можливості розв’язання різноманітних задач за допомогою паралельних алгоритмів. Навчитися виділяти незалежні гілки обчислень та виконувати їх паралельно. Завдання: 11. Лабіринт задається матрицею з’єднань в якій для кожної пари кімнат вказано чи з’єднані вони коридором. Задати (ввести з клавіатури, або генерувати випадковим чином): кількість кімнат лабіринту (n); матрицю з’єднань для них; Побудувати шлях з кімнати з номером i в кімнату з номером j. Припустимо, що нам необхідно знайти шлях з кімнати М у кімнату Н: Оскільки нам невідомий початковий напрям руху при пошуку шляху з кімнати М у кімнату Н, то задача вирішується перебором всіх можливих шляхів з кімнати М. Задача вирішується тоді, коли при переборі шляхів ми натрапляємо на шукану кімнату Н. На прикладі, що зображений ліворуч, помічаємо, що починаючи пошук з кімнати М наступною може бути будь-яка з кімнат 1, 2, 3. Пошук в цих напрямках не залежить один від іншого, тому можна розпаралелити задачу – одночасно вести пошук в трьох напрямках (виділили 3 підзадачі). Після того як, наприклад, ми дійшли до кімнати 1 у нас теж можливе те, що наступною може бути одна з декількох кімнат, які безпосередньо зв’язані з кімнатою 1. Звичайно, що і на цьому етапі можна виконати розпаралелення пошуку шляху. Кількість одночасно перебираємих шляхів безпосередньо залежить (а вірніше рівна) від кількості процесорних елементів. Після того, як ми задали початкову кімнату М – пошук шляхів почнеться одночасно в напрямках М-1-…, М-2-…, М-3-… на трьох процесорних елементах. Якщо ще є вільні процесорні елементи, то, наприклад продовження пошуку шляху по напрямку М-1-… можна знову розпаралелити (якщо з кімнати 1 виходить більше одного шляху). Звичайно, що шляхи пошуку можуть відрізнятись за глибиною (довжиною) – це трапляється, коли ми приходимо в "глухий кут", або перебрали всі можливі шляхи у з певної вершини (а отже на певному процесорному елементі). В такому разі процесорний елемент починає пошук шляху в певному напрямку при розпаралеленні іншої гілки (іншого шляху). Часові (обчислювальні) затрати вирішення задачі залежать насамперед від матриці зв’язків, а не від кількості кімнат (оскільки кількість кімнат може бути великою, а будь-які зв’язки між ними відсутні). Часові затрати залежать від кількості можливих шляхів з початкової кімнати, та від глибини шляхів. На малюнку, що зображено ліворуч існує 9 можливих варіантів проходження з вершини 1 у вершину 9 (у випадку а), "а" у випадку "б" – таких варіантів є 16. Текст програми //вибірковий … var A:array of array of byte; //матриця зв’язків ton,fromn:integer; //початок, кінець found:boolean; //шлях знайдено resultstring:string; //шлях … //Перевірка чи шлях проходив через дану кімнату function checkpath(path:string;n:integer):boolean; var ret:boolean; i:integer; begin ret:=false; for i:=1 to length(path) do if ord(path[i])=n then ret:=true; result:=ret end; //Пошук шляху procedure REK(cn:integer;path:string); var i:integer; temppath:string; begin temppath:=path; if not found then //if found then stop all begin for i:=1 to NewN-1 do //width begin if (i=ton) and (A[cn,i]=1) then begin found:=true; resultstring:=path+chr(i) end; if A[cn,i]=1 then //if n==>i path present if not checkpath(path,i) then begin temppath:=temppath+chr(i); REK(i,temppath) end; temppath:=path; //try other end; end end; … //main resultstring:=''; found:=false; fromn:=strtointdef(form1.edit1.Text,1); ton:=strtointdef(form1.edit2.Text,1); REK(fromn,chr(fromn)); end; Результат виконання програми:  Висновок: У ході виконання лабораторної роботи дослідили можливості розв’язання різноманітних задач за допомогою паралельних алгоритмів. Навчилися виділяти незалежні гілки обчислень та виконувати їх паралельно.
Антиботан аватар за замовчуванням

31.03.2013 14:03-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!
Нічого не вибрано
0%

Оголошення від адміністратора

Антиботан аватар за замовчуванням

Подякувати Студентському архіву довільною сумою

Admin

26.02.2023 12:38

Дякуємо, що користуєтесь нашим архівом!