Почему векторизация цикла не имеет улучшения производительности
Я изучаю влияние векторизации на производительность программы. В связи с этим я написал следующий код:
#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#define LEN 10000000
int main(){
struct timeval stTime, endTime;
double* a = (double*)malloc(LEN*sizeof(*a));
double* b = (double*)malloc(LEN*sizeof(*b));
double* c = (double*)malloc(LEN*sizeof(*c));
int k;
for(k = 0; k < LEN; k++){
a[k] = rand();
b[k] = rand();
}
gettimeofday(&stTime, NULL);
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
gettimeofday(&endTime, NULL);
FILE* fh = fopen("dump", "w");
for(k = 0; k < LEN; k++)
fprintf(fh, "c[%d] = %f\t", k, c[k]);
fclose(fh);
double timeE = (double)(endTime.tv_usec + endTime.tv_sec*1000000 - stTime.tv_usec - stTime.tv_sec*1000000);
printf("Time elapsed: %f\n", timeE);
return 0;
}
В этом коде я просто инициализирую и умножаю два вектора. Результаты сохраняются в векторе c, В основном меня интересует эффект векторизации следующего цикла:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
Я компилирую код, используя следующие две команды:
1) icc -O2 TestSMID.c -o TestSMID -no-vec -no-simd
2) icc -O2 TestSMID.c -o TestSMID -vec-report2
Я ожидаю увидеть улучшение производительности, так как вторая команда успешно векторизует цикл. Однако мои исследования показывают, что при векторизации цикла улучшения производительности не происходит.
Возможно, я что-то здесь упустил, так как я не очень знаком с этой темой. Поэтому, пожалуйста, дайте мне знать, если что-то не так с моим кодом.
Заранее спасибо за помощь.
PS: я использую Mac OSX, поэтому нет необходимости выравнивать данные, так как все выделенные памяти выровнены по 16 байтов.
Изменить: Я хотел бы сначала поблагодарить всех вас за ваши комментарии и ответы. Я подумал об ответе, предложенном @Mysticial, и здесь следует упомянуть еще несколько моментов. Во-первых, как упомянул @Vinska, c[k]=a[k]*b[k] не занимает всего один цикл. В дополнение к приращению индекса цикла и сравнения, чтобы убедиться, что k меньше чем LENЕсть и другие вещи, которые нужно сделать, чтобы выполнить операцию. Взглянув на ассемблерный код, сгенерированный компилятором, можно увидеть, что для простого умножения требуется гораздо больше, чем один цикл. Векторизованная версия выглядит так:
L_B1.9: # Preds L_B1.8
movq %r13, %rax #25.5
andq $15, %rax #25.5
testl %eax, %eax #25.5
je L_B1.12 # Prob 50% #25.5
# LOE rbx r12 r13 r14 r15 eax
L_B1.10: # Preds L_B1.9
testb $7, %al #25.5
jne L_B1.32 # Prob 10% #25.5
# LOE rbx r12 r13 r14 r15
L_B1.11: # Preds L_B1.10
movsd (%r14), %xmm0 #26.16
movl $1, %eax #25.5
mulsd (%r15), %xmm0 #26.23
movsd %xmm0, (%r13) #26.9
# LOE rbx r12 r13 r14 r15 eax
L_B1.12: # Preds L_B1.11 L_B1.9
movl %eax, %edx #25.5
movl %eax, %eax #26.23
negl %edx #25.5
andl $1, %edx #25.5
negl %edx #25.5
addl $10000000, %edx #25.5
lea (%r15,%rax,8), %rcx #26.23
testq $15, %rcx #25.5
je L_B1.16 # Prob 60% #25.5
# LOE rdx rbx r12 r13 r14 r15 eax
L_B1.13: # Preds L_B1.12
movl %eax, %eax #25.5
# LOE rax rdx rbx r12 r13 r14 r15
L_B1.14: # Preds L_B1.14 L_B1.13
movups (%r15,%rax,8), %xmm0 #26.23
movsd (%r14,%rax,8), %xmm1 #26.16
movhpd 8(%r14,%rax,8), %xmm1 #26.16
mulpd %xmm0, %xmm1 #26.23
movntpd %xmm1, (%r13,%rax,8) #26.9
addq $2, %rax #25.5
cmpq %rdx, %rax #25.5
jb L_B1.14 # Prob 99% #25.5
jmp L_B1.20 # Prob 100% #25.5
# LOE rax rdx rbx r12 r13 r14 r15
L_B1.16: # Preds L_B1.12
movl %eax, %eax #25.5
# LOE rax rdx rbx r12 r13 r14 r15
L_B1.17: # Preds L_B1.17 L_B1.16
movsd (%r14,%rax,8), %xmm0 #26.16
movhpd 8(%r14,%rax,8), %xmm0 #26.16
mulpd (%r15,%rax,8), %xmm0 #26.23
movntpd %xmm0, (%r13,%rax,8) #26.9
addq $2, %rax #25.5
cmpq %rdx, %rax #25.5
jb L_B1.17 # Prob 99% #25.5
# LOE rax rdx rbx r12 r13 r14 r15
L_B1.18: # Preds L_B1.17
mfence #25.5
# LOE rdx rbx r12 r13 r14 r15
L_B1.19: # Preds L_B1.18
mfence #25.5
# LOE rdx rbx r12 r13 r14 r15
L_B1.20: # Preds L_B1.14 L_B1.19 L_B1.32
cmpq $10000000, %rdx #25.5
jae L_B1.24 # Prob 0% #25.5
# LOE rdx rbx r12 r13 r14 r15
L_B1.22: # Preds L_B1.20 L_B1.22
movsd (%r14,%rdx,8), %xmm0 #26.16
mulsd (%r15,%rdx,8), %xmm0 #26.23
movsd %xmm0, (%r13,%rdx,8) #26.9
incq %rdx #25.5
cmpq $10000000, %rdx #25.5
jb L_B1.22 # Prob 99% #25.5
# LOE rdx rbx r12 r13 r14 r15
L_B1.24: # Preds L_B1.22 L_B1.20
И не векторизованная версия:
L_B1.9: # Preds L_B1.8
xorl %eax, %eax #25.5
# LOE rbx r12 r13 r14 r15 eax
L_B1.10: # Preds L_B1.10 L_B1.9
lea (%rax,%rax), %edx #26.9
incl %eax #25.5
cmpl $5000000, %eax #25.5
movsd (%r15,%rdx,8), %xmm0 #26.16
movsd 8(%r15,%rdx,8), %xmm1 #26.16
mulsd (%r13,%rdx,8), %xmm0 #26.23
mulsd 8(%r13,%rdx,8), %xmm1 #26.23
movsd %xmm0, (%rbx,%rdx,8) #26.9
movsd %xmm1, 8(%rbx,%rdx,8) #26.9
jb L_B1.10 # Prob 99% #25.5
# LOE rbx r12 r13 r14 r15 eax
Кроме того, процессор не загружает только 24 байта. При каждом доступе к памяти загружается полная строка (64 байта). Что еще более важно, так как память, необходимая для a, b, а также c является смежным, prefetcher определенно очень поможет и загружает следующие блоки заранее. Сказав это, я думаю, что пропускная способность памяти, рассчитанная @Mysticial, слишком пессимистична.
Кроме того, использование SIMD для повышения производительности программы при очень простом добавлении упоминается в Руководстве по векторизации Intel. Следовательно, похоже, что мы сможем добиться некоторого улучшения производительности для этого очень простого цикла.
Edit2: еще раз спасибо за ваши комментарии. Кроме того, благодаря примеру кода @Mysticial, я наконец-то увидел влияние SIMD на улучшение производительности. Проблема, как отметил Mysticial, заключалась в пропускной способности памяти. С выбором небольшого размера для a, b, а также c которые вписываются в кэш L1, видно, что SIMD может значительно повысить производительность. Вот результаты, которые я получил:
icc -O2 -o TestSMIDNoVec -no-vec TestSMID2.c: 17.34 sec
icc -O2 -o TestSMIDVecNoUnroll -vec-report2 TestSMID2.c: 9.33 sec
А развертывание цикла еще больше повышает производительность:
icc -O2 -o TestSMIDVecUnroll -vec-report2 TestSMID2.c -unroll=8: 8.6sec
Кроме того, я должен отметить, что моему процессору требуется всего один цикл для завершения итерации при компиляции с -O2,
PS: Мой компьютер - MacBook Pro Core i5 @2,5 ГГц (двухъядерный)
4 ответа
Этот первоначальный ответ был действителен еще в 2013 году. Что касается аппаратного обеспечения 2017 года, все изменилось настолько, что и вопрос, и ответ устарели.
Смотрите конец этого ответа для обновления 2017 года.
Оригинальный ответ (2013):
Потому что вы ограничены пропускной способностью памяти.
Хотя векторизация и другие микрооптимизации могут повысить скорость вычислений, они не могут увеличить скорость вашей памяти.
В вашем примере:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
Вы делаете один проход по всей памяти, выполняя очень мало работы. Это увеличивает пропускную способность вашей памяти.
Таким образом, независимо от того, как это оптимизировано (векторизовано, развернуто и т. Д.), Оно не станет намного быстрее.
Типичная настольная машина 2013 года имеет пропускную способность порядка 10 ГБ / с *.
Ваш цикл касается 24 байт / итерация.
Без векторизации современный процессор x64, вероятно, может выполнять около 1 итерации за цикл *.
Предположим, вы работаете на частоте 4 ГГц:
(4 * 10^9) * 24 bytes/iteration = 96 GB/s
Это почти в 10 раз больше пропускной способности вашей памяти - без векторизации.
* Не удивительно, что несколько человек усомнились в цифрах, которые я привел выше, поскольку я не цитировал их. Ну, это было с моей головы из опыта. Итак, вот некоторые критерии, чтобы доказать это.
Итерация цикла может выполняться так же быстро, как 1 цикл / итерация:
Мы можем избавиться от узкого места в памяти, если уменьшить LEN так что вписывается в кеш.
(Я проверял это на C++, так как это было проще. Но это не имеет значения.)
#include <iostream>
#include <time.h>
using std::cout;
using std::endl;
int main(){
const int LEN = 256;
double *a = (double*)malloc(LEN*sizeof(*a));
double *b = (double*)malloc(LEN*sizeof(*a));
double *c = (double*)malloc(LEN*sizeof(*a));
int k;
for(k = 0; k < LEN; k++){
a[k] = rand();
b[k] = rand();
}
clock_t time0 = clock();
for (int i = 0; i < 100000000; i++){
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
}
clock_t time1 = clock();
cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;
}
- Процессор: Intel Core i7 2600K @ 4,2 ГГц
- Компилятор: Visual Studio 2012
- Время: 6,55 секунды
В этом тесте я выполнил 25 600 000 000 итераций всего за 6,55 секунды.
6.55 * 4.2 GHz= 27 510000 000 циклов27,510,000,000 / 25,600,000,000= 1,074 циклов / итерация
Теперь, если вам интересно, как это можно сделать:
- 2 нагрузки
- 1 магазин
- 1 умножить
- счетчик приращений
- сравнить + ветка
все в одном цикле...
Это потому, что современные процессоры и компиляторы потрясающие.
Хотя каждая из этих операций имеет задержку (особенно умножение), процессор может выполнять несколько итераций одновременно. Моя тестовая машина представляет собой процессор Sandy Bridge, который способен выдерживать нагрузки 2x128b, 1x128b хранения и 1x256b векторных FP, умножаемых каждый цикл. И, возможно, еще один или два векторных или целочисленных операций, если нагрузки являются операндами источника памяти для микросинхронных операций. (2 загрузки + 1 пропускная способность хранилища только при использовании 256b загрузок / сохранений AVX, в противном случае только два полных операций памяти за цикл (не более одного хранилища)).
Глядя на сборку (которую я опущу для краткости), кажется, что компилятор развернул цикл, тем самым уменьшив накладные расходы цикла. Но это не совсем удалось векторизовать его.
Пропускная способность памяти составляет порядка 10 ГБ / с:
Самый простой способ проверить это через memset():
#include <iostream>
#include <time.h>
using std::cout;
using std::endl;
int main(){
const int LEN = 1 << 30; // 1GB
char *a = (char*)calloc(LEN,1);
clock_t time0 = clock();
for (int i = 0; i < 100; i++){
memset(a,0xff,LEN);
}
clock_t time1 = clock();
cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;
}
- Процессор: Intel Core i7 2600K @ 4,2 ГГц
- Компилятор: Visual Studio 2012
- Время: 5,811 секунд
Поэтому моей машине требуется 5,811 секунды для записи в 100 ГБ памяти. Это около 17,2 ГБ / с.
И мой процессор на верхнем конце. Процессоры Nehalem и Core 2 поколения имеют меньшую пропускную способность памяти.
Обновление март 2017:
С 2017 года все стало сложнее.
Благодаря DDR4 и четырехканальной памяти, один поток больше не может насыщать пропускную способность памяти. Но проблема пропускной способности не обязательно исчезнет. Несмотря на увеличение пропускной способности, процессорные ядра также улучшились - и их стало больше.
Математически:
- Каждое ядро имеет ограничение пропускной способности
X, - Основная память имеет ограничение пропускной способности
Y, - В старых системах
X > Y, - На современных высокопроизводительных системах,
X < Y, НоX * (# of cores) > Y,
Еще в 2013 году: Sandy Bridge @ 4 ГГц + двухканальная DDR3 @ 1333 МГц
- Без векторизации (8-байтовая загрузка / хранилища):
X = 32 GB/sа такжеY = ~17 GB/s - Векторизованное SSE* (16-байтовая загрузка / хранилища):
X = 64 GB/sа такжеY = ~17 GB/s
Теперь в 2017 году: Haswell-E @ 4 ГГц + четырехканальный DDR4 @ 2400 МГц
- Без векторизации (8-байтовая загрузка / хранилища):
X = 32 GB/sа такжеY = ~70 GB/s - Векторизованный AVX* (32-байтная загрузка / хранение):
X = 64 GB/sа такжеY = ~70 GB/s
(Как для Sandy Bridge, так и для Haswell архитектурные ограничения в кэше будут ограничивать пропускную способность до 16 байтов / цикл независимо от ширины SIMD.)
Поэтому в настоящее время один поток не всегда может насытить пропускную способность памяти. И вам нужно будет векторизовать, чтобы достичь этого предела X, Но вы все равно достигнете предела пропускной способности основной памяти Y с 2 или более нитями.
Но одна вещь не изменилась и, вероятно, не изменится в течение длительного времени: вы не сможете запустить цикл переключения пропускной способности на всех ядрах без насыщения общей пропускной способности памяти.
Как уже было сказано в Mysticial, ограничения пропускной способности основной памяти являются узким местом для больших буферов. Обходной путь заключается в том, чтобы перестроить вашу обработку для работы с частями, которые помещаются в кэш. (Вместо умножения двойных целых 200 МБ, умножьте только на 128 КБ, а затем сделайте что-нибудь с этим. Таким образом, код, который использует выходные данные умножения, найдет его все еще в кэше L2. L2 обычно составляет 256 КБ и является частным для каждого ядра ЦП, о последних разработках Intel.)
Этот метод называется блокировкой кэша или циклическим разбиением. Это может быть сложно для некоторых алгоритмов, но выигрыш заключается в разнице между пропускной способностью кэша L2 и пропускной способностью основной памяти.
Если вы сделаете это, убедитесь, что компилятор не генерирует потоковые хранилища (movnt...). Эти записи обходят кэши, чтобы не загрязнять их данными, которые не подходят. Следующее чтение этих данных должно будет коснуться основной памяти.
РЕДАКТИРОВАТЬ: изменил ответ много. Также, пожалуйста, не обращайте внимания на большинство из того, что я писал ранее о том, что ответ Mystical не совсем верен Тем не менее, я все еще не согласен с тем, что память является узким местом, поскольку, несмотря на проведение очень широкого спектра тестов, я не вижу никаких признаков того, что исходный код связан со скоростью памяти. Между тем он продолжал показывать явные признаки того, чтобы быть связанным с процессором.
Там может быть много причин. И поскольку причина [ы] может быть очень зависимой от аппаратного обеспечения, я решил, что не стоит спекулировать на основании догадок. Просто в общих чертах расскажу об этих вещах, с которыми я столкнулся во время более позднего тестирования, где я использовал гораздо более точный и надежный метод измерения времени процессора и циклический цикл 1000 раз. Я считаю, что эта информация может быть полезной. Но, пожалуйста, возьмите его с крошкой соли, так как это зависит от аппаратного обеспечения.
- При использовании инструкций из семейства SSE полученный векторизованный код был на 10% быстрее по сравнению с не векторизованным кодом.
- Векторизованный код с использованием семейства SSE и векторизованный код с использованием AVX более или менее работали с одинаковой производительностью.
- При использовании инструкций AVX не векторизованный код работал быстрее всего - на 25% или более быстрее, чем все остальные попытки.
- Результаты масштабируются линейно с тактовой частотой процессора во всех случаях.
- На результаты почти не повлияли часы памяти.
- Результаты значительно повлияли на задержку памяти - намного больше, чем тактовая частота памяти, но не так сильно, как тактовая частота процессора влияла на результаты.
Пример WRT Mystical - выполнение почти 1 итерации за такт - я не ожидал, что планировщик ЦП будет настолько эффективным, и предполагал, что 1 итерация каждые 1,5-2 такта. Но, к моему удивлению, это не так; Я уверен, что был неправ, извините за это. Мой собственный процессор работал еще эффективнее - 1,048 циклов / итерация. Так что я могу засвидетельствовать, что эта часть ответа Мистикала определенно права.
На всякий случай a[] b[] и c[] борются за кеш L2:
#include <string.h> /* for memcpy */
...
gettimeofday(&stTime, NULL);
for(k = 0; k < LEN; k += 4) {
double a4[4], b4[4], c4[4];
memcpy(a4,a+k, sizeof a4);
memcpy(b4,b+k, sizeof b4);
c4[0] = a4[0] * b4[0];
c4[1] = a4[1] * b4[1];
c4[2] = a4[2] * b4[2];
c4[3] = a4[3] * b4[3];
memcpy(c+k,c4, sizeof c4);
}
gettimeofday(&endTime, NULL);
Сокращает время работы с 98429,000000 до 67213,000000; Развертывание петли в 8 раз уменьшает ее до 57157,000000 здесь.