Лабораторная работа 4 (Решение задачи поиска кратчайшего пути в обыкновенном графе с учетом веса рёбер (Захаров))

Посмотреть архив целиком

Национальный Исследовательский Университет

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

Институт автоматики и вычислительной техники

Кафедра прикладной математики

Лабораторная работа № 4

Решение задачи поиска кратчайшего пути

в обыкновенном графе с учетом веса рёбер

Курс «Параллельные системы и параллельные вычисления»




Выполнил

студент 5 курса группы А-13-08

Захаров Антон

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

Панков Николай Александрович


Постановка задачи

Пусть дана матрица смежности графа :

Требуется найти путь минимальной длины из начальной вершины в конечную .

Для нахождения кратчайшего пути необходимо составить последовательно-параллельную программу на языке C или C++, использующую принципы нитевого распараллеливания, а также исследовать характеристики разработанной программы в зависимости от числа исполнителей.



Тестирование проводились на компьютере со следующей конфигурацией:

ПРОЦЕССОР Intel Core i5 2500MHz Ivy Bridge

ОПЕРАТИВНАЯ ПАМЯТЬ 16Gb DDR3 1600MHz

ФИЗИЧЕСКИЙ НАКОПИТЕЛЬ OCZ-VERTEX3 (120Gb, SATA600, SSD)

ГРАФИЧЕСКИЙ ПРОЦЕССОР AMD Radeon HD 7700 (1Gb DDR5 4.6GHz)

ОПЕРАЦИОННАЯ СИСТЕМА Windows 7 Ultimate x64 (SP1)



Последовательный алгоритм решения

Алгоритм Флойда-Уоршелла

Один из нескольких алгоритмов, высчитывающих кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа на ряду с алгоритмами Дейкстры, Джонсона и Данцига.

Пусть вершины графа пронумерованы от до и введено обозначение для длины кратчайшего пути от до , который кроме самих вершин , проходит только через вершины . Очевидно, что – длина (вес) ребра , если таковое существует (в противном случае его длина может быть обозначена как ).

Существует два варианта значения :

  1. Кратчайший путь между , не проходит через вершину , тогда

  2. Существует более короткий путь между i,\;j, проходящий через k, тогда он сначала идёт от до , а потом от до . В этом случае, очевидно,

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

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения , . Полученные значения являются длинами кратчайших путей между вершинами . Алгоритм можно легко дополнить для получения интересующего пути, добавив вычисление матрицы предшествования .


  1. for (k = 0; k < n; k++) {

  2. for (i = 0; i < n; i++) {

  3. for (j = 0; j < n; j++) {

  4. if(M[i][j] > M[i][k] + M[k][j]) {

  5. P[i][j] = P[k][j];

  6. M[i][j] = M[i][k] + M[k][j];

  7. } } } }

Параллельный алгоритм решения

В данной работе предложена параллельная реализация алгоритма Флойда-Уоршелла: матрица смежности и исходная матрица предшествования делятся между потоками, каждый поток вычисляет по одной полосе фиксированного размера двух искомых матриц (матрицы весов кратчайших путей и матрицы предшествования). На каждой k-ой итерации осуществляется синхронизация потоков и повторная обработка матриц потоками.


Результаты вычислительного эксперимента

Число вершин 100


Число
потоков

Время
решения1
(сек)

Ускорение

1

0,0544

1,0000

2

0,0309

1,7627

3

0,0246

2,2153

4

0,0204

2,6607

5

0,0200

2,7151

6

0,0218

2,4954

7

0,0213

2,5541

8

0,0214

2,5446

9

0,0212

2,5689

10

0,0211

2,5801

11

0,0235

2,3119

12

0,0225

2,4204








Время

(сек)

Зависимость времени решения задачи от числа потоков

Число

потоков





Ускорение

Зависимость ускорения параллельного решения от числа потоков

Число

потоков


Число вершин 1000


Число
потоков

Время
решения2
(сек)

Ускорение

1

4,3253

1,0000

2

2,3451

1,8444

3

1,5679

2,7586

4

1,2814

3,3756

5

1,2740

3,3952

6

1,2332

3,5074

7

1,2493

3,4621

8

1,2532

3,4514

9

1,3427

3,2214

10

1,3270

3,2595

11

1,3520

3,1993

12

1,3602

3,1800





Время

(сек)

Зависимость времени решения задачи от числа потоков

Число

потоков





Ускорение

Зависимость ускорения параллельного решения от числа потоков

Число

потоков




Число вершин 5000


Число
потоков

Время
решения
(сек)

Ускорение

1

398,8928

1,0000

2

224,9230

1,7735

3

157,5963

2,5311

4

120,8167

3,3016

5

123,4528

3,2311

6

125,5733

3,1766

7

124,2586

3,2102

8

125,3230

3,1829

9

130,0439

3,0674

10

136,1236

2,9304

11

140,7151

2,8348

12

143,6665

2,7765





Время

(сек)

Зависимость времени решения задачи от числа потоков

Число

потоков





Ускорение

Зависимость ускорения параллельного решения от числа потоков

Число

потоков






Приложение. Код программы.

// Отключение предупреждений безопасности

#define _CRT_SECURE_NO_WARNINGS

#define _CRT_SECURE_NO_DEPRECATE

#define _CRT_NONSTDC_NO_DEPRECATE


// Коды ошибок

#define E_THREAD_ALLOC 1

#define E_THREAD_CREATE 2


#include

#include

#include

#include

#include

#include

#include

#include

#include

#include



// --- Настройки программы ---


// Включение режима отладки

// #define DEBUG


// Число запусков теста

#define TEST_COUNT 5


// Ограничения на генерируемые веса рёбер

#define MIN_WEIGHT 1

#define MAX_WEIGHT 9


// Связность графа

#define DENSITY 0.80


// Число вершин графа

#define V_SIZE 5000


// Тип числа вершин в графе

typedef int vsize;


// Тип весов рёбер графа

typedef int weight;


// Путь к файлу логов

#define LOG_PATH "lab.log"


// Определение бесконечного веса ребра

#define INF 10000



// --- Настройки потоков ---


// Ограничения на число потоков

#define MIN_THREADS 1

#define MAX_THREADS 12



weight get_random(weight a, weight b, float density, weight inf);

vsize gen_random(vsize a, vsize b);

void print_log(const char *message, ...);

void print_err(const char *message);


DWORD WINAPI MyThreadFunction(LPVOID lpParam);


// Структура данных потока

typedef struct ThreadData {

int i; // Номер потока

} TDATA, *PTDATA;


weight **M;

vsize **P;


// Число вершин графа G=(V,E), |V|=n

vsize n = V_SIZE;


// Пути к файлам матрицы смежности, запросов и результата

const char *M_path = "M.txt"; FILE *Mstream;

const char *Q_path = "query.txt"; FILE *Qstream;

const char *R_path = "result.txt"; FILE *Rstream;

const char *L_path = "lab.log"; FILE *Lstream;


// Числа строк матрицы M, обрабатываемые потоками

vsize Wrows[MAX_THREADS];


// Номера строк матрицы M, обрабатываемые потоками

vsize Nrows[MAX_THREADS];


vsize k;


int _tmain()

{

srand((UINT32) time(NULL));

vsize i, j, p, h;


// Номера начальной и конечной вершин искомого пути

vsize Vstart, Vend;


// Время выполнения каждого из запусков программы

double time[TEST_COUNT];


PTDATA pDataArray[MAX_THREADS];

DWORD dwThreadIdArray[MAX_THREADS];

HANDLE hThreadArray[MAX_THREADS];


// Запускаем программу для 1, 2, ..., MAX_THREADS потоков

for(int threads = MIN_THREADS; threads <= MAX_THREADS; threads++)

{

// Запускаем тест TEST_COUNT раз

for(h = 0; h < TEST_COUNT; h++)

{

// Фиксируем время начала работы программы

time[h] = (double) clock();


// Пытаемся открыть файлы с матрицей смежности и запросов

Mstream = fopen(M_path, "r");

Qstream = fopen(Q_path, "r");

// Обработка ошибок при открытии файлов

if(Mstream == NULL || Qstream == NULL)

{

if((Mstream != NULL && fclose(Mstream)) || (Qstream != NULL && fclose(Qstream)))

{

print_log("[ERROR] Не удалось закрыть файлы исходных данных");

return 0;

}


if(n <= 0)

{

print_log("[ERROR] Не удалось сгенерировать файл с матрицей смежности:

Не верно задана размерность матрицы");

return 0;

}


Mstream = fopen(M_path, "w");

Qstream = fopen(Q_path, "w");


if(Mstream == NULL || Qstream == NULL)

{

print_err("Не удалось сгенерировать файлы");

return 0;

}


// Записываем число вершин графа

if(fprintf(Mstream, "%d\n", n) < 0)

{

print_err("Не удалось сгенерировать файлы");

fclose(Mstream);

fclose(Qstream);

return 0;

}


vsize Msize = n * n;

weight **M = (weight**) malloc(n * sizeof(weight*));

if(M == NULL)

{

print_err("Не удалось выделить память");

fclose(Mstream);

fclose(Qstream);

return 0;

}

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

M[i] = (weight*) malloc(n * sizeof(weight));

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

{

for(j = 0; j < n; j++)

{

if(j < i)

M[i][j] = M[j][i];

else if(j == i)

M[i][j] = 0;

else

M[i][j] = get_random(MIN_WEIGHT, MAX_WEIGHT, (float) DENSITY, INF);

}

}


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

{

for(j = 0; j < n - 1; j++)

{

if(fprintf(Mstream, "%d ", M[i][j]) < 0)

{

print_err("Не удалось сгенерировать файлы");

fclose(Mstream);

fclose(Qstream);

free(M);

return 0;

}

}

if(fprintf(Mstream, "%d\n", M[i][n - 1]) < 0)

{

print_err("Не удалось сгенерировать файлы");

fclose(Mstream);

fclose(Qstream);

free(M);

return 0;

}

}

free(M);


vsize r1, r2;

do

{

r1 = gen_random(1, n);

r2 = gen_random(1, n);

} while(n > 1 && r1 == r2);


if(fprintf(Qstream, "%d -> %d", r1, r2) < 0)

{

print_err("Не удалось сгенерировать файлы");

fclose(Mstream);


Случайные файлы

Файл
31264.rtf
554.doc
2092.rtf
24872-1.rtf
10907.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.