Число вершин 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 <windows.h>
#include <tchar.h>
#include <strsafe.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <time.h>
#include <stdarg.h>
#include <math.h>
// --- Настройки программы ---
// Включение режима отладки
// #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);
fclose(Qstream);
return 0;
}
if(fclose(Mstream) || fclose(Qstream))
{
print_err("Не удалось закрыть файлы");
return 0;
}
// Не учитываем время, затраченное на генерацию файлов
time[h] = (double) clock();
Mstream = fopen(M_path, "r");
Qstream = fopen(Q_path, "r");
if(Mstream == NULL || Qstream == NULL)
{
print_err("Не удалось открыть файлы");
return 0;
}
}
// Считываем число вершин в графе
if(fscanf(Mstream, "%d\n", &n) <= 0)
{
print_log("[ERROR] Не удалось считать число вершин графа");
fclose(Mstream);
fclose(Qstream);
return 0;
}
// Проверка числа вершин
if(n <= 0)
{
print_log("[ERROR] Не верно задано число вершин графа:
|V| = n должно быть больше нуля");
fclose(Mstream);
fclose(Qstream);
return 0;
}
// Чтение начальной и конечной вершин искомого пути
if(fscanf(Qstream, "%d -> %d", &Vstart, &Vend) <= 0)
{
print_log("[ERROR] Не удалось считать число вершин графа");
fclose(Mstream);
fclose(Qstream);
return 0;
}
Vstart--; Vend--;
// Проверка начальной и конечной вершин искомого пути
if(Vstart < 0 || Vend < 0 || Vstart >= n || Vend >= n)
{
print_log("[ERROR] Не верно заданы начальная и конечная вершины искомого пути");
fclose(Mstream);
fclose(Qstream);
return 0;
}
fclose(Qstream);
// Делим строки матрицы W между потоками
p = (vsize) floor(double(n / threads));
for(i = 0; i < threads; i++)
{
Wrows[i] = p;
Nrows[i] = i * p;
}
p = n % threads;
for(i = 0; p != 0; p--)
{
Wrows[i]++;
for(j = i + 1; j < threads; j++)
Nrows[j]++;
i = (i < threads) ? i + 1 : 0;
}
// Запись информации о группе тестов в лог-файл
if(!h)
{
print_log("----------------------------------------------\n
Число потоков %d\n
Число вершин %d\n
Память %f МБ\n\n", threads, n,
double((n * n * sizeof(weight) + n * n * sizeof(vsize)) / 1024.0 / 1024.0));
print_log("[DEBUG] Распределение строк матрицы M между потоками:\n{");
for(i = 0; i < threads - 1; i++)
print_log("%d (%d), ", Wrows[i], Nrows[i]);
print_log("%d (%d)}\n\n", Wrows[threads - 1], Nrows[threads - 1]);
}
vsize Msize = n * n;
vsize Psize = n * n;
// Матрица смежности
M = (weight**) malloc(n * sizeof(weight*));
// Матрица предшествования
P = (vsize**) malloc(n * sizeof(vsize*));
if(M == NULL || P == NULL)
{
print_err("Не удалось выделить память");
fclose(Mstream);
return 0;
}
for(i = 0; i < n; i++)
{
M[i] = (weight*) malloc(n * sizeof(weight));
P[i] = (vsize*) malloc(n * sizeof(vsize));
}
// Чтение матрицы смежности
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
fscanf(Mstream, "%d", &M[i][j]);
fclose(Mstream);
// Инициализация матрицы предшествования
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
P[i][j] = (M[i][j] == INF) ? -1 : i;
}
// Выделяем память для потока
for(i = 0; i < threads; i++)
{
pDataArray[i] = (PTDATA) HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(TDATA));
#ifdef DEBUG
// Если не удалось выделить память, то прерываем выполнение программы
if(pDataArray[i] == NULL)
{
print_log("[ERROR] Не удалось выделить память для потока\n");
free(M); free(P);
ExitProcess(E_THREAD_ALLOC);
}
#endif // DEBUG
pDataArray[i]->i = i;
}
for(k = 0; k < n; k++)
{
for(i = 0; i < threads; i++)
{
// Создаём поток
hThreadArray[i] = CreateThread(
NULL, // атрибуты безопасности по умолчанию
0, // используем размер стека по умолчанию
MyThreadFunction, // имя функции потока
pDataArray[i], // аргумент функции потока
0, // используем стандартные флаги
&dwThreadIdArray[i] // получаем идентификатор потока
);
// Если не удалось запустить поток, то прерываем выполнение программы
if(hThreadArray[i] == NULL)
ExitProcess(E_THREAD_CREATE);
}
// Ждём, пока не выполнятся все потоки
WaitForMultipleObjects(threads, hThreadArray, TRUE, INFINITE);
// Закрываем все дескрипторы потоков
for(i = 0; i < threads; i++)
CloseHandle(hThreadArray[i]);
}
// Осовобождаем выделенную память
for(i = 0; i < threads; i++)
{
if(pDataArray[i] != NULL)
{
HeapFree(GetProcessHeap(), 0, pDataArray[i]);
pDataArray[i] = NULL;
}
}
if(threads == MIN_THREADS && !h)
{
print_log("[DEBUG] Матрица весов кратчайших путей:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n - 1; j++)
{
if(M[i][j] >= INF)
print_log("- ");
else
print_log("%d ", M[i][j]);
}
if(M[i][n - 1] >= INF)
print_log("-\n");
else
print_log("%d\n", M[i][n - 1]);
}
print_log("\n[DEBUG] Матрица предшествования:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n - 1; j++)
{
if(P[i][j] == -1)
print_log("- ");
else
print_log("%d ", P[i][j] + 1);
}
if(P[i][n - 1] == -1)
print_log("-\n");
else
print_log("%d\n", P[i][n - 1] + 1);
}
print_log("\n");
}
// Вершины искомого пути (в обратном порядке)
vsize *path = (vsize*) malloc(n * sizeof(vsize));
i = 0;
path[i] = Vend;
do
{
i++;
if(i < n)
path[i] = P[Vstart][path[i-1]];
} while(i < n && path[i] != Vstart && path[i] != -1);
// Запись результата в файл
Rstream = fopen(R_path, "w");
if(M[Vstart][Vend] >= INF || path[i] == -1)
{
fprintf(Rstream, "Путь из вершины %d в вершину %d не существует\n",
Vstart + 1, Vend + 1);
}
else
{
fprintf(Rstream, "Искомый путь (длина %d):\n", M[Vstart][Vend]);
while(i >= 0)
{
if(i)
fprintf(Rstream, "%d => ", path[i] + 1);
else
fprintf(Rstream, "%d", path[i] + 1);
i--;
}
}
fclose(Rstream);
// Освобождаем память
free(M);
free(P);
free(path);
// Записываем время в лог-файл
time[h] = ((double) clock() - time[h]) / CLOCKS_PER_SEC;
print_log("Время (%d): %f сек\n", h + 1, time[h]);
}
// Записываем среднее время в лог-файл
time[0] = time[0] / TEST_COUNT;
for(i = 1; i < TEST_COUNT; i++)
time[0] += time[i] / TEST_COUNT;
print_log("Среднее : %f сек\n\n", time[0]);
}
return 0;
}
DWORD WINAPI MyThreadFunction(LPVOID lpData)
{
PTDATA data = (PTDATA) lpData;
int t = data->i;
vsize first = Nrows[t];
vsize last = first + Wrows[t];
vsize i, j;
for(i = first; i < last; i++)
{
for(j = 0; j < n; j++)
{
if(M[i][j] > (M[i][k] + M[k][j]))
{
P[i][j] = P[k][j];
M[i][j] = M[i][k] + M[k][j];
}
}
}
return 0;
}
// Генерирует псевдо-случайное число из интервала [a;b]
vsize gen_random(vsize a, vsize b)
{
return (vsize) (a + (b - a) * ((float) rand() / RAND_MAX));
}
// Генерирует псевдо-случайное число из интервала [a;b], возвращая inf с вероятностью (1 - p)
weight get_random(weight a, weight b, float p, weight inf)
{
return (weight)((((double)rand()/RAND_MAX) >= p) ? inf : (a + (b-a) * ((double)rand()/RAND_MAX)));
}
// Записывает сообщение message в лог
void print_log(const char *message, ...)
{
va_list ptr;
va_start(ptr, message);
// Открываем файл логов
FILE *stream = fopen(L_path, "a");
if(stream == NULL)
return;
// Записываем сообщение в лог
vfprintf(stream, message, ptr);
fclose(stream);
va_end(ptr);
}
// Выводит сообщение по коду ошибки errno
// message - необязательное дополнительное описание ошибки
void print_err(const char *message)
{
char *msg = (char *)"[ERROR] ";
if(message != NULL)
msg = strcat(msg, message);
switch(errno)
{
case E2BIG : msg = strcat(msg, "Список аргументов слишком длинный"); break;
case EACCES : msg = strcat(msg, "Отказ в доступе"); break;
case EADDRINUSE : msg = strcat(msg, "Адрес используется"); break;
// ...
default : msg = strcat(msg, "Неизвестная ошибка");
}
print_log(msg);
}
1 Среднее арифметическое по результатам 5 измерений
2 Среднее арифметическое по результатам 5 измерений
Москва, 2012