Thuật toán/giải pháp nbody nhanh (với opengl/C++/??)

Question

Tôi đang làm việc trên một dự án (C++, opengl), nơi tôi cần phải có rất nhiều hạt ảnh hưởng đến nhau, nếu tôi đúng, điều này được gọi là vấn đề. Có ai biết giải pháp nào có cho các thuật toán như thế này không.

Tôi biết thuật toán túp lều barnes và có thể tôi có thể nhìn xung quanh openCL, mặc dù tôi không chỉ tự hỏi nếu bạn có thể sử dụng các giải pháp khác.

Mã mà tôi sẽ tạo ra sẽ có rất nhiều:

for(int i = 0; i < num_particles; ++i) { 
    for(int j = i+1, j < num_particles; ++j) 
    dist = distance(particles[i],particles[j]); 
    if(dist > limit) {....} 
    } 
} 

Kind regards, Pollux

Answer 1

Kd-trees lý tưởng để tìm tất cả các đối tượng (hạt trong trường hợp này) ở khoảng cách tối đa. Nếu cây là cân bằng nhìn lên là O(log n).

Answer 2

Đây là nơi mà các cấu trúc dữ liệu như Octrees có ích. Họ có thể giảm các vòng O(N^2) của bạn xuống O(N*log(N)), với chi phí mất một chút chính xác.

Answer 3

Nếu bạn muốn có sức mạnh tính toán HUGE trên nhiều cơ quan khá đơn giản - hãy quan tâm đến nvidia CUDA và thực hiện công việc của bạn trên các đơn vị shader GPU. Điều này có thể cung cấp cho bạn hiệu suất cao hơn ngay cả khi so sánh với CPU quad-core với đa luồng

Answer 4

Có bạn đi: GPU Gems 3. Đó là trong CUDA, nhưng dễ dàng di chuyển để mởCL.

Tuy nhiên, phiên bản này tính các tương tác N²/2 mà bạn có thể không muốn.

Answer 5

Phân chia diện tích 1024x512 pixel theo hộp pixel 4x4, phân bổ 15 ô cho các hạt trong mỗi hộp, có hạt 12k chỉ có lực loại trừ để tính toán, không quá 8ms cho Intel HD-400 (có 12 đơn vị tính toán, qua apencl api) cho:

for(each particle) // this part unfolded on N workitems of opencl 
for(each neighboring box) {  
    for(each particle in selected box) 
    { 
     dist = distance(particles[i],particles[j]); 
     if(dist < limit) {/* sqrt, mult, div, add, sub */} 
     } 
} 

để phân vùng không gian và sử dụng opencl chắc chắn tăng tốc độ. Nếu không có phân vùng, brute-force mất 44ms mà không phải là xấu cho một gpu tích hợp cấp thấp với bộ nhớ kênh đơn chậm.

Đồng thời sử dụng CPU thứ hai đồng thời, giúp khoảng 0,5ms - 0,1ms nhưng do bộ nhớ bị tắc trong nền.