Tính toán sự khác biệt tuyệt đối giữa các số nguyên không dấu bằng cách sử dụng SSE

Question

Trong C là có một kỹ thuật chi nhánh ít hơn để tính toán sự khác biệt tuyệt đối giữa hai int không dấu? Ví dụ cho các biến a và b, tôi muốn giá trị 2 cho các trường hợp khi a = 3, b = 5 hoặc b = 3, a = 5. Lý tưởng nhất là tôi cũng muốn có thể vector hóa tính toán bằng cách sử dụng thanh ghi SSE.

Answer 1

max(i,j) - min(i,j) 
(i>j)*(i-j) + (j>i)*(j-i) 

bạn chắc chắn có thể sử dụng các thanh ghi SSE, nhưng trình biên dịch có thể làm điều này cho bạn anyways

Answer 2

Có một số cách để làm điều đó, tôi sẽ chỉ đề cập đến một:

SSE4

• Sử dụng PMINUD và PMAXUD để tách giá trị lớn hơn trong thanh ghi số 1 và giá trị nhỏ hơn trong thanh ghi số 2.
• Trừ chúng.

MMX/SSE2

• lật bit dấu hiệu của hai giá trị vì chỉ lệnh kế tiếp chỉ chấp nhận ký so sánh số nguyên.
• PCMPGTD. Sử dụng kết quả này làm mặt nạ.
• Tính toán kết quả của cả hai (a-b) và (b-a)
• Sử dụng POR (PAND (mask, a-b), PANDN (mask, b-a)) để chọn giá trị chính xác cho chênh lệch tuyệt đối.

Answer 3

Hãy thử điều này (giả định bổ sung thứ 2, đó là OK judgning bởi thực tế rằng bạn đang yêu cầu cho SSE):

int d = a-b; 
int ad = ((d >> 30) | 1) * d; 

Giải thích: ký-bit (bit 31) được truyền xuống 1 bit. các | 1 phần đảm bảo rằng hệ số là 1 hoặc -1. Phép nhân nhanh trên các CPU hiện đại.

Answer 4

tính toán độ lệch và trả về giá trị tuyệt đối

__m128i diff = _mm_sub_epi32(a, b); 
__m128i mask = _mm_xor_si128(diff, a); 
mask = _mm_xor_si128(mask, b); 
mask = _mm_srai_epi32(mask, 31); 
diff = _mm_xor_si128(diff, mask); 
mask = _mm_srli_epi32(mask, 31); 
diff = _mm_add_epi32(diff, mask); 

Điều này đòi hỏi một ít hoạt động mà bằng cách sử dụng các ký so sánh op, và tạo ra áp lực đăng ký ít hơn.

Cùng một lượng áp lực đăng ký như trước, thêm 2 ops, chi nhánh tốt hơn và sáp nhập chuỗi phụ thuộc, ghép nối hướng dẫn để giải mã uops và sử dụng đơn vị riêng biệt. Mặc dù điều này đòi hỏi một tải, có thể được ra khỏi bộ nhớ cache. Tôi ra khỏi ý tưởng sau này.

__m128i mask, diff; 
diff = _mm_set1_epi32(-1<<31); // dependency branch after 
a = _mm_add_epi32(a, diff); // arithmetic sign flip 
b = _mm_xor_si128(b, diff); // bitwise sign flip parallel with 'add' unit 
diff = _mm_xor_si128(a, b); // reduce uops, instruction already decoded 
mask = _mm_cmpgt_epi32(b, a); // parallel with xor 
mask = _mm_and_si128(mask, diff); // dependency merge, branch after 
a = _mm_xor_si128(a, mask); // if 2 'bit' units in CPU, parallel with next 
b = _mm_xor_si128(b, mask); // reduce uops, instruction already decoded 
diff = _mm_sub_epi32(a, b); // result 

Sau khi định thời gian mỗi phiên bản với 2 triệu lần lặp trên Core2Duo, sự khác biệt là vô lượng. Vì vậy, chọn bất cứ điều gì dễ hiểu hơn.

Answer 5

SSE2:

Dường như có cùng tốc độ với chức năng thứ hai của Phernost. Đôi khi GCC lên lịch cho nó là một chu kỳ đầy đủ nhanh hơn, thời gian khác chậm hơn một chút.

__m128i big = _mm_set_epi32(INT_MIN, INT_MIN, INT_MIN, INT_MIN); 

a = _mm_add_epi32(a, big); // re-center the variables: send 0 to INT_MIN, 
b = _mm_add_epi32(b, big); // INT_MAX to -1, etc. 
__m128i diff = _mm_sub_epi32(a, b); // get signed difference 
__m128i mask = _mm_cmpgt_epi32(b, a); // mask: need to negate difference? 
mask = _mm_andnot_si128(big, mask); // mask = 0x7ffff... if negating 
diff = _mm_xor_si128(diff, mask); // 1's complement except MSB 
diff = _mm_sub_epi32(diff, mask); // add 1 and restore MSB 

SSSE3:

bao giờ nên hơi nhanh hơn so với trước đây. Có rất nhiều biến thể tùy thuộc vào cách những thứ bên ngoài vòng lặp được khai báo. (Ví dụ, làm cho a và bvolatile làm cho mọi thứ nhanh hơn! Nó có vẻ là một hiệu ứng ngẫu nhiên lên lịch biểu.) Nhưng điều này luôn luôn nhanh nhất bằng một chu kỳ hoặc lâu hơn.

__m128i big = _mm_set_epi32(INT_MIN, INT_MIN, INT_MIN, INT_MIN); 

a = _mm_add_epi32(a, big); // re-center the variables: send 0 to INT_MIN, 
b = _mm_add_epi32(b, big); // INT_MAX to -1, etc. 
__m128i diff = _mm_sub_epi32(b, a); // get reverse signed difference 
__m128i mask = _mm_cmpgt_epi32(b, a); // mask: need to negate difference? 
mask = _mm_xor_si128(mask, big); // mask cannot be 0 for PSIGND insn 
diff = _mm_sign_epi32(diff, mask); // negate diff if needed 

SSE4 (thx rwong):

Không thể kiểm tra điều này.

__m128i diff = _mm_sub_epi32(_mm_max_epu32(a, b), _mm_min_epu32(a, b)); 

Answer 6

Erm ... nó khá dễ dàng ...

int diff = abs(a - b); 

Dễ dàng vectorisable (Sử dụng SSE3 như):

__m128i sseDiff = _mm_abs_epi32(_mm_sub_epi32(a, b)); 

a và b là các số nguyên unsigned. Xem xét a = 0 và b = 0xffffffff. Sự khác biệt tuyệt đối chính xác là 0xffffffff, nhưng giải pháp của bạn sẽ cung cấp cho 1.

Answer 7

Từ tommesani.com, một giải pháp cho vấn đề này là sử dụng phép trừ chưa ký trừ hai lần.

Khi trừ bão hòa không bao giờ đi dưới 0, bạn tính toán: r1 = (ab) .saturating r2 = (ba) .saturating

Nếu a lớn hơn b, r1 sẽ chứa các câu trả lời, và r2 sẽ là 0 và ngược lại với b> a. HOẶC hai kết quả một phần với nhau sẽ mang lại kết quả mong muốn.

Theo the VTUNE users manual, PSUBUSB/PSUBUSW có sẵn cho thanh ghi 128 bit, vì vậy bạn sẽ có thể nhận được một tấn song song theo cách này.

Answer 8

Một hoặc nhiều bên dưới có thể dẫn đến mã không có nhánh, tùy thuộc vào máy và trình biên dịch, vì các biểu thức điều kiện đều rất đơn giản.

Tôi chưa trải qua tất cả các câu trả lời của câu trả lời nhưng có thể một số phần dưới đây được trình bày trong mã vectơ; chắc chắn tất cả các bên dưới là vectorizable (nếu bạn có sự so sánh unsigned để bắt đầu với, hoặc giả mạo nó bằng cách chuyển đổi các msb đầu tiên.). Tôi nghĩ sẽ hữu ích khi có một số câu trả lời vô hướng thực tế cho câu hỏi này.

unsigned udiff(unsigned a, unsigned b) 
{ 
     unsigned result = a-b; // ok if a<b; 
     if(a <b) result = -result; 
     return result; 
} 
unsigned udiff(unsigned a, unsigned b) 
{ 
     unsigned n =(a<b)? (unsigned)-1 : 0u; 
     unsigned result = a-b; 
     return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF 
} 


unsigned udiff(unsigned a, unsigned b) 
{ 
     unsigned axb = a^b; 
     if(a < b) axb = 0; 
     return (axb^b) - (axb^a); // a-b, or b-a 
} 

này sẽ làm việc trên x86_64 (hoặc bất cứ điều gì nơi temps 64-bit về cơ bản miễn phí)

unsigned udiff(unsigned a, unsigned b) 
{ 
     unsigned n= (unsigned)( 
     (long long)((unsigned long long)a - (unsigned long long)b)>>32 
        ); // same n as 2nd example 
     unsigned result = a-b; 
     return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF 
}