ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.03.2025
Просмотров: 144
Скачиваний: 1
Национальный Исследовательский Университет
МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
Институт автоматики и вычислительной техники
Кафедра прикладной математики
Лабораторная работа № 2
LU-разложение матрицы
Выполнила Студентка А-13-09 Шорникова Дарья
Преподаватель Панков Николай Александрович
Москва, 2013 г.
1
Постановка задачи
Дана квадратная матрица. Требуется найти ее LU-разложение, т.е. представление в виде произведения нижнетреугольной матрицы на верхнетреугольную с единицами на главной диагонали. Составить последовательно-параллельную программу на языке C или C++, использующую принципы нитевого распараллеливания, а также исследовать характеристики разработанной программы в зависимости от числа потоков.
Тестирование проводились на компьютере со следующей конфигурацией:
Intel Core i7-3720 2.6 Ггц, 8Гб ОЗУ, Windows 8 x64
Последовательный алгоритм решения
Получить LU-разложение квадратной матрицы последовательным способом можно несколькими способами.
1. Схема единственного деления.
При выполнении первого шага исключения по схеме единственного деления матрица приводится к виду
где
Введем матрицу
Аналогично можно получить |
и |
. Тогда |
Проведя подобные выкладки, можно получить LU-разложение матрицы (нерациональный способ).
2. Из полученных соотношений можно вывести формулы:
2
Используя эти формулы можно получить LU – разложение матрицы.
Параллельный алгоритм решения.
Данный алгоритм имеет высокую зависимость по данным, так как каждое вычисление следующей строки использует результаты вычисления предыдущих строк. Это создает трудности при написании последовательно-параллельного алгоритма и снижает максимальное ускорение из-за синхронизации.
Матрицы L и U являются нижнедиагональными и верхнедиагональными, причем на местах, где у L могут быть ненулевые элементы, у U гарантировано нули, и наоборот. После вычисления некоторых значений искомых матриц часть разлагаемой матрицы А становится неиспользуемой. Поэтому можно сохранять найденные элементы прямо в разлагаемую матрицу.
3
Матрицы 2500 × 2500
Число |
Время |
Ускоре |
|
решения |
|||
потоков |
ние |
||
(сек) |
|||
1 |
14,31 |
1 |
|
2 |
8,102 |
1,766 |
|
3 |
6,218 |
2,301 |
|
4 |
5,652 |
2,531 |
|
5 |
5,305 |
2,697 |
|
6 |
5,116 |
2,797 |
|
7 |
4,873 |
2,936 |
|
8 |
4,93 |
2,902 |
|
9 |
5,418 |
2,641 |
|
Зависимость времени решения от числа потоков |
||||||||
16 |
||||||||
14 |
||||||||
12 |
||||||||
10 |
||||||||
8 |
||||||||
6 |
||||||||
4 |
||||||||
2 |
||||||||
0 |
||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Время решения, сек |
||||||||
Зависимость ускорения от числа потоков |
||||||||
3,5 |
||||||||
3 |
||||||||
2,5 |
||||||||
2 |
||||||||
1,5 |
||||||||
1 |
||||||||
0,5 |
||||||||
0 |
||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Ускорение |
||||||||
4 |
||||||||
Матрицы 5000 × 5000
Число |
Время |
Ускоре |
|
решения |
|||
потоков |
ние |
||
(сек) |
|||
1 |
115,281 |
1 |
|
2 |
59,81 |
1,927 |
|
3 |
49,776 |
2,315 |
|
4 |
45,682 |
2,523 |
|
5 |
43,715 |
2,637 |
|
6 |
40,351 |
2,856 |
|
7 |
37,891 |
3,042 |
|
8 |
39,636 |
2,908 |
|
9 |
43,678 |
2,639 |
|
Зависимость времени решения от числа потоков |
||||||||
140 |
||||||||
120 |
||||||||
100 |
||||||||
80 |
||||||||
60 |
||||||||
40 |
||||||||
20 |
||||||||
0 |
||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Время решения, сек |
||||||||
Зависимость ускорения от числа потоков |
||||||||
3,5 |
||||||||
3 |
||||||||
2,5 |
||||||||
2 |
||||||||
1,5 |
||||||||
1 |
||||||||
0,5 |
||||||||
0 |
||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Ускорение |
||||||||
5 |
||||||||
Матрицы 10000 × 10000
Число |
Время |
Ускоре |
|
решения |
|||
потоков |
ние |
||
(сек) |
|||
1 |
895,484 |
1 |
|
2 |
498,104 |
1,797 |
|
3 |
375,62 |
2,384 |
|
4 |
346,971 |
2,580 |
|
5 |
344,612 |
2,598 |
|
6 |
322,383 |
2,777 |
|
7 |
305,412 |
2,932 |
|
8 |
318,208 |
2,814 |
|
9 |
338,067 |
2,648 |
|
Зависимость времени решения от числа потоков |
||||||||
1000 |
||||||||
800 |
||||||||
600 |
||||||||
400 |
||||||||
200 |
||||||||
0 |
||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Время решения, сек |
||||||||
Зависимость ускорения от числа потоков |
||||||||
3,5 |
||||||||
3 |
||||||||
2,5 |
||||||||
2 |
||||||||
1,5 |
||||||||
1 |
||||||||
0,5 |
||||||||
0 |
||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Ускорение |
||||||||
6 |
||||||||
Приложение. Код программы
SyncObject.h
#pragma once
#define MAX_THREADS 2 #include <Windows.h>
struct SyncObject {
volatile unsigned int RunningCount; HANDLE StartEvent;
HANDLE EndEvent;
SyncObject(){ RunningCount = 0;
StartEvent = CreateEvent(NULL,true,false,NULL); EndEvent = CreateEvent(NULL,true,true,NULL);
};
~SyncObject() { CloseHandle(StartEvent); CloseHandle(EndEvent);
}
void syncStart(){ InterlockedIncrement(&RunningCount);
if(RunningCount == MAX_THREADS){ ResetEvent(EndEvent); SetEvent(StartEvent);
}
else{ WaitForSingleObject(StartEvent,INFINITE);
}
}
void syncEnd()
{
InterlockedDecrement(&RunningCount);
if (RunningCount == 0) { ResetEvent(StartEvent); SetEvent(EndEvent);
}
else {
WaitForSingleObject(EndEvent, INFINITE);
}
}
};
#include "stdafx.h" #include <math.h> #include <stdio.h> #include <time.h> #include <stdlib.h> #include "SyncObject.h"
#define NSIZE 5000 SyncObject sSync;
DWORD WINAPI MyThreadFunction(LPVOID lpParam);
7
FILE *fp; double **matr;
DWORD dwThreadIds[MAX_THREADS];
HANDLE hThread[MAX_THREADS];
void PrintMatr(double **m)
{
for (int i=0; i<NSIZE; i++)
{
for (int j=0; j<NSIZE; j++)
{
fprintf(fp,"%.2f",m[i][j]); fprintf(fp,"%c",'\t');
}
fprintf(fp,"%c",'\n');
}
}
DWORD WINAPI MyThreadFunction(LPVOID lpParam)
{
int index=(int)lpParam; clock_t t;
t=clock();
for (int k = 0; k < NSIZE - 1; k++)
{
sSync.syncStart();
for (int i =k + 1; i < NSIZE; i++)
{
if ( (i%MAX_THREADS) == index)
{
double factor = matr[i][k] / matr[k][k]; for (int j = k+1; j < NSIZE; j++)
{
matr[i][j] -= factor * matr[k][j];
}
matr[i][k] = factor;
}
}
sSync.syncEnd();
}
t=clock()-t;
printf("Thread lasts %f\n",(float)t/CLOCKS_PER_SEC); return 0;
}
int main(int argc, char* argv[])
{
if ((matr = (double**)malloc(NSIZE * sizeof(double *))) == NULL) printf("Memory allocation failed\n");
for (int i=0; i<NSIZE; i++)
{
if ((matr[i] = (double *)malloc(NSIZE * sizeof(double))) == NULL) printf("Memory allocation failed\n");
}
srand(time(0));
for (int i=0; i<NSIZE; i++) for (int j=0; j<NSIZE; j++)
{
//matr[i][j]=(i+j+1); matr[i][j]=(rand() % 100)+1;
8