Оптимизация поиска в таблицах SSE/NEON

у меня есть следующий код поиска и интерполяции для оптимизации. (таблица с плавающей запятой размером 128) Она будет использоваться с компилятором Intel для Windows, GCC для OSX и GCC с неоновой OSX.

for(unsigned int i = 0 ; i < 4 ; i++)
{
    const int iIdx = (int)m_fIndex[i];
    const float frac = m_fIndex - iIdx;
    m_fResult[i] = sftable[iIdx].val + sftable[iIdx].val2 * frac;
}

Я все проверил с помощью sse/neon. (макросы конвертируются в инструкции sse/neon)

VEC_INT iIdx = VEC_FLOAT2INT(m_fIndex);
VEC_FLOAT frac = VEC_SUB(m_fIndex ,VEC_INT2FLOAT(iIdx);
m_fResult[0] = sftable[iIdx[0]].val2;
m_fResult[1] = sftable[iIdx[1]].val2;
m_fResult[2] = sftable[iIdx[2]].val2;
m_fResult[3] = sftable[iIdx[3]].val2;
m_fResult=VEC_MUL( m_fResult,frac);
frac[0] = sftable[iIdx[0]].val1;
frac[1] = sftable[iIdx[1]].val1;
frac[2] = sftable[iIdx[2]].val1;
frac[3] = sftable[iIdx[3]].val1;
m_fResult=VEC_ADD( m_fResult,frac);

я думаю, что доступ к таблице и перемещение в выровненную память является настоящим узким местом здесь. Я плохо разбираюсь в ассемблере, но есть много unpcklps и mov:

10026751  mov         eax,dword ptr [esp+4270h] 
10026758  movaps      xmm3,xmmword ptr [eax+16640h] 
1002675F  cvttps2dq   xmm5,xmm3 
10026763  cvtdq2ps    xmm4,xmm5 
10026766  movd        edx,xmm5 
1002676A  movdqa      xmm6,xmm5 
1002676E  movdqa      xmm1,xmm5 
10026772  psrldq      xmm6,4 
10026777  movdqa      xmm2,xmm5 
1002677B  movd        ebx,xmm6 
1002677F  subps       xmm3,xmm4 
10026782  psrldq      xmm1,8 
10026787  movd        edi,xmm1 
1002678B  psrldq      xmm2,0Ch 
10026790  movdqa      xmmword ptr [esp+4F40h],xmm5 
10026799  mov         ecx,dword ptr [eax+edx*8+10CF4h] 
100267A0  movss       xmm0,dword ptr [eax+edx*8+10CF4h] 
100267A9  mov         dword ptr [eax+166B0h],ecx 
100267AF  movd        ecx,xmm2 
100267B3  mov         esi,dword ptr [eax+ebx*8+10CF4h] 
100267BA  movss       xmm4,dword ptr [eax+ebx*8+10CF4h] 
100267C3  mov         dword ptr [eax+166B4h],esi 
100267C9  mov         edx,dword ptr [eax+edi*8+10CF4h] 
100267D0  movss       xmm7,dword ptr [eax+edi*8+10CF4h] 
100267D9  mov         dword ptr [eax+166B8h],edx 
100267DF  movss       xmm1,dword ptr [eax+ecx*8+10CF4h] 
100267E8  unpcklps    xmm0,xmm7 
100267EB  unpcklps    xmm4,xmm1 
100267EE  unpcklps    xmm0,xmm4 
100267F1  mulps       xmm0,xmm3 
100267F4  movaps      xmmword ptr [eax+166B0h],xmm0 
100267FB  mov         ebx,dword ptr [esp+4F40h] 
10026802  mov         edi,dword ptr [esp+4F44h] 
10026809  mov         ecx,dword ptr [esp+4F48h] 
10026810  mov         esi,dword ptr [esp+4F4Ch] 
10026817  movss       xmm2,dword ptr [eax+ebx*8+10CF0h] 
10026820  movss       xmm5,dword ptr [eax+edi*8+10CF0h] 
10026829  movss       xmm3,dword ptr [eax+ecx*8+10CF0h] 
10026832  movss       xmm6,dword ptr [eax+esi*8+10CF0h] 
1002683B  unpcklps    xmm2,xmm3 
1002683E  unpcklps    xmm5,xmm6 
10026841  unpcklps    xmm2,xmm5 
10026844  mulps       xmm2,xmm0 
10026847  movaps      xmmword ptr [eax+166B0h],xmm2

При профилировании нет особой пользы от версии sse на win.

Есть ли у вас какие-либо предложения, как улучшить? Ожидаются ли какие-либо побочные эффекты с neon/gcc?

В настоящее время я думаю просто сделать первую часть vecorized и выполнять чтение таблицы и интерполяцию в цикле, надеясь, что это выиграет от оптимизации компилятора.


c++ optimization lookup-tables sse neon
person evitan    schedule 18.07.2013    source источник
comment
Просто глядя на это, кажется, что очень длинный набор инструкций для выполнения первого набора кода.   -  person Mats Petersson    schedule 18.07.2013
comment
Для этого AVX2 (! - Только Haswell) было предоставлено семейство инструкций VGATHER для поиска в больших (находящихся в памяти) таблицах. В Intel вы можете выполнять маленький (крошечный) поиск по таблицам путем перетасовки в SSE/AVX, но только если в вашей таблице не больше записей, чем вы можете поместить в один регистр SSE/AVX (так что для float, нет более 4/8). ARM NEON может сделать то же самое через VTBL (и таблица может содержать до четырех неоновых регистров, так что, опять же, восемь чисел с плавающей запятой).   -  person FrankH.    schedule 18.07.2013
comment
К сожалению, мне нужна максимальная совместимость, поэтому мне нет смысла оптимизировать для haswell.   -  person evitan    schedule 21.07.2013

Ответы (3)


arrow_upward
2
arrow_downward

ОС X? Тогда это не имеет ничего общего с NEON.

Кстати, NEON все равно не может обрабатывать такие большие LUT. (Я не знаю о SSE в этом отношении)

Сначала проверьте, может ли SSE обрабатывать LUT такого размера, если да, я предлагаю использовать другой компилятор, поскольку GCC имеет тенденцию делать из встроенных функций внутренние ошибки.

person Jake 'Alquimista' LEE    schedule 18.07.2013
comment
просто хотел уточнить, что код будет работать на разных платформах и что он будет включать неоновый векторный код, который я компилирую на OSX. - person evitan; 21.07.2013

arrow_upward
1
arrow_downward

Это один из самых худших кодеков компилятора, которые я когда-либо видел (при условии, что оптимизатор включен). Стоит зарегистрировать ошибку против GCC.

Главные проблемы:

  • Загрузка val и val2 для каждого поиска отдельно.
  • Получение индекса для val и val2 в георадар отдельно.
  • Запись вектора индексов в стек и последующая загрузка их в GPR.

Чтобы заставить компиляторы генерировать более качественный код (одна загрузка для каждой строки таблицы), вам может потребоваться загрузить каждую строку таблицы, как если бы она была двойной, затем привести строку к вектору из двух чисел с плавающей запятой и прокрутить строки, чтобы получить однородный векторы. Как на NEON, так и на SSE для этого потребуется всего четыре загрузки и три или четыре распаковки (намного лучше, чем нынешние восемь загрузок + шесть распаковок).

Избавиться от лишнего трафика стека может быть сложнее. Убедитесь, что оптимизатор включен. Исправление проблемы с множественной загрузкой уменьшит вдвое трафик стека, потому что вы будете генерировать каждый индекс только один раз, но чтобы полностью избавиться от него, может потребоваться написать ассемблер вместо встроенных функций (или использовать более новую версию компилятора).

person Stephen Canon    schedule 18.07.2013
comment
Кроме того, измените источник. Обвинять компилятор в том, что он делает неизбежное (перезагружается), потому что вы не дали понять (достаточно), что память не может измениться под вами, несправедливо... - person FrankH.; 18.07.2013
comment
@FrankH.: (при условии, что таблица не помечена как volatile, а m_fResult является локальной, что почти наверняка так и есть) компилятору разрешено (и должно) предполагать, что записи таблицы не изменятся под ней. Тем не менее, да, источник можно было бы написать более чисто (я предложил, как это сделать в своем ответе). - person Stephen Canon; 18.07.2013
comment
Это верно для m_fResult, но НЕ для самого sftable[]. - person FrankH.; 18.07.2013
comment
@FrankH.: только хранилища между загрузками от sftable до frac, которые, как мы видим, являются локальными, и m_fResult, я полагаю, локальными. Таким образом, компилятор может предположить, что они не используют псевдоним sftable и, следовательно, значения в sftable не изменяются во время выполнения последовательности кода, если только sftable не объявлено volatile (маловероятно). - person Stephen Canon; 18.07.2013
comment
Спасибо. я понял, что m_fResult не был локальным, поэтому это было одной из причин плохой сборки. Сейчас лучше, но не идеально, я думаю. Я посмотрю, смогу ли я дать компилятору больше подсказок об ограничении sftable. Сборка была создана intelcompiler xe13 кстати. - person evitan; 21.07.2013

arrow_upward
0
arrow_downward

Одна из причин, по которой компилятор создает здесь "странный" код (с большим количеством повторных загрузок), заключается в том, что для корректности он должен предположить, что данные в sftable[] массивах могут измениться. Чтобы сделать сгенерированный код лучше, реструктурируйте его, чтобы он выглядел так:

VEC_INT iIdx = VEC_FLOAT2INT(m_fIndex);
VEC_FLOAT frac = VEC_SUB(m_fIndex ,VEC_INT2FLOAT(iIdx);
VEC_FLOAT fracnew;

// make it explicit that all you want is _four loads_
typeof(*sftable) tbl[4] = {
    sftable[iIdx[0]], sftable[iIdx[1]], sftable[iIdx[2]], sftable[iIdx[3]]
};

m_fResult[0] = tbl[0].val2
m_fResult[1] = tbl[1].val2;
m_fResult[2] = tbl[2].val2;
m_fResult[3] = tbl[3].val2;
fracnew[0] = tbl[0].val1;
fracnew[1] = tbl[1].val1;
fracnew[2] = tbl[2].val1;
fracnew[3] = tbl[3].val1;

m_fResult=VEC_MUL( m_fResult,frac);
m_fResult=VEC_ADD( m_fResult,fracnew);
frac = fracnew;

Возможно, имеет смысл (из-за чередования макета того, что у вас есть в sftable[]), использовать встроенные функции, потому что оба векторных массива с плавающей запятой fResult и frac вполне вероятно загружаются из tbl[] с помощью одной инструкции (unpack hi/lo в SSE, распакуйте в Neon). Поиск в «основной» таблице невозможно векторизовать без помощи чего-то вроде инструкции AVX2 VGATHER, но это не должно быть более четырех загрузок.

person FrankH.    schedule 18.07.2013
comment
я попробую с этим. Моя основная ошибка заключалась в использовании нелокальной памяти (m_fResult и m_fIndex). Я посмотрю, что выйдет, если я локализую их. - person evitan; 21.07.2013