В данной статье будут рассмотрены стандарты 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 Песочница Под катом есть несколько картинок! Формально задача ставится следующим образом: * This source code was highlighted with Source Code Highlighter
.
struct
matrixMulParam{ DWORD matrixMulNoHack(LPVOID p){ Delete ((matrixMulParam*)p); Рассмотрим графики зависимости относительного времени работы от количества потоков для алгоритма c использованием исходной матрицы: Следующие графики представляют зависимости относительного времени работы от количества потоков для алгоритма c использованием транспонированной матрицы: P.S. Так выглядел процесс сбора данных Теги:
параллельные вычисления, умножение, матрица, c plus plus
Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.Параллельное умножение матриц или магия кэша. Небольшое исследование
Введение
Данная статья посвящена небольшому исследованию, которое было проведено из чистого любопытства. Но так как результаты получились интересные, я решил их опубликовать. Были рассмотрены основы параллельных вычислений на простой и удобной для этого задаче: умножении матриц.
Даны две матрицы 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];
}
Существует известный трюк, который позволяет ускорить работу приведенного выше кода в 4-5 раз. Это замена массива b на массив bt, в котором содержится транспонированная матрица В: 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];
}
Ускорение работы в этом случае связано с устройством кэша процессора. При обращении к какой-то ячейке памяти в кэш записывается не только она, но и несколько соседних ячеек. В первом случае элементы массива b, к которым мы обращаемся в цикле по k, находятся в разных строках, но в одном столбце, а значит в оперативной памяти они расположены на расстоянии равному размеру одной строки массива. Во втором случае мы последовательно обращаемся к элементам одной строки массива bt, которые расположены в памяти подряд.Решение с использованием параллельных вычислений
Так как каждый элемент матрицы С вычисляется независимо от других и матрицы А и В не изменяются, то для того, чтобы вычислить произведение параллельно, достаточно просто указать какие элементы С какому потоку вычислять.
Для этого была создана функция, которой передается 2 числа: lf и rg. Функция вычисляет строки матрицы С с lf по rg включительно с использованием исходной матрицы B: #define
forn(i, n) for
(int
i = 0; i < int
(n); ++i)
Точно так же была написана функция с использованием транспонированной матрицы.
int
lf, rg;
matrixMulParam(int
cLf = 0, int
cRg = 0) : lf(cLf), rg(cRg){}
};
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];
}
return
0;
}
* This source code was highlighted with Source Code Highlighter
.
Сбор данных о времени работы
Вычисления проводились на 4-х разных компьютерах с разными процессорами:
Для получения статистики варьировались следующие параметры:
Это не опечатка. Вот ссылка на сайт Intel , и вот скриншоты диспетчера задач и диспетчера устройств моего нетбука
примерно равный по мощности 2-м Intel Xeon E5410
Для каждой комбинации указанных параметров вычисления производились не менее 5 раз, и в качестве результата использовалось среднее арифметическое времен работы программы.
Матрицы заполнялись псевдослучайными целыми числами от 1 до 1000.Результаты
Так как я рассматривал разные процессоры с разными параметрами, то для сравнения нельзя использовать абсолютное время работы программы в миллисекундах. Для этого введем относительное время работы: отношение в процентах времени вычисления произведения матриц при определенных параметрах к времени вычисления произведения этих же матриц с этими же параметрами в один поток.
Этот график соответствует всем ожиданиям: время работы падает при увеличении числа потоков до числа ядер, а потом остается примерно неизменным. Однако, если результаты для Core2Quad и Xeon отличаются от идеальных менее, чем на 1%, то для Core2Duo и Atom результаты хуже. 
При увеличении размера данных в 4 раза, отставание проявляется еще сильнее. Особенно на Atom N550 (нетбуки явно не рассчитаны на перемножение матриц 2000х2000 за ). Это объясняется точно так же, как и уменьшение времени при использовании транспонированной матрицы. Когда есть несколько потоков, обращающихся к разным участкам памяти, то каждый поток в отдельности будет работать медленнее, чем один поток обходящий память по порядку. Но, несмотря на это, несколько потоков отработают быстрее, чем один.
Так как ускорение при использовании транспонированной матрицы связано с более эффективным использованием кэша, то оно начинает работать хуже, если увеличить число потоков и нарушить последовательность доступа к памяти. Интересно ведут себя 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. 
Мне так и не удалось понять такого роста эффективности трюка с кэшем и транспонированием. Надеюсь, в комментариях мы сможем докопаться до истины. Заключение
Во-первых,
кэш процессора существенно влияет на скорость выполнение программы, хотя в большинстве случаев мы об этом даже не задумываемся.
Во-вторых,
исходники, и вообще все, что я использовал в этой статье, можно скачать по ссылке одним архивом .
В-третьих,
использовался компилятор g++ 4.5.2, строка компиляции g++ -Wall -O
,
ОС Windows 7 и Windows Server 2008 R2 на Amazon"е.
Спасибо за внимание.
C уважением, Иван.
