입자 수치 계산 및 OpenMP+Tree 테스트 계산 및 성능 평가

※ 이 기사는 반쯤 썼습니다.
개시하다
입자법은 천문학 등에서 광범위하게 사용되는 수치 계산 방법 중의 하나이다
세계의 동량 보존 규칙 등은 모두 입자 간의 상호작용으로 전환된다.
입자법은 너무 정직하게 계산하면 자기 주위의 모든 입자와의 상호작용을 계산하는 것이다
입자 수가 $N이면 $N^2달러의 계산 비용이 듭니다.
따라서 통상적으로 Tree법이라고 불리는 방법(Barnes & Hut, 1986)과 병행계산(e.g., OpenMP, MPI) 등을 조합하여 고속계산을 한다.
그럼에도 불구하고 병렬 트리법으로 성능을 발휘하려면 상당히 어려운 인코딩을 해야 한다.
따라서 이 문제를 해결하기 위해 개발한 소프트웨어는 이 같은 일을 자동으로 수행할 수 있는 소프트웨어인 Framework for Developing Partical Simulator로 약칭 FDPShttp://www.jmlab.jp/?p=503&lang=ja라고 한다.
아니면 나도 개발을 돕기 위해 노력했거나.
그럼, 슬프죠. 그러면 코어 수 CPU를 얼마나 많이 사면 빨라지겠죠.
즉
(1) 트리 방법은 입자 수가 적은 곳에서 일반적인 계산보다 느리다.
(2) OpenMP는 핵심 수를 투입해도 쉽게 빨라질 수 없다.
이런 일이 있어서.
이번에는 실제로 저것을 보자.
계산의 방정식
이번 결정은 간단하게 중력을 풀기로 했다.
즉

\frac{\mathrm{d}^2 \vec{r}_i}{\mathrm{d} t^2} = - \sum_j \frac{m_j}{|\vec{r}_{ij}|^2} \hat{{r}}_{ij}

.
이것은 분명히 $N^2달러의 계산량이 필요한 계산이다.
Tree Practice $N\log 사용8 달러 (N) 의 계산 원가가 되다.
측량하다
다음은 FDPS 사용 방법에 대한 특별한 설명이 없습니다.
한 마디로 하면 $[0,1]^3달러의 계산box에 $N달러의 입자를 무작위로 퍼뜨려 상호작용 계산에 걸린 계산 시간을 한 번 봅시다.
측정은 2달러부터 시작해서 2배씩 증가한다.
병렬 계산에 사용되는 핵수도 $1부터 순서대로 2배로 증가한다.
측정용 Intel(R) Xeon(R) CPU E5-2670v3 @ 2.30GHz는 12개의 코어 24 스레드입니다.
C 함수gettimeofday를 사용하여 시간을 측정합니다.
또 편차를 억제하기 위해 여러 차례 이상 측정해 13차례 정도 진행했다.
코드
생략... 며칠 뒤에 github한테 줄 수도 있어요.
결실
우선 가로축의 입자수와 세로축의 시간을 계산한다.

파란색 점은 Tree법의 측정점, 빨간색은 $N^2달러로 계산된 측정전, 녹색 곡선은 $Nlog8달러.
사용 핵수는 1핵에 불과하다.
이를 통해 알 수 있듯이 입자 수가 적은 곳($N<2048달러)에서 직접 계산하는 것이 더 빠르다.
트리 구조의 생성에는 워낙 시간이 걸리기 때문에 입자 수가 적은 부분은 트리를 만들지 않고 솔직히 $N^2달러를 만드는 것이 더 빠르기 때문이다.
이어 가로축은 핵심수, 세로축은 시간을 계산해 얻은 물체를 나타냈다.
입자 수는 65536이다.

지금부터 12개 라인까지의 계산 시간은 순조롭게 줄어들지만 앞으로는 좀 고민이 될 것이다.
(이게 뭐였지? 현금동기화?)
HT 때문인지 물리 연산 장치가 늘어나지 않아 여기서 먼저 꺾어보자.
또 24라인을 모두 사용하면 계산 시간이 상승할 때도 있다.
이것은 OS jitter 같은 것으로 여겨지기 때문에 안전을 확보하려면 24개의 라인을 모두 사용하는 것이 아니다
23, 22 근처에 두면 방지할 수 있어요.
또는 12개의 라인의 계산은 2개이다.
결론
따라서 Tree vs.Direct의 계산 시간을 비교해 보고 핵심 수 의존성을 살펴본다.
"빨라진다"는 말이 아니라 자신이 하고 싶은 계산에 가장 효율적인 configuration을 선택하세요.