Vector hóa quần áo có liên quan có điều kiện

Question

Tôi đang sử dụng cấu trúc nhỏ gọn gồm 2 quần short không dấu cho biết vị trí bắt đầu và kết thúc.
Tôi cần để có thể nhanh chóng xác định xem có bất kỳ đối tượng Range nào có độ dài (chênh lệch từ đầu đến cuối) vượt quá giá trị ngưỡng hay không.

Tôi sẽ có một số lượng lớn các đối tượng với từng mảng Range của riêng mình, do đó, không thể theo dõi được đối tượng nào trong số đó là một đối tượng trong danh sách hoặc thứ gì đó. Mã này cũng sẽ được chạy rất thường xuyên (nhiều lần một giây cho mỗi mảng), do đó, nó cần phải được hiệu quả.

struct Range 
{ 
unsigned short start; 
unsigned short end; 
} 

Tôi sẽ luôn có một mảng Range có kích thước 2^n. Trong khi tôi muốn hủy bỏ ngay sau khi tôi tìm thấy một cái gì đó trên ngưỡng, tôi khá chắc chắn nó sẽ được nhanh hơn chỉ đơn giản là HOẶC tất cả cùng nhau và kiểm tra ở cuối ... giả sử tôi có thể vectorize vòng lặp. Mặc dù nếu tôi có thể làm một tuyên bố if trên đoạn kết quả cho mỗi véc tơ, đó sẽ là lớn.

size_t rangecount = 1 << resolution; 
Range* ranges = new Range[rangecount]; 

... 

bool result = false; 
for (size_t i = 0; i < ranges; ++i) 
{ 
result |= (range[i].end - range[i].start) > 4; 
} 

Không ngạc nhiên, trình tự động vector cung cấp lỗi 1202 vì loại dữ liệu của tôi không rộng 32 hoặc 64 bit. Tôi thực sự không muốn tăng gấp đôi kích thước dữ liệu của tôi và làm cho mỗi trường một int không dấu. Vì vậy, tôi đoán cách tiếp cận tự động-vectorizer là ra cho điều này.

Có hướng dẫn véc tơ nào có thể xử lý biến 16 bit không? Nếu có, làm thế nào tôi có thể sử dụng chúng trong c + + để vectorize vòng lặp của tôi?

Answer 1

Bạn đang tự hỏi liệu có giá trị nào lớn hơn 4 không?

Có, có hướng dẫn SIMD cho việc này. Thật không may là việc tự động vectơ hóa không thể xử lý kịch bản này. Dưới đây là một thuật toán vectorized:

diff_v = end_v - start_v; // _mm_hsub_epi16 
floor_v = max(4_v, diff_v); // _mm_max_epi16 
if (floor_v != 4_v) return true; // wide scalar comparison 

Sử dụng _mm_sub_epi16 với một cấu trúc của mảng hoặc _mm_hsub_epi16 với một mảng của cấu trúc.

Thực tế kể từ khi start được lưu trữ trước tiên trong bộ nhớ, bạn sẽ làm việc trên start_v - end_v, vì vậy hãy sử dụng _mm_min_epi16 và vectơ -4.

Mỗi lệnh SSE3 sẽ thực hiện 8 lần so sánh cùng một lúc. Nó vẫn sẽ nhanh nhất để trở về sớm thay vì lặp lại. Tuy nhiên, việc bỏ vòng lặp nhiều hơn một chút có thể giúp bạn mua thêm tốc độ (chuyển bộ kết quả đầu tiên vào chức năng tối thiểu/tối đa được đóng gói để kết hợp chúng).

Vì vậy, bạn kết thúc với (ước tính):

most_negative = threshold = _mm_set_epi64(0xFCFCFCFCFCFCFCFC); // vectorized -4 

loop: 
    a = load from range; 
    b = load from range; 
    diff = _mm_hsub_epi16(a, b); 
    most_negative = _mm_min_epi16(most_negative, diff); 

    // unroll by repeating the above four instructions 4 times or so 
    if (most_negative != threshold) return true; 
repeat loop