Алгоритм решения СЛАУ прямым методом Гаусса
Изучение последовательного алгоритма Гаусса решения систем линейных уравнений. Программная реализация последовательного алгоритма Гаусса. Зависимость времени реализации алгоритма от размера матрицы. Вычисление эффективности параллельного алгоритма.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 27.12.2019 |
Размер файла | 243,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство высшего образования и науки РФ
Пермский национальный исследовательский политехнический университет
Электротехнический факультет
Кафедра ИТАС
Курсовая работа
по дисциплине "Вычислительные комплексы и системы"
на тему "Алгоритм решения СЛАУ прямым методом Гаусса"
Морозов И.С.
Пермь, 2019
Содержание
Введение
1. Изучение последовательного алгоритма Гаусса решения систем линейных уравнений
1.1 Прямой ход метода Гаусса
1.2 Обратный ход алгоритма Гаусса
1.3 Программная реализация последовательного алгоритма Гаусса
2. Технология MPI
2.1 Программная реализация параллельного строчно-ориентированного алгоритма решения СЛАУ методом ГАУССА с использованием библиотеки MPI
3. Расчет эффективности и ускорения параллельных вычислений методом Гаусса
Вывод
Список используемых источников
Задание на курсовую работу
Реализуйте последовательный алгоритм решения СЛАУ прямым методом Гаусса с выбором ведущего элемента, получите зависимость времени реализации алгоритма от размера матрицы. Реализуйте параллельный строчно-ориентированный алгоритм решения СЛАУ прямым методом Гаусса с выбором ведущего элемента, вычислите время реализации алгоритма на различном числе процессоров для размера матрицы от 102 х 102 до 105 х 105. Вычислите ускорение и эффективность параллельного алгоритма по сравнению с последовательным.
Введение
Для выполнения поставленной задачи будем использовать персональный компьютер на базе процессора Intel Core i7-4770K 3.50GHz c оперативной памятью DDR3-1333 DDR3 SDRAM 16 ГБ под управлением Microsoft Windows 7 Ultimate 64-bit и программное обеспечение Oracle VM VirtualBox Version 4.3.26 Edition. В нашем случае узлами вычислительного кластера будут являться виртуальные машины, т.к. кластер будет расположен в виртуальной среде. алгоритм линейный матрица
1. Изучение последовательного алгоритма Гаусса решения систем линейных уравнений
Метод Гаусса основывается на возможности выполнения преобразований линейных уравнений, которые не меняют при этом решение рассматриваемой системы (такие преобразования носят наименование эквивалентных). К числу таких преобразований относятся:
· Умножение любого из уравнений на ненулевую константу
· Перестановка уравнений
· Прибавление к уравнению любого другого уравнения системы
Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе - прямой ход метода Гаусса - исходная система линейных уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду
где матрица коэффициентов получаемой системы имеет вид
На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1, после этого из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д.
1.1 Прямой ход метода Гаусса
Прямой ход метода Гаусса состоит в последовательном исключении неизвестных в уравнениях решаемой системы линейных уравнений. На итерации i метода производится исключение неизвестной i для всех уравнений с номерами k, большими i. Для этого из этих уравнений осуществляется вычитание строки i, умноженной на константу (aki/aii), с тем, чтобы результирующий коэффициент при неизвестной xi в строках оказался нулевым. Вычисления, выполняемые над элементами матрицы A и вектора b, определяются следующими соотношениями.
На рисунке 1 представлена общая схема состояния данных на i-ой итерации прямого хода алгоритма Гаусса. Все коэффициенты при неизвестных, расположенные ниже главной диагонали и левее столбца i, уже являются нулевыми. На i-ой итерации прямого хода метода Гаусса осуществляется обнуление коэффициентов столбца i, расположенных ниже главной диагонали, путем вычитания строки i, умноженной на нужную ненулевую константу. После проведения (n-1) подобной итерации матрица, определяющая систему линейных уравнений, становится приведенной к верхнему треугольному виду.
Рисунок 1- Общая схема состояния данных на i-ой итерации прямого хода алгоритма Гаусса
При выполнении прямого хода метода Гаусса строка, которая используется для исключения неизвестных, носит наименование ведущей, а диагональный элемент ведущей строки называется ведущим элементом. Как можно заметить, выполнение вычислений является возможным только, если ведущий элемент имеет ненулевое значение. Более того, если ведущий элемент a(i,i) имеет малое значение, то деление и умножение строк на этот элемент может приводить к накоплению вычислительной погрешности и вычислительной неустойчивости алгоритма.
Возможный способ избежать подобной проблемы может состоять в следующем - при выполнении каждой очередной итерации прямого хода метода Гаусса следует определить коэффициент с максимальным значением по абсолютной величине в столбце, соответствующем исключаемой неизвестной, т.е.
и выбрать в качестве ведущей строку, в которой этот коэффициент располагается (данная схема выбора ведущего значения носит наименование метода главных элементов).
1.2 Обратный ход алгоритма Гаусса
После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1, после этого из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д. В общем виде, выполняемые вычисления при обратном ходе метода Гаусса могут быть представлены при помощи соотношений:
Определим вычислительную сложность метода Гаусса. В прямом ходе алгоритма для выбора ведущей строки на каждой итерации должно быть определено максимальное значение в столбце с исключаемой неизвестной. По мере исключения неизвестных количество строк и элементов в строках сокращается.
Текущее число элементов строки (включая правую часть), с которыми производятся действия сложения и вычитания (первый элемент без вычислений полагается равным нулю), равно (n-i), где i, - номер итерации прямого хода. Поскольку кроме выполнения двух операций (умножения и вычитания) с каждым элементом строки предварительно должен быть вычислен масштабирующий коэффициент aik/aii, общие затраты на выполнение действий в одной строке составят 2(n-i)+1 операций.
С учетом того, что на каждой итерации обрабатывается n-i строк, общее число операций в прямом ходе метода Гаусса определяется выражением
Для реализации обратного хода на каждой i-й итерации,(итерация для удобства присваиваем номера от n-2 до 0) необходимо произвести n-i-1 умножений, столько же вычитаний, а также одно деление для определения очередной неизвестной. Следовательно, общая вычислительная сложность обратного хода составит
Суммируя затраты на реализацию прямого и обратного хода, получаем
В последнем равенстве пределы и порядок суммирования изменены с учетом замены j=n-i.
Используя формулы суммирования,
получаем следующее соотношение для оценки вычислительной сложности метода Гаусса при его реализации в виде последовательного алгоритма:
Вычислительная сложность алгоритма Гаусса имеет порядок O (n3). [2]
1.3 Программная реализация последовательного алгоритма Гаусса
Реализуем данный алгоритм на языке объектно-ориентированного программирования С++.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
// Вывод системы уравнений
void show (double **a, double *y, int n)
{
int i = 0;
for (; i < n; i++)
{
int j = 0;
for (; j < n; j++)
{
printf("%f*x%i", a[i][j], j);
if (j < n - 1)
{
printf(" + ");
}
}
printf(" = %f\n", y[i]);
}
return;
}
double* gauss(double **a, double *y, int n)
{
int index;
const double eps = 0.00001; // точность
double* x = (double*) malloc(sizeof(double)*n);
int k = 0;
while (k < n)
{
// Поиск строки с максимальным a[i][k]
double max = fabs(a[k][k]);
index = k;
for (int i = k + 1; i < n; i++)
{
if (fabs(a[i][k]) > max)
{
max = fabs(a[i][k]);
index = i;
}
}
// Перестановка строк
if (max < eps)
{
// нет ненулевых диагональных элементов
printf("Решение получить невозможно из-за нулевого столбца %i матрицы A.\n", index);
return 0;
}
for (int j = 0; j < n; j++)
{
double temp = a[k][j];
a[k][j] = a[index][j];
a[index][j] = temp;
}
double temp = y[k];
y[k] = y[index];
y[index] = temp;
// Нормализация уравнений
for (int i = k; i < n; i++)
{
double temp = a[i][k];
if (fabs(temp) < eps) continue; // для нулевого коэффициента пропустить
for (int j = 0; j < n; j++)
{
a[i][j] = a[i][j] / temp;
}
y[i] = y[i] / temp;
if (i == k) continue; // уравнение не вычитать само из себя
for (int j = 0; j < n; j++)
{
a[i][j] = a[i][j] - a[k][j];
}
y[i] = y[i] - y[k];
}
k++;
}
// обратная подстановка
for (k = n - 1; k >= 0; k--)
{
x[k] = y[k];
for (int i = 0; i < k; i++)
{
y[i] = y[i] - a[i][k] * x[k];
}
}
return x;
}
int main(int argc, char* argv[])
{
clock_t starttime = clock();
int n = 10;
if (argc == 2)
{
int exp = 2;
sscanf(argv[1], "%i", &exp);
for (; exp > 0; --exp)
{
n *= 10;
}
}
double **a = (double**) malloc(sizeof(double*)*n);
double *y = (double *) malloc(sizeof(double)*n);
srand(time(NULL));
int i = 0;
for (; i < n; i++)
{
a[i] = (double*) malloc(sizeof(double)*n);
int j = 0;
for (; j < n; j++)
{
a[i][j] = rand() % 10 + 1;
}
}
for (i = 0; i < n; i++)
{
y[i] = rand() % 10 + 1;
}
// show(a, y, n);
double *x = gauss(a, y, n);
for (i = 0; i < n; i++)
{
printf("x[%i] = %f\n", i, x[i]);
}
printf("Calculation time = %f sec.\n", ((double)(clock() - starttime)/CLOCKS_PER_SEC));
return 0;
}
На рисунке 2 представлен результат выполнения программы.
Рисунок 2- Результат выполнения программы
В таблице 1 представлено время выполнения вычислений разного размера матриц для последовательного алгоритма.
Таблица 1. Результаты вычислений для последовательного алгоритма Гаусса
Размер матрицы |
Затраченное время (сек) |
|
100*100 |
0,012 |
|
500*500 |
0,418 |
|
1000*1000 |
1,7 |
|
2000*2000 |
12,595 |
|
3000*3000 |
41,72 |
|
4000*4000 |
98,369 |
|
5000*5000 |
194 |
|
Из рисунка 3 видно, что чем больше размер матрицы, тем больше времени уходит на выполнение расчетов.
Рисунок 3- График зависимости времени выполнения от размера матрицы
Согласно заданию на курсовую работу, размер матрицы должен достигать 100 000 элементов. Поскольку, при тестировании программы на время выполнения вычислений при размере матрицы равной 10 000*10 000 возникают трудности, выражающиеся в зависании программного обеспечения, максимально проверенный размер матрицы на время выполнения вычислений составляет 5 000*5 000 элементов.
2. Технология MPI
Наиболее распространенной технологией программирования для параллельных компьютеров с распределенной памятью в настоящее время является MPI. Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии - Message Passing Interface (интерфейс передачи сообщений). Стандарт MPI фиксирует интерфейс, который должен соблюдаться как системой программирования на каждой вычислительной платформе, так и пользователем при создании своих программ. Современные реализации, чаще всего, соответствуют стандарту MPI версии 1.1. В 1997- 1998 годах появился стандарт MPI-2.0, значительно расширивший функциональность предыдущей версии. Однако до сих пор этот вариант MPI не получил широкого распространения и в полном объеме не реализован ни на одной системе.
MPI поддерживает работу с языками Фортран и Си. Однако это совершенно не является принципиальным, поскольку основные идеи MPI и правила оформления отдельных конструкций для этих языков во многом схожи. Полная версия интерфейса содержит описание более 125 процедур и функций.
Интерфейс MPI поддерживает создание параллельных программ в стиле MIMD (Multiple Instruction Multiple Data), что подразумевает объединение процессов с различными исходными текстами. Однако писать и отлаживать такие программы очень сложно, поэтому на практике программисты гораздо чаще используют SPMD-моделъ (Single Program Multiple Data) параллельного программирования, в рамках которой для всех параллельных процессов используется один и тот же код. В настоящее время все больше и больше реализаций MPI поддерживают работу с нитями.
Поскольку MPI является библиотекой, то при компиляции программы необходимо прилинковать соответствующие библиотечные модули. Это можно сделать в командной строке или воспользоваться предусмотренными в большинстве систем командами или скриптами mpicc++(для программ на языке Си), mpicc++ (для программ на языке Си++), и mpif 77/ mpif 90 (для программ на языках Фортран 77/90). Опция компилятора "-о name" позволяет задать имя name для получаемого выполнимого файла, по умолчанию выполнимый файл указывается на out, например:
mpif77 -o program program.f .
После получения выполнимого файла необходимо запустить его на требуемом количестве процессоров. Для этого обычно предоставляется команда запуска MPI-приложений mpirun, например:
mpirun -np N <программа с аргументами>,
где N - число процессов, которое должно быть не более разрешенного в данной системе числа процессов для одной задачи. После запуска одна и та же программа будет выполняться всеми запущенными процессами, результат выполнения в зависимости от системы будет выдаваться на терминал или записываться в файл с предопределенным именем.
Все дополнительные объекты: имена процедур, константы, предопределенные типы данных и т.п., используемые в MPI, имеют префикс MPI_. Если пользователь не будет использовать в программе имен с таким префиксом, то конфликтов с объектами MPI заведомо не будет. В языке Си, кроме того, является существенным регистр символов в названиях функций. Обычно в названиях функций MPI первая буква после префикса MPI_ пишется в верхнем регистре, последующие буквы - в нижнем регистре, а названия констант MPI записываются целиком в верхнем регистре. Все описания интерфейса MPI собраны в файле mpif.h (mpi.h), поэтому в начале MPI-программы должна стоять директива include 'mpif.h' (#include "mpi.h" для программ на языке Си).
MPI-программа - это множество параллельных взаимодействующих процессов. Все процессы порождаются один раз, образуя параллельную часть программы. В ходе выполнения MPI-программы порождение дополнительных процессов или уничтожение существующих не допускается (в MPI-2.0 такая возможность появилась). Каждый процесс работает в своем адресном пространстве, никаких общих переменных или данных в MPI нет. Основным способом взаимодействия между процессами является явная посылка сообщений.
Для локализации взаимодействия параллельных процессов программы можно создавать группы процессов, предоставляя им отдельную среду для общения- коммуникатор. Состав образуемых групп произволен. Группы могут полностью совпадать, входить одна в другую, не пересекаться или пересекаться частично. Процессы могут взаимодействовать только внутри некоторого коммуникатора, сообщения, отправленные в разных коммуникаторах, не пересекаются и не мешают друг другу.
При старте программы всегда считается, что все порожденные процессы работают в рамках всеобъемлющего коммуникатора, имеющего предопределенное имя MPI_COMM_WORLD. Этот коммуникатор существует всегда и служит для взаимодействия всех запущенных процессов MPI-программы. Кроме него при старте программы имеется коммуникатор MPI_COMM_SELF, содержащий только один текущий процесс, а также коммуникатор MPI_COMM_NULL, не содержащий ни одного процесса. Все взаимодействия процессов протекают в рамках определенного коммуникатора, сообщения, переданные в разных коммуникаторах, никак не мешают друг другу.
Каждый процесс MPI-программы имеет в каждой группе, в которую он входит, уникальный атрибут номер процесса, который является целым неотрицательным числом. С помощью этого атрибута происходит значительная часть взаимодействия процессов между собой. Ясно, что в одном и том же коммуникаторе все процессы имеют различные номера. Но поскольку процесс может одновременно входить в разные коммуникаторы, то его номер в одном коммуникаторе может отличаться от его номера в другом. Отсюда становятся понятными два основных атрибута процесса: коммуникатор и номер в коммуникаторе. Если группа содержит п процессов, то номер любого процесса в данной группе лежит в пределах от 0 до п - 1.
Основным способом общения процессов между собой является явная посылка сообщений. Сообщение - это набор данных некоторого типа. Каждое сообщение имеет несколько атрибутов, в частности, номер процесса-отправителя, номер процесса-получателя, идентификатор сообщения и другие. Одним из важных атрибутов сообщения является его идентификатор или тэг. По идентификатору процесс, принимающий сообщение, например, может различить два сообщения, пришедшие к нему от одного и того же процесса. Сам идентификатор сообщения является целым неотрицательным числом, лежащим в диапазоне от 0 до MPI_TAG_UP, причем гарантируется, что MPI_TAG_UP не меньше 327 67. Для работы с атрибутами сообщений введен массив (в языке Си - структура), элементы которого дают доступ к их значениям. [3]
2.1 Программная реализация параллельного строчно-ориентированного алгоритма решения СЛАУ методом ГАУССА с использованием библиотеки MPI
#include "mpi.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
int main(int argv,char* argc[])
{
int rank,size;
int count = 1000;
double t1, t2;
MPI_Status status;
MPI_Init(&argv,&argc);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Bcast(&count,1,MPI_INT,0,MPI_COMM_WORLD);
double temp;
int maxCol;
double maxValue;
double *trX = (double*) malloc(sizeof(double)*count);
int numb;
int* ind = (int*) malloc(sizeof(int)*count);
int i, j, p, k;
for(i =0; i < count; i++)
{
ind[i] = i;
}
int N = count/size;
double** A = (double**) malloc(sizeof(double*)*count);
for(i = 0; i < count; i++)
{
A[i] = (double*) malloc(sizeof(double)*N);
}
double*B = (double*) malloc(sizeof(double)*count);
for(i = 0; i < count; i++)
{
B[i] = rand()%100+1;
}
srand(time(NULL) + rank);
for(i = 0; i < count; i++)
{
for(j = 0; j < N;j++)
{
A[i][j] = rand()%100+1;
}
}
int recv = 0;
double* L = (double*) malloc(sizeof(double)*count);
double orB = B[0];
t1 = MPI_Wtime();
for(p = 0; p < size; p++)
{
if(p == rank)
{
for(k = 0;k<N;k++)
{
maxValue = A[N*p+k][k];
maxCol = N*p + k;
for(i = N*p + k + 1; i < count; i ++)
{
if(abs(A[i][k]) > abs(maxValue))
{
maxValue = A[i][k]; maxCol = i;
}
}
for(i = 0; i < N; i++)
{
temp = A[N*p+k][i];
A[N*p+k][i] = A[maxCol][i];
A[maxCol][i] = temp;
}
if(maxCol!=N*p+k)
{
temp = ind[N*p+k];
ind[N*p+k] =ind[maxCol];
ind[maxCol] = temp;
temp = B[N*p+k];
B[N*p+k] = B[maxCol];
B[maxCol] = temp;
}
for(j = N*p + k; j < count - 1; j++)
{
L[j] = A[j+1][k]/A[p*N+k][k];
}
int proc;
for(proc = p + 1;proc < size; proc++)
{
MPI_Send(L,count,MPI_DOUBLE,proc,1,MPI_COMM_WORLD);
MPI_Send(&k,1,MPI_DOUBLE,proc,2,MPI_COMM_WORLD);
MPI_Send(&maxCol,1,MPI_INT,proc,22,MPI_COMM_WORLD);
MPI_Send(ind,count,MPI_INT,proc,33,MPI_COMM_WORLD);
}
for(i = N*p + k + 1; i < count; i++)
{
for(j = k; j < N; j++)
{
A[i][j] = A[i][j] - A[N*p + k][j] * L[i - 1];
if(abs(A[i][j]) < 0.00001) A[i][j] = 0;
}
B[i] = B[i] - B[N*p + k]*L[i - 1];
}
if(p != size - 1)
{
for(proc = p + 1;proc < size; proc++)
{
MPI_Send(B,count,MPI_DOUBLE,proc,3,MPI_COMM_WORLD);
}
}
}
}
if(rank > p)
{
for(k = 0;k<N;k++)
{
MPI_Recv(&numb,1,MPI_DOUBLE,p,2,MPI_COMM_WORLD,&status);
MPI_Recv(L,count,MPI_DOUBLE,p,1,MPI_COMM_WORLD,&status);
MPI_Recv(B,count,MPI_DOUBLE,p,3,MPI_COMM_WORLD,&status);
MPI_Recv(ind,count,MPI_INT,p,33,MPI_COMM_WORLD,&status);
MPI_Recv(&maxCol,1,MPI_INT,p,22,MPI_COMM_WORLD,&status);
for(i = 0; i < N; i++)
{
temp = A[maxCol][i];
A[maxCol][i] = A[N*p + numb][i];
A[N*p + numb][i] = temp;
}
for(i = numb + 1; i < count; i++)
{
for(j = numb; j < N; j++)
{
A[i][j] = A[i][j] - A[k][j] * L[i - 1];
}
}
}
}
}
MPI_Bcast(B,count,MPI_DOUBLE,size - 1,MPI_COMM_WORLD);
MPI_Bcast(ind,count,MPI_INT,size - 1, MPI_COMM_WORLD);
double* X = (double*) malloc(sizeof(double)*count);
orB = B[0];
for(p = size - 1; p >=0; p--)
{
if(p == rank)
{
X[N*p + N - 1] = B[N*p + N - 1]/ A[N*p + N-1][N-1];
for(i = N - 2; i>=0; i--)
{
for(j = i + 1; j < N; j++)
{
B[N*p + i] = B[N*p + i] - A[N*p + i][j] * X[N*p+j];
}
X[N*p + i] = B[N*p + i]/A[N*p + i][i];
}
for(i = 0; i < N*p; i++)
{
for(j = 0; j < N;j++)
{
B[i] = B[i] - A[i][j] * X[N*p + j];
}
}
if(p>0)
{
MPI_Send(B,count,MPI_DOUBLE,p-1,4,MPI_COMM_WORLD);
MPI_Send(X,count,MPI_DOUBLE,p-1,5,MPI_COMM_WORLD);
}
}
if(rank == p - 1)
{
MPI_Recv(B,count,MPI_DOUBLE,p,4,MPI_COMM_WORLD,&status);
MPI_Recv(X,count,MPI_DOUBLE,p,5,MPI_COMM_WORLD,&status);
}
}
t2 = MPI_Wtime();
printf("time = %f\n",t2 - t1);
double ch = 0;
MPI_Bcast(X,count,MPI_DOUBLE,0,MPI_COMM_WORLD);
for(p = 0; p < size; p++)
{
if(rank == p)
{
for(i = 0; i < N; i++)
{
ch = ch + A[0][i] * X[N*p + i];
}
if(p != size - 1)
{
MPI_Send(&ch,1,MPI_DOUBLE,p + 1,223,MPI_COMM_WORLD);
}
if(p == size - 1)
{
printf("pogreshnost = %2.16f\n",orB - ch);
}
}
if(rank == p + 1)
{
MPI_Recv(&ch,1,MPI_DOUBLE,p,223,MPI_COMM_WORLD,&status);
}
}
MPI_Finalize();
}
На рисунке 4 представлен результат выполнения параллельного алгоритма Гаусса.
Рисунок 4 - Реализация алгоритма Гаусса с использованием библиотеки MPI
В таблице 2 представлено время выполнения вычислений алгоритмом Гаусса на различном числе потоков.
Таблица 2. Результаты вычислений для параллельного алгоритма Гаусса
Размер матрицы |
Количество потоков |
||||
2 |
3 |
4 |
8 |
||
Время выполнения, с |
|||||
100*100 |
0,009 |
0,273 |
0,051 |
0,234 |
|
500*500 |
0,249 |
1,305 |
0,445 |
0,750 |
|
1000*1000 |
1,747 |
8,631 |
1,474 |
1,871 |
|
2000*2000 |
13,02 |
28,140 |
9,17 |
7,371 |
|
3000*3000 |
43,98 |
65,321 |
27,547 |
17,786 |
|
4000*4000 |
103,335 |
126,698 |
65,143 |
23,645 |
|
5000*5000 |
189,462 |
250,312 |
115,517 |
50,433 |
|
На рисунке 5 представлен график зависимости времени выполнения от размера матрицы на различном числе потоков.
Рисунок 5 - График зависимости времени выполнения от размера матрицы на разном количестве потоков
3. Расчет эффективности и ускорения параллельных вычислений методом Гаусса
Ускорением параллельного алгоритма называется отношение:
Эффективность параллельного алгоритма:
В таблице 3 приведено ускорение и эффективность выполнения вычислений параллельным алгоритмом Гаусса по сравнению с последовательным.
Таблица 3. Расчет ускорения и эффективности использования параллельных вычислений
Размер матрицы |
T1 |
Количество потоков |
Ускорение |
Эффективность |
|
100*100 |
0,012 |
2 |
1,33 |
0,67 |
|
3 |
0,04 |
0,01 |
|||
4 |
0,24 |
0,06 |
|||
8 |
0,051 |
0,006 |
|||
500*500 |
0,418 |
2 |
1,68 |
0,84 |
|
3 |
0,32 |
0,11 |
|||
4 |
0,94 |
0,24 |
|||
8 |
0,56 |
0,07 |
|||
1000*1000 |
1,7 |
2 |
0,97 |
0,49 |
|
3 |
0,20 |
0,07 |
|||
4 |
1,15 |
0,23 |
|||
8 |
0,91 |
0,11 |
|||
2000*2000 |
12,595 |
2 |
0,97 |
0,49 |
|
3 |
0,45 |
0,15 |
|||
4 |
1,37 |
0,34 |
|||
8 |
1,71 |
0,21 |
|||
3000*3000 |
41,72 |
2 |
0,95 |
0,48 |
|
3 |
0,64 |
0,21 |
|||
4 |
1,51 |
0,38 |
|||
8 |
2,35 |
0,29 |
|||
4000*4000 |
98,369 |
2 |
0,95 |
0,48 |
|
3 |
0,78 |
0,26 |
|||
4 |
1,51 |
0,38 |
|||
8 |
4,16 |
0,52 |
|||
5000*5000 |
194 |
2 |
1,02 |
0,51 |
|
3 |
0,78 |
0,26 |
|||
4 |
1,68 |
0,42 |
|||
8 |
3,85 |
0,48 |
|||
Если сложность решаемой задачи является фиксированной, то при росте числа потоков эффективность, как правило, будет убывать за счет роста накладных расходов. При фиксации числа потоков эффективность использования потоков можно улучшить путем повышения сложности решаемой задачи (предполагается, что при росте параметра сложности n накладные расходы увеличиваются медленнее, чем объем вычислений. Как результат, при увеличении числа потоков в большинстве случаев можно обеспечить определенный уровень эффективности при помощи соответствующего повышения сложности решаемых задач. В этой связи важной характеристикой параллельных вычислений становится соотношение необходимых темпов роста сложности расчетов и числа используемых процессоров. Проще говоря, при росте числа потоков время выполнения программы сравнительно уменьшается до определенного значения, а далее растет в связи с увеличением накладных расходов на организацию потока. [4]
Вывод
В данной работе был рассмотрен алгоритм Гаусса (прямой и обратный ход). Разработана программа, реализующая последовательный алгоритм на языке объектно-ориентированного программирования С++, рассчитано время выполнения последовательного алгоритма для разного размера матриц и построен график зависимости времени от размера матрицы.
Также в данной работе рассмотрена технология MPI, разработана программа, реализующая параллельный строчно-ориентированного алгоритм решения СЛАУ методом Гаусса на языке Си. Построены графики зависимости времени выполнения расчета матриц от числа потоков.
Для оценки оптимальности разрабатываемых методов параллельных вычислений приведены широко используемые в теории и практике параллельного программирования основные показатели качества - ускорение (speedup), показывающее, во сколько раз быстрее осуществляется решение задач при использовании нескольких потоков, и эффективность (efficiency), которая характеризует долю времени реального использования потоков вычислительной системы.
При внимательном рассмотрении можно обратить внимание, что попытки повышения качества параллельных вычислений по одному из показателей (ускорению или эффективности) может привести к ухудшению ситуации по другому показателю, ибо показатели качества параллельных вычислений являются противоречивыми. Так, например, повышение ускорения обычно может быть обеспечено за счет увеличения числа процессоров, что приводит, как правило, к падению эффективности. И, обратно, повышение эффективности достигается во многих случаях при уменьшении числа процессоров. В предельном случае идеальная эффективность Ep(n)=1 легко обеспечивается при использовании одного процессора. Как результат, разработка методов параллельных вычислений часто предполагает выбор некоторого компромиссного варианта с учетом желаемых показателей ускорения и эффективности. [4]
В результате работы получены следующие данные:
наилучшее ускорение на матрицу 100*100 - 1,33 на двух потоках, и эффективность выше также на двух потоках и составляет 0,67;
наилучшее ускорением на матрицу 500*500 - 1,68 на двух потоках, и эффективность выше также на двух потоках и составляет 0,84;
наилучшее ускорение на матрицу 1000*1000 - 1,15 на четырех потоках, причем эффективность лучше на двух потоках;
наилучшее ускорение на матрицу 2000*2000 - 1,71 на восьми потоках, а эффективность выше на двух потоках и составляет 0,49;
наилучшее ускорение на матрицу 3000*3000 - 2,35 на восьми потоках, а эффективность выше на двух потоках и составляет 0,48;
наилучшее ускорение на матицу 4000*4000 - 4,16 на восьми потоках и эффективность также выше на восьми потоках и составляет 0,52;
наилучшее ускорение на матрицу 5000*5000 - 3,85 на восьми потоках, а эффективность выше на втором потоке и составляет 0,51.
Список используемых источников
1. Решение систем линейных уравнений [Электронный ресурс]. - Режим доступа: http://www.intuit.ru/studies/courses/1156/190/lecture/4956 (Дата обращения 20.05.2016 г).
2. Решение систем линейных уравнений методом Гаусса [Электронный ресурс]. - Режим доступа: http://www.hpcc.unn.ru/?dir=1086 (дата обращения 20.05.2016 г).
3. Технологии параллельного программирования [Электронный ресурс]. - Режим доступа: https://parallel.ru/vvv/mpi.html (Дата обращения 20.05.2016 г).
4. Показатели эффективности параллельного алгоритма [Электронный ресурс]. - Режим доступа:http://www.intuit.ru/studies/courses/4447/983/lecture/14931?page=12 (дата обращения 27.05.2016 г).
Размещено на Allbest.ru
...Подобные документы
Сущность и особенности языка программирования Си. Основные этапы алгоритма решения системы линейных алгебраических уравнений методом Гаусса, реализация программы для их расчета. Инструкции пользователя и программиста. Тестирование функции решения.
курсовая работа [153,9 K], добавлен 18.02.2013Применение численного метода решения систем линейных алгебраических уравнений, используемых в прикладных задачах. Составление на базе метода матрицы Гаусса вычислительной схемы алгоритма и разработка интерфейса программы на алгоритмическом языке.
курсовая работа [823,9 K], добавлен 19.06.2023Преобразование матрицы системы линейных алгебраических уравнений (СЛАУ) с помощью алгоритма Гаусса. Решение задачи методом простой итерации. Создание блок-схемы и текста программы для решения СЛАУ, реализованной на языке программирования Turbo Pascal.
курсовая работа [1,2 M], добавлен 15.06.2013Системы линейных алгебраических уравнений. Код программы для решения систем линейных алгебраических уравнений. Математические и алгоритмические основы решения задачи методом Гаусса. Программная реализация решения. Алгоритмы запоминания коэффициентов.
лабораторная работа [23,5 K], добавлен 23.09.2014Разработка алгоритма составления системы уравнений при помощи законов Кирхгофа по определенной электрической схеме. Приложение для решения данной системы методом Гаусса с выбором ведущего элемента по строке. Описание программы, руководство пользователя.
курсовая работа [435,9 K], добавлен 02.07.2010Решение нелинейных краевых задач. Входные данные и содержание алгоритма Бройдена. Содержание алгоритма Бройдена. Метод исключения Гаусса для решения СЛАУ. Вывод формулы пересчета Бройдена. Разработка программы, исследование результата и примеры ее работы.
курсовая работа [912,3 K], добавлен 01.04.2010Решение системы линейных алгебраических уравнений методом Гаусса с выборкой ведущего элемента. Изучение особенности программной реализации алгоритма, составленной средствами разработки Microsoft Visual Studio. Проведение сложения и умножения двух матриц.
курсовая работа [702,6 K], добавлен 22.03.2015Основные методы решения систем линейных уравнений. Применение способа единственного деления. Способ Гаусса с выбором главного элемента по столбцу и по всей матрице. Сравнение итерационных и прямых методов. Программа решения СЛАУ по методу Гаусса.
курсовая работа [604,0 K], добавлен 28.05.2015Применение итерационных методов численного решения системы линейных алгебраических уравнений при вычислении на ЭВМ. Математические и алгоритмические основы решения задачи, метод Гаусса. Функциональные модели и блок-схемы, программная реализация решения.
курсовая работа [527,5 K], добавлен 25.01.2010Составление алгоритма и программного обеспечения для реализации конечноразностных интерполяционных формул Ньютона, Гаусса и Стирлинга. Описание метода полиномиальной интерполяции. Изучение метода оптимального исключения для решения линейных уравнений.
курсовая работа [19,8 K], добавлен 25.12.2013Разработка программного продукта для решения систем линейных алгебраических уравнений методом Гаусса с помощью ЭВМ. Математическое описание объекта моделирования, начальные и граничные условия. Алгоритм реализации задачи. Использование модуля CRT.
курсовая работа [269,6 K], добавлен 07.01.2016Программный продукт для решения систем линейных уравнений методом Гаусса. Алгоритм для проведения вычислений. Цель разработки и область ее применения. Схема информационных потоков. Метод Гаусса: исключение неизвестных. Проектирование удобного интерфейса.
курсовая работа [340,0 K], добавлен 02.07.2010Алгоритм решения систем линейных уравнений методом Гаусса, его этапы. Система уравнений для определения коэффициентов сплайна, представляющая собой частный случай систем линейных алгебраических уравнений. Программная реализация, тестовый пример.
курсовая работа [431,8 K], добавлен 15.06.2013Разработка алгоритма аппроксимации данных методом наименьших квадратов. Средства реализации, среда программирования Delphi. Физическая модель. Алгоритм решения. Графическое представление результатов. Коэффициенты полинома (обратный ход метода Гаусса).
курсовая работа [473,6 K], добавлен 09.02.2015Сферы использования компьютеров, сущность и языки программирования. Применение модифицированного метода Гаусса и расширенной матрицы для решения системы линейных алгебраических уравнений (СЛАУ). Разработка программы, системные требования для ее работы.
курсовая работа [657,1 K], добавлен 09.01.2014Выполнение арифметических операций, этапы решения задач с помощью ЭВМ - постановка задачи, составление алгоритма решения, программная реализация алгоритма в среде Qbasic. Решение систем линейных уравнений по формулам Крамера. Графический режим Qbasic.
курсовая работа [101,7 K], добавлен 29.09.2009Приведение системы линейных алгебраических уравнений к треугольному виду прямым ходом метода Гаусса. Применение обратного хода метода вращений. Создание алгоритма, блок-схемы и кода программы. Тестовый пример решения уравнения и его проверка в MathCad.
лабораторная работа [164,3 K], добавлен 02.10.2013Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
курсовая работа [1010,4 K], добавлен 10.08.2014Методы решения систем линейных уравнений трехдигонального вида: прогонки, встречных прогонок, циклической редукции. Параллельные алгоритмы решения. Метод декомпозиции области. Основные возможности и особенности технологии CUDA. Анализ ускорения алгоритма.
дипломная работа [1,4 M], добавлен 21.06.2013Решение систем алгебраических линейных уравнений методом Гаусса. Вычисление обратной матрицы и определителя. Декомпозиция задачи. Схема взаимодействия интерфейсных форм. Описание процедур и функций. Тестирование разработанного программного продукта.
курсовая работа [1,1 M], добавлен 05.06.2012