빠른 nbody 알고리즘/솔루션 (opengl/C++/??)

나는 이것이 서로에게 영향을 미치는 많은 입자를 필요로하는 (C++, OpenGL) 프로젝트에서 일하고 있습니다. 문제가 생겼어. 누군가 이런 알고리즘을위한 해결책이 무엇인지 알고 있습니까?빠른 nbody 알고리즘/솔루션 (opengl/C++/??)

나는 barnes hut 알고리즘을 알고 있고 어쩌면 다른 솔루션을 사용하고 있는지 궁금하지 않을지라도 openCL을 들여다 볼 수 있습니다. 나는 많은 것 만들 것이다

코드 : Octrees 같은 데이터 구조가 유용하게 사용할 경우

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) {....} 
    } 
}

종류 안부, 폴룩스

출처

2010-07-28 pollux

Kd-trees은 최대 거리에서 모든 개체 (이 경우 입자)를 찾는 데 이상적입니다. 나무가 균형을 잡으면 룩업은 O(log n)입니다.

출처

2010-07-28 20:02:25 Staffan

Thanks Staffan! 이런 자료 구조에 대한 좋은 책을 아십니까? – pollux

Mark의 [Computational Geometry] (http://www.amazon.com/Computational-Geometry-Applications-Mark-Berg/dp/3642096816/ref=sr_1_1?ie=UTF8&s=books&qid=1280350460&sr=8-1)를 확인하십시오. de Berg et al. Kd- 트리, 쿼드 트리 및 델루 네이 삼각 측량과 같은 컴퓨터 기하학에 대한 훌륭한 소개입니다. 아마존에서 TOC를 탐색 할 수 있습니다. – Staffan

이입니다. 그들은 O(N^2) 루프를 O(N*log(N))으로 줄일 수 있습니다. 약간의 정확성을 잃어 버리는 대신에.

출처

2010-07-28 19:58:59

아주 간단한 몸체에서 엄청난 계산 능력을 얻으려면 nvidia CUDA에 관심을 갖고 GPU 쉐이더 유닛에서 작업하십시오. 이렇게하면 멀티 스레딩으로 쿼드 코어 CPU와 비교해도 더 많은 성능을 얻을 수 있습니다.

출처

2010-07-28 20:01:19

여기까지 : GPU Gems 3. CUDA이지만 openCL에 쉽게 이식 가능합니다.

그러나이 버전은 원하지 않는 N²/2 상호 작용을 계산합니다.

출처

2010-07-29 07:54:40 Calvin1602

4x4 픽셀 박스로 1024x512 픽셀 영역을 나눠서 각 상자에 입자에 15 개의 셀을 할당하고 계산을위한 배타적 힘이있는 12k 개의 입자가있는 경우 Intel HD-400 (12 개의 연산 장치, opencl API를 통해) :

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 */} 
     } 
}

그래서 공간 분할과 opencl을 사용하면 분명히 속도가 향상됩니다. 파티셔닝을하지 않으면 brute-force는 44ms가 걸리며 단일 채널 슬로우 메모리가있는 로우 엔드 통합 gpu의 경우 나쁘지 않습니다.

또한 두 번째 CPU를 동시에 사용하면 백그라운드에서 병목 현상이 발생하기 때문에 약 0.5ms - 0.1ms가 소요됩니다.

출처

2017-03-19 18:34:19

빠른 nbody 알고리즘/솔루션 (opengl/C++/??)

답변

관련 문제