Введение
Данная статья посвящена небольшому исследованию, которое было проведено из чистого любопытства. Но так как результаты получились интересные, я решил их опубликовать. Были рассмотрены основы параллельных вычислений на простой и удобной для этого задаче: умножении матриц.
Под катом есть несколько картинок!
Формально задача ставится следующим образом:
Даны две матрицы 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];
}
* This source code was highlighted with Source Code Highlighter.
Существует известный трюк, который позволяет ускорить работу приведенного выше кода в 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];
}
* This source code was highlighted with Source Code Highlighter.
Ускорение работы в этом случае связано с устройством кэша процессора. При обращении к какой-то ячейке памяти в кэш записывается не только она, но и несколько соседних ячеек. В первом случае элементы массива b, к которым мы обращаемся в цикле по k, находятся в разных строках, но в одном столбце, а значит в оперативной памяти они расположены на расстоянии равному размеру одной строки массива. Во втором случае мы последовательно обращаемся к элементам одной строки массива bt, которые расположены в памяти подряд.
Решение с использованием параллельных вычислений
Так как каждый элемент матрицы С вычисляется независимо от других и матрицы А и В не изменяются, то для того, чтобы вычислить произведение параллельно, достаточно просто указать какие элементы С какому потоку вычислять.
Для этого была создана функция, которой передается 2 числа: lf и rg. Функция вычисляет строки матрицы С с lf по rg включительно с использованием исходной матрицы B:
#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.Точно так же была написана функция с использованием транспонированной матрицы.
Сбор данных о времени работы
Вычисления проводились на 4-х разных компьютерах с разными процессорами:
- Intel Atom N550
- Тактовая частота: 1.5 GHz
- Кол-во ядер: 2
- Кол-во потоков: 4
Это не опечатка. Вот ссылка на сайт Intel, и вот скриншоты диспетчера задач и диспетчера устройств моего нетбука
- Размер L2 кэша: 1 MB
- Intel Core2Duo P8600
- Тактовая частота: 2.4 GHz
- Кол-во ядер: 2
- Кол-во потоков: 2
- Размер L2 кэша: 3 MB
- Intel Core2Quad Q6600
- Тактовая частота: 2.4 GHz
- Кол-во ядер: 4
- Кол-во потоков: 4
- Размер L2 кэша: 8 MB
- Amazon EC2 High-CPU Extra Large Instance,
примерно равный по мощности 2-м Intel Xeon E5410
- Тактовая частота: 2.33 GHz
- Кол-во ядер: 4 (8 в сумме)
- Кол-во потоков: 4 (8 в сумме)
- Размер L2 кэша: 12 (24 в сумме) MB
Для получения статистики варьировались следующие параметры:
- Размер матриц: 1000х1000 или 2000х2000.
Матрицы заполнялись псевдослучайными целыми числами от 1 до 1000.
- Количество потоков от 1 до 16.
- Использование исходной матрицы B или транспонированной.
Для каждой комбинации указанных параметров вычисления производились не менее 5 раз, и в качестве результата использовалось среднее арифметическое времен работы программы.
Результаты
Так как я рассматривал разные процессоры с разными параметрами, то для сравнения нельзя использовать абсолютное время работы программы в миллисекундах. Для этого введем относительное время работы: отношение в процентах времени вычисления произведения матриц при определенных параметрах к времени вычисления произведения этих же матриц с этими же параметрами в один поток.
Рассмотрим графики зависимости относительного времени работы от количества потоков для алгоритма 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.
Мне так и не удалось понять такого роста эффективности трюка с кэшем и транспонированием. Надеюсь, в комментариях мы сможем докопаться до истины.
Заключение
Во-первых, кэш процессора существенно влияет на скорость выполнение программы, хотя в большинстве случаев мы об этом даже не задумываемся.
Во-вторых, исходники, и вообще все, что я использовал в этой статье, можно скачать по ссылке одним архивом.
В-третьих, использовался компилятор g++ 4.5.2, строка компиляции g++ -Wall -O,
ОС Windows 7 и Windows Server 2008 R2 на Amazon'е.
Спасибо за внимание.
C уважением, Иван.
P.S. Так выглядел процесс сбора данных
