본 논문은 2010 European Wireless Conference에서 공개되었다. 현재 진행하고 있는 과제와 관련되어 읽고 정리하였다.
Introduction
모바일 기기(핸드폰, 태블릿 등)의 개수가 증가하면서 더 정확한 wireless simulation환경이 필요하다. 기존에는 Maxwell’s equation을 사용한 statistical model기법을 사용하였다. Statistical modeling의 경우 장해물이 없는 환경에서는 정확한 modeling이 가능하나 건물이나 장애물이 많이 존재하는 환경에서는 정확한 modeling이 불가능하다. 이런 문제를 해결하기 위해 해당 논문에서 GPU를 사용한 Ray Tracing 기술을 제안하였다. Ray Tracing기술은 transmitting source에서 Ray를 생성하고 각 ray의 linear path를 trace하는 방법이다. Ray tracing의 경우 각 Ray의 반사(reflection) 또는 굴절(refraction)을 고려할 수 있다. (2010년 논문이라 다소 오래된 논문이다. 지금은 다양한 GPU 가속화 기법이 존재한다)
Propagating Model
본 논문에서는 Ray Tracing 알고리즘에서 고려해야 하는 부분을 크게 6개로 나누어 정리하였다.
- Primary Rays
그림 1: Transmitter에서 Ray가 생성되는 예제
Ray Tracing 알고리즘에서는 transmitter에서 모든 방향으로 X 각도 만큼의 간격으로 ray를 생성한다. 각 Ray는 가장 가까운 object에서 반사되거나, receiver에 도달하게 된다. 그림 1은 transmitter에서 ray가 생성되는 예를 보여준다.
- Specularly Reflected and Transmitted Rays
그림 2: Ray가 Intersection되는 경우와 Trasmit되는 경우
Transmitter에서 생성된 Ray는 크게 3가지 나뉘게 된다.
- 특정 object 또는 reception과 만나지 않고 ray가 한 방향으로 계속 진행한다.
- 특정 object에서 intersection 되어 reflection된다.
- 특정 object를 만나 transmit (투과)하는 경우이다.
그림 2는 Ray가 특정 object에서 intersection되는 경우와 transmit 되는 경우를 보여준다.
각 방향으로 진행하는 Ray는 power값을 가지고 있으며 해당 power가 특정 값 이하로 내려가면 소멸된 것으로 간주한다. 또한, max_recurse (반사?)를 넘을 경우도 소멸될 수 있다. Ray가 reflection하거나 transmit 할 경우 power가 감소한다. 그리고 reflection 된 ray 파워와 transmit된 ray의 power합은 항상 처음 object에 도달한 ray의 파워보다 작거나 같아야 한다. 거리에 따른 파워 손실은 아래의 Friis free-space formula에 의해 결정된다.
λ: the wavelength of the ray
d: the total distance the path of rays have traveled from transmitter to receiver
Pt: Transmitted signal power
Pr: Received signal power
Gt: Transmitter antenna gain
Gr: Receiver antenna gain
Ray의 intersection 또는 trasmit로 인한 파워 손실은 실제 intersection되는 object의 성질에 따라 달라진다. 하지만 본 논문에서는 계산의 효율성을 위해 object의 성질을 고려하지 않고 동일한 파워의 양이 줄어드는 것으로 가정하였다.
- Ray Reception
Ray가 reception circle (receiver)을 지나가는 경우 receiver에 도달하였다고 가정한다. Receiver에 도달한 ray는 총 이동한 거리와 총 손실된 power의 값을 가지게 된다. 이를 기준으로 received power가 계산된다. 또한, 여러 개의 ray가 하나의 receiver에 도달할 수 있다. 이 경우 비슷한 travel pattern을 가진 ray를 제거하는 방법이 필요하다. 논문에 짧게 설명이 되어 있지만, 정확하게 설명의 의도를 파악하지 못하여서 작성하지 못하였다. (다음에 이해를 하게되면 수정이 필요하다)
- Calculation of Received Power
Reflection, Transmission, Travel distance의 이유로 Ray의 power가 약해지는 원인이다. 논문에서는 아래의 식을 기준으로 transmitted power와 received power를 계산한다.
Ri: The reflection coefficient at the i-th reflection
Tj: The transmission coefficient at the j-th transmission
여러 개의 signal의 파워 계산은 단순히 모든 ray의 파워는 아래의 식과 같이 단순히 summation을 한다. 
Ray tracing에서 파워 계산은 intensity를 사용하여 연산을 수행한다. 파워 계산에 amplitude (electric field strength)에 대한 고려는 하지 않는다. 여러 가지 필드를 무시하는 이유는 현재 제공되는 상세한 정보가 정확하지 않기 때문이다.
- Diffracted Rays
Diffracted Ray를 고려하지 않을 경우 각 Ray 당 최대 2개의 Ray만 더 생성하면 된다 (Reflection Ray & Transmitted Ray). Diffracted Ray를 생성할 경우 새로 생성된 Ray의 정보를 저장할 공간이 필요하지만, 해당 저장 공간의 크기가 너무 크기 때문에 본 연구에서는 Diffracted Ray를 무시하였다. 하지만, Diffracted Ray의 경우 power가 상당히 작으므로 무시할 수 있다고한다.
- Supersampling
Ray가 source로부터 멀어질수록 Ray 간의 간격이 멀어지는 현상이 발생한다. 이 경우 작은 object의 경우 모든 ray가 intersection 되지 않고 지나는 문제가 발생할 수 있다. 이런 경우를 제거하기 위해 본 논문에서는 supersampling 기법을 사용하였다.
그림 3: Supersampling 기법위 그림은 supersampling 기법의 설명하는 그림이다. supersampling이란 특정 Ray 사이의 간격을 더 세분이 나누어 Ray를 생성하는 방법이다. 그림과 같이 Ray를 더 많이 만들면 각 ray의 파워는 새로 생성된 Ray의 수만큼 작아진다. 물론 더 많은 ray를 생성하기 때문에 성능은 느려지는 현상이 발생한다.
Ray Tracing Algorithm
Propagating Model에서 설명한 바와 같이 모든 Ray를 모든 object와 intersection 여부를 테스트할 경우 많은 연산이 필요하다. 또한, intersection 된 Ray의 경우 2개의 Ray가 생성되기 때문에 연산량이 지속해서 증가한다. 이러한 문제를 해결하기 위해 space division을 사용하여 Ray와 object의 intersection 판단을 위한 연산량을 줄이는 방법이 존재한다.
- Uniform Grid 방법
Uniform Grid의 경우 전체 지도를 같은 space 크기로 나누어 연산하는 방법이다. 각 Ray를 가장 가까운 space의 object와 먼저 intersection 여부를 테스트한다. 이런 식으로 연산을 수행하면 모든 object와 연산을 하지 않고 가까운 object를 좀 더 빠른 시간에 찾을 수 있다. 하지만 uniform 하게 space를 나눌 경우 특정 space에 많은 object가 존재하는 경우가 발생하고 해당 space에서의 연산 시간이 길어지게 된다. 또한, space에 많은 object가 있으면 당연히 intersection 되어 생성되는 Transmitted Ray와 Intersection Ray 또한 같은 space 공간의 object와 다시 intersection 될 확률이 증가하여 연산량이 많은 space의 object와 계속 연산을 수행하게 되는 문제가 발생한다.
- Bound Volume Hierarchy (BVH) or KD-Tree 방법
BVH의 경우 space를 object의 개수로 나누어 각 space에서의 Ray 연산량을 비슷하게 유지하는 방법이다. KD-Tree는 크게 Construction과 Traversal로 구성되어 있다.
KD-Tree Construction
Tree의 root은 해당 지도 전체를 의미한다. 각 child node는 root node를 split 하여 생성하게 된다. Tree construction의 결과가 추후 tree traversal의 성능에 영향을 준다. 본 논문에서는 Surface Area Heuristic (SAH) 방법을 사용하여 node 간의 balance를 유지한다. KD-Tree의 가장 큰 단점은 Tree Construction에 상당히 많은 시간이 걸린다. 하지만 처음 한 번만 실행하면 되는 부분이라 무시 가능하다.
KD-tree Traversal
Traversal에 크게 아래와 같은 3가지 방법이 있다.
- Stack technique
Stack에 Ray가 지나는 모든 child node를 저장하고 node는 거리순으로 정렬되어 있다. 가장 가까운 space (leaf node)의 object와 intersection 여부를 판단하고 만약 intersection이 발생하지 않으면 stack에서 pop을 하여 다음 node를 검색하는 방법이다. 이 방법은 GPU의 제한된 shared memory 용량으로 인해 바로 사용하기에 무리가 있다. Shared memory를 사용하지 않고 global memory를 사용할 경우 leaf node access에 오랜 시간이 발생할 수 있다.
- KD-Restart
Stack을 사용하지 않고 매번 traversal을 재시작하는 방법이다. Ray가 가장 가까운 space에 intersection 하는 object가 존재하지 않는 경우 space의 exit point를 기준으로 다시 Tree는 search 하여 진행하는 방법이다. 매번 KD-Tree를 재탐색하기 때문에 traversal에 상당한 시간이 걸린다.
- Short stack Technique
이 방법은 Stack-Based Technique와 KD-Restart를 같이 사용하는 방법이다. Constant 한 stack을 사용하여 Stack-Based Technique을 사용한다. 만약 stack에 저장된 모든 leaf node에서 intersection 하는 object가 없으면 KD-restart를 사용하여 다시 traversal을 진행한다.
Evaluation
성능 측정을 위해 Sierpinski carpet algorithm을 사용하여 map을 생성하였다. 생성된 map의 경우 real과는 거리가 있지만, stress test를 하기에는 적합하다.
그림 4: 성능 결과
위 그림은 millions of rays computed per second (Mrays/S)로 성능을 측정한 결과이다. GPU 개수가 늘어나면 같이 성능이 향상하는 것을 확인할 수 있다. 또한, CPU + GPU를 동시에 사용하면 더 높은 성능을 확인할 수 있다.
출처
- Acceleration of Wireless Channel Simulation Using GPUs (http://ieeexplore.ieee.org/document/5483525/)