SSE Intrinsics и развертывание цикла
Я пытаюсь оптимизировать некоторые циклы, и мне удалось, но мне интересно, если я сделал это только частично правильно. Скажем, например, что у меня есть этот цикл:
for(i=0;i<n;i++){
b[i] = a[i]*2;
}
развернув это в 3 раза, вы получите следующее:
int unroll = (n/4)*4;
for(i=0;i<unroll;i+=4)
{
b[i] = a[i]*2;
b[i+1] = a[i+1]*2;
b[i+2] = a[i+2]*2;
b[i+3] = a[i+3]*2;
}
for(;i<n;i++)
{
b[i] = a[i]*2;
}
Теперь это эквивалент перевода SSE:
__m128 ai_v = _mm_loadu_ps(&a[i]);
__m128 two_v = _mm_set1_ps(2);
__m128 ai2_v = _mm_mul_ps(ai_v, two_v);
_mm_storeu_ps(&b[i], ai2_v);
либо это:
__m128 ai_v = _mm_loadu_ps(&a[i]);
__m128 two_v = _mm_set1_ps(2);
__m128 ai2_v = _mm_mul_ps(ai_v, two_v);
_mm_storeu_ps(&b[i], ai2_v);
__m128 ai1_v = _mm_loadu_ps(&a[i+1]);
__m128 two1_v = _mm_set1_ps(2);
__m128 ai_1_2_v = _mm_mul_ps(ai1_v, two1_v);
_mm_storeu_ps(&b[i+1], ai_1_2_v);
__m128 ai2_v = _mm_loadu_ps(&a[i+2]);
__m128 two2_v = _mm_set1_ps(2);
__m128 ai_2_2_v = _mm_mul_ps(ai2_v, two2_v);
_mm_storeu_ps(&b[i+2], ai_2_2_v);
__m128 ai3_v = _mm_loadu_ps(&a[i+3]);
__m128 two3_v = _mm_set1_ps(2);
__m128 ai_3_2_v = _mm_mul_ps(ai3_v, two3_v);
_mm_storeu_ps(&b[i+3], ai_3_2_v);
Я немного запутался по поводу раздела кода:
for(;i<n;i++)
{
b[i] = a[i]*2;
}
что это делает? Это просто сделать дополнительные части, например, если цикл не делится на фактор, который вы выбрали, чтобы развернуть его? Спасибо.
Решение
Ответ — первый блок:
__m128 ai_v = _mm_loadu_ps(&a[i]);
__m128 two_v = _mm_set1_ps(2);
__m128 ai2_v = _mm_mul_ps(ai_v,two_v);
_mm_storeu_ps(&b[i],ai2_v);
Это уже занимает четыре переменные одновременно.
Вот полная программа с закомментированным эквивалентным разделом кода:
#include <iostream>
int main()
{
int i{0};
float a[10] ={1,2,3,4,5,6,7,8,9,10};
float b[10] ={0,0,0,0,0,0,0,0,0,0};
int n = 10;
int unroll = (n/4)*4;
for (i=0; i<unroll; i+=4) {
//b[i] = a[i]*2;
//b[i+1] = a[i+1]*2;
//b[i+2] = a[i+2]*2;
//b[i+3] = a[i+3]*2;
__m128 ai_v = _mm_loadu_ps(&a[i]);
__m128 two_v = _mm_set1_ps(2);
__m128 ai2_v = _mm_mul_ps(ai_v,two_v);
_mm_storeu_ps(&b[i],ai2_v);
}
for (; i<n; i++) {
b[i] = a[i]*2;
}
for (auto i : a) { std::cout << i << "\t"; }
std::cout << "\n";
for (auto i : b) { std::cout << i << "\t"; }
std::cout << "\n";
return 0;
}
Что касается эффективности; кажется, что сборка в моей системе генерирует movups инструкции, тогда как рукописный код может быть сделан для использования movaps который должен быть быстрее.
Я использовал следующую программу, чтобы сделать некоторые тесты:
#include <iostream>
//#define NO_UNROLL
//#define UNROLL
//#define SSE_UNROLL
#define SSE_UNROLL_ALIGNED
int main()
{
const size_t array_size = 100003;
#ifdef SSE_UNROLL_ALIGNED
__declspec(align(16)) int i{0};
__declspec(align(16)) float a[array_size] ={1,2,3,4,5,6,7,8,9,10};
__declspec(align(16)) float b[array_size] ={0,0,0,0,0,0,0,0,0,0};
#endif
#ifndef SSE_UNROLL_ALIGNED
int i{0};
float a[array_size] ={1,2,3,4,5,6,7,8,9,10};
float b[array_size] ={0,0,0,0,0,0,0,0,0,0};
#endif
int n = array_size;
int unroll = (n/4)*4;for (size_t j{0}; j < 100000; ++j) {
#ifdef NO_UNROLL
for (i=0; i<n; i++) {
b[i] = a[i]*2;
}
#endif
#ifdef UNROLL
for (i=0; i<unroll; i+=4) {
b[i] = a[i]*2;
b[i+1] = a[i+1]*2;
b[i+2] = a[i+2]*2;
b[i+3] = a[i+3]*2;
}
#endif
#ifdef SSE_UNROLL
for (i=0; i<unroll; i+=4) {
__m128 ai_v = _mm_loadu_ps(&a[i]);
__m128 two_v = _mm_set1_ps(2);
__m128 ai2_v = _mm_mul_ps(ai_v,two_v);
_mm_storeu_ps(&b[i],ai2_v);
}
#endif
#ifdef SSE_UNROLL_ALIGNED
for (i=0; i<unroll; i+=4) {
__m128 ai_v = _mm_load_ps(&a[i]);
__m128 two_v = _mm_set1_ps(2);
__m128 ai2_v = _mm_mul_ps(ai_v,two_v);
_mm_store_ps(&b[i],ai2_v);
}
#endif
#ifndef NO_UNROLL
for (; i<n; i++) {
b[i] = a[i]*2;
}
#endif
}
//for (auto i : a) { std::cout << i << "\t"; }
//std::cout << "\n";
//for (auto i : b) { std::cout << i << "\t"; }
//std::cout << "\n";
return 0;
}
Я получил следующие результаты (x86):
NO_UNROLL: 0,994 секунды, SSE не выбран компиляторомUNROLL: 3,511 секунд, используетmovupsSSE_UNROLL: 3,315 секунд, используетmovupsSSE_UNROLL_ALIGNED: 3,276 секунд, используетmovaps
Таким образом, ясно, что развертывание цикла не помогло в этом случае. Даже гарантируя, что мы используем более эффективный movaps не очень помогает
Но я получил еще более странный результат при компиляции в 64 бит (x64):
NO_UNROLL: 1,138 секунды, SSE не выбран компиляторомUNROLL: 1,409 секунды, SSE не выбран компиляторомSSE_UNROLL: 1,420 секунды, Компилятор еще не выбрал SSE!SSE_UNROLL_ALIGNED: 1,476 секунды, Компилятор еще не выбрал SSE!
Кажется, что MSVC просматривает предложение и генерирует лучшую сборку, несмотря на то, что все еще медленнее, чем если бы мы вообще не пробовали какую-либо ручную оптимизацию.
Другие решения
Как обычно, неэффективно развертывать циклы и пытаться сопоставить инструкции SSE вручную. Компиляторы могут сделать это лучше, чем вы. Например, предоставленный образец автоматически компилируется в SSM с поддержкой SSE:
foo:
.LFB0:
.cfi_startproc
testl %edi, %edi
jle .L7
movl %edi, %esi
shrl $2, %esi
cmpl $3, %edi
leal 0(,%rsi,4), %eax
jbe .L8
testl %eax, %eax
je .L8
vmovdqa .LC0(%rip), %xmm1
xorl %edx, %edx
xorl %ecx, %ecx
.p2align 4,,10
.p2align 3
.L6:
addl $1, %ecx
vpmulld a(%rdx), %xmm1, %xmm0
vmovdqa %xmm0, b(%rdx)
addq $16, %rdx
cmpl %esi, %ecx
jb .L6
cmpl %eax, %edi
je .L7
.p2align 4,,10
.p2align 3
.L9:
movslq %eax, %rdx
addl $1, %eax
movl a(,%rdx,4), %ecx
addl %ecx, %ecx
cmpl %eax, %edi
movl %ecx, b(,%rdx,4)
jg .L9
.L7:
rep
ret
.L8:
xorl %eax, %eax
jmp .L9
.cfi_endproc
Циклы также могут быть развернуты, это просто увеличит длину кода, который я не хочу здесь вставлять. Вы можете мне доверять — компиляторы развертывают циклы.
Заключение
Ручная раскрутка вам не поможет.