According to recent commodity GPU improvements, applications for multiple GPU and Cluster Graphics have started to spread widely. Basically, the commodity based cluster graphics systems use the off-the-shelf components; but there has been little considerations within the pipeline to combining intermediate results between GPUs. When it comes to combining intermediate results for efficient interactive or realtime rendering, the rendering performance will probably drop without further architectural support or improvement. One option to bypass such communication is to process pixel areas with a single dedicated processor; this is one of the key characteristics of sort first architecture. For the commodity based cluster graphics systems which do not have the high bandwidth necessary to interchange intermediate results of GPUs, sort-first architecture has been widely selected as a parallel rendering architecture.
Such processor isolation provides architectural advantages, but also incurs certain disadvantages. One advantage is to eliminate intermediate exchange results such as image space projected polygons or depth buffers. On the other hand, one disadvantage is the fact that such a system faces load imbalance because partition algorithm did not divide graphics primitives but image area. Another disadvantage arises because it has to divide image space for processors. Primitives happen to be projected on the pixel area of more than one processor and cause inefficiently redundant processes on more than one processor. Such overlapped primitives become a major reason for performance inefficiency.
According to recent GPU improvements, the performance gap between CPUs and GPUs has increased. If individual primitives are selected as work units, a typical CPU could be unable to keep pace with the GPU processing speed. Therefore, a chunk or group of primitives is selected as a rendering unit by recent realtime rendering algorithms and applications. When relatively larger primitive groups becomes overlapped, their redundant processing would worsen the efficiency of the parallel rendering.
The k-d partition and its extension have been widely selected for the pixel area divide methods. But this method cannot take into account the efficiency of the image partition. Inefficiency could exist in the k-d partitions. The current state of art in the detection and reduction of the inefficiency is the hybrid architecture method, which takes advantages of different architectures.
As opposed to the hybrid method, our research focus has been on the improvement of the image partition algorithm of sort-first parallel rendering. We will confirm the efficacy of our approach by conducting experiments on two algorithmic challenges.
First, based on the fact that efficient partition has fewer overlap primitives, our study performs an adaptation experiment with spectral bisection method in order to reduce overlap primitives. The spectral bisection method is a kind of graph partition method and seeks to find the minimum boundary cost of load balanced binary partitions. With relaxation of the discrete conditions, the method computes partitions quite efficiently and is widely used to partition large scientific and engineering problems. To use the spectral bisection method, an approximation model of workload graphs from tile rendering complexities is proposed. The spectral bisection method is considered to be a computable lower bound algorithm of optimal partition.
Second, direct max load minimization methods using discrete method are studied. One of these methods is the forest branch and bound method. The branch and bound method is a general global optimization method and its application to the tile assignment problem is considered. Parallel computing API is used to speed up algorithm performance. Each sub trees in the forest is executed concurrently. The other ones use the separation theorem to measure possible partitions‘ max load efficiently. Each partition in this method is partitioned by a separation line. The problem is redefined as a searching the most efficient separation line among all lines. For power-of-2 count processors, the partitioning method could be recursively applied. As a result, such partitioning is similar to binary space partitioning. The algorithm is called the binary space partition search algorithm.
In our experiment, the binary space partition search algorithm reduces the max load among processor loads by 19.2% on average and 32.2% maximum. Even in case in which the k-d method does not show reduction of the max load despite additional partition, our algorithm successfully reduces max load by 11.3% on average and 35.1% maximum. Our over 30% max load reduction is comparable to a doubling of the number of processors, which could reduce the max load by 50% in an ideal case.
최근 GPU의 성능 향상에 따라, 다중 GPU 및 클러스터 그래픽스 기법이 널리 사용되고 있다. 기본적으로 클러스터 그래픽스는 판매되는 상용 부품들을 이용하기 때문에 GPU들간의 중간 처리 결과의 교환을 위한 파이프라인 내부의 고려가 적다. 효과적인 사용자 반응형 혹은 실시간 렌더링을 위해 중간 결과를 합성하는 경우에는 구조적인 지원이나 발전 없이는 렌더링 성능이 줄어들 것이다. 이러한 통신 문제를 피하는 방법 중에 하나는 화소 영역을 단일 프로세서가 처리하는 것이다. 이러한 점은 선정렬 시스템의 중요 특징 중의 하나이다. GPU들의 중간 결과를 교환할 수 있는 고성능의 통신 능력이 없는 상용 부품 기반의 클러스터 시스템에는 선정렬 시스템이 병렬 렌더링 구조로 널리 사용되고 있다.
이러한 프로세서의 고립은 구조적 장점과 동시에 단점을 제공한다. 하나의 장점은 이미지 공간에 투사된 폴리곤이나 깊이 버퍼들 같은 중간 계산 결과의 교환을 제거하는 것이고 단점 중의 하나는 하나의 프로세서로는 주어진 시간 안에 렌더링할 수 없는 집중된 화소영역에서의 부하 불균형 문제에 직면한다는 것이다. 또한 선정렬 구조는 그래픽스 프리미티브가 아닌 이미지 공간을 분할해야 되기 때문에 또 하나의 단점이 생긴다. 프리미티브는 하나이상의 프로세서 분할 화소 영역에 프로젝션될 수 있기 때문에 여러 개의 프로세서에 처리되어야하는 비효율적인 중복 처리를 야기한다. 이러한 중복 프리미티브는 성능 비효율성의 중요 요인이 된다.
최근 GPU의 발전에 따라, CPU와 GPU의 처리 능력의 차이가 증가되고 있다. 개개의 프리미티브가 작업의 단위로 사용된다면 CPU는 GPU의 처리속도에 보조를 맞추기 어려울 수 있다. 그러므로 최근 실시간 렌더링 알고리즘이나 응용에서는 프리미디의 덩어리 혹은 그룹을 작업의 단위로 선택하고 있다. 이러한 상대적으로 큰 프리미티브 그룹이 겹침 프리미티브가 된다면, 중복적 처리는 병렬 렌더링의 효율을 더욱 악화 시킬 수 있다.
k-d 분할법과 그의 변종은 화소 영역 분할방법으로 널리 사용되고 있다. 그러나 이미지 분할의 효율성 측면은 인지하지 못하는 방법이다. k-d 결과 분할에는 비효욜이 존재할 수 있다. 최근의 최선의 기술은 비효율을 감지하고 줄이는 기법으로 서로 다른 구조의 장점을 취하는 구조 혼용 기법이다.
구조 혼합 방법과는 반대로, 본 연구에서는 선정렬 병렬 렌더링 시스템에서 이미지 분할 알고리즘의 개선에 초점을 맞추었다. 두 가지의 알고리즘 차원의 방안들에 대한 실험을 통해서 본 연구의 효과성을 확인한다.
첫 번째로 효과적인 분할은 겹침 프리미티브가 적다는 사실에 근거하여, 스펙트럴 이진 분할법을 겹침 프리미티브를 줄이는 데 적용하는 실험을 수행하였다. 스펙트럴 이진 분할법은 그래프 분할법의 일종으로서 경계 영역의 비용을 최소화하는 균형 부하 이진 분할을 찾는다. 이산적 제약조건을 완화하여, 분할을 매우 효과적으로 계산하며, 큰 과학 및 공학문제에 널리 적용되고 있는 방법이다. 스펙트럴 이진 분할을 이용하기 위하여 이미지 타일의 렌더링 비용에 근거한 작업 그래프 근사 모델을 제안한다. 스펙트럴 이진 분할 방법은 최적 분할의 계산할 수 있는 최선 성능의 알고리즘으로 고려되었다.
이미지 분할 알고리즘의 효율성을 직접 개선하기 위해, 이산적 분할 방법들이 실험되었다. 하나는 Forest branch and bound 기법이다. Branch and bound 기법은 일반적인 전역 최적화 방법으로 타일 할당 문제에 적용을 고려하였다. 병렬 계산 API를 사용하여 고속화화였다. forest 상의 개개의 트리는 병렬적으로 수행된다. 다른 하나의 방법은 Separation 이론을 이용하는 것으로 가능한 파티션들의 최대 적재량을 효과적으로 측정한다. 이 방법상에서 개개의 파티션은 하나의 분할 직선에 의해서 분할된다. 2진수의 프로세서 개수를 위하여 재귀적으로 적용될 수 있다. 결과적으로 분할은 이진 공간 분할과 동일하다.
우리의 실험에 의하면 이진 공간 분할 검색 알고리즘은 프로세서들의 적재량 중에 가장 큰 적재량을 k-d 알고리즘과 비교했을 때, 평균 19.2% 줄이며 최대 32.2% 줄인다. 또한 추가적인 분할을 수행해도 최대 적재량이 줄지 않는 경우에도 우리의 알고리즘은 평균 11.3%, 최대 35.1%의 작업량을 줄였다. 본 실험의 30% 이상의 최대 적재량 감소는 이상적인 경우에 최대 적재량을 50% 줄일 수 있는 프로세서를 두 배 쓰는 것과 비교할 만하다.
