Современные информационные технологии/Вычислительная техника и программирование

Кравчук В.П.,Мясіщев О.А.

Хмельницький національний університет

Дослідження ефективності компіляторів та бібліотек Intel у паралельних обчисленнях в галузі лінійної алгебри.

З розвитком науки з'являється все більше задач, що потребують інтенсивних обчислень для їх вирішення. Однією з найбільш широко зустрічаючихся задач лінійної алгебри є задача вирішення системи лінійних рівнянь, якими можна описати деякі процеси. Ця задача має кілька підходів до вирішення, але ті з підходів, які можуть бути автоматизовані, є досить схожими, а алгоритми їх відомі. Звичайно, одним з основних питань, що постає при дослідженні різних шляхів вирішення задачі є питання ефективності, тобто швидкості обчислень.

Швидкість вирішення задач залежить від набору факторів, які можна розділити на дві групи: ефективність технічних засобів та ефективність програмного забезпечення. Ці два фактори тісно пов'язані одне з одним, адже належне використання технічних засобів забезпечується саме програмною частиною. В той же час, в компетенції розробника є лише програмні інструменти.

Основні аспекти програмного забезпечення, що впливають на швидкість обчислень:

1.Компілятор, що використовується.

2.Використання спеціальних бібліотек, якість вихідного коду програми, використання спеціальних бібліотек.

3.Застосування паралелізму.

Саме дослідженню можливості пришвидшення обчислень систем лінійних рівнянь за допомогою найоптимальнішого використання програмних засобів і присвячена дана робота.

Вибір компілятора.

Як відомо, компілятор призначений, грубо кажучи, для перетворення програми, написаної на деякій мові програмування високого рівня у її еквівалент в машинному коді, який може бути виконаний безпосередньо центральним процесором.

Відповідно, перетворити вихідний код у виконуваний можна різними шляхами і результат з точки зору швидкодії також буде різним. Виробники компіляторів намагаються втілювати нові розробки, що дозволяють оптимізувати виконання, застосовують технології, що здатні пришвидшити виконання програми за рахунок використання спеціальних інструкції процесорів, багатопоточності, тощо.

Операційні системи сімейства Linux досить широко використовуються для виконання обчислень різними організаціями, завдяки відкритості коду, безкоштовності та наявних можливостей для створення високопродуктивних обчислювальних кластерів.

В якості мови програмування, що використовується для написання специфічних програм, що виконують обчислення в галузі лінійної алгебри, набули широкого вжитку Fortran та C++. Не дивлячись на те, що перший компілятор Fortran був розроблений у 1957 році, ця мова продовжує служити інженерним та математичним задачам більш ніж п’ятдесят років потому. C++ є набагато новішою та більш широко використовуваною мовою, що продовжує активно розвиватись.

Серед компіляторів Fortran для Linux є два основних – GNU Fortran (gfortran) та Intel Fortran. Основними компіляторами C++ також є компілятор GNU що входить до набору GCC та Intel C++ Compiler.

Компілятори GNU є безкоштовними та розповсюджується під ліцензією GNU General Public License.

Компілятори Intel є комерційними продуктами, проте є безкоштовна версія компіляторів під Linux для некомерційного використання. Компілятори Intel є цікавими з тієї точки зору, що Intel одночасно є виробником процесорів та намагається підвищити швидкодію скомпільованих програм на процесорах свого виробництва за рахунок використання спеціальних інструкцій.

Використання спеціальних бібліотек.

На даний момент в програмуванні в цілому продовжує розвиватись тенденція до використання бібліотек та фреймворків, які містять набори коду для вирішення найбільш розповсюджених задач. Цей підхід в цілому є виправданим, так як дозволяє заощадити час, витрачений на розробку програми і при цьому часто дає приріст у швидкодії за рахунок того, що функції в бібліотеках постійно вдосконалюються, а над ними працюють команди досвідчених розробників. Тому, коли задачу можна вирішити за допомогою функцій з готових бібліотек, то це часто є більш доцільним аніж власноручне створення програми «з нуля».

Для компіляторів GNU, основною бібліотекою, що реалізує операції лінійної алгебри є бібліотека LAPACK і її версія для систем з розподіленою пам'яттю ScaLAPACK. Також існує бібліотека PARDISO, що призначена конкретно для вирішення систем лінійних рівнянь і дає найкращі результати при вирішенні систем, в яких матриця коефіцієнтів містить достатньо нулів. Код бібліотеки PARDISO є закритим, проте є можливість безкоштовно отримати ліцензію для академічного користування.

Для компіляторів Intel існує власна розробка — інтегрована бібліотека MKL. При цьому, бібліотека доступна для некомерційного використання на таких же умовах, що і компілятор. До складу MKL входять BLAS, LAPACK, ScaLAPACK, PARDISO та додаткові засоби для виконання математичних операцій, при чому вищезгадані бібліотеки вже модифіковані для надання оптимальної швидкодії, багато з функцій у них вже використовують паралелізм та оптимізовані для використання з процесорами Intel. MKL має вбудовану підтримку OpenMP і вдало інтегрується з такими IDE як Eclipse, Microsoft Visual Studio, XCode.

Застосування паралелізму.

Безперечно, найкращі показники швидкодії можуть бути досягнуті лише при повному використанні наявних в системі ресурсів, а саме ядер процесора коли йде мова про одну обчислювальну машину з багатоядерним процесором.

Бібліотека MKL автоматично намагається застосовувати паралелізм і самостійно завантажувати наявні в системі процесори та їх ядра. У разі ж відмови від використання готових бібліотек паралелізм можна достигнути за допомогою MPI та OpenMP.

Розв'язування системи лінійних рівнянь з використанням компілятора Intel C++ та бібліотеки PARDISO.

Розглянемо варіант розв'язання системи лінійних алгебраїчних рівнянь за допомогою бібліотеки PARDISO та компілятора Intel C++.

У бібліотеці PARDISO існує функція pardiso що і проводить вирішення системи рівнянь, а також кроки, що допомагають оптимізувати процес вирішення шляхом попереднього впорядкування матриць.

Загальний синтаксис функції має наступне представлення:

pardiso (pt, maxfct, mnum, mtype, phase, n, a, ia, ja, perm, nrhs, iparm, msglvl, b, x, error).

Важливою деталлю є те, що значення iparm[12] за замовчуванням рівне 1 для несиметричних матриць, але як стало відомо в результаті досліджень, цей параметр надзвичайно негативно впливав на швидкість обчислень за рахунок інтенсивного використання пам'яті. Зміна цього параметру на 0 допомгла збільшити швидкість обчислень приблизно в 10 раз.

Розглянемо приклад розв'язання системи лінійних рівнянь:

x₁ – x₂ – 3x₄ = 1

-2x₁ + 5x₂ = 1

4x₃ + 6x₄ + 4x₅ = 1

-4x₁ + 2x₃ + 7x₄ = 1

8x₂ – 5x₅ = 1

При таких умовах необхідно задати наступні вхідні змінні:

int n = 5;

int ia[ 6] = { 1, 4, 6, 9, 12, 14 };

int ja[13] = { 1, 2, 4, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5 };

double a[18] = { 1.0, -1.0, -3.0, -2.0, 5.0, 4.0, 6.0, 4.0, -4.0, 2.0, 7.0,8.0, -5.0};

int mtype = 11;

nrhs = 1;

b[5] = {1, 1, 1, 1, 1};

iparm[0] = 1; /* No solver default */

iparm[1] = 2; /* Fill-in reordering from METIS */

/* Numbers of processors, value of OMP_NUM_THREADS */

iparm[2] = 2;

iparm[3] = 0; /* No iterative-direct algorithm */

iparm[4] = 0; /* No user fill-in reducing permutation */

iparm[5] = 0; /* Write solution into x */

iparm[6] = 0; /* Not in use */

iparm[7] = 2; /* Max numbers of iterative refinement steps */

iparm[8] = 0; /* Not in use */

iparm[9] = 13; /* Perturb the pivot elements with 1E-13 */

iparm[10] = 1; /* Use nonsymmetric permutation and scaling MPS */

iparm[11] = 0; /* Not in use */

iparm[12] = 0; /* Maximum weighted matching algorithm is switched-on (default for non-symmetric) */

iparm[13] = 0; /* Output: Number of perturbed pivots */

iparm[14] = 0; /* Not in use */

iparm[15] = 0; /* Not in use */

iparm[16] = 0; /* Not in use */

iparm[17] = -1; /* Output: Number of nonzeros in the factor LU */

iparm[18] = -1; /* Output: Mflops for LU factorization */

iparm[19] = 0; /* Output: Numbers of CG Iterations */

maxfct = 1; /* Maximum number of numerical factorizations. */

mnum = 1; /* Which factorization to use. */

msglvl = 1; /* Print statistical information in file */

error = 0; /* Initialize error flag */

Виконуємо перестановку, факторизацію, та обчислення:

phase = 13;

PARDISO (pt, &maxfct, &mnum, &mtype, &phase,

&n, a, ia, ja, &idum, &nrhs,

iparm, &msglvl, b, x, &error);

В кінці очищуємо пам'ять:

phase = -1; /* Release internal memory. */

PARDISO (pt, &maxfct, &mnum, &mtype, &phase,

&n, &ddum, ia, ja, &idum, &nrhs,

iparm, &msglvl, &ddum, &ddum, &error);

В результаті виконання отримано:

x [0] = -0.522321

x [1] = -0.008929

x [2] = 1.220982

x [3] = -0.504464

x [4] = -0.214286

Розв'язування системи лінійних рівнянь з використанням компілятора Intel C++ та бібліотеки LAPACK.

До складу бібліотеки LAPACK входить набір функцій

?gesv( int* n, int* nrhs, double* a, int* lda, int* ipiv, double* b, int* ldb, int* info );

В залежності від типу даних, над якими проводяться обчислення, підставляється перша літера в назві функції. У нашому випадку для чисел подвійної точності функція називається dgesv.

Варто зауважити, що без спеціалізованих ключів компілятора, програма не могла проводити обчислення систем рівнянь з більше ніж 1000 невідомими та повертала помилку segmentation fault. Для того, щоб запобігти цій помилці необхідно виконати команду ulimit -s unlimited перед компіляцією та компілювати з ключем -std=c99.

Програма, що виконує обчислення за допомогою бібліотеки LAPACK на базі згенерованої системи в 1000 рівнянь приведена нижче:

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

/* DGESV prototype */

extern void dgesv( int* n, int* nrhs, double* a, int* lda, int* ipiv,

double* b, int* ldb, int* info );

/* Parameters */

#define N 1000

#define NRHS 1

#define LDA N

#define LDB N

/* Main program */

int main() {

/* Locals */

int n = N, nrhs = NRHS, lda = LDA, ldb = LDB, info;

/* Local arrays */

int i,j,z;

int *ipiv[N];

double a[N][N], b[LDB*NRHS], o;

z=0;

for(i=1; i<(n+1); i++) {

for(j=1; j<(n+1); j++) {

o = (i+j)/0.89;

if(i==j-1) o = 10;

if(i==j+1) o = 2;

a[i-1][j-1]=o;

z++;

}

}

for(i=1; i<(n+1); i++) b[i-1] = (i*21 + 101) / 1.3;

dgesv( &n, &nrhs, a, &lda, ipiv, b, &ldb, &info );

/* Check for the exact singularity */

if( info > 0 ) {

printf( "The diagonal element of the triangular factor of A,\n" );

printf( "U(%i,%i) is zero, so that A is singular;\n", info, info );

printf( "the solution could not be computed.\n" );

exit( 1 );

}

exit( 0 );

}

Розв'язування системи лінійних рівнянь з використанням компілятора Intel C++ та програми, написаної з використанням OpenMP.

Коли немає можливості використовувати бібліотеки сторонніх розробників, можна власноруч створити програму для вирішення задачі. Розпаралелювання було виконане за допомогою засобів розпаралелювання циклу for в OpenMP. Текст програми що знаходить корені системи 1000 рівнянь наведено нижче:

#include <stdlib.h>

#include <stdio.h>

#include <omp.h>

#define ABS(x) (x < 0 ? -(x) : (x))

#define EPS 0.00001

#define TRUE 1

#define FALSE 0

#define N 1000

int GSolve(double **a,int n,double *x)

{

int i,j,k,maxrow;

double tmp;

for (i=0;i<n;i++) {

/* Find the row with the largest first value */

maxrow = i;

for (j=i+1;j<n;j++) {

if (ABS(a[i][j]) > ABS(a[i][maxrow]))

maxrow = j;

}

/* Swap the maxrow and ith row */

for (k=i;k<n+1;k++) {

tmp = a[k][i];

a[k][i] = a[k][maxrow];

a[k][maxrow] = tmp;

}

if (ABS(a[i][i]) < EPS) return(FALSE);

/* Eliminate the ith element of the jth row */

#pragma omp parallel for

for (j=i+1;j<n;j++) {

for (k=n;k>=i;k--) {

a[k][j] -= a[k][i] * a[i][j] / a[i][i];

}

}

}

/* Do the back substitution */

for (j=n-1;j>=0;j--) {

tmp = 0;

for (k=j+1;k<n;k++)

tmp += a[k][j] * x[k];

x[j] = (a[n][j] - tmp) / a[j][j];

}

return(TRUE);

}

int main(int argc,char **argv)

{

int i,j,z,n = N;

double x[N], o;

double **a;

a = (double **)malloc((n+1)*sizeof(double *));

for (i=0;i<n+1;i++)

a[i] = (double *)malloc(n*sizeof(double));

z = 0;

for(i=1; i<(n+1); i++) {

for(j=1; j<(n+1); j++) {

o = (i+j)/0.89;

if(i==j-1) o = 10;

if(i==j+1) o = 2;

a[i-1][j-1]=o;

z++;

}

}

for(i=0; i<n; i++) {x[i] = 0; a[n][i] = ((i+1)*21 + 101) / 1.3;}

GSolve(a,n,x);

}

Порівняння швидкодії.

Для оцінки швидкодії обчислень програми, згадані вище були запущені для розв'язання систем рівнянь з кількістю невідомих від 1000 до 7000. В кожному випадку рівняння були однакові, так як генерувались за одним і тим же алгоритмом.

Час виконання замірявся за допомогою вбудованих функцій бібліотеки PARDISO та програми time для Ubuntu 9.10.

Для обчислень використовувалась обчислювальна машина на базі Intel(R) Core(TM)2 Duo CPU T5550 @ 1.83GHz, 3 GB RAM, Linux Ubuntu 9.10. Результати наведені у таблиці.

PARDISO:

Кількість рівнянь	Час виконання на одному ядрі, сек.	Час виконання на двох ядрах, сек.	Прискорення
1000	0.45	0.37	1.22
2000	2.25	1.7	1.32
3000	6.13	4.42	1.39
4000	12.84	8.83	1.45
5000	23.06	15.3	1.51
6000	37.6	24.89	1.51
7000	56.75	36.7	1.55

LAPACK:

Кількість рівнянь	Час виконання на одному ядрі, сек.	Час виконання на двох ядрах, сек.	Прискорення
1000	0.24	0.45	0.53
2000	1.34	0.95	1.41
3000	3.54	2.57	1.38
4000	8.04	5.86	1.37
5000	14.99	10.63	1.41
6000	25.29	17.27	1.46
7000	44.89	27.79	1.62

Власна програма з OpenMP:

Кількість рівнянь	Час виконання на одному ядрі, сек.	Час виконання на двох ядрах, сек.	Прискорення
1000	7.66	4.95	1.55
2000	61.71	35.12	1.76
3000	209.55	114.19	1.84
4000	509.1	279.93	1.82
5000	1021.32	608.93	1.68

Висновки.

1.Використання спеціалізованих бібліотек є доцільним та дає приріст швидкодії до 60 раз в порівнянні з простою програмою, що використовує OpenMP.

2.Бібліотека PARDISO дещо поступається бібліотеці LAPACK у швидкодії, але це можна пояснити оптимізацією цієї бібліотеки під системи рівнянь, де є значна кількість нулів у матриці коефіцієнтів.

3.Спеціалізовані бібліотеки все ще дають прискорення при використанні кількох ядер. Це прискорення є меншим ніж прискорення в простій програмі з використанням OpenMP, що пояснюється значною оптимізацією алгоритмів.

4.Прискорення у простій програмі з використанням OpenMP є значним, найкращий показник досягається при обчисленні систем з 3000-4000 рівнянь.

Література.

1.Intel® Math Kernel Library 10.2 Reference Manual. http://software.intel.com/sites/products/documentation/hpc/compilerpro/en-us/cpp/win/mkl/refman/index.htm — 2010

2.Intel® Math Kernel Library 10.2 User's Guide http://software.intel.com/sites/products/documentation/hpc/mkl/lin/index.htm — 2010

3.Intel® Math Kernel Library 9.0 for Linux Technical User Notes http://www.intel.com/software/products/mkl/docs/mklusel.htm — 2006

4.Форуми Intel MKL http://software.intel.com/en-us/forums/intel-math-kernel-library/

5.PARDISO Solver Project http://www.pardiso-project.org/index.php?p=manual

6.LAPACK — Linear Algebra Package http://www.netlib.org/lapack/