Có ai có thể cung cấp cho tôi thuật toán song song để tính toán hệ số Cholesky thưa thớt không? Nó phải phù hợp để thực thi trên GPU. Bất kỳ câu trả lời nào trong CUDA, OpenCL, hoặc thậm chí cả mã giả sẽ được đánh giá cao.Thuật toán thống kê Sparse Cholesky cho GPU
Nói chung, các phương pháp thưa thớt trực tiếp không phù hợp với GPU. Trong khi các giải pháp trực tiếp tốt nhất (suy nghĩ về các gói như CHOLMOD, SuperLU, MUMPS ở đây) sử dụng các chiến lược để tạo các khối con dày đặc có thể được xử lý bằng L3 BLAS, kích thước và hình dạng của các khối không có xu hướng lợi nhuận từ việc sử dụng BLAS GPU để tăng tốc. Nó không có nghĩa là nó không thể được thực hiện, chỉ là những cải tiến hiệu suất có thể không có giá trị nỗ lực.
Thấy như bạn đang hỏi về một yếu tố Cholesky thưa thớt, tôi giả định ma trận là xác định dương xác định đối xứng. Trong trường hợp đó, bạn có thể xem xét sử dụng một trình giải quyết lặp - có một số cách triển khai tốt của Conjugate Gradient và các phương thức không gian con Krylov khác với các điều kiện tiên quyết đơn giản có thể sử dụng một số. Thư viện Cusp cho CUDA có thể đáng để điều tra nếu sự cố của bạn tuân theo các phương pháp lặp lại. Thư viện ViennaCL cung cấp một cái gì đó tương tự nếu bạn đang tìm kiếm OpenCL.
Tôi sẽ thử phương pháp Conjugate Gradient để bắt đầu. Cảm ơn! –
Xem các bài viết này, với sự cho phép của ACM (SC'08 và PPoPP '09 là các hội nghị xuất sắc).
V. Volkov, J. W. Demmel. Chuẩn hóa GPU để điều chỉnh đại số tuyến tính dày đặc. SC'08.
Jung, J.H., O’Leary, D.P. Phân tích Cholesky và Lập trình tuyến tính trên GPU. Giấy học giả, Đại học của Maryland, 2006.
G. Quintana-Orti, F. D. Igual, E. S. Quintana-Orti, R. A. van de Geijn. Giải quyết các hệ thống tuyến tính dày đặc trên nền tảng với nhiều bộ tăng tốc phần cứng. PPoPP '09.
Nếu bạn không có quyền truy cập vào các thông qua Cổng ACM/DL, chúng có thể trực tuyến ở đâu đó. Nếu không ... Tôi có thể trích dẫn một số phần có liên quan nhất, với trích dẫn và sử dụng hợp lý.
EDIT:
Kiểm tra điều này có thể?
EDIT2: Thiếu phần "thưa thớt".
Nhìn xung quanh trực tuyến và tại ACM/IEEE, tôi không thấy nhiều thứ nhảy ra khỏi tôi. Những gì tôi thấy không có vẻ hứa hẹn ... đây có thể không phải là một tính toán mà bạn thấy rất nhiều lợi ích khi sử dụng GPU.
Tất cả các tham chiếu này dường như là cho hệ số ma trận dày đặc. Các thuật toán cho phân tách thưa thớt có một chút khác biệt ... –
Ồ, hoàn toàn bị bỏ lỡ trong câu hỏi. Tôi sẽ xem xét lại ... – Patrick87
Thuật toán nhiều mặt có vẻ là một lựa chọn phổ biến cho hệ số yếu song song. Xem gói MUMPS, here.
Như tôi đã hiểu, mã này sử dụng rộng rãi các cuộc gọi cấp 3 BLAS (DGEMM và v.v.) để đạt hiệu suất cao. Tôi sẽ điều tra xem liệu có thể liên kết với triển khai dựa trên thực hiện hay không, chẳng hạn như CUDA BLAS hoặc tương tự nếu bạn muốn sử dụng GPU thay vì FPU.
Trái ngược với hệ số dày đặc, phương pháp thưa thớt luôn bao gồm số lượng không đáng kể số nguyên làm việc ngoài công việc dấu phẩy động (mặc dù dấu phẩy động vẫn chiếm ưu thế). Tôi không có chuyên gia về GPU's, nhưng liệu CPU có phù hợp hơn với công việc số nguyên hơn là GPU ?? Đây có thể là một lý lẽ chống lại việc triển khai toàn bộ thuật toán cho GPU ...
Hy vọng điều này sẽ hữu ích.
Điều nguyên bản, không phải là một đối số chống lại GPU. Điều đó đang được nói, các mẫu truy cập bộ nhớ bất thường/cấu trúc dữ liệu (ví dụ: với con trỏ) và/hoặc luồng kiểm soát phân nhánh/phân kỳ là các đối số mạnh mẽ chống lại việc sử dụng GPU. Tôi không có chuyên gia về yếu tố Cholesky thưa thớt, nhưng làm thưa thớt Cholesky là khá nhiều đứa trẻ poster cho truy cập bộ nhớ bất thường và dòng điều khiển phân kỳ, phải không? – Patrick87
@ Patrick87 - Những điểm tốt. Như tôi đã nhận xét ở trên, tôi không nên quá cụ thể trong câu hỏi của tôi. Bất kỳ thuật toán để giải quyết một hệ thống đối xứng thưa thớt của phương trình tuyến tính sẽ làm. –
@Pat: Thuật toán tốt (nghĩa là nhiều mặt trước, siêu tân vv) sử dụng cập nhật "bị chặn", ít nhất là đối với công việc dấu chấm động, trong đó cấu trúc phụ gần như dày đặc cho phép sử dụng hạt nhân dày đặc (tức là 'thói quen BLAS') . Giai đoạn nguyên bản "biểu tượng" ban đầu thường liên quan đến truy cập bất thường, theo như tôi hiểu. –
Yếu tố chính xác của Cholesky trên GPU là một vấn đề mở. Ngay cả các Linear Programmingpaper được đề cập trước đây sử dụng một thuật toán dày đặc trong khi hầu hết các vấn đề là thưa thớt. Thị trường giải độc LP thương mại rất cạnh tranh, nhưng không ai có sản phẩm sử dụng nhiều GPU.
Xem UHM - Bộ giải mã ma trận Hyper chưa lắp ráp. Nó có thể tính toán hệ số Cholesky thưa thớt bằng cách sử dụng nhiều GPU trên một máy chủ.
Đăng một số mã giả để thực hiện việc này trên bộ xử lý không thường xuyên và tôi rất sẵn lòng thảo luận việc chuyển nó vào GPU. Ngoài ra, đây có lẽ là thứ đã tồn tại ... hãy để tôi tìm kiếm nhanh. Aha. Xem câu trả lời của tôi dưới đây. – Patrick87
Nó có phải là một yếu tố đáng tin cậy không? Nói chung thưa thớt, các phương pháp lặp lại có thể tận dụng hiệu suất spMV hiệu suất cao phù hợp hơn với các GPU trực tiếp giải quyết. – talonmies
@talonmies - Ah! Tôi không nên là cụ thể. Những gì tôi thực sự cần là một thuật toán giải quyết hệ thống đối xứng thưa thớt của các phương trình tuyến tính. Hệ số Cholesky là những gì hiện đang được sử dụng để giải quyết vấn đề này. Tuy nhiên, trong trường hợp của GPU, nếu các thuật toán khác phù hợp hơn, tôi sẽ mở nó. –