我需要實現一個前綴和算法，并且需要盡可能快。例如：[3, 1, 7, 0, 4, 1, 6, 3]應該給：[3, 4, 11, 11, 15, 16, 22, 25]有沒有辦法使用SSE SIMD CPU指令來執行此操作？我的第一個想法是遞歸地將每一對并行求和，直到所有總和都如下計算！//in parallel do for (int i = 0; i < z.length; i++) { z[i] = x[i << 1] + x[(i << 1) + 1];}為了使算法更清楚一點，z它不是最終的輸出，而是用來計算輸出的。int[] w = computePrefixSum(z);for (int i = 1; i < ouput.length; i++) { ouput[i] = (i % 2 == 0) ? (x[i] + ouput[i - 1]) : w[(i - 1) >> 1];}
3 回答
qq_笑_17
TA貢獻1818條經驗 獲得超7個贊
您可以利用一些較小的并行機制來獲得較大的寄存器長度和較小的和。例如，將16個1字節的值相加（恰好適合一個sse寄存器），僅需要對數2 16的加法和相等的移位數。
數量不多，但比15個依賴的附加項和附加的內存訪問快。
__m128i x = _mm_set_epi8(3,1,7,0,4,1,6,3,3,1,7,0,4,1,6,3);
x = _mm_add_epi8(x, _mm_srli_si128(x, 1));
x = _mm_add_epi8(x, _mm_srli_si128(x, 2));
x = _mm_add_epi8(x, _mm_srli_si128(x, 4));
x = _mm_add_epi8(x, _mm_srli_si128(x, 8));
// x == 3, 4, 11, 11, 15, 16, 22, 25, 28, 29, 36, 36, 40, 41, 47, 50
如果總和更長，則可以通過利用指令級并行性并利用指令重新排序來隱藏依賴項。
編輯：類似
__m128i x0 = _mm_set_epi8(3,1,7,0,4,1,6,3,3,1,7,0,4,1,6,3);
__m128i x1 = _mm_set_epi8(3,1,7,0,4,1,6,3,3,1,7,0,4,1,6,3);
__m128i x2 = _mm_set_epi8(3,1,7,0,4,1,6,3,3,1,7,0,4,1,6,3);
__m128i x3 = _mm_set_epi8(3,1,7,0,4,1,6,3,3,1,7,0,4,1,6,3);
__m128i mask = _mm_set_epi8(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
x0 = _mm_add_epi8(x0, _mm_srli_si128(x0, 1));
x1 = _mm_add_epi8(x1, _mm_srli_si128(x1, 1));
x2 = _mm_add_epi8(x2, _mm_srli_si128(x2, 1));
x3 = _mm_add_epi8(x3, _mm_srli_si128(x3, 1));
x0 = _mm_add_epi8(x0, _mm_srli_si128(x0, 2));
x1 = _mm_add_epi8(x1, _mm_srli_si128(x1, 2));
x2 = _mm_add_epi8(x2, _mm_srli_si128(x2, 2));
x3 = _mm_add_epi8(x3, _mm_srli_si128(x3, 2));
x0 = _mm_add_epi8(x0, _mm_srli_si128(x0, 4));
x1 = _mm_add_epi8(x1, _mm_srli_si128(x1, 4));
x2 = _mm_add_epi8(x2, _mm_srli_si128(x2, 4));
x3 = _mm_add_epi8(x3, _mm_srli_si128(x3, 4));
x0 = _mm_add_epi8(x0, _mm_srli_si128(x0, 8));
x1 = _mm_add_epi8(x1, _mm_srli_si128(x1, 8));
x2 = _mm_add_epi8(x2, _mm_srli_si128(x2, 8));
x3 = _mm_add_epi8(x3, _mm_srli_si128(x3, 8));
x1 = _mm_add_epi8(_mm_shuffle_epi8(x0, mask), x1);
x2 = _mm_add_epi8(_mm_shuffle_epi8(x1, mask), x2);
x3 = _mm_add_epi8(_mm_shuffle_epi8(x2, mask), x3);
- 3 回答
- 0 關注
- 527 瀏覽
添加回答
舉報
0/150
提交
取消