Giảm hiệu quả từng phần cho các mảng của các phần tử, độ lệch và độ dài của các danh sách con

Question

Đối với ứng dụng của tôi, tôi phải xử lý một loạt các đối tượng (ví dụ: int s). Để kết thúc này, tôi lưu trữ các yếu tố trong một mảng liên tục đơn

arr = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...} 

và các thông tin về xô (danh sách con) được cho bởi offsets tới phần tử đầu tiên trong thùng tương ứng và độ dài của sublist.

Vì vậy, ví dụ, cho

offsets = {0,3,8,..} 
sublist_lengths = {3,5,2,...} 

sẽ dẫn đến việc chia rẽ sau:

0 1 2 || 3 4 5 6 7 || 8 9 || ... 

Những gì tôi đang tìm kiếm là một cách hơi nói chung và hiệu quả để chạy các thuật toán, như cắt giảm, trên các nhóm chỉ sử dụng hạt nhân tùy chỉnh hoặc thư viện thrust. Cách tổng hợp các xô nên cung cấp:

3 || 25 || 17 || ... 

Những gì tôi đã đi lên với:

• tùy chọn 1: hạt nhân tùy chỉnh đòi hỏi khá nhiều mày mò, bản vào bộ nhớ chia sẻ, sự lựa chọn đúng đắn kích thước khối và lưới và thực hiện riêng các thuật toán, như quét, giảm, v.v. Ngoài ra, mọi thao tác đơn lẻ sẽ yêu cầu một hạt nhân riêng. Nói chung nó là rõ ràng với tôi làm thế nào để làm điều này, nhưng sau khi đã sử dụng thrust cho mấy ngày vừa qua tôi có ấn tượng rằng có thể có một cách thông minh hơn

• phương án 2: tạo ra một loạt các phím từ các khoảng trống ({0,0,0,1,1,1,1,1,2,2,3,...} trong ví dụ trên) và sử dụng thrust::reduce_by_key. Tuy nhiên, tôi không thích thế hệ danh sách bổ sung.

• tùy chọn 3: Sử dụng thrust::transform_iterator cùng với thrust::counting_iterator để tạo đưa ra ở trên danh sách chủ chốt khi đang bay. Thật không may, tôi không thể đưa ra một thực hiện mà không yêu cầu gia số của các chỉ số vào danh sách bù đắp trên thiết bị và đánh bại song song.

Cách nào tốt nhất để thực hiện việc này?

Answer 1

Trong vòng Thrust, tôi không thể nghĩ ra giải pháp nào tốt hơn Option 2. Hiệu suất sẽ không khủng khiếp, nhưng chắc chắn không phải là tối ưu.

Cấu trúc dữ liệu của bạn tương tự như định dạng Compressed Sparse Row (CSR) để lưu trữ ma trận thưa thớt, vì vậy bạn có thể sử dụng các kỹ thuật được phát triển để tính toán sparse matrix-vector multiplies (SpMV) cho các ma trận như vậy nếu bạn muốn hiệu suất tốt hơn. Lưu ý rằng mảng "offset" của định dạng CSR có độ dài (N + 1) đối với ma trận có N hàng (nghĩa là các thùng trong trường hợp của bạn) trong đó giá trị offset cuối cùng là độ dài arr. Các CSR SpMV code trong Cusp là một chút phức tạp, nhưng nó phục vụ như là một điểm khởi đầu tốt cho hạt nhân của bạn. Chỉ cần xóa mọi tham chiếu đến Aj hoặc x khỏi mã và vượt qua offsets và arr vào các đối số Ap và Av tương ứng.

Answer 2

Bạn không đề cập đến mức độ lớn của các nhóm. Nếu các thùng đủ lớn, có thể bạn có thể lấy đi bằng cách sao chép các offset và sublist_lengths tới máy chủ, lặp lại chúng và thực hiện một cuộc gọi Thrust riêng biệt cho mỗi nhóm. Fermi có thể có 16 hạt nhân trong chuyến bay cùng một lúc, do đó, trên kiến ​​trúc đó bạn có thể xử lý các thùng nhỏ hơn và vẫn sử dụng tốt.