Tôi đã giải quyết vấn đề khá chuẩn trên GPU, nhưng tôi khá mới đối với GPGPU thực tế, vì vậy tôi đang tìm ý tưởng để tiếp cận vấn đề này.giảm phân đoạn với phân đoạn rải rác
Tôi có nhiều điểm trong 3 không gian được gán cho một số lượng rất nhỏ các nhóm (mỗi điểm thuộc về một nhóm), cụ thể là 15 trong trường hợp này (không bao giờ thay đổi). Bây giờ tôi muốn tính toán ma trận trung bình và hiệp phương sai của tất cả các nhóm. Vì vậy, trên CPU nó gần giống như:
for each point p
{
mean[p.group] += p.pos;
covariance[p.group] += p.pos * p.pos;
++count[p.group];
}
for each group g
{
mean[g] /= count[g];
covariance[g] = covariance[g]/count[g] - mean[g]*mean[g];
}
Kể từ khi số lượng các nhóm là vô cùng nhỏ, bước cuối cùng có thể được thực hiện trên CPU (Tôi cần những giá trị trên CPU, anyway). Bước đầu tiên thực sự chỉ là một phân đoạn giảm, nhưng với các phân đoạn nằm rải rác xung quanh.
Vì vậy, ý tưởng đầu tiên tôi đưa ra, là lần đầu tiên sắp xếp các điểm theo nhóm của họ. Tôi nghĩ về một loại xô đơn giản bằng cách sử dụng atomic_inc để tính toán kích thước thùng và chỉ mục di chuyển mỗi điểm (có ý tưởng tốt hơn để sắp xếp ?, nguyên tử có thể không phải là ý tưởng tốt nhất). Sau đó chúng được sắp xếp theo nhóm và tôi có thể có thể đưa ra một sự thích nghi của các thuật toán quét phân đoạn được trình bày here.
Nhưng trong trường hợp đặc biệt này, tôi nhận được một lượng dữ liệu rất lớn trên mỗi điểm (9-10 nổi, thậm chí có thể tăng gấp đôi nếu cần), vì vậy thuật toán chuẩn sử dụng phần tử bộ nhớ chia sẻ cho mỗi luồng và chuỗi điểm có thể gây ra các vấn đề liên quan đến tài nguyên đa bộ xử lý như bộ nhớ chia sẻ hoặc thanh ghi (Ok, nhiều hơn nữa về khả năng tính toán 1.x so với 2.x, nhưng vẫn còn).
Do số lượng nhóm rất nhỏ và không đổi, tôi nghĩ có thể có cách tiếp cận tốt hơn. Có lẽ đã có những ý tưởng hiện có phù hợp cho những đặc tính cụ thể của một vấn đề tiêu chuẩn như vậy. Hoặc có lẽ cách tiếp cận chung của tôi không tệ và bạn có ý tưởng để cải thiện từng bước, như thuật toán phân loại phù hợp với số lượng khóa hoặc một số thuật toán giảm phân đoạn giảm thiểu việc sử dụng bộ nhớ/đăng ký dùng chung.
Tôi đang tìm cách tiếp cận chung và không muốn sử dụng thư viện bên ngoài. FWIW Tôi đang sử dụng OpenCL, nhưng nó không thực sự quan trọng vì khái niệm chung về tính toán GPU không thực sự khác biệt so với các khung chính.
Đây là một mẫu khá phổ biến. Sử dụng Thrust, trước tiên bạn phải 'sort_by_key' để đưa dữ liệu vào từng phân đoạn cùng nhau, và sau đó là' reduce_by_key' để tính trung bình & hiệp phương sai của mỗi nhóm. –