OpenMPLab2015_1

Задание 1.

Решение систем линейных уравнений методом Гаусса .

Исследование эффективности параллельной OpenMP-программы.

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

Дана параллельная OpenMP-программа для решения систем линейных уравнений

Ах=b,

где А – матрица размером nxn, в – вектор размером n элементов. Размер матрицы задается в файле data.in.

Требуется провести исследование эффективности параллельной программы.

Требуется.

1. Исследовать время решения задачи в зависимости от размера матрицы и количества используемых ядер на суперкомпьютерном комплексе «Ломоносов».

2. Построить таблицу:

Размер системы	Последовательный алгоритм	Параллельный алгоритм
		1 ядро		2 ядра		4 ядра		8 ядер
		Время	Ускорение	Время	Ускорение	Время	Ускорение	Время	Ускорение
2000
3000
4000
6000
7000

Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, определяется величиной:

Speedup(n) = T₁(n)/T_p(n),

где T₁(n)- время последовательного выполнения задачи,

Tp(n)- время параллельного выполнения задачи при использовании p процессоров.

1. Построить графики - зависимость ускорения от количества ядер для разных размеров систем линейных уравнений.

2. Сделать выводы по полученным результатам (объяснить убывание или возрастание производительности параллельной программы при увеличении числа используемых процессоров, сравнить поведение параллельной программы в зависимости от размера матрицы).

Методические указания.

1. Алгоритм Гаусса.

2. Трансляция OpenMP программ.

3. Запуск программы на счет.

4. Параллельная программа.

5. Литература.

1. Алгоритм Гаусса.

Метод Гаусса основывается на возможности выполнения преобразований линейных уравнений, которые не меняют при этом решение рассматриваемой системы (такие преобразования носят наименование эквивалентных).

К числу таких преобразований относятся:

• Умножение любого из уравнений на ненулевую константу.

• Перестановка уравнений.

• Прибавление к уравнению любого другого уравнения системы.

Метод Гаусса включает последовательное выполнение двух этапов.

На первом этапе – прямой ход метода Гаусса – исходная система линейный уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду.

На итерации i, 0≤ i<n-1, метода производится исключение неизвестной i для всех уравнений с номерами k, больших i (т.е. i<k≤n-1,). Для этого из этих уравнений осуществляется вычитание строки i, умноженной на константу (a_ki/a_ii) с тем, чтобы результирующий коэффициент при неизвестной x_i в строках оказался нулевым – все необходимые вычисления могут быть определены при помощи соотношений:

a^'_kj=a_kj- (a_ki /a_ii)*a_ij

b'_k=b_k- (a_ki /a_ii)*b_i

где i≤j≤n-1,i<k≤n-1, 0≤i<n-1.

На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной x_n-1, после этого из предпоследнего уравнения становится возможным определение переменной x_n-2 и т.д. В общем виде, выполняемые вычисления при обратном ходе метода Гаусса могут быть представлены при помощи соотношений:

, i=n-2,n-3,...0

Если система линейных уравнений является невырожденной, то метод Гаусса гарантирует нахождение решения с погрешностью, определяемой точностью машинных вычислений.

1. Трансляция OpenMP-программ.

   1. Для входа в среду компиляции на суперкомпьютере «Ломоносов» введите команду

ssh compiler

1. Для компиляции OpenMP-программы c использованием компилятора GCС:

/usr/bin/gcc -fopenmp <имя_программы>.c -o <имя_программы>

1. Для компиляции OpenMP-программы c использованием компилятора Intel:

/opt/intel/composerxe/bin/icc -openmp -o <имя_программы> <имя_программы>.c

1. Для компиляции OpenMP-программы c использованием компилятора Portland Group:

/opt/pgi/linux86-64/2012/bin/pgcc -mp -o <имя_программы> <имя_программы>.c

1. Запуск OpenMP-программы на счет.

   1. Для запуска OpenMP-программы на счет на суперкомпьютере «Ломоносов»:

установите количество нитей, которые требуются для выполнения программы:

export OMP_NUM_THREADS=<количество нитей>

и используйте команду:

sbatch –p <раздел системы очередей> run ./<имя_программы>

Например,

export OMP_NUM_THREADS=4

sbatch -p test run ./gauss_omp

Текущая конфигурация суперкомпьютера «Ломоносов» доступна:

http://parallel.ru/cluster/actual-T500.html

1. Параллельная программа.

/* GAUSS_OMP */ #include <math.h> #include <stdlib.h> #include <stdio.h> #include <sys/time.h> #ifdef _OPENMP #include <omp.h> #endif void prt1a(char *t1, double *v, int n,char *t2) ; void wtime(double *t) { static int sec = -1; struct timeval tv; gettimeofday(&tv, (void *)0); if (sec < 0) sec = tv.tv_sec; *t = (tv.tv_sec - sec) + 1.0e-6*tv.tv_usec; } int N; double *A; #define A(i,j) A[(i)*(N+1)+(j)] double *X; int main(int argc,char **argv){ double time0, time1; FILE *in; int i, j, k; in=fopen("data.in","r"); if(in==NULL) { printf("Can not open 'data.in' "); exit(1); } i=fscanf(in,"%d", &N); if(i<1) { printf("Wrong 'data.in' (N ...)"); exit(2); } /* create arrays */ A=(double *)malloc(N*(N+1)*sizeof(double)); X=(double *)malloc(N*sizeof(double)); printf("GAUSS %dx%d\n----------------------------------\n",N,N); /* time0=omp_get_wtime (); */ wtime(&time0); #pragma omp parallel private(k,j,i) shared(A,X) { /* initialize array A*/ #pragma omp for for(i=0; i <= N-1; i++) for(j=0; j <= N; j++) if (i==j || j==N) A(i,j) = 1.f; else A(i,j)=0.f; /* elimination */ for (i=0; i<N-1; i++) { #pragma omp for for (k=i+1; k <= N-1; k++) for (j=i+1; j <= N; j++) A(k,j) = A(k,j)-A(k,i)*A(i,j)/A(i,i); } /* reverse substitution */ #pragma omp single X[N-1] = A(N-1,N)/A(N-1,N-1); for (j=N-2; j>=0; j--) { #pragma omp for for (k=0; k <= j; k++) A(k,N) = A(k,N)-A(k,j+1)*X[j+1]; X[j]=A(j,N)/A(j,j); } } /* end of parallel */ wtime(&time1); /* time1=omp_get_wtime (); */ #ifdef _OPENMP printf("Number of threads=%d\n",omp_get_max_threads()); #endif printf("Time in seconds=%gs\n",time1-time0); prt1a("X=(", X,N>9?9:N,"...)\n"); free(A); free(X); return 0; } void prt1a(char * t1, double *v, int n,char *t2){ int j; printf("%s",t1); for(j=0;j<n;j++) printf("%.4g%s",v[j], j%10==9? "\n": ", "); printf("%s",t2); }

1. Литература.

• Презентация «Технология параллельного программирования OpenMP»:

ftp://ftp.keldysh.ru/K_student/Academy2015/OpenMP.ppt

• Антонов А.С. "Параллельное программирование с использованием технологии OpenMP: Учебное пособие".-М.: Изд-во МГУ, 2009. - 77 с. http://parallel.ru/info/parallel/openmp/

• OpenMP Application Program Interface. Version 3.1 July 2011

http://www.openmp.org/mp-documents/OpenMP3.1.pdf

• Инструкция по использованию суперкомпьютерного комплекса «Ломоносов»

http://parallel.ru/sites/default/files/cluster/T500_user_guide-3.pdf