Міністерство освіти і науки України Національний університет «Львівська політехніка» Лабораторна робота №2 з дисципліни: «Технології розподілених систем та паралельних обчислень» Варіант - 6 Тема роботи: Розподілене програмування на основі технології MPI. Мета роботи: Оволодіти практичними прийомами розробки паралельних алгоритмів та розподілених програм за допомогою технології MPІ, дослідити їх переваги при розв’язанні практичних задач. Завдання: Знаходження шляху на графі з допомогою алгоритму Лі. Виконання. Код програми: #include <iostream> #include <string> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <time.h> #include <dos.h> #include <windows.h> #include <mpi.h> using namespace std; #include <stdio.h> #define FALSE 0 #define TRUE 1 #define NROWS 6 #define MCOLS 6 // Symbols: // '.' = open // '#' = blocked // 'S' = start // 'G' = goal // '+' = path // 'x' = bad path char maze[NROWS][MCOLS] = { { 'S', '.', '.', '.', '#', '#' }, { '#', '.', '#', '.', '.', '.' }, { '#', '.', '#', '#', '.', '#' }, { '.', '.', '#', '.', '#', '#' }, { '#', '.', '.', '.', '#', 'G' }, { '#', '.', '#', '.', '.', '.' } }; void display_maze(void); int find_path(int x, int y); int main(void) { //MPI_Init(&argc, &argv); //MPI_Comm_size(MPI_COMM_WORLD, &size); // Розмір комунікатора //MPI_Comm_rank(MPI_COMM_WORLD, &myrank); // Одержуємо наш номер clock_t t = clock(); display_maze(); if (find_path(0, 0) == TRUE) printf("Success!\n"); else printf("Failed\n"); display_maze(); int i; cin >> i; clock_t t1 = clock(); cout << "TIME: " << (t1 - t) / 1000 << "ms" << endl; //MPI_Finalize(); system("pause"); return 0; } void display_maze(void) { int i; printf("MAZE:\n"); for (i = 0; i < NROWS; i++) printf("%.*s\n", MCOLS, maze[i]); printf("\n"); return; } int find_path(int x, int y) { // If x,y is outside maze, return false. if (x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1) return FALSE; // If x,y is the goal, return true. if (maze[y][x] == 'G') return TRUE; // If x,y is not open, return false. if (maze[y][x] != '.' && maze[y][x] != 'S') return FALSE; // Mark x,y part of solution path. maze[y][x] = '+'; // If find_path North of x,y is true, return true. if (find_path(x, y - 1) == TRUE) return TRUE; // If find_path East of x,y is true, return true. if (find_path(x + 1, y) == TRUE) return TRUE; // If find_path South of x,y is true, return true. if (find_path(x, y + 1) == TRUE) return TRUE; // If find_path West of x,y is true, return true. if (find_path(x - 1, y) == TRUE) return TRUE; // Unmark x,y as part of solution path. maze[y][x] = 'x'; return FALSE; } Програма в роботі: Без використання MPI: / З використанням MPI: / mpi працює швидше. Хоча опрацьовувались не велика кількість даних, але отримано результат.