Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

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

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

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

Лабораторная работа № 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];

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лабораторной работы