Sử dụng GPU để tăng tốc độ tính toán BigInteger

Question

Tôi gần như đã hoàn thành với một thuật toán xử lý một số số nguyên rất lớn (khoảng thứ tự 2 được nâng lên 100.000.000 điện). Điều này cần một vài giờ mã song song cao trên một máy chủ lõi 16 với bộ nhớ đầy đủ hơn vì thuật toán không phải là bộ nhớ chuyên sâu. Tôi tận dụng các lớp BigInteger trong .NET 4.

Các chi tiết cụ thể của thuật toán là không quan trọng nhưng đối với bối cảnh, đây là danh sách khá đầy đủ các hoạt động thực hiện trên những số nguyên và một số tính năng nổi bật của thuật toán:

• Cộng/trừ.
• Nhân số lớn với số lượng nhỏ.
• Phân chia số lượng lớn theo số rất nhỏ (ví dụ 2).
• Cơ sở 2 Nhật ký.
• Cơ sở 2 Nguồn.
• So sánh hai hoặc nhiều số lớn (Min/Max).
• Không có sự tham gia của bất kỳ số nguyên tố nào.
• Thuật toán được thiết kế đặc biệt không phải là bộ nhớ chuyên sâu vì hiệu quả truy cập bộ nhớ truy cập nhiều hơn so với một số tính toán trực tuyến thông minh. Tuy nhiên, nếu truy cập bộ nhớ được cải thiện, thuật toán có thể được hưởng lợi một cách hợp lý.

Tôi đã được tối ưu hóa mã càng nhiều càng tốt và hồ sơ hiện nay cho thấy chỉ có hai nút thắt cổ chai:

• Tính cơ sở 2 Đăng nhập với số lượng lớn như vậy.
• Kiểm tra các mẫu chữ số nhị phân được xác định trước trong các số này. Điều này là do cách duy nhất để truy cập dữ liệu cơ bản của BigInteger là bằng cách sử dụng ToByteArray đầu tiên thay vì các hoạt động tại chỗ. Ngoài ra, hoạt động trên các khối có kích thước byte không giúp hiệu suất.

Xem xét truy cập bộ nhớ và hoạt động Đăng nhập, tôi bắt đầu nghĩ về GPU và liệu tôi có thể giảm tải một số công việc một cách hiệu quả hay không. Tôi biết rất ít về GPU ngoại trừ việc chúng được tối ưu hóa cho các hoạt động điểm nổi.

Câu hỏi của tôi là sử dụng thư viện như GPU .NET, làm cách nào để xử lý số lượng lớn như vậy trên GPU? Tôi có thể bằng cách nào đó sử dụng các tối ưu hóa dấu phẩy động để tính Nhật ký cho các số lớn như vậy không?

Tìm kiếm điểm khởi đầu để hình thành một chiến lược.

Answer 1

Tôi đang tìm kiếm GPU hoạt động trong C# và đang xem xét Tidepowerd.com GPU.NET và CUDAfy.NET. Cả Nvidia cụ thể và CUDAfy không hỗ trợ mono khi tôi kiểm tra lần cuối. Nhưng cả hai đều cho phép mã tìm kiếm hợp lý bình thường trong C# chạy trên GPU.

Ngoài ra, bạn có cân nhắc sử dụng thư viện của bên thứ ba không ?. Có một số thư viện BigInteger rất tốt, cũng là nguồn mở. GMP là rất tốt và miễn phí; http://gmplib.org/, có ít nhất một trình bao bọc C# (mà tôi không có kinh nghiệm) http://www.emilstefanov.net/Projects/GnuMpDotNet/

Lớp BigInteger trong .NET là không thay đổi và theo kinh nghiệm của tôi không thuận tiện. Nếu bạn có 2 ints kích thước của bạn (khoảng 100MB) kết quả Add operation trong BigInt 100MB thứ ba. Nó có thể được thực hiện cách nhanh hơn nếu ví dụ sẽ sửa đổi một trong hai bản gốc.

C = A + B means allocating 100MB for C (this is what BigInt does) 
A = A + B means you no longer have the original A, but a much faster calculation 

Answer 2

Nếu ai đó thấy hữu ích, đây là triển khai Log Base 2 cho BigInteger nhanh hơn nhiều so với việc sử dụng chức năng được tích hợp sẵn.

private static BigInteger LogBase2(BigInteger num) { 
    if (num <= Zero) 
     return MinusOne; //does not support negative values. 
    BigInteger i = Zero; 
    while (!(num >>= 1).IsZero) 
     i++; 
    return i; 
}