GPGPU 를활용한 PDEVS 시뮬레이터개발방법론 Abstract Key Words : DEVS, PDEVS, GPGPU, CUDA
한국시뮬레이션학회 10 춘계학술대회 2010.05.28 홍익대학교조치원캠퍼스 1. 서론게임소프트웨어발전과더불어그래픽카드도발전해왔고더불어 GPU내프로세서의수도증가하였다. 표 1은최근의그래픽카드의프로세서의수를나타낸다. 표 1. NVIDIA 그래픽카드프로세서수 [1] 현재판매되는 CPU 프로세서의수가 2~8 개임을고려하면위의 GPU 프로세서의수는엄청나다. 이렇게많은 GPU의프로세서를그래픽연산에만사용할것이아니라시뮬레이션에이용하고자한다. 이처럼 GPU를그래픽이미지연산이아닌그밖의목적으로쓰는것을 GPGPU(General-Purpose computing on Graphics Processing Units) 라한다. 시뮬레이션을하기위해서는시스템을기술하기위한형식론이필요하다. 그중하나인 DEVS(Discrete Event System Specification) [2] 형식론은지금까지활발히연구되었고사용되고있다. DEVS 기반의시뮬레이션에서는모델단위로스케줄된순서대로모델이동작한다. DEVS 시뮬레이터는여러모델이동일시간에스케줄이되었을경우에는동시에그모델들의동작을수행하지않고, 시뮬레이션시간은멈춰있는동안우선순위순서대로모델을하나씩동작시킨다. 이처럼 DEVS 기반의시뮬레이션에서는모델이순차적으로동작을하기때문에다른프로세서를사용할필요가없다. 그러므로멀티프로세서환경에서 DEVS 기반시뮬레이션은적합하지않다. 반면, PDEVS(Parallel DEVS) 형식론은동시에여러모델을수행할수있도록 DEVS 형식론을확장하였다. 이는이미병렬, 분산환경에서많은연구가진행되어왔다 [3]. GPU에서 PDEVS 시뮬레이션이이루어지게되면많은모델이같은시간에스케줄이되더라도모델을동작시키는프로세서의수가 100~260개나되므로빠른시간내에동작시킬수있다. 이러면순차적으로동작하는 DEVS 시뮬레이션에비해같은시간에스케줄이되는모델이많을수록시뮬레이션시간은크게단축될것이다. 하지만 GPU 프로세서는 CPU프로세서와달리 SIMD (Single Instruction, Multiple Data) 특성을가진다. 이특성으로인해특정한조건을만족하는모델들만 GPU에서 PDEVS 시뮬레이션이가능하다. 이와같은 GPU의단점을극복하고자본논문에서는 PDEVS 시뮬레이터를기존의 DEVS 시뮬레이터에활용한 DEVS-PDEVS 시뮬레이터를제안한다. 그리고이시뮬레이터의동작알고리즘과장점을설명하고기존 DEVS 시뮬레이터와성능을비교하였다. 본논문의구성은다음과같다. 2장에서 PDEVS 형식론을소개하고, 3장에서 GPGPU 의한계를설명하고, 4장에서는 DEVS-PDEVS 및동작알고리즘을설명한다. 5장에서는 DEVS 시뮬레이터와 DEVS-PDEVS 시뮬레이터의성능을비교하는실험을하고 6장에서결론을맺는다. 2. PDEVS PDEVS(Parallel DEVS) 는 DEVS를확장한형식론이다. 대표적인차이는 DEVS에서는하나의입력에의해외부천이함수가발생하지만 PDEVS에서는여러입력에의해외부천이함수가발생했을때상태가어떻게바뀌어야할지를표현할수있다. 2.1 PDEVS 원자모델표현원자모델 (Atomic Model) 은 PDEVS 형식
GPGPU 를활용한 PDEVS 시뮬레이터개발방법론 론을구성하는가장기본적인모듈로서시스템의행동을기술하는모델이다. 원자모델 M의수학적인표현은다음과같다. M = <X, Y, S, δext, δint, δcon, λ, ta> X : 이산사건입력집합 Y : 이산사건출력집합 S : 일련의이산사건상태의집합 δint : S S : 내부상태천이함수 δext : Q X b S: 외부상태천이함수 X b 는 X의원소들로이루어진 bag들의집합 bag이란 {a,b,a,c} 와같이원소중복을허용하는유사집합이다. Q={(s,e) s S, 0 e ta(s)} δcon : S X b S : 융합천이함수 λ : S Y : 외부상태천이함수 ta : S R0, + : 시간진행함수 2.2 PDEVS 결합모델표현결합모델 (Coupled Model) 은여러모델을내부적으로연결하여만든모델로 DEVS 결합모델에서 SELECT 함수가제외되었다. 결합모델 CM의수학적인표현은다음과같다. CM = <X, Y, {Mi}, EIC, EOC, IC > X : 이산사건입력집합 Y : 이산사건출력집합 {M i }: 모든이산사건콤퍼넌트모델들의집합 EIC : 외부입력연결관계 EOC : 외부출력연결관계 IC : 내부연결관계 3. PDEVS 시뮬레이터로 GPGPU 응용 GPU는 CPU보다많은프로세서를가지고있지만 SIMD 특성을가진다. SIMD(single instruction, Multiple data) 란하나의명령어로여러자료를처리하는것을말한다. 그림 1. 같은명령어를참조하고있는 GPU 프로세서그림 1과같이 SIMD 특성때문에 GPU의여러프로세서는같은명령어를수행하고있다. 실제 GPU에서서로다른모델 M1, M2 가 PDEVS 기반으로시뮬레이션이되고있다고가정하자. 그리고어느시점에모델 M1과 M2가동시에다른내부상태천이함수가동작해야한다. 이때모델 1의내부상태천이함수명령어들은프로세서1에서처리되고모델 2 의내부상태천이함수명령어들은프로세서2에서처리된다면서로다른두모델의내부상태천이함수는병렬적으로동시에수행이가능할것이다. 그렇지만앞서밝힌 SIMD 특성에의해서로다른프로세서가다른명령어들을처리하는것은불가능하다. 반면에두모델이같은명령어를가지는내부상태천이함수를수행해야한다면서로다른프로세서에서동시에수행하는것이가능하다. 따라서 GPU를활용하여 PDEVS 시뮬레이션을하기위해서는모델들의 PDEVS 원자모델형식론의함수의내부명령어가같아야한다. 예를들면 cellular automata에서 cell이나워게임시뮬레이션에서동일한교리를따르는군인들, 동일한운동방정식을가지는미사일등이있다. 4. DEVS-PDEVS 시뮬레이터실제같은종류의모델들로만시뮬레이션할경우는흔치않다. 따라서 PDEVS 시뮬레이터가독자적으로동작하는방식이아니라기존개발된 DEVS 시뮬레이터와함께동작하는 DEVS-PDEVS 시뮬레이터를제안한다.
한국시뮬레이션학회 10 춘계학술대회 2010.05.28 홍익대학교조치원캠퍼스 그림 2. DEVS-PDEVS 시뮬레이터 4.2 PDEVS 시뮬레이터동작알고리즘전체시뮬레이션시작은 DEVS 시뮬레이터에의해이루어지고 DEVS 시뮬레이터에서종료가된다. PDEV 시뮬레이터는 IF 모델의 δext, δint, λ, ta가호출되면동작한다. 이렇게 PDEVS 시뮬레이터는 DEVS 시뮬레이터에의존적으로동작을하기때문에 PDEVS 형식론이다음과같이변경하였다. DEVS-PDEVS 시뮬레이터전체구성은그림 2와같다. CPU에는 DEVS 시뮬레이터가동작하고 GPU에는 PDEVS 시뮬레이터가동작한다. GPU 위의 PDEVS 시뮬레이터에서동작이가능한모델은 GPU에두고, 그외의모델은 DEVS 시뮬레이터위에서동작시킨다. 그리고 DEVS 시뮬레이터 IF( 인터페이스 ) 모델을통해서두시뮬레이터간데이터를교환한다. 이방법을통해기존의 DEVS 시뮬레이터를재사용하면서제약이있는 GPU의 PDEVS 시뮬레이터를다른모델들과시뮬레이션이가능하게하였다. 4.1 IF(Interface) 모델 IF 모델은 PDEVS 시뮬레이터모델들을대표하고 DEVS-PDEVS 두시뮬레이터사이의시간동기화를한다. 그리고 PDEVS와 DEVS 의형식론차에의해서발생하는문제를해결해주어야한다. 예를들면 PDEVS 모델에서 DEVS 모델로향하는출력이 {y1, y2, y3} 라면 IF 모델은 ta=0인 3번의내부천이함수가이루어지면서 y1, y2, y3 를한번씩출력한다. 이렇게 PDEVS 의출력 bag이시간진행하지않으면서순차적으로 3번나오기때문에 DEVS 시뮬레이터에서모델은순차적으로외부상태천이함수동작이가능해졌다. M=<X, Y, S, δexti, δexto, δint, δcon, λ, ta> δexti는 GPU 내부모델로부터입력을받았을때수행되는외부상태천이함수이고, δexto 는 DEVS 모델로부터입력을받았을때호출되는외부상태천이함수를말한다. PDEV 시뮬레이터가 IF 모델로부터호출되어동작하면 DEVS 시뮬레이터는 PDEVS 시뮬레이터동작이끝날때까지기다리고, 동작이끝나면 DEVS 시뮬레이터는계속동작한다. PDEVS 시뮬레이터동작알고리즘은다음과같다. ➀ IF 모델의 δext가호출된경우 ( 가 ) PDEVS 시뮬레이터현재시간을 IF 모델의함수가호출된 DEVS 시뮬레이터시간에맞추고, 각모델의스케줄까지남은시간을수정한다. ( 나 ) IF 모델의입력을확인하고그입력이실제로 PDEVS의어느모델로향하는지확인한다. 그리고그 PDEVS 모델의 δ exto를수행한다. 이때남은시간이 0이면 δcon을호출하여 δexto와 δint중우선순위를결정한다. 그리고우선순위에맞게 δexto, δint를수행한다. ( 다 ) 상태가바뀐모델의 ta를호출하고스케줄까지남은시간을 ta 값으로수정한다.
GPGPU 를활용한 PDEVS 시뮬레이터개발방법론 ➁ IF 모델의 δint가호출된경우 ( 가 ) PDEVS 시뮬레이터현재시간을 IF 모델의함수가호출된 DEVS 시뮬레이터시간에맞추고, 각모델의스케줄까지남은시간을수정한다. ( 나 ) 남은시간이 0인모델들에대해서 PDEVS의 δint를수행한다. ( 다 ) 상태가바뀐모델의 ta를호출하고스케줄까지남은시간을 ta 값으로수정한다. ➂ IF 모델의 λ, 가호출된경우 ( 가 ) 1 알고리즘 ( 가 ) 와 λ동일 ( 나 ) 스케줄까지남은시간이 0인모델들에대해서 PDEVS의 λ를수행한다. ( 다 ) 이때발생한출력중 DEVS 모델로가는출력들을 IF 모델에게알려준다. ( 라 ) 출력이 PDEVS 모델의입력으로들어갈때에는해당모델에대해 δexti를수행한다. 이때그모델이스케줄까지남은시간이 0인경우 δcon을호출하여 δexti 와 δint중우선순위를결정한다. 그리고우선순위에맞게 δexti, δint를수행한다. ( 마 ) 1 알고리즘 ( 다 ) 와동일 션종료시간을비교하였다. 실험컴퓨터사양은아래와같다. 표 3. 시뮬레이션컴퓨터사양 Intel Core 2 Quad CPU Processor Q9550 RAM 4GB GPU Geforce GTX 260 DEVS CUDA 시뮬레이션의경우, 숲 cell들은 PDEVS 시뮬레이터에서동작하고헬리콥터모델은 DEVS 시뮬레이터에서동작한다. 그리고 DEVS 시뮬레이터의경우모든모델이 DEVS에서동작한다. DEVS 시뮬레이터는기존에개발되었던 DEVSim++[5] 을이용하였고, PDEVS 시뮬레이터는본논문에서제시한알고리즘을기반으로 CUDA 환경에서만들어졌다. 두시뮬레이션종료까지의걸리는시간은다음과같다. ➃ IF 모델의 ta가호출된경우 ( 가 ) 1 알고리즘 ( 가 ) 와동일 ( 나 ) PDEVS 전체모델중스케줄까지남은시간이가장작은것은값을 IF모델에게알려준다. 이값을 GPGPU의병렬연산을이용해서발견할수있다. 5. 실험 cellular automata의한예인산불이퍼지고이를헬리콥터로진압하는것을 DEVS-PDEVS 시뮬레이터를사용했을때와 DEVS 시뮬레이터만을사용했을때시뮬레이 그림 3. 시뮬레이션종료시간결과를보면처음숲 cell의숫자가적을때는 DEVS 시뮬레이터로만시뮬레이션했을때에는더좋은성능이나왔지만 cell의숫자가커질수록 DEVS-PDEVS를함께사용한것이더좋음을볼수있다. 이이유는 cell 수가적을때에는 PDEVS를사용해서생기는이득보다 CPU, GPU 간의통신시간증가에
한국시뮬레이션학회 10 춘계학술대회 2010.05.28 홍익대학교조치원캠퍼스 의한손해가더크기때문이다. 그렇지만 cell 수가증가하면서동시다발적으로불이발생하는지점이늘어나고, 그만큼 PDEV에의해동시에수행되는모델의수가늘면서 DEVS 로만시뮬레이션한것보다성능이좋음을확인할수있다. 6. 결론이논문을 GPGPU를이용해서 PDEVS 시뮬레이터로활용하는방법을제시했다. 그리고 GPU의 SIMD 특성으로인해 PDEVS 시뮬레이터모델의제약있지만기존 DEVS 시뮬레이터에연동하여동작하게함으로써기존 DEVS 시뮬레이터도재사용하고 PDEVS 시뮬레이터도활용성을높였다. GPU에서동작하는모델의수가크지않으면잦은 CPU, GPU간통신오버헤드로인해성능이저하될수있다. 그렇지만실험에서처럼동시에수행되는작업이많다면큰성능향상을얻을수가있다. 참고문헌 1. http://www.anandtech.com/show/2619 2. Bernard P. Zeigler, Herbert Praehofer and Tag Gon Kim, Theory of Modeling and Simulation. ACADEMIC PRESS, 2001. 3. Jan Himmelspach, Roland Ewald, Stefan Leye and Adelinde M. Uhrmacher. Parallel and distributed simulation of Parallel DEVS models" in proceedings of the 2007 spring simulation multiconference, pages 249-256,2007 4. NVIDIA CUDA Compute Unified Device Architecture- Programming Guide, 2008. 5.Tag Gon Kim, DEVSim++ v3.0 Developer 's Manual, 2006, http://smslab.kaist.ac.kr/