Ray tracing is a technique for rendering a 2D image from 3D objects by tracing the paths of light through pixels in the 2D image screen and simulating the effects of encounters with the 3D objects. Ray trac-ing takes various paths of light, the sources of global illumination, into accounts when it calculates the color of a pixel so that it is usually capable of producing a very high degree of visual realism than that of typical rasterization methods. To achieve the high realism, it needs massive computing power, especially floating-point (FP) calculations. A single-instruction, multiple-thread (SIMT) based ray tracing processor provides massive computing power, but it suffers from two problems, branch divergence and shared memory conten-tion.
In this dissertation we present a mobile ray tracing processor (MRTP) that is based on multiple cores of reconfigurable SIMT processor to mitigate the performance degradation due to both branch divergence and shared memory contention. We present the analysis results of ray tracing, and propose two types of reconfigurable SIMT architectures (R-SIMT I and R-SIMT II) to improve the SIMT processor’s utilization that is prone to significantly decrease due to branch divergence. R-SIMT I is configured as scalar SIMT to execute a regular kernel without branch instructions, and is reconfigured as vector SIMT to execute an irregu-lar kernel with branch instructions. R-SIMT II is configured as one wide SIMT to execute a regular kernel, and is reconfigured as multiple-instruction, multiple data (MIMD) architecture. Shared memory contention is alleviated by both an access managing unit and a new time-division multiplexing with multi-phase clocks to hide arbitration delays. The performance improvements of proposed reconfigurable SIMT architectures are evaluated using simulation results collected from both a ray tracing program and a cycle-accurate GPU simulator. The utilization of R-SIMT I is improved by 19.9% compared to a conventional SIMT processor using the same number of computing units as R-SIMT I, and R-SIMT II improves the utilization even more than R-SIMT I, 20.5% compared to that of R-SIMT I. Then, two processors (MRTP-I and MRTP-II) adopting two proposed R-SIMT architectures are fabricated in low power CMOS process technologies, 130nm process for MRTP-I and 90nm process for MRTP-II, with 4mm x 4mm die size. The functionalities of the processors are verified on FPGA test board using Logic Analyzer, and their power consumptions are measured at 100MHz with 1.2V, 156mW for MRTP-I and 221mW for MRTP-II. To the best of my knowledge, this is the first silicon implementation of mobile ray tracing processor.
최근의 프로세서는 다수의 코어를 하나의 칩에 집적하는 멀티코어 구조가 일반적이다. 이미 데스크 탑 CPU는 4개 이상의 코어를 집적하고 있고, 최신의 스마트 폰과 테블렛 PC 에서도 디스플레이의 높은 해상도를 지원하기 위해 멀티코어 프로세서가 사용되고 있다.
싱글 코어와는 달리, 멀티코어 시스템에서는 다수의 코어를 효과적으로 사용하지 못하면 높은 연산능력을 충분히 활용하지 못하는 상황이 빈번히 발생하기 때문에, 멀티코어 프로세서를 효과적으로 사용하기 위해서 다양한 분야에서 연구가 진행되고 있다. 그 중에서 가장 대표적인 것이 3차원 그래픽스 분야이다. 3차원 그래픽스는 기본적으로 많은 연산량이 필요할 뿐 아니라, 연산들간의 의존성이 없어 다수의 코어에서 병렬적으로 작업을 수행할 수 있기 때문이다. 3차원 그래픽스 중에서도 최근에는 기존의 rasterization 방식이 제공할 수 없는 높은 수준의 현실감을 제공하기 위해서 ray tracing 이라는 렌더링 알고리즘이 각광받고 있다. Ray tracing 은 가상의 카메라 픽셀에 도달하는 빛의 경로를 역추적하여 해당 픽셀의 색깔을 계산하기 때문에, 실제로 빛이 3차원 공간상에 존재하는 물체들과 상호작용하여 발생하는 global illumination 현상을 정확하고, 자연스럽게 구현해 낼 수 있다. 하지만, 다양한 빛의 경로를 추적할 때 요구되는 많은 연산량을 제공할 수 없어, 실시간으로는 구현 하지 못하고 있다가, 최근 10년간 멀티코어의 등장으로 다시 각광받고 있다.
Ray tracing 을 구현하기 위해서는 ray tracing 에 내재되어 있는 연산의 병렬성을 최대한 활용해야 한다. 이를 위해 사용되는 하드웨어 구조가 Single-Instruction, Multiple-Thread (SIMT) 구조이다. 즉, 하나의 instruction 을 fetch 하여 다수의 Processing Element (PE) 에 공급하여 동일한 연산을 다수의 스레드 (Thread) 로 병렬적으로 처리할 수 있도록 하는 것이다. SIMT 구조를 이용하면 다수의 스레드를 병렬로 처리 할 수 있기 때문에, ray tracing 에 내재되어 있는 thread-level parallelism (TLP) 을 적극 활용할 수 있다. 하지만, SIMT 기반의 프로세서로 ray tracing 을 구현하는데는 두 가지 문제점이 있다. 병렬적으로 실행되는 스레드들의 execution flow 가 발산하는 경우 (branch divergence) SIMT datapath 의 사용률이 급격히 하락하는 문제, 그리고 다수의 프로세싱 유닛 (unit)이 하나의 메모리에 동시에 접근 함으로써 발생하는 공유 메모리에 대한 경쟁으로 인한 datapath 사용률 감소 문제가 바로 그것들이다.
본 연구에서는 ray tracing 을 모바일 환경에서 효과적으로 구현하기 위해 구조변경 가능한 SIMT 기반의 프로세서 구조를 제안하였다. 현재의 VLSI 공정 발달로 미루어 보면, 현재 진행되고 있는 데스크탑 PC 상에서의 ray tracing 구현이 머지않아 모바일 상으로 넘어갈 것이 분명해 보인다. 그때를 대비하여 미리 모바일 환경에서 ray tracing 을 구현할 때 발생할 수 있는 문제를 해결하고자 한다. 모바일 플랫폼에서는 다양한 자원들이 제한을 받게 되는데 특히나 제한된 칩 면적과 베터리에 의존하는 제한된 에너지 예산이 그것이다. 따라서, 제한된 자원이 가지고 있는 최대한의 성능을 이끌어 내기 위해 투입된 자원의 사용률을 극대화하는 구조를 제안하였다. 일반적으로 사용되는 SIMT datapath 에 구조를 변경할 수 있도록 하여 branch divergence 로 인한 datapath 사용률 감소를 줄이도록 하였다. 이를 위해 ray tracing 알고리즘과 하드웨어로 실행시에 요구되는 assembly code을 분석하여 ray tracing 을 구현하는데 활용될 수 있는 thread-level parallelism (TLP)와 instruction-level parallelism (ILP)를 최대한 활용할 수 있는 하드웨어 구조를 제안하였다. 제안된 하드웨어는 coarse-grained parallelism 을 활용하기 위해 다수의 코어에서 서로 다른 kernel 을 병렬적으로 처리하도록 하였고, fine-grained parallelism 을 활용하기 위해 구조변경 가능한 SIMT 구조를 제안하였다.
제안된 구조는 두 가지로, 첫째, branch divergence 가 발생하는 상황을 줄이기 위해 스칼라 SIMT 와 벡터 SIMT 로 구조 변경 가능한 SIMT datapath, 둘째 SIMT 기반의 datapath 를 MIMD 처럼 동작하도록 구조를 변경할 수 있는 SIMT datapath 를 제안하였다. 공유 메모리에 대한 contention 문제는 접근을 관리하는 하드웨어 유닛을 추가하여 평균적으로 1cycle 내로 데이터를 읽을 수 있도록 하였다. 이로인해, 공유메모리 접근으로 인한 datapath stall 을 감소시켰고, 다양한 위상을 가지는 새로운 time-division multiplexing (TDM) 방식의 접근 방식을 제안하여 공유메모리에 대한 contention 문제를 자연스럽게 피할 수 있도록 하였다.
제안된 구조의 성능을 평가하기 위해서 두 가지의 simulator 를 사용하였다. PBRT 라는 ray tracing 프로그램을 이용하여, 실제 ray tracing 을 실행한 결과를 추출하였고, shader 언어로 구현된 ray tracing code 로부터 assembly code 를 추출하여 하드웨어 실행시에 datapath 의 사용률을 계산하였다. 공유 메모리에 대한 스레드들의 접근은 GPU 하드웨어를 cycle 단위로 모사한 시뮬레이터 (GPGPU-Sim)를 활용하여 각 프로세싱 유닛들의 공유메모리에 대한 접근을 추출하여 분석하였다. 스칼라와 벡터 SIMT 로 구조 변경 가능한 SIMT datapath 의 경우, 동시에 처리하는 스레드의 개수를 12개에서 4개로 줄임으로써 동일한 개수의 프로세싱 유닛을 사용하는 일반적인 SIMT 보다 datapath 사용률을 평균 19.9% 향상시켰으며, 이를 위해 추가로 투입된 하드웨어 리소스는 전체 SIMT datapath의 0.1% 에 불구하다. 4개의 4wide SIMT 코어들을 하나의 SIMT 또는 MIMD 로 동작하도록 제안한 SIMT datapath 의 경우, 벡터 SIMT 로 구조 변경 가능한 것 보다 면적대비 성능이 26% 증가하였다.
제안된 두 개의 SIMT datapath 는 각각 130nm, 90nm CMOS 공정을 이용하여 4mm x 4mm 2 의 실리콘 면적에 칩으로 제작되었다. FPGA test board 상에서 검증된 결과, 1.2V 의 공급전압과 100MHz 의 동작 주파수로 각각 156mW, 221mW 의 전력을 소모함을 측정하였다.
결과적으로, 제안된 두 가지의 구조 변경 가능한 SIMT datapath 는 기존 SIMT datapath 보다 비슷하거나 적은 면적으로 높은 datapath 사용률을 얻을 수 있으므로, 모바일 상에서 제한된 연산능력을 최대한 활용할 수 있는 구조라 할 수 있겠다. 또한, 높은 datapath 사용률은 실행시간을 줄여 소비 에너지를 줄일 뿐 아니라, 누수전력이 동작전력 보다 증가하게 되는 65nm 이하의 공정에서 유휴 datapath 에서 소비되는 누수전력을 줄일 수 있어 제한된 파워예산을 가진 모바일 환경에서 더욱 유리한 구조라 할 수 있겠다.
