Умножение матриц (g++)

@Ksardas_178 · Регистрация: 01.01.2018

Author24 — интернет-сервис помощи студентам

Имеется демонстрационный код (умножение матриц). Структура вида:

-Инициализация данных
-Алгоритм без распараллеливания
-Алгоритм с использованием директивы openMP (parallel for)

После каждого из алгоритмов выводится время выполнения.
Компилирую так:

Код

$ g++ fileName -o -matrix -fopenmp
$ ./matrix

Прирост производительности - нулевой. Причем разделение на потоки происходит - достаточно раскомментировать соответствующие строчки и посмотреть вывод. В чем проблема?

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#include <cstdio>
#include <ctime>
#include <omp.h>
 
using namespace std;
 
const int n=1000;
double a[n][n];
double b[n][n];
double c[n][n];
 
 
int main(int argc, char *argv[])
{
    /*init*/
    
    for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
    {
        a[i][j] = (rand() % 100)/100.0+1.0;
        b[i][j] = (rand() % 100)/100.0+1.0;
    }
 
    /*First block (single)*/
    
    long t1 = clock();
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++)
        {
            //printf ("iteration %d, thread=%d\n", j, omp_get_thread_num());
            double cc = 0;
            for (int k=0; k<n; k++)
                cc += a[i][k]*b[k][j];
            c[i][j] = cc;
        }
    }
    
    long t2 = clock();
 
    cout<<c[n-1][n-1]<<endl;
    cout<<(t2-t1)/1000.0<<" - total time single (ms)"<<endl;
    
    t1 = clock();
    
    /*Second block (parallel)*/
        
    #pragma omp parallel for
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++)
        {
            //printf ("iteration %d, thread=%d\n", j, omp_get_thread_num());
            double cc = 0;
            for (int k=0; k<n; k++)
                cc += a[i][k]*b[k][j];
            c[i][j] = cc;
        }
    }
    
    t2 = clock();
 
    cout<<c[n-1][n-1]<<endl;
    cout<<(t2-t1)/1000.0<<" - total time parallel (ms)"<<endl;
    return 0;
}

@VTsaregorodtsev · 09.12.2020, 16:54

Сообщение от Ksardas_178

В чем проблема?

Проблема совсем не в этом. Проблема в том, что пытаетесь распараллелить говнокод.
А именно - хреновый паттерн доступа к памяти (при обращении к элементам матрицы b).
Перед перемножением транспонируйте матрицу b (т.е. в коде затем будет умножаться строка из a на строку из b^T) - и перемножение ускорится в разы даже без распараллеливания.
Для более быстрого проведения эксперимента можете даже не транспонировать - а предположить, что матрица b уже транспонирована, и просто переставить в умножающей строке индексы (будет *b[j][k]).
Ждём-с цифр времени выполнения исходного варианта кода и предлагаемого транспонированного

@Ksardas_178 · 09.12.2020, 19:06 **[ТС]**

Сообщение от VTsaregorodtsev

Перед перемножением транспонируйте матрицу b (т.е. в коде затем будет умножаться строка из a на строку из bT) - и перемножение ускорится в разы даже без распараллеливания.

Да, встречал в одном примере такой эффект. Что-то про опережающее считывание в кэш процессора. Даже в этой программе пробовал. Сейчас написал еще раз, добавил двойной for для транспонирования, вынес за расчет времени выполнения. В этом случае - да, есть "минус" по времени. Параллельный код все еще жрет столько же, сколько нераспараллеленный.

Кликните здесь для просмотра всего текста

C++

#include <iostream>
#include <cstdio>
#include <ctime>
#include <omp.h>
 
using namespace std;
 
const int n=1000;
double a[n][n];
double b[n][n];
double c[n][n];
 
 
int main(int argc, char *argv[])
{
    /*init*/
    
    for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
    {
        a[i][j] = (rand() % 100)/100.0+1.0;
        b[i][j] = (rand() % 100)/100.0+1.0;
    }
    
    
    for (int i=0; i<n; i++) 
    for (int j=0; j<i; j++) 
        swap(b[i,j],b[j,i]);
 
    /*First block (single)*/
    
    long t1 = clock();
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++)
        {
            //printf ("iteration %d, thread=%d\n", j, omp_get_thread_num());
            double cc = 0;
            for (int k=0; k<n; k++)
                cc += a[i][k]*b[j][k];
            c[i][j] = cc;
        }
    }
    
    long t2 = clock();
 
    cout<<c[n-1][n-1]<<endl;
    cout<<(t2-t1)/1000.0<<" - total time single (ms)"<<endl;
    
    /*Second block (parallel)*/
        
    t1 = clock();
    
    #pragma omp parallel for
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++)
        {
            //printf ("iteration %d, thread=%d\n", j, omp_get_thread_num());
            double cc = 0;
            for (int k=0; k<n; k++)
                cc += a[i][k]*b[j][k];
            c[i][j] = cc;
        }
    }
    
    t2 = clock();
 
    cout<<c[n-1][n-1]<<endl;
    cout<<(t2-t1)/1000.0<<" - total time parallel (ms)"<<endl;
    return 0;
}

@oleg-m1973 · 09.12.2020, 20:00

Сообщение от Ksardas_178

Параллельный код все еще жрет столько же, сколько нераспараллеленный.

У меня твой код показывает

2260.33
1.291 - total time single (ms)
2260.33
0.25 - total time parallel (ms)

Добавлено через 1 минуту
И в дебаге примерно такое же соотношение

Добавлено через 37 секунд
Ты наверное openmp не включил в опциях компилятора

Добавлено через 4 минуты
И где ты проверяешь, на локальном компе?

@Ksardas_178 · 09.12.2020, 20:07 **[ТС]**

Сообщение от oleg-m1973

Ты наверное openmp не включил в опциях компилятора

Все подключаемые опции привел в первом сообщении.

Сообщение от oleg-m1973

И где ты проверяешь, на локальном компе?

Да, на своем локальном и у сокурсника.

@oleg-m1973 · 09.12.2020, 20:11

Сообщение от Ksardas_178

Да, на своем локальном и у сокурсника.

Ну, в Visual C++ всё работает нормально, я показал. Проверить на gcc возможности нет, но проблема, скорее всего не в коде

@Ksardas_178 · 09.12.2020, 22:53 **[ТС]**

Проблема была в использованной библиотеке для подсчета времени выполнения. Как мне объяснили, clock() выдает суммарное время работы всех потоков. Заменили на chrono - все заработало.

@VTsaregorodtsev 1566 / 1492 / 248 Регистрация: 19.02.2010 Сообщений: 4,048
	09.12.2020, 16:54	2
	Сообщение от Ksardas_178 В чем проблема? Проблема совсем не в этом. Проблема в том, что пытаетесь распараллелить говнокод. А именно - хреновый паттерн доступа к памяти (при обращении к элементам матрицы b). Перед перемножением транспонируйте матрицу b (т.е. в коде затем будет умножаться строка из a на строку из b^T) - и перемножение ускорится в разы даже без распараллеливания. Для более быстрого проведения эксперимента можете даже не транспонировать - а предположить, что матрица b уже транспонирована, и просто переставить в умножающей строке индексы (будет *b[j][k]). Ждём-с цифр времени выполнения исходного варианта кода и предлагаемого транспонированного 1

@oleg-m1973 6770 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	09.12.2020, 20:00	4
	Сообщение от Ksardas_178 Параллельный код все еще жрет столько же, сколько нераспараллеленный. У меня твой код показывает 2260.33 1.291 - total time single (ms) 2260.33 0.25 - total time parallel (ms) Добавлено через 1 минуту И в дебаге примерно такое же соотношение Добавлено через 37 секунд Ты наверное openmp не включил в опциях компилятора Добавлено через 4 минуты И где ты проверяешь, на локальном компе? 1

@Ksardas_178 58 / 42 / 21 Регистрация: 01.01.2018 Сообщений: 273
	09.12.2020, 20:07 [ТС]	5
	Сообщение от oleg-m1973 Ты наверное openmp не включил в опциях компилятора Все подключаемые опции привел в первом сообщении. Сообщение от oleg-m1973 И где ты проверяешь, на локальном компе? Да, на своем локальном и у сокурсника. 0

@oleg-m1973 6770 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	09.12.2020, 20:11	6
	Сообщение от Ksardas_178 Да, на своем локальном и у сокурсника. Ну, в Visual C++ всё работает нормально, я показал. Проверить на gcc возможности нет, но проблема, скорее всего не в коде 1

@Ksardas_178 58 / 42 / 21 Регистрация: 01.01.2018 Сообщений: 273
	09.12.2020, 22:53 [ТС]	7
	Проблема была в использованной библиотеке для подсчета времени выполнения. Как мне объяснили, clock() выдает суммарное время работы всех потоков. Заменили на chrono - все заработало. 0