Có bất kỳ hướng dẫn asm nào có thể tăng tốc độ tính toán của min/max của vectơ tăng gấp đôi/số nguyên trên kiến trúc Core i7 không?x86 tối đa/phút asm hướng dẫn?
Cập nhật:
Tôi không mong đợi câu trả lời giàu như vậy, cảm ơn bạn. Vì vậy, tôi thấy rằng tối đa/phút có thể thực hiện mà không cần phân nhánh. Tôi có câu hỏi phụ:
Có cách nào hiệu quả để lấy chỉ mục của gấp đôi lớn nhất trong mảng không?
SSE4 có PMAXSD hoặc PMAXUD cho số nguyên 32 bit đã ký/không dấu, có thể hữu ích.
SSE2 có MAXPD và MAXSD so sánh giữa các cặp đôi, vì vậy bạn thực hiện theo n/2-1 MAXPD với một MAXSD để nhận được tối đa vectơ của n, với sự xen kẽ thông thường của tải và thao tác.
Có MIN tương đương ở trên.
Đối với trường hợp tăng gấp đôi, bạn có lẽ sẽ không làm tốt hơn trong lắp ráp hơn một trình biên dịch ++ C nửa phong nha trong chế độ SSE:
peregrino:$ g++ -O3 src/min_max.cpp -o bin/min_max
peregrino:$ g++ -O3 -msse4 -mfpmath=sse src/min_max.cpp -o bin/min_max_sse
peregrino:$ time bin/min_max
0,40
real 0m0.874s
user 0m0.796s
sys 0m0.004s
peregrino:$ time bin/min_max_sse
0,40
real 0m0.457s
user 0m0.404s
sys 0m0.000s
nơi min_max tính min và max của một mảng của 500 đôi 100.000 lần sử dụng một vòng lặp ngây thơ:
bool min_max (double array[], size_t len, double& min, double& max)
{
double min_value = array [ 0 ];
double max_value = array [ 0 ];
for (size_t index = 1; index < len; ++index) {
if (array [ index ] < min_value) min_value = array [ index ];
if (array [ index ] > max_value) max_value = array [ index ];
}
min = min_value;
max = max_value;
}
để đối phó với phần hai, việc tối ưu hóa truyền thống để loại bỏ nhánh từ một hoạt động tối đa là so sánh các giá trị, có cờ như một hát le bit (cho 0 hoặc 1), trừ một (cho 0 hoặc 0xffff_ffff) và 'và' nó với xor của hai kết quả có thể, do đó bạn nhận được tương đương với (a > best ? (current_index^best_index) : 0)^best_index). Tôi nghi ngờ có một cách SSE đơn giản để làm điều đó, đơn giản bởi vì SSE có xu hướng hoạt động trên các giá trị đóng gói hơn là các giá trị được gắn thẻ; có một số hoạt động chỉ mục ngang, vì vậy bạn có thể thử tìm giá trị tối đa, sau đó trừ đi tất cả các phần tử trong vector gốc, sau đó thu thập bit dấu, và ký hiệu số không tương ứng với chỉ mục của giá trị tối đa, nhưng có thể không phải là một cải tiến trừ khi bạn đang sử dụng quần short hoặc byte.
Bạn chỉ cần log2 (vector_length) shuffle + MAXPS/MAXPD hoạt động, không phải VL/2, để có được tối đa ngang của một vector SIMD duy nhất. Về cơ bản, nó giống như một [số tiền ngang] (https://stackoverflow.com/questions/6996764/fastest-way-to-do-horizontal-float-vector-sum-on-x86): thu hẹp một nửa mỗi lần . (Hoặc để lại kết quả phát sóng cho mọi phần tử, hoán đổi cao/thấp). –
Việc ghi danh với nhiều bộ cộng dồn phải tăng tốc gấp 2 lần, nếu bạn không bị nghẽn cổ chai trong bộ nhớ. ('MAXPD' có độ trễ chu kỳ 3 hoặc 4, nhưng thông lượng là 1 cho mỗi chu kỳ, vì vậy bạn cần trình biên dịch phát ra asm sử dụng nhiều vectơ và kết hợp chúng ở cuối mảng.) Clang có xu hướng làm điều này trong khi tự động- vectơ, nhưng gcc vẫn thường không. –
MAXPS và MINPS từ SSE đều hoạt động trên các số dấu chấm động có độ chính xác đóng gói đơn. PMAXSW, PMINSW, PMAXUB và PMINUB tất cả hoạt động trên các từ 8 bit được đóng gói, hoặc đã ký hoặc chưa ký. Xin lưu ý rằng chúng so sánh hai thanh ghi SSE đầu vào hoặc vị trí địa chỉ một cách khôn ngoan và lưu kết quả vào thanh ghi SSE hoặc vị trí bộ nhớ.
Các phiên bản MAXE và MINPS của SSE2 sẽ hoạt động trên các phao nổi chính xác kép.
Bạn đang sử dụng cờ biên dịch và tối ưu hóa nào? gcc 4.0 và tốt hơn sẽ tự động vector hóa hoạt động nếu mục tiêu của bạn hỗ trợ chúng, các phiên bản trước đó có thể cần một cờ cụ thể.
nếu bạn đang sử dụng thư viện IPP của Intel bạn có thể sử dụng các vector statistical functions để tính toán vector min/max (trong số những thứ khác)
Để đối phó với câu hỏi thứ hai của bạn: trên hầu hết các nền tảng, có thư viện mà đã chứa được tối ưu hóa triển khai thực hiện hoạt động này (và hầu hết các hoạt động vector đơn giản khác). Sử dụng chúng.
vDSP_maxviD() và cblas_idamax() trong Accelerate.frameworkcblas_idamax()cblas_idamax() trong thư viện BLAS, có thể hoặc không được điều chỉnh tốt tùy thuộc vào nguồn gốc của nó; người dùng quan tâm đến hiệu suất thường sẽ có một cài đặt tốt (hoặc có thể được thuyết phục để cài đặt)Để trả lời câu hỏi thứ hai của bạn, bạn có thể cân nhắc cách bạn thu thập và lưu trữ dữ liệu này.
Bạn có thể lưu trữ dữ liệu trong một cây B giữ cho dữ liệu được sắp xếp mọi lúc, chỉ yêu cầu hoạt động so sánh lôgarit.
Sau đó, bạn biết mọi lúc ở mức tối đa.
Vì bạn đang đối phó với chỉ 300 đôi, một cây nhị phân tự cân bằng có lẽ là tốt nhất. http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree – Drew
Tại sao không phải là một đống nhị phân? Thời gian liên tục tốt hơn logarit ... –
Cập nhật: Tôi chỉ nhận ra bạn nói "mảng", không phải "vector" trong phần 2. Tôi sẽ để lại này đây anyway trong trường hợp nó rất hữu ích.
lại: một phần hai: tìm ra chỉ số của phần tử max/min trong một vector SSE:
Thực hiện tối đa ngang. Đối với vectơ 128b của 2 double yếu tố, đó chỉ là một shufpd + maxpd để rời kết quả phát sóng cho cả hai yếu tố.
Đối với các trường hợp khác, tất nhiên sẽ mất nhiều bước hơn. Xem Fastest way to do horizontal float vector sum on x86 để biết các ý tưởng, thay thế addps bằng maxps hoặc minps. (Nhưng lưu ý rằng số nguyên 16 bit là đặc biệt, vì bạn có thể sử dụng SSE4 phminposuw. Đối với giá trị tối đa, trừ từ 255)
Thực hiện so sánh giữa vector gốc vectơ và vectơ.
(pcmpeqq mẫu bit nguyên hoặc thông thường cmpeqpd cả hai đều hoạt động trong trường hợp double).
int _mm_movemask_pd (__m128d a) (movmskpd) để nhận kết quả so sánh dưới dạng bitmap số nguyên.bsf) đối với kết quả (đầu tiên): index = _bit_scan_forward(cmpmask). cmpmask = 0 là không thể nếu bạn sử dụng so sánh số nguyên (vì ít nhất một phần tử sẽ khớp ngay cả khi chúng là NaN).Điều này chỉ được biên dịch thành 6 hướng dẫn (bao gồm movapd). Yup, chỉ cần kiểm tra trên the Godbolt compiler explorer và nó, với SSE.
#include <immintrin.h>
#include <x86intrin.h>
int maxpos(__m128d v) {
__m128d swapped = _mm_shuffle_pd(v,v, 1);
__m128d maxbcast = _mm_max_pd(swapped, v);
__m128d cmp = _mm_cmpeq_pd(maxbcast, v);
int cmpmask = _mm_movemask_pd(cmp);
return _bit_scan_forward(cmpmask);
}
Lưu ý rằng _mm_max_pd is not commutative with NaN inputs.Nếu NaN là có thể, và bạn không quan tâm đến hiệu suất trên Intel Nehalem, bạn có thể xem xét sử dụng _mm_cmpeq_epi64 để so sánh các mẫu bit. Tuy nhiên, sự chậm trễ từ float đến vec-int là một vấn đề trên Nehalem.
NaN! = NaN trong điểm nổi IEEE, do đó, mặt nạ kết quả _mm_cmpeq_pd có thể là tất cả 0 trong trường hợp tất cả NaN.
Một việc khác bạn có thể thực hiện trong trường hợp 2 yếu tố để luôn nhận được 0 hoặc 1 là thay thế bit-scan bằng cmpmask >> 1. (bsf là lạ với input = all-zero).
Ngôn ngữ máy chủ là gì? Nếu nó là c/C++ tôi sẽ không lo lắng về nó quá nhiều. –
tối đa khoảng 300 đôi là trong vòng lặp lớn nhất của chương trình lớn. 85% thời gian được chi tiêu trong khoảng 10 trong số 8'000 dòng mã. Ngôn ngữ máy chủ không quan trọng chỉ vì điều đó. Nhưng có nó là C + + –