Các quy trình số nguyên dài có thể hưởng lợi từ SSE không?

Question

Tôi vẫn đang làm việc về các thường trình cho các số nguyên dài tùy ý trong C++. Cho đến nay, tôi đã thực hiện phép cộng/trừ và phép nhân cho CPU Intel 64 bit.

Mọi thứ hoạt động tốt, nhưng tôi tự hỏi liệu tôi có thể tăng tốc độ một chút bằng SSE hay không. Tôi duyệt qua các tài liệu SSE và danh sách hướng dẫn xử lý, nhưng tôi không thể tìm thấy bất cứ điều gì tôi nghĩ rằng tôi có thể sử dụng và đây là lý do:

• SSE có một số hướng dẫn số nguyên, nhưng hầu hết các lệnh xử lý dấu chấm động. Nó không giống như nó được thiết kế để sử dụng với số nguyên (ví dụ như có một số nguyên so sánh cho ít hơn?)

• Ý tưởng SSE là SIMD (cùng một lệnh, nhiều dữ liệu), vì vậy nó cung cấp hướng dẫn cho 2 hoặc 4 hoạt động độc lập. Tôi, mặt khác, muốn có một cái gì đó giống như một số nguyên 128 bit thêm (128 bit đầu vào và đầu ra). Điều này dường như không tồn tại. (Tuy nhiên? Trong AVX2 có thể?)

• Việc bổ sung và trừ số nguyên không xử lý cả đầu vào lẫn đầu ra. Vì vậy, nó rất cồng kềnh (và do đó, chậm) để làm điều đó bằng tay.

Câu hỏi của tôi là: đánh giá của tôi đúng hay có điều gì tôi đã bỏ qua không? Các số nguyên dài có thể hưởng lợi từ SSE không? Đặc biệt, họ có thể giúp tôi viết nhanh hơn, phụ hay thường lệ không?

Answer 1

Trước đây, câu trả lời cho câu hỏi này là một câu hỏi "không". Nhưng đến năm 2017, tình hình đang thay đổi.

Nhưng trước khi tôi tiếp tục, thời gian đối với một số thuật ngữ nền:

1. Full Lời Arithmetic
2. phần Lời Arithmetic

Full-Word Arithmetic:

này là biểu diễn chuẩn, nơi số được lưu trữ trong cơ sở 2 hoặc 2 sử dụng một mảng các số nguyên 32 bit hoặc 64 bit. Nhiều thư viện và ứng dụng bignum (bao gồm GMP) sử dụng biểu diễn này.

Trong biểu diễn toàn từ, mỗi số nguyên có một biểu diễn duy nhất. Các hoạt động như so sánh dễ dàng. Nhưng những thứ như bổ sung thì khó hơn vì sự cần thiết phải truyền bá.

Đây là sự truyền bá này làm cho số học bignum hầu như không thể vector hóa.

Partial-Word Arithmetic

Đây là một đại diện ít sử dụng khi số lượng sử dụng một cơ sở thấp hơn phần cứng từ kích thước. Ví dụ, chỉ đặt 60 bit trong mỗi từ 64 bit. Hoặc sử dụng cơ sở 1,000,000,000 với kích thước từ 32 bit cho số học thập phân.

Các tác giả của GMP gọi đây là "đinh" nơi "đinh" là phần không sử dụng của từ đó.

Trong quá khứ, việc sử dụng số học một phần chủ yếu được giới hạn cho các ứng dụng hoạt động trong cơ sở không nhị phân. Nhưng ngày nay, nó ngày càng trở nên quan trọng hơn ở chỗ nó cho phép truyền bá thông tin bị trì hoãn.

---

Vấn đề với Full-Word Arithmetic:

Vectorizing toàn chữ số học trong lịch sử là một nguyên nhân bị mất:

1. SSE/AVX2 không có người hỗ trợ cho carry-tuyên truyền.
2. SSE/AVX2 không có thêm/phụ 128 bit.
3. SSE/AVX2 không có số nguyên 64 x 64-bit nhân. *

* AVX512-DQ thêm một-nửa dưới 64x64-bit nhân. Nhưng vẫn không có chỉ dẫn nửa trên.

Hơn nữa, x86/x64 có rất nhiều chuyên ngành vô hướng hướng dẫn bignums:

• Add-với-Carry: adc, adcx, adox.
• Nhân đôi từ: Đơn hạng mul và mulx.

Trong điều kiện này, cả việc thêm nhân đôi và bignum đều rất khó để SIMD đánh bại vô hướng trên x64. Chắc chắn không phải với SSE hoặc AVX.

Với AVX2, SIMD gần như cạnh tranh với nhân vô hướng nếu bạn sắp xếp lại dữ liệu để bật "vector hóa dọc" của 4 khác nhau (và độc lập) nhân với cùng độ dài trong mỗi làn trong số 4 làn đường SIMD.

AVX512 sẽ giúp mọi thứ có lợi cho SIMD một lần nữa giả sử vector dọc. Tuy nhiên, đối với hầu hết các phần, "vectorization ngang" của bignums phần lớn vẫn là một nguyên nhân bị mất, trừ khi bạn có nhiều người trong số họ (có cùng kích thước) và có thể đủ khả năng chi phí chuyển đổi chúng để làm cho chúng "theo chiều dọc".

bản vẽ Gia của phần-Word Arithmetic

Với phần chữ số học, các thêm "đinh" bit cho phép bạn để trì hoãn carry-tuyên truyền.

Vì vậy, miễn là bạn khi bạn không tràn từ, SIMD add/sub có thể được thực hiện trực tiếp. Trong nhiều triển khai, biểu diễn từng phần sử dụng các số nguyên đã ký để cho phép các từ đi tiêu cực.

Bởi vì có (thông thường) không cần phải thực hiện carryout, SIMD add/sub trên một phần từ có thể được thực hiện hiệu quả như nhau trên cả hai chiều dọc và chiều ngang vectorigned bignums.

Thực hiện trên bignums được vector vectơ theo chiều ngang vẫn rẻ khi bạn chỉ chuyển móng tay sang làn đường tiếp theo.Một carryout đầy đủ để hoàn toàn rõ ràng các bit móng tay và nhận được một đại diện duy nhất thường là không cần thiết, trừ khi bạn cần phải làm một so sánh của hai con số gần như giống nhau.

Phép nhân phức tạp hơn với số học từng phần vì bạn cần xử lý các bit móng tay. Nhưng như với add/sub, nó vẫn có thể làm điều đó một cách hiệu quả trên các bignums vectơ theo chiều ngang.

AVX512-IFMA (đi kèm với bộ vi xử lý Cannonlake) sẽ có hướng dẫn cung cấp đầy đủ 104 bit của một 52 x 52-bit nhân (có lẽ là sử dụng phần cứng FPU). Điều này sẽ chơi rất tốt với các biểu diễn từng phần sử dụng 52 bit cho mỗi từ.

lớn Phép nhân sử dụng FFTs

Đối bignums thực sự lớn, nhân được thực hiện một cách hiệu quả nhất bằng Fast-Fourier Transforms (FFTs).

FFT hoàn toàn có thể vector hóa được vì chúng hoạt động độc lập double s. Điều này có thể bởi vì về cơ bản, đại diện cho rằng FFT sử dụng là đại diện một phần từ.

---

Tóm tắt, vector hóa số học bignum là có thể. Nhưng hy sinh phải được thực hiện.

Nếu bạn mong đợi SSE/AVX có thể tăng tốc một số mã bignum hiện tại mà không thay đổi cơ bản về cách trình bày và/hoặc bố trí dữ liệu, điều đó không có khả năng xảy ra.

Tuy nhiên, số học bignum có thể được vector hóa.

---

Tiết lộ:

Tôi là tác giả của y-cruncher mà làm nhiều arihmetic số lượng lớn.