Песочница
весёлый усач 25 июля 2011 в 00:59Под катом есть несколько картинок!
Формально задача ставится следующим образом:
Даны две матрицы A и B размерности NxN. Необходимо вычислить их произведение: матрицу С.
C[i][j] = сумма по k от 1 до N A[i][k]*B[k][j].
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j){
c[i][j] = 0;
for (int k = 0; k < n; ++k)
c[i][j] = a[i][k]*b[k][j];
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
bt[i][j] = b[j][i];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j){
c[i][j] = 0;
for (int k = 0; k < n; ++k)
c[i][j] = a[i][k]*bt[j][k];
}* This source code was highlighted with Source Code Highlighter .
#define forn(i, n) for (int i = 0; i < int (n); ++i)Точно так же была написана функция с использованием транспонированной матрицы.struct matrixMulParam{
int lf, rg;
matrixMulParam(int cLf = 0, int cRg = 0) : lf(cLf), rg(cRg){}
};DWORD matrixMulNoHack(LPVOID p){
for (int i = ((matrixMulParam*)p)->lf; i <= ((matrixMulParam*)p)->rg; ++i)
forn(j, n){
c[i][j] = 0;
forn(k, n)
c[i][j] += a[i][k] * b[k][j];
}Delete ((matrixMulParam*)p);
return 0;
}
* This source code was highlighted with Source Code Highlighter .
Рассмотрим графики зависимости относительного времени работы от количества потоков для алгоритма c использованием исходной матрицы:
Этот график соответствует всем ожиданиям: время работы падает при увеличении числа потоков до числа ядер, а потом остается примерно неизменным. Однако, если результаты для Core2Quad и Xeon отличаются от идеальных менее, чем на 1%, то для Core2Duo и Atom результаты хуже.
При увеличении размера данных в 4 раза, отставание проявляется еще сильнее. Особенно на Atom N550 (нетбуки явно не рассчитаны на перемножение матриц 2000х2000 за ). Это объясняется точно так же, как и уменьшение времени при использовании транспонированной матрицы. Когда есть несколько потоков, обращающихся к разным участкам памяти, то каждый поток в отдельности будет работать медленнее, чем один поток обходящий память по порядку. Но, несмотря на это, несколько потоков отработают быстрее, чем один.
Следующие графики представляют зависимости относительного времени работы от количества потоков для алгоритма c использованием транспонированной матрицы:
Так как ускорение при использовании транспонированной матрицы связано с более эффективным использованием кэша, то оно начинает работать хуже, если увеличить число потоков и нарушить последовательность доступа к памяти. Интересно ведут себя Atom и Core2Quad: график Atom"а практически не изменился, а показатели Core2Quad резко ухудшились при переходе от 1000х1000 к 2000х2000.
Это объясняется следующим образом: при размере матриц 1000х1000 мы имеем 2 массива (а и b) с 1000*1000 элементов по 4 байта (int). То есть примерно 8 мегабайт. В 1 MB кэша Atom N550 входит лишь 1/8 всех данных, когда в кэш Core2Quad помещаются все данные. Когда мы расширяем массивы до 2000х2000, мы увеличиваем количество данных в 4 раза. Таким образом в кэш Core2Quad теперь помещается только 1/4 данных и трюк с транспонированием становится менее эффективным, а на процессоре Atom он как не работал, так и продолжает не работать.
Чтобы проиллюстрировать описанный выше эффект рассмотрим еще два графика.
Назовем эффективностью использования транспонированной матрицы отношение времени работы алгоритма с использованием транспонированной матрицы при определенных параметрах к времени работы алгоритма с использованием исходной матрицы при тех же параметрах.
Данный график хорошо иллюстрирует все вышесказанное. Эффективность у Core2Quad и Xeon уменьшается, в связи с большим количеством одновременно действующих потоков, обращающихся к разным участкам памяти и разрывающих кэш на части. Эффективность у Core2Duo почти неизменна из-за того, что на нем одновременно действуют только 2 потока и из-за не такого большого объема кэша, как у предыдущих процессоров.
Следующий рисунок содержит тот же график, только с добавлением показателей Atom N550.
Мне так и не удалось понять такого роста эффективности трюка с кэшем и транспонированием. Надеюсь, в комментариях мы сможем докопаться до истины.
P.S. Так выглядел процесс сбора данных
Теги: параллельные вычисления, умножение, матрица, c plus plus
Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.
В данной статье будут рассмотрены стандарты POSIX Threads и OpenMP. А именно параллельное умножение матриц NxN с использованием данных стандартов и их сравнение.
1) Код умножения матриц с использованием OpenMP.
#include 2) Код умножения матриц с использованием Pthread.
#include #include
#include
#include
#include 3) Тестирование
Умножение матриц размера 1000×1000 элементов на процессоре Intel Atom
Исходя из полученных данных видно что незначительное увеличение производительности происходит на 2ух потоках из за технологии hyper threading, которую поддерживает процессор. Последующее увеличение числа потоков не привело к росту производительности а наоборот замедлило. Так же видно что ручное распараллеливание за счет Pthread эффективней нежели автоматическое за счет OpenMP. Умножение матриц размера 1000×1000 элементов на процессоре Intel Xeon
Исходя из полученных данных видно что производительность растет на 2х и 4х потоках так как процессор в состоянии выделить под каждый поток отдельное ядро. Но производительность начинает падать когда мы пытаемся запустить программу в 10 потоков, это происходит и за затрат времени на квантование между потоками. Из данной таблицы можно предположить что эффективней всего запускать по одному потоку на ядро (лучшую производительность приложение показало на 4х потоках). Так же видно что распараллеливание вручную через Pthread оказалось эффективней чем автоматическое через OpenMP. Ваша проблема связана с состоянием гонки на переменной внутреннего цикла j . Его нужно сделать приватным. В C89 я бы сделал что-то вроде этого:
#pragma omp parallel
{
int i, j, k;
#pragma omp for
for(i=0; ...
Для С++ или C99 используйте смешанные объявления
#pragma omp parallel for
for(int i=0; ...
Выполняя это, вам не нужно явно объявлять что-либо общее или личное. Некоторые дополнительные комментарии к вашему коду. При использовании B[k][j] ваш однопоточный код не кэширует. Это считывает кешью, затем переходит к следующей строке кэша и так далее до тех пор, пока не будет выполнен точечный продукт, и к этому времени другие кегли будут выселены. Вместо этого сначала нужно перенести транспонирование и получить доступ как BT[j][k] . Кроме того, вы выделили массивы массивов, а не один непрерывный 2D-массив. Я исправил ваш код, чтобы использовать транспонирование и смежный 2D-массив. Вот время, которое я получаю для size = 512. No transpose no openmp 0.94s
no transpose, openmp 0.23s
tranpose, no openmp 0.27s
transpose, openmp 0.08s
#include