Умножение матрицы на вектор

Умножение матрицы на вектор

Коллеги,

Тривиальная программа умножения матрицы на вектор:

#define n 5000
double a[n][n], b[n], c[n];

int _tmain (int argc, char *argv[])
{
  omp_set_num_threads (1);
  double start = omp_get_wtime ();

#pragma omp parallel for
  for (int i = 0; i < n; i++)
    {
      c[i] = 0;
      for (int k = 0; k < n; k++)
        {
          c[i] += a[i][k] * b[k];
        }

    }
  printf ("time = %lf (%d)\\n", omp_get_wtime () - start, omp_get_num_threads());
}

время работы: 1 поток 0.17 с, 2 потока 0.18 с, 4 потока 0.18 с (время колеблется вокруг этих
цифр).  Процессор Intel Core 2 Quad. Вопрос: почему не ускоряется?

Intel Amplifier показывает плохую утилизацию процессора, но не понятна причина. Больше всего красного в Sleep  - который вообще не вызывается. Не подскажете, что с этим всем делать?

10 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.
Dmitry Vyukov's picture

Я думаю, что причина не Sleep(), а в том, что программа упирается в пропускную способность памяти. Фактически тут на одно обращение к памяти приходится всего одно умножение, это слишком мало. По большому счёту с этим ничего нельзя сделать, не считая покупки NUMA машины или кардинальной переработки алгоритма.

All about lock-free algorithms, multicore, scalability, parallel computing and related topics: http://www.1024cores.net
Dmitry Vyukov's picture

На оригинальной программе я получаю следующий вывод:

threads = 1
time = 108.369310
time = 44.251929
time = 44.033111

threads = 2
time = 40.108161
time = 40.132069
time = 39.615010

Для проверки гипотезы сделаем побольше вычислений на одно обращение к памяти:

#   pragma omp parallel for
    for (int i = 0; i < n; i++)
    {
        double tmp = 0.0;
        for (int k = 0; k < n; k++)
            tmp += a[i][k] * b[k] + a[i][k] / b[k] + b[k] / a[i][k] + a[i][k] * a[i][k] + b[k] * b[k];
        c[i] = tmp;
    }

Результат:

threads = 1
time = 202.449791
time = 140.509652
time = 141.707479

threads = 2
time = 111.192875
time = 78.628269
time = 78.984457

Программа стала хорошо масштабироваться.

All about lock-free algorithms, multicore, scalability, parallel computing and related topics: http://www.1024cores.net

Дмитрий, спасибо за ответ. Наверное, Вы правы. Наверное, но чтобы ответитьь точно, нужна профилировочная информация по памяти (cache hit/miss etc. ) Не знаете, с помощью каких инструментов можно было бы эти времена замерить?

Дмитрий, а что означает три времени? Как Вы их вычисляете?

Dmitry Vyukov's picture

ЦитироватьMikhail Posypkin
Дмитрий, а что означает три времени? Как Вы их вычисляете?

 

Просто 3 раза подряд запускаю в цикле. Видно, что первый раз идёт "прогрев".

 

 

All about lock-free algorithms, multicore, scalability, parallel computing and related topics: http://www.1024cores.net
Dmitry Vyukov's picture

ЦитироватьMikhail Posypkin
Дмитрий, спасибо за ответ. Наверное, Вы правы. Наверное, но чтобы ответитьь точно, нужна профилировочная информация по памяти (cache hit/miss etc. ) Не знаете, с помощью каких инструментов можно было бы эти времена замерить?

 

Intel PTU/AMD CodeAnalyst.

Более простой вариант - отпрофилировать однопоточный и многопоточный вариант и поглядеть в каких местах в многопоточном варианте возрастает время. Если программа упирается в память, то падение производительности (возрастание времени) будет на инструкциях загрузки из массивов a и b. Это я к тому, что не обязательно спускаться на уровень счётчиков производительности (cache miss).

 

All about lock-free algorithms, multicore, scalability, parallel computing and related topics: http://www.1024cores.net
yuriisig's picture

На i7 860 при использовании всех ядер получаю ускорение 2.03 для исходного кода (поправку на частоту ввел)

Legendary intelligence officer Drozdov was nicknamed «Fabergé» owing to his unique capability to work with information, to get information, and to convert it into the most precious treasures.

Цитироватьyuriisig

На i7 860 при использовании всех ядер получаю ускорение 2.03 для исходного кода (поправку на частоту ввел)

 
Ядер ( 4 ) или потоков ( 8 ) ?

yuriisig's picture

ЦитироватьyuryserdyukЯдер ( 4 ) или потоков ( 8 ) ?

 Я HT не пользую.

Legendary intelligence officer Drozdov was nicknamed «Fabergé» owing to his unique capability to work with information, to get information, and to convert it into the most precious treasures.

Login to leave a comment.