내 최종 프로젝트

OCLBHGS: OpenCL 바인스 오두막 성계 시뮬레이터(그 이야기)
내가 4학년 때, 나는 구체적인 지도 원칙을 따라야 하는 항목이 있었다.나는 내가 이 문제를 해결하는 더 좋은 방법이 있다고 확신한다. 이런 방법은 결과를 크게 개선하고 예상을 초과할 것이다. 그러나 일부 규칙이 깨지기 때문에 평가 과정에서 나는 약간의 비용을 들일 것이다.
그것은 나에게 더욱 자신 있게 자신의 용기를 믿는 것을 가르쳐 주었다.

데모 링크

C+OpenCL이므로 코드를 쉽게 실행할 수 있는 링크가 없습니다.모든 코드는 검사할 수 있습니다.나는 이 GIF를 작품 미리보기로 추가했다.하지만 나는 그 뒤에 있는 이야기가 더 재미있다고 생각한다!

코드에 연결

모템 / oclbhgs

🛰💫 OpenCL Barnes Hut Galaxy 시뮬레이터 | GPU를 활용하여 n체 시뮬레이터에서 대규모 데이터 병렬 계산

COMP426 작업 4

10K 차체 시뮬레이션 예, GTX 1060에서 60FPS 매끄러움

(GIF가 올바르게 로드되어 시뮬레이션을 볼 때까지 기다립니다)git checkout v1.0 시뮬레이션 보기
git checkout v1.1 시뮬레이션 보기
git checkout v1.2 시뮬레이션 보기

달리기

gcc, cmake, OpenCL, OpenGL, GLUT이 있어야 운행할 수 있습니다.

mkdir build
cd build
cmake
make
./oclbhgs

OpenCL Barnes Hut 은하 시뮬레이터

이름.
성씨
학생 ID
유리안
로타르
40102558

소개

마지막으로 할당된 목표는 OpenCL을 사용하여 n체 시뮬레이션을 계산하는 것입니다.OpenCL의 특수성은 CPU 또는 GPU 장치의 코어를 작성할 수 있다는 점입니다.
이 프로젝트를 완성하기 위해서 저는 C99에서 처음부터 시뮬레이션을 시작했습니다. 보고서에서 원인을 설명할 것입니다.

데이터 이동과 동기화를 최소화하기 위해 CPU와 GPU 간의 작업은 어떻게 분배됩니까?

그래서...
View on GitHub

나는 어떻게 그것을 구축했습니까? (창고가 무엇입니까? 제가 문제를 만났거나 새로운 것을 발견했습니까?)

이 프로젝트는 순수 C95 및 OpenCL에서 구축되었습니다.C95를 선택해야 하는 이유OpenCL 커널(CPU나 GPU 등 장치에서 병행 작업을 수행하기 위해 실행되는 코드)은 C95이기 때문에 호스트 코드(모든 코드를 준비하는 코드)와 장치(CPU/GPU)에서 실행되는 코드를 같은 언어(무질서 열거, 클래스 없음, 변환 없음)로 사용하기 쉽다.나는 많은 문제에 부딪혔지만, 마지막 절에서 모든 것을 설명했다.

다른 생각/느낌/이야기

바로 제가 파리 에피테크에서 3년째, 학사 주기가 끝났을 때, 저는 캐나다로 파견되어 콘코디아 대학에서 1년 동안 밀집된 소프트웨어 공학과 컴퓨터 과학 과정을 공부했습니다.1년 동안 정말 자랑스러운 프로젝트가 하나 있었다.이 과목은 다중 핵 프로그래밍으로 우리 컴퓨터에서 사용할 수 있는 모든 장치를 사용하여 병행 작업을 수행하는 데 관한 것이다.이 시간에 우리는 네 가지 항목이 있는데 항상 같은 문제지만 다른 도구를 사용한다.우리는 가능한 한 많은 물체를 운행할 수 있도록 n체 시뮬레이터를 만들고 Barnes-Hut 알고리즘을 실현해야 한다.

N체 시뮬레이션

n체 시뮬레이션의 주요 문제는 계산의 복잡도가 지수급으로 발전하는 것이다.물체는 특정한 방식으로 상호작용한다. 우리의 예에서 중력은 반드시 시뮬레이션에 응용해야 한다.이것은 이 문제의 가장 기본적인 방법은 모든 물체를 취하여 시뮬레이션 중의 다른 물체의 중력 영향에 따라 그 속도와 방향을 계산하는 것이다.네, 이것은 지금까지 최악의 방법입니다. 이것이 바로 왜 서로 다른 형식의 병행을 통해 n체 시뮬레이션을 구할 수 있는지입니다.("해결됨"이란 수량 기구에 적용되는 완벽한 해결 방안이 없는 향상된 문제를 말합니다.)

병렬 유형

우리의 교실에서 우리는 두 가지 주요 병행 유형인 임무 병행과 데이터 병행을 배웠다.작업 병행성은 서로 다른 유형의 작업과 작업을 병행하여 실행하는 것을 가리킨다.데이터 병행성은 서로 다른 데이터에서 완전히 같은 작업을 실행하는 것을 가리킨다.성능 향상을 시도할 때 데이터의 병행성은 지금까지 가장 좋은 방법이다.오늘날의 하드웨어(GPU👀) 구축은 간단한 작업을 수행하는 데 사용되지만 가장 큰 데이터 집합을 사용할 수 있습니다.그것은 이미지 처리 같은 일에 있어서는 절대적으로 좋지만, 해결 방안이 데이터 병행 방식으로 실행될 수만 있다면, 그것은 어떤 유형의 문제에도 응용될 수 있다.

Barnes-Hut 알고리즘

Barnes-Hut 알고리즘은 n체 시뮬레이션에 사용되는 해결 방안 중의 하나입니다.작동 방식은 다음과 같습니다.

은 네 갈래 트리(노드당 네 개의 하위 노드가 있는 트리)를 만들고 이 트리는 시뮬레이션을 실행할 공간을 표시합니다.첫 번째 노드는 시뮬레이션의 전체 너비/높이입니다.4 자 노드는 부모 노드의 4/4입니다.

이 트리에 실체를 놓아서 실체가 한 노드에서 단독으로 끝날 수 있도록 합니다. (한 노드에 여러 개의 실체가 존재한다면, 우리는 이 노드를 4개로 나누고, 하위 노드에서 실체를 스케줄링합니다. 우리는 실체가 단독으로 끝날 때까지 계속 이렇게 합니다.)

한도값

을 정의했습니다.
현재, 우리가 물체 간의 중력 당김을 계산하려고 할 때, 우리는 나무의 한 노드를 사용하여 계산하고, 자물체에 포함된 모든 물체를 하나의 단독 물체(모든 물체의 질심)로 간주하여 분해할 수 있다.이것은 실행 공식(저장소에서 찾을 수 있음)을 통해 임계값보다 낮은지 확인한 것입니다. 임계값보다 낮으면 노드를 분해합니다. 그렇지 않으면 트리에서 계속 발굴합니다.

마지막 도전: OpenCL

우리의 이전 프로젝트는 이 알고리즘을 OpenCL에 이식하여 CPU와 GPU에서 실행하는 것이다.평가는 CPU와 GPU 코어 (디바이스에서 실행되는 코드) 를 모두 보유하고 있다는 점수를 주었습니다.
이것이 바로 내가 이 해결 방안을 의심하기 시작한 곳이다.만약 내가 GPU로만 모든 계산을 할 수 있고 알고리즘의 모든 단계에서 대량의 데이터 병행 작업을 실행할 수 있다면 어떻게 될까요?그렇다면 CPU가 왜 필요합니까?GPU에 대해 알아야 할 것은 CPU처럼 RAM 메모리에 접근할 수 없다는 것이다. 그렇다. CPU 상하문(RAM)에서 GPU 상하문(장치의 각종 메모리 영역 중 하나)으로 복사해야 한다. 알고리즘을 재구성하면 엄청난 비용으로 완전히 삭제할 수 있다.
나는 마침내 유일한 문제는 나무에서 나온다는 것을 알게 되었다.트리는 동적 데이터 구조의 일종이다.이것은 그 일을 하기 위해 많은 분배/분배를 취소해야 한다는 것을 의미한다.나는 어떻게 이 알고리즘을 계속 사용할 수 있는지 알고 싶다. 그러나 정적 데이터 구조로 나의 몸을 수용할 수 있니?
신체의 수가 증가함에 따라 모든 사람들은 같은 문제에 직면하기 시작했다. 두 몸이 매우 가까울 때 그들은 나무에서'발굴'이 매우 깊어서 알고리즘이 매우 느리다.이것은 우리 나무에 최대 깊이를 설정함으로써 방지할 수 있다.이것은 대다수 학생들이 채택하는 해결 방안으로 나로 하여금 동적 데이터 구조가 필요한지 직접 의심하게 한다.네 갈래 나무는 알고리즘에 있어서는 매우 흥미롭지만, GPU 분배에 있어서는 매우 나쁘다.
해결 방안은 간단합니다 = > 네 갈래 트리를 정적 2D 패턴에 저장합니다.우리는 이 나무의 최대 크기를 알고 있다. (왜냐하면 우리는 현재 최대 깊이가 있기 때문이다.) 그래서 우리는 노드의 총수를 계산하고 모든 내용을 미리 분배하며, 어떤 노드가 활동 상태에 있는지 판별할 수 있다.

     /--------|-------|
|0| |1|2|3|4| |5|6|7|8|9|10|11|12|13|...
 \__|_______|

그리고 노드의 위치부터 그 공간 위치와 나무의 깊이를 계산하는 것은 간단해진다.이 점에서 모든 것이 바뀌었다. 나는 이 문제를 새로운 방식으로 대하기 시작했다. => 나는 어떻게 GPU에서 모든 것을 동적 분배나 CPU 코어에 의존하지 않고 실행합니까?
이것이 바로 내가 마침내 얻은 성과다.대부분의 경우 RAM에 트리를 할당하고 데이터 병렬 작업을 수행할 때 상태를 GPU로 복사하지만, 실제로 프로그램을 시작할 때 GPU에 트리를 직접 할당했습니다.나는 단지 표시 목적으로 GPU에서 그것을 복사했을 뿐이다.이 알고리즘의 모든 절차는 데이터가 병행되는 방식으로 작동하도록 수정되었다. (완전한 트리를 즉시 처리하는 것은 보잘것없어졌다!)그것은 GPU에 매우 적합하다.성능 향상에 미친 짓:
이 기계의 라인을 사용하여 나는 매끄러운 700체 시뮬레이션을 실현했다.
TBB를 통해 나는 매끄러운 700체 시뮬레이션도 실현했다.
CUDA, 작업 병렬, 데이터 병렬을 사용하여 GTX 1060에서 매끄러운 1.5k 시뮬레이션을 실현했습니다.
OpenCL을 사용합니다. 이 "새로운"알고리즘과 유일한 데이터 병행성을 사용하여 저는 GTX 1060에서 매끄러운 10k 시뮬레이션을 실현했습니다.
여기서 제가 만든 시뮬레이션을 보실 수 있습니다. (GIF가 정확하게 불러오기를 기다리세요!)10.000 bodies gravitating around 1 insanely heavy body10.000 bodies with random masses and initial positions2 galaxies with 5.000 bodies
마지막으로 나는 모든 점수를 얻지 못했다. 왜냐하면 나는 CPU 코어가 없기 때문이다(😢), 그런데 누가 신경 써, 내가 처리할 수 있는 시체는 반의 다른 사람들보다 훨씬 많아.👍.
당신이 이 작은 이야기를 좋아하길 바랍니다:)