Código SIMD para exponenciação
-
26-09-2019 - |
Pergunta
Estou usando o SIMD para calcular o resultado rápido da exponenciação. Eu comparo o tempo com o código não SIMD. A exponenciação é implementada usando o algoritmo quadrado e multiplique.
Versão Ordinária (não SIMD) do código:
b = 1;
for (i=WPE-1; i>=0; --i){
ew = e[i];
for(j=0; j<BPW; ++j){
b = (b * b) % p;
if (ew & 0x80000000U) b = (b * a) % p;
ew <<= 1;
}
}
Versão Simd:
B.data[0] = B.data[1] = B.data[2] = B.data[3] = 1U;
P.data[0] = P.data[1] = P.data[2] = P.data[3] = p;
for (i=WPE-1; i>=0; --i) {
EW.data[0] = e1[i]; EW.data[1] = e2[i]; EW.data[2] = e3[i]; EW.data[3] = e4[i];
for (j=0; j<BPW;++j){
B.v *= B.v; B.v -= (B.v / P.v) * P.v;
EWV.v = _mm_srli_epi32(EW.v,31);
M.data[0] = (EWV.data[0]) ? a1 : 1U;
M.data[1] = (EWV.data[1]) ? a2 : 1U;
M.data[2] = (EWV.data[2]) ? a3 : 1U;
M.data[3] = (EWV.data[3]) ? a4 : 1U;
B.v *= M.v; B.v -= (B.v / P.v) * P.v;
EW.v = _mm_slli_epi32(EW.v,1);
}
}
O problema é que está computando corretamente, a versão SIMD está levando mais tempo do que a versão não-SIMD.
Por favor me ajude a depurar os motivos. Quaisquer sugestões sobre a codificação SIMD também são bem -vindas.
Obrigado e cumprimentos, Anup.
Solução
Todas as funções no FOR loops devem ser funções SIMD, não apenas duas. O tempo que leva para definir os argumentos para suas 2 funções é menos ideal do que o seu exemplo original (que provavelmente é otimizado pelo compilador)
Outras dicas
Um loop SIMD para dados de 32 bits int normalmente se parece com o seguinte:
for (i = 0; i < N; i += 4)
{
// load input vector(s) with data at array index i..i+3
__m128 va = _mm_load_si128(&A[i]);
__m128 vb = _mm_load_si128(&B[i]);
// process vectors using SIMD instructions (i.e. no scalar code)
__m128 vc = _mm_add_epi32(va, vb);
// store result vector(s) at array index i..i+3
_mm_store_si128(&C[i], vc);
}
Se você achar que precisa se mover entre o código escalar e o código SIMD dentro do loop, provavelmente não ganhará nada com a otimização SIMD.
Grande parte da habilidade na programação SIMD vem de encontrar maneiras de fazer seu algoritmo funcionar com o número limitado de instruções e tipos de dados suportados que uma determinada arquitetura SIMD fornece. Você frequentemente precisará explorar a priori Conhecimento do seu conjunto de dados para obter o melhor desempenho possível, por exemplo, se você tiver certeza de que seus valores inteiros de 32 bits realmente têm um intervalo que se encaixa em 16 bits, isso tornaria a parte da multiplicação do seu algoritmo muito mais fácil de implementar.