ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ УМНОЖЕНИЯ МАТРИЦ И ВЕКТОРОВ. - презентация

1 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ УМНОЖЕНИЯ МАТРИЦ И ВЕКТОРОВ

2 УМНОЖЕНИЕ МАТРИЦЫ НА ВЕКТОР

3 РЕАЛИЗАЦИЯ ДЛЯ СИСТЕМ С ОБЩЕЙ ПАМЯТЬЮ Обрабатывать различные строки на разных вычислительных ядрах.

4 Пример реализации на OpenMP void mxv(int n, double* a, double* b, double* c) { int i; #pragma omp parallel for for(i = 0; i < n; i ++){ double s = 0.; int j; double *v; v = a + i * n; for(j = 0; j < n; j ++) { s += v[j] * b[j]; } c[i] = s; }

5 УМНОЖЕНИЕ МАТРИЦ: БАЗОВЫЙ АЛГОРИТМ void mxm (int n, double* a, double* b, double* c) { for(i := 0; i < n; i ++) { for(j: =0; j < n; j ++) { c[i*n + j] = 0.; for(k : = 0; k < n; k ++) c[i*n + j] += a[i*n + k] * b[k*n + j]; } Недостаток: доступ по столбцу к элементам матрицы b во внутреннем цикле.

6 УМНОЖЕНИЕ МАТРИЦ: БОЛЕЕ ЭФФЕКТИВНЫЙ АЛГОРИТМ void mxm2(int n, double* a, double* b, double* c) { int i; for(i = 0; i < n; i ++){ int k; for(k = 0; k < n; k ++) { int j; for(j = 0; j < n; j ++) { if(k == 0) c[i * n + j] = 0.; c[i * n + j] += a[i * n + k] * b[k * n + j]; }

7 УМНОЖЕНИЕ МАТРИЦ: РЕАЛИЗАЦИЯ НА OpenMP void mxm2(int n, double* a, double* b, double* c) { int i; #pragma parallel for for(i = 0; i < n; i ++){ int k; for(k = 0; k < n; k ++) { int j; for(j = 0; j < n; j ++) { if(k == 0) c[i * n + j] = 0.; c[i * n + j] += a[i * n + k] * b[k * n + j]; }

8 РЕЗУЛЬТАТЫ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА Число потоковБазовый алгоритм Улучшенный алгоритм Рассматривается матрица 1024x1024, процессор 4 core Xeon, 3 GHz Число потоковБазовый алгоритм Улучшенный алгоритм Без компилятороной оптимизации С оптимизацией (-О)