232 정보과학회논문지 : 시스템및이론제 32 권제 5 호 (2005.6) 빠른하드웨어 / 소프트웨어통합합성을위한데이타플로우명세로부터의하드웨어합성 (Hardware Synthesis From Coarse-Grained Dataflow Specification For Fast HW/SW Cosynthesis) 정현욱 하순회 (Hyunuk Jung) (Soonhoi Ha) 요약이논문에서는빠른하드웨어 / 소프트웨어통합합성을위해데이타플로우그래프 (DFG: Dataflow Graph) 로부터하드웨어를자동으로합성하는내용을다룬다. 이데이타플로우그래프에서노드는 FIR(Finite Impulse Response) 필터나 DCT(Discrete Cosine Transform) 블록과같이크기가어느정도되는하드웨어블록을나타내며, 이노드의포트는한번수행할때마다하나이상의데이타샘플을주고받을수있다. 즉, 멀티레이트데이타샘플 (multi-rate data sample) 을교환한다. 이러한특성들은기존의 Behavioral Synthesis 와구별되는점이며, 따라서 Behavioral Synthesis 보다어려운문제가된다. 본논문에서제안하는설계방법을사용하면알고리즘을명세하는데이타플로우그래프는하드웨어리소스의할당과스케줄정보에따라다양한하드웨어구조로매핑될수있다. 따라서하드웨어설계시에면적 / 성능트레이드오프관계를손쉽게관리할수있으며, 하드웨어를자동으로합성하는기존의방식보다구현가능한하드웨어설계공간을더욱넓혀주는효과를거둘수있다. 키워드 : 하드웨어 / 소프웨어통합설계, 시스템수준설계, 데이타플로우그래프, VHDL, 자동하드웨어합성 Abstract This paper concerns automatic hardware synthesis from data flow graph (DFG) specification for fast HW/SW cosynthesis. A node in DFG represents a coarse grain block such as FIR and DCT and a port in a block may consume multiple data samples per invocation, which distinguishes our approach from behavioral synthesis and complicates the problem. In the presented design methodology, a dataflow graph with specified algorithm can be mapped to various hardware structures according to the resource allocation and schedule information. This simplifies the management of the area/performance tradeoff in hardware design and widens the design space of hardware implementation of a dataflow graph compared with the previous approaches. Through experiments with some examples, the usefulness of the proposed technique is demonstrated. Key words :HW/SW Codesign, System Level Design, Dataflow Graph(DFG), VHDL, Automatic Hardware Synthesis 1. 서론 시스템온칩 (SoC: System-on-Chip) 설계시에설계복잡도가증가하고적기시장출하 (time-to-market) 에대한 본연구는국가지정연구실프로그램 ( 번호 M1-0104-00-0015), 두뇌한국 21 프로젝트, SystemIC 2010 프로젝트에의해지원되었으며, 이연구를위해연구장비를지원하고공간을제공한서울대학교컴퓨터연구소에감사드립니다. 비회원 : 서울대학교전기컴퓨터공학부 jung@iris.snu.ac.kr 정회원 : 서울대학교전기컴퓨터공학부교수 sha@iris.snu.ac.kr 논문접수 : 2005년 1월 24일심사완료 : 2005년 3월 16일 압력이점점늘어남에따라시스템수준의설계방법론 (system level design methodology) 이더욱주목을받고있다. 시스템수준설계에서는시스템수준의명세가체계적인방법을통해최적의아키텍처로매핑되고, 빠른설계공간탐색을위해그매핑이구현되기전에평가되어야한다. 우리는시스템수준의명세를위해여러명세모델들중에서데이타플로우모델 (Dataflow Model) 을사용한다. 이모델은읽기쉽고, 정형적인특성을가지기때문에많은상위수준설계환경 [1-3] 에서적용하고있으며특히신호처리와멀티미디어응용에서많이사용되고있다.
빠른하드웨어 / 소프트웨어통합합성을위한데이타플로우명세로부터의하드웨어합성233 이데이타플로우모델은 Behavioral Synthesis에서사용하는 CDFG(Control/Data Flow Graph)[4] 와는다르다. CDFG에서는노드가덧셈또는곱셈과같은간단한연산을나타내는데반해, 그림 1(a) 의데이타플로우그래프 G(V, E) 에서는노드가 FIR 필터나 DCT 블록과같이상대적으로큰블록을나타낸다. 그러므로데이타플로우그래프의노드는 I/O 타이밍, 데이타타입, 내부상태 (internal state) 와같은복잡한특성을가진다. 지금부터명확한설명을위해두용어, 하드웨어리소스 (hardware resource) 와하드웨어콤포넌트 (hardware component) 를다음과같이구분하고자한다. 하드웨어리소스는한노드가라이브러리형태로하드웨어로구현된것을의미하며, 하드웨어콤포넌트는 FPGA나 ASIC과같은단위로서하드웨어리소스들이결합되어집합적으로이루어진것을의미한다. 그림 1: (a) 초기데이타플로우명세 (b) 하드웨어로매핑된분할된서브그래프 (c) 멀티레이트그래프의순차수행 (d) 멀티레이트그래프의병렬수행 (e) 멀리레이트그래프의하이브리드수행한노드가수행이되면입력단에서명시한개수만큼의데이타샘플을소비하고출력단에서명시한개수만큼데이타샘플을내보낸다. 본논문에서는 SDF (Synchronous Dataflow) 모델 [5] 과이모델을확장한 FRDF(Fractional Rate Dataflow) 모델 [6] 을사용한다. 이모델들의특징은포트에서입출력되는데이타샘플을개수가미리정해져있어서수행되는동안고정되어있다는점이다. 그리고그개수가 1보다큰경우에는멀티레이트그래프 (multi-rate graph) 라고한다. 그림1에서보는바와같이데이타플로우그래프에서명시한데이타샘플레이트 (data sample rate) 에의하면노드 B 가한번수행된후에노드 C는네번수행되어야한다. 앞으로한노드의한번수행을그노드의인스턴스라고부르기로하겠다. 이렇게데이타플로우모델을제한함으로서시스템성능을예측하기위한중요한메모리제한성, 종료여부등의속성을검증할수있다. 제안하는설계방법론에서는데이타플로우그래프의한노드에해당하는기능블록하나가하드웨어 / 소프트 웨어분할의단위가된다. 본논문의설계환경에서는각기능블록들이소프트웨어구현을위해서는 C 코드로, 하드웨어구현을위해서는 VHDL 코드로기술되어있다고가정하고있으며, 기존의 IP 블록들도약간의인터페이스코드를붙이면데이타플로우블록으로사용할수있다. 하드웨어 / 소프트웨어분할이수행된후에는하드웨어또는소프트웨어콤포넌트 (Component) 로매핑되는몇개의서브그래프로나뉘게된다. 그림 1(b) 는하드웨어콤포넌트로매핑되는서브그래프의예를보여주고있으며서브그래프의경계에 Rcv(receive), Snd (send) 등의인터페이스블록이자동으로붙게된다. 그림 2는데이타플로우명세로부터시작하는하드웨어 / 소프트웨어통합설계절차를단순화하여보여주고있다. 그림에서보듯이각 Processing Element(PE, 소프트웨어의경우는프로세서, 하드웨어의경우는하드웨어 IP또는 Component) 에서수행되는각노드의성능은노드-PE 데이타베이스에서주어진다고가정한다. 본논문에서제안하는설계환경에서는초기데이타플로우명세가자동으로분할되고스케줄되는데, 각노드들의성능과가격에기반해서각데이타플로우가어느 PE로매핑될지를결정한다. 분할기법에관한자세한내용은 [7] 에서소개하고있다. 선택한아키텍처에대해분할과스케줄링이모두수행되고나면소프트웨어와하드웨어코드가자동으로생성되고, 시스템성능을검증하기위해통합시뮬레이션이수행된다. 만약에시스템성능이원하는만큼만족스럽지않으면, 아키텍처선택과정으로되돌아가서다른 PE 또는아키텍처를선택하여야한다. 이와같이반복되는설계과정에걸리는시간을줄이기위해서는데이타플로우명세로부터하드웨어와소프트웨어코드를자동으로생성하는일이매우중요해진다. 또한코드를자동으로생성하면코딩하는시간뿐만아니라디버깅시간까지도절약할수있는효과까지거둘수있다. 그림 2 제안하는시스템설계과정
234 정보과학회논문지 : 시스템및이론제 32 권제 5 호 (2005.6) 본논문은그림 2 중에서특별히어두운색으로표시한하드웨어의자동합성과정에초점을맞추고있으며, 이는하드웨어설계와검증과정의시간을줄이기위해서꼭필요한일이다. 데이타플로우노드들이수행되는순서를스케줄이라고부르는데, 이스케줄과구현에필요한각노드의하드웨어리소스의개수가이전의분할 (Partitioning) 단계에서주어지므로, 하드웨어를합성하는문제는라이브러리로부터하드웨어리소스들을할당하고각블록들간의인터페이스코드 (interface code) 와전체적으로필요한제어코드 (control code) 들을합성하는일이된다. 물론합성된하드웨어는데이타플로우모델의규칙 (dataflow semantic) 을지키도록설계되어원래알고리즘기술에서의도한것과똑같이수행되어야한다. 멀티레이트데이타플로우그래프 (multi-rate dataflow graph) 는멀티미디어응용에서자주사용된다. 멀티레이트그래프로부터하드웨어콤포넌트를합성할때는알고리즘의병렬성에의해조금더자유도가큰설계공간을고려할수있다. 데이타플로우그래프로부터자동으로하드웨어를합성하는연구가몇몇이루어졌었지만, 이병렬성을고려하는연구는지금까지없었다. 기존연구를크게두가지접근방식으로나누면, 그림 1(c) 와같이완전히순차적으로수행하는경우 [8,9] 와그림 1(d) 와같이완전히병렬적으로수행하는경우 [10] 가있다. 본논문에서는이두가지방식을포함함과동시에그중간단계의구현 ( 그림 1(e)) 까지지원함으로서다양한하드웨어성능 / 면적트레이드오프관계를고려할수있는방법을제안하려한다. 본논문이기여하는바를명확히열거하면다음과같다. 1. 하드웨어합성의자동화 : 데이타플로우모델로명세한알고리즘으로부터하드웨어를자동으로합성함으로써설계공간을신속히탐색할수있게하였으며, 시간이오래걸리고에러가많이발생하는, 하드웨어블록의연결및통합작업을자동화하였다. 2. 합성된하드웨어동작의정확성보장 (correct by construction) : 스케줄정보에따라하드웨어의동작이데이타플로우모델의규칙대로이루어지도록부가로직 (glue logic) 들과콘트롤러 (controller) 를합성하였다. 따라서자동으로합성된하드웨어는데이타플로우알고리즘명세에서의도한대로정확히동작할수있다. 3. 하드웨어설계공간의다양화 : 스케줄링과정과하드웨어합성과정을분리함으로써주어진하나의데이타플로우명세로부터다양한하드웨어아키텍처를구현할수있었다. 사용자는단순히스케줄과리소스공유정보만을변경하면나머지합성과정은자동으로 이루어진다. 이러한기법을통해, 데이타플로우기반으로하드웨어를자동생성하는기존접근방식보다하드웨어구현의설계공간을훨씬넓힐수있었다. 본논문의구성은다음과같다. 다음장에서는본연구에동기를부여한예제와함께몇몇관련연구들을소개하고, 3장에서그예제를이용하여제안하는기법을설명하고자한다. 그리고, 4장에서는하드웨어로구현되는각블록의타입에관해자세히기술하고, 실험결과들은 5장에정리하였다. 마지막으로 6장에서남은과제들을검토하고결론을맺고자한다. 2. 기존연구들과동기부여예제빠른하드웨어 / 소프트웨어통합합성을하기위해서, 상위수준명세또는 C/C++ 로쓰여진소프트웨어명세로부터하드웨어를자동으로합성하기위한많은연구가있었다. 하드웨어기술언어 (HDL: Hardware Description Language) 들로부터 Behavioral 수준합성을하는연구 [4,11,12] 는오랫동안이루어져왔지만제한적인성공을거두는데그쳤고, C나 C++ 명세로부터하드웨어합성을하는연구 [13-15] 는최근까지지속되고있다. 최근의연구들은포인터분석과병렬성검출및이용등과같이 C/C++ 명세의제약점들을극복하려는시도에초점이모아지고있다. 그러나이러한연구들은하드웨어블록을자동으로구현하는것을주목적으로하는것이고본논문에서언급하는내용은주어진하드웨어라이브러리블록을이용하여시스템수준에서통합하여하드웨어를구성하는방법에관한것이라는점에서차이가있다. 한편, 빠른프로토타이핑을위해 SDL(Specification and Description Language) 명세로부터하드웨어를합성하는연구 [16,17] 가있었다. 이접근방식은시스템수준의설계를목적으로한다는점에서우리의접근방식과유사하지만명세하는모델과응용의범위가다르다. SDL은 Asynchronously Communicating Process를모델로사용하며주로통신시스템의기술을목표로하는반면에, 본논문에서는멀티미디어응용의기술을목표로하여잘정의된모델인 SDF[5] 를사용한다. 그림 3은 2차원 DCT(discrete cosine transform) 알고리즘의데이타플로우그래프표현이다. 이그래프는비교적큰 64와 8의데이타샘플레이트 (data sample rate) 로표현된멀티레이트데이타플로우그래프 (multirate dataflow graph) 이다. 이알고리즘은다양한하드웨어구조로구현될수있는데, Ptolemy[10] 방식에서는두개의 Transpose 블록사이에 8개의 DCT1D 블록리소스를사용하여완전히병렬적으로구현한다 ( 그림 4(a)). 그림을살펴보면 Transpose 블록이 64개의데이
빠른하드웨어 / 소프트웨어통합합성을위한데이타플로우명세로부터의하드웨어합성235 그림 3 2차원 DCT 알고리즘의데이타플로우명세 (a) (b) (c) 그림 4(a) Ptolemy[10], (b) Meyr의연구 [9], (c) GRAPE[3] 으로부터생성된하드웨어구조타샘플을출력한후에 8개의 DCT1D 리소스들이동시에수행가능한상태가됨을알수있다. 그리고블록들사이가버퍼없이곧바로연결되어있다. 이러한병렬구현은가장빠른수행시간을갖게되지만 16개의 DCT1D 리소스를사용해야하므로, 우리실험결과에따르면하드웨어면적이약 243,000 게이트 (gate) 에이르게되어면적면에서손해가가장크다. Meyr의접근방식 [8,9,18] 에서는데이타플로우그래프와일대일대응관계로하드웨어가합성된다. 다시말하면, 그래프의한노드가그대로하드웨어블록리소스하나로생성되는것이다. 그림 4(b) 에나타난바와같이 8개의데이타샘플을입력으로받아 8개의데이타샘플을출력하는 DCT1D 블록 1) 이하나밖에없기때문에 64 개의데이타샘플을받아 64개데이타샘플을출력하려면하나의 DCT1D 블록이순차적으로 8번수행되어야 1) 원래 Meyr 의연구에서는노드가한번수행될때마다출력단에는한개의데이타샘플만이생성된다. 따라서이예제에서 8개의데이타샘플을출력하기위해서는노드가 8번수행되어야한다. 그러나효율적인구현을위해서그림 3의 DCT1D 블록에 8개의다른출력단이있다고가정하였다. 한다. 만약에 DCT1D 블록의내부가파이프라인형태로구현되어있다면, 8번의순차적수행이파이프라인되어겹쳐서수행될수는있다. 이러한순차적구현에서는 64개의데이타샘플을모아두기위해 FIFO큐와 MUX 같은부가회로가필요하지만병렬구현에서의하드웨어크기와비교해서는매우미미한정도에불과하다. 이접근방식의어려운점은정밀한그래프분석 [18] 을통해서많은제어신호 (control signal) 들의타이밍을미리계산해야한다는점이다. 또하나의제약점은이러한타이밍계산과콘트롤러합성을위해모든하드웨어블록들이고정된수행시간만을가질수있다는점이다. Ade가연구한 GRAPE 시스템 [3,19,20] 또한하드웨어를순차적인방식으로구현한다. Meyr의방식과다른점이있다면각각의하드웨어블록들이그내부에로컬콘트롤러 (local controller) 를가지고있어복잡하게중앙콘트롤러 (central controller) 를구현할필요가없다는점이다 ( 그림 4(c)). GRAPE 시스템에서는이웃한블록들간에핸드셰이킹프로토콜 (handshaking protocol) 을사용하여각블록이언제수행할수있는지를판단한다. 이예제에서는 Transpose 블록이한번수행된후에 DCT1D 블록이순차적으로 8번수행되는데, 각수행마다핸드셰이킹에필요한제어신호 (control signal) 를반복적으로주고받아야한다. 따라서 GRAPE 시스템은노드의수행시간이고정되지않고가변적인경우에도문제없이잘수행된다는장점이있으나핸드셰이킹을사용하는노드간의비동기적통신 (asynchronous communication) 이수행시간을증가시키는단점을가지고있다. 또한데이타플로우그래프로표현한노드들의크기가작은경우에는구현에포함된 FIFO 버퍼들과로컬콘트롤러의크기를무시할수없다. 따라서최적화된 ASIC 설계에서는작은블록들간에위와같은분산제어 (distributed control) 와비동기적통신을사용하지않는경우가대부분이다. 그림 4에서 (a) 와 (b) 는병렬구현과순차구현의양극단을보여주고있다. 그러나그외에다른많은구현방식이존재할수있다. 그림 5에그중일부를소개하였다. 그림 5(a) 를보면그림 3의두 DCT1D 노드가하나의 DCT1D 리소스를공유하고있다. 이 DCT1D 리소스는 16번수행되는데, 8번은 column DCT를위해서, 8 번은 row DCT 연산을위해서수행된다. 이구현은성능은가장느리지만가장적은하드웨어면적을차지한다. 만약에더나은성능이필요하다면 column DCT와 row DCT 를위해리소스를각각따로할당하고그림 4(b) 와같이파이프라인형태로동시에수행할수있다. 그래도시각제약조건을맞추기어려운경우에는그림
236 정보과학회논문지 : 시스템및이론제 32 권제 5 호 (2005.6) 3. 제안하는하드웨어합성기법 그림 5 일반적으로사용되는 DCT의하드웨어구조 (a) 하나의 DCT1D 리소스사용 (b) 네개의 DCT1D 리소스사용 5(b) 에서각 DCT1D 노드에대해 DCT1D 리소스를두개씩할당한것처럼더많은리소스를할당하면된다. 본논문에서는기존연구에포함되었던완전병렬구현과완전순차구현을포함함과동시에앞에서설명한리소스공유와, 병렬과순차의중간형태의구현까지모두고려할수있는기법을제시하고자한다. 이기법을사용함으로써데이타플로우명세로부터자동생성될수있는하드웨어설계공간이넓어질수있다. 제어회로의설계에서는블록의수행시간이가변적인경우도포함하기위하여 [21] 에서제시한제어기법을그대로적용하였다. [21] 에서는데이타플로우의명세가멀티레이트인경우는고려하지않고데이타플로우그래프와일대일대응관계로하드웨어를생성하였지만, 본연구에서는멀티레이트로명세된데이타플로우가여러가지방식으로구현될수있도록자동화하는것을주내용으로하고있으며, 리소스를공유하는코드를생성하는내용까지포함하고있다. 아래의표 1에서는보다명확한이해를돕기위해서지금까지소개한각접근방식을비교하여정리하였다. 앞에서언급한내용이지만, 제안하는방법에서는분할단계로부터스케줄정보를얻는다. 그림 6은스케줄정보의한예를보여주고있는데, 그림 4(b) 의하드웨어아키텍쳐를얻기위한스케줄정보이다. 이는크게두부분으로이루어져있는데먼저리소스할당테이블 (Resource Allocation Table) 이기술되고그뒤에매핑 / 스케줄정보 (Mapping/Schedule Information) 가기술된다. 리소스할당테이블은단순히리소스타입의이름과그리소스의개수를열거한것이다. 그림 6을보면 Transpose와 DCT1D 리소스가각각두개씩있음을알수있다. 매핑 / 스케줄정보는노드의각인스턴스의리소스매핑과수행시간및타이밍정보를정의하고있다. 매핑 / 스케줄정보는또한루프 (Loop) 에의해계층적으로묶일수있는데, 자세한정보는다음의 BNF를통해구조적으로기술하였다. <schudule information> ::= <allocation table> <mapping_schedule information> <allocation table> ::= set of <allocation item> <allocation item> ::= <resource type name> <number of resources> <mapping_schedule information> ::= set of <mapping_ schedule item> <mapping_schedule item> ::= <instance mapping_ schedule> < loop mapping_schedule> <instance mapping_schedule> ::= <node name> <mapped resource number> <start timing> <execution time> <loop mapping_schedule> ::= loop <loop count> <start timing> <loop period> { <mapping_schedule information> } Transpose_1 1 17 1 을예로들어설명하면다음과같다. Transpose_1 노드의첫번째인스턴스는두 Transpose 리소스중에서두번째리소스 (Resource 표 1 데이타플로우명세로부터하드웨어합성하는방식비교 접근방식 Ptolemy Meyr의방식 GRAPE 제안하는방식 멀티레이트의구현 병렬구현 순차구현 순차구현 병렬 / 순차 / 하이브리드 리소스할당 블록간통신 복수할당 (multiple-resource allocation) 동기적레지스터버퍼사용 단일할당 (single-resource allocation) 동기적레지스터버퍼사용 단일할당 (single-resource allocation) 비동기적 FIFO 버퍼사용 복수 / 단일 / 공유할당 (multiple/single/shared allocation) 동기적레지스터버퍼사용 블록수행제어 중앙제어방식 중앙제어방식 분산제어방식 중앙제어방식 블록수행시간 고정 고정 가변 가변
빠른하드웨어 / 소프트웨어통합합성을위한데이타플로우명세로부터의하드웨어합성237 Number = 1) 를사용하고시작타이밍 (start timing) 은 17 수행시간 (execution time) 은 1 사이클임을의미한다. 만약하드웨어설계자가그림 5(a) 와같이하나의 DCT1D 리소스로공유하는구조로하드웨어를생성하고자한다면그림 6의내용에서다음과같이 DCT1D 리소스의개수를 1로바꾸고 DCT1D_1 노드가매핑된리소스를첫번째리소스 (0번리소스 ) 로바꾸어주기만하면된다. DCT1D 1 DCT1D_1 0 0 2 이는단하나의 DCT1D 리소스가할당되고, DCT1D_1 노드의모든여덟번의인스턴스들이 0번리소스로매핑됨을의미한다. 부가적으로설명하면 DCT1D_1 노드는루프 (Loop) 에의해여덟번수행되므로여덟개의인스턴스를가진다. 시작타이밍과수행시간에사용되는시간단위는클럭사이클 (clock cycle) 이다. 시작시각은루프안에서의상대적인시각을의미하므로루프안의맨처음에나오는매핑 / 스케줄정보의시작시각은 0으로시작되어야한다. Loop 8 1 2 { DCT1D_0 0 0 2 } 와같은내용이의미하는바는 DCT1D 노드의모든 (8개의) 인스턴스들은첫번째 (0번) 리소스를사용하고그리소스는수행시간이 2 사이클인데 8번연속적으로수행된다는것이다. 루프 (Loop) 명령의인자들이의미하는바는순서대로반복횟수, 시작시각, 반복의주기이므로, 이루프는 1에시작하여 2 사이클간격으로 8번반복수행된다. 그림 5(b) 와같이하드웨어를바꾸어생성하려면스케줄정보를 Loop 4 1 2 { DCT1D_0 0 0 2, DCT1D_0 1 0 2 } 와같이넣어주면된다. 이스케줄정보는 DCT1D_0 노드의첫번째, 세번째, 다섯번째, 일곱번째인스턴스는 0번리소스에, 두번째, 네번째, 여섯번째, 여덟번째리소스는 1번리소스에매핑되도록만들어준다. 그리고데이타플로우그래프는무한루프처럼반복수행되므로전체스케줄또한하나의루프로간주한다. 그림 6 그림 4(b) 의아키텍쳐를위한스케줄정보 제안하는하드웨어합성기법은주어진스케줄정보를가지고그에상응하는하드웨어아키텍쳐를합성해내는것이다. 그림 6의스케줄정보로부터그림 4(b) 의하드웨어가자동으로합성되는데, 이과정에필요한두가지핵심요소는콘트롤러합성과 MUX, 레지스터와같은부가회로들의합성이다. 먼저콘트롤러를만들기위해서두가지자료구조가필요한데, 하나는리소스제어를위해또하나는노드의출력버퍼를위해필요하다. 리소스제어를위해서는리소스입력단의 MUX제어신호와공유리소스의 start 신호 (start signal) 가필요한데스케줄정보를분석하여이리소스에매핑된인스턴스정보와각인스턴스들의시작및종료시간을정리하여만들어진다. 노드의출력버퍼제어신호는비교적간단한데, 어느리소스의출력데이타샘플을언제버퍼에담을지를스케줄정보를분석하여결정하면된다. 이내용들을구체적으로정리하면다음과같다. <resource start information> ::= set of <mapped instance start time> <resource input mux information> ::= set of <mapped instance input mux information> <mapped instance input mux information> ::= <input buffer name> <mapped instance start time> <mapped instance end time> <output buffer control information> ::= set of <output buffer assignment> <output buffer assignment> ::= <resource output signal name> <buffer latch timing> 위의내용에서리소스시작정보 (resource start information) 는각리소스별로매핑된인스턴스들의시작시간들을집합으로가지고있으며, 리소스입력단의 MUX 제어정보 (resource input mux information) 와출력버퍼제어정보 (output buffer control information) 는각포트별로정보가구성된다. MUX 제어정보의경우는매핑된각인스턴스들의입력버퍼이름과시작및종료시간을하나의자료구조로묶어서이들의집합으로구성하며, 출력버퍼의제어정보는각리소스출력의이름과그출력시각을하나의자료구조를묶어서이들의집합으로구성한다. 자료구조가다만들어지고나면이자료구조로부터 VHDL 코드가생성된다. 맨먼저카운터 (counter) 를사용해서루프 (Loop) 의제어신호들이생성된다. 그림 7(a) 는그림 4(b) 의 DCT1D 에대한버퍼, 루프, MUX
238 정보과학회논문지 : 시스템및이론제 32 권제 5 호 (2005.6) 를제어하는신호들의타이밍을보여준다. Loop0는가장상위수준에서의제어를담당하고나머지루프들은순서대로번호가매겨진다. Loop_Counter 신호는매클럭마다증가하며 Loop_IterNum 신호는매루프주기의마지막에한번씩증가한다. 그후에버퍼 /MUX의제어신호와각리소스의 start 신호 (start signal) 가생성된다. 이신호들의타이밍은루프제어신호 (Looping control signal) 에의해결정된다. 예를들면, DCT1D_0 의출력버퍼는 Loop1_IterNum = 0이고 Loop1_ Counter = 1일때데이타를로드한다. MUX와 start 신호들도같은방식으로제어되는데, MUX의경우는대상리소스가수행되는동안계속입력데이타의값을유지하고있어야하므로카운터값의범위에의해제어된다. 본설계환경에서생성하는제어신호들의연결구조는그림 7(b) 에나타나있으며, 제어신호들의 VHDL 코드는앞에서만든자료구조를바탕으로다음과같이생성된다. 스케줄에루프가존재하는경우는그림 7(a) 처럼루프의 Iteration조건까지반영하여시간조건문이보다복잡하게나타날수있으나다음의 VHDL 코드에서는이해를돕기위하여간단하게카운터 (Counter) 의값만을이용하여조건문을나타내었다.... elsif Counter = <latch timing_n> then <output buffer signal name> <= <resource output signal_n name>; end if; end if; end process; 하드웨어블록의수행시간이수행중에변하는경우에는최소수행시간을스케줄정보에기술하고블록내부로부터생성되는 done 신호 (done signal) 를콘트롤러가검사하도록한다. Done 신호가참이아닐때는콘트롤러가카운터값을계속같은값으로유지하면서 done 신호가참이될때까지기다리는방식으로동작한다. 이콘트롤러동작에관한자세한내용은 [21] 에소개되어있다. --<start signal code> <start signal name> <= '1' when Counter = <instance_1 start time> else '1' when Counter = <instance_2 start time> else... '1' when Counter = <instance_n start time> else '0'; (a) --<input mux code> <resource input signal name> <= <input buffer_1 name> when Counter >= <start time_1> and Counter <= <end time_1> else <input buffer_2 name> when Counter >= <start time_2> and Counter <= <end time_2> else... <input buffer_n name>; --<output buffer code> process(clk, rst) begin if rst = '1' then <output buffer signal name> <= (others => '0'); elsif rising_edge(clk) then if Counter = <latch timing_1> then <output buffer signal name> <= <resource output signal_1 name>; elsif Counter = <latch timing_2> then <output buffer signal name> <= <resource output signal_2 name>; (b) 그림 7(a) 타이밍다이어그램과 VHDL 코드 (b) 그림 4(b) 의 DCT1D 블록을위한제어신호의하드웨어구조 4. 블록타입그림 3에서사용된 DCT1D와 Transpose 블록은단순히조합회로 (combinational logic) 로구현되어있다. 따라서별다른제어신호를필요로하지않는다. 그러나
빠른하드웨어 / 소프트웨어통합합성을위한데이타플로우명세로부터의하드웨어합성239 블록들은 clock과 reset 신호를필요로하는레지스터를내부에가지고있는순차회로 (sequential logic) 으로구성될수도있다. 게다가각블록의수행시간은외부메모리접근이나조건부연산과같은동적인특성으로인해미리고정되어있지않을수도있다. 본논문에서제안하는설계환경에서는이러한블록들의성질을반영하여각라이브러리블록들의타입을 4가지로분류하였다. 덧셈기 (adder) 와같은경우는조합회로, 누산기 (accumulator) 와같이한 cycle이면수행이완료되는단사이클순차회로 (single-cycle sequential logic), 수행하는데여러사이클이소요되는다사이클순차회로 (multi-cycle sequential logic) 로나뉘며, 다사이클순차회로는수행시간이고정되어있는경우와수행시간이가변적인경우로다시나누었다. 다사이클순차회로는콘트롤러가 clock, reset, start 신호를넣어주어야하며, 가변수행시간다사이클순차회로는블록내부에서 done 신호를만들어서수행이종료되었음을알려주어야한다. 그림 8(a) 는네가지타입으로구성된예제를보여주고있다. 이예제는라이브러리블록들과생성된콘트롤러를통합하여그림 8(b) 와같은하드웨어로만들어진다. 그림 8(c) 에는예상되는제어신호들의타이밍을그려넣었다. 여기서는 A, B, C 각블록들의수행시간을각각 30, 20, 80이고, D의수행시간은가변적이라고가정하였다. 그러므로 D 블록의 done 신호는수행중에변할수있다. 모든경우에각블록들은 strict execution을가정한다. 다시설명하면, 각블록은모든입력데이타샘플들이유효한값을가진후에수행가능하며, 모든출력데이타샘플들의값이유효해진후에블록의수행을끝마친것으로본다. 이것은각입출력단에서명세한데이타샘플개수만큼입출력버퍼가필요함을의미한다. 반면에 Meyr의연구 [9] 에서는멀티레이트예제에서도한번에한개의데이타샘플만을입출력한다. 그림9의간단한예제를살펴보자. 제안하는방식에서는 Ramp 블록의출력데이타샘플들을저장하기위해 Add4 블록의입력버퍼를 4개할당한다. Meyr의방식에서는 Add4블록이 4번수행되므로한개의버퍼만이필요할것이다. 사실두접근방식은 Add4블록의내부구현에서도차이를보인다. Meyr의방식에서는 Add4 블록이내부상태레지스터를가지는순차회로로만들어져있다. 멀티레이트예제에대해 strict execution을가정하는것이버퍼면적에있어큰오버헤드를초래할때는 Meyr의방식과같은직렬적인 I/O (serial I/O) 구현이더좋다고할수있다. 이러한단점을극복하기위해서 FRDF(fractional rate dataflow) 모델 [6] 을사용한다. 이방식을사용하면똑같은알고리즘을기술하면서도 그림 8(a) 다양한타입을블록으로구성된 DFG의예 (b) 합성된하드웨어구조 (c) 제어신호들의예상타이밍 (a) (b) 그림 9 보통의데이타플로우명세 (a) 와 FRDF 명세 (b) 의하드웨어구현 Meyr 방식의 Add4블록의직렬적인 I/O(serial I/O) 로구현할수있다. 그림 9(b) 에같은알고리즘을기술한 FRDF 그래프와그하드웨어구현을묘사하였다. Add4 블록의출력단에있는 1/4이라는분수꼴의샘플레이트 (fractional sample rate) 는 Add4블록이 4번수행되는동안하나의데이타샘플만을출력으로내보낸다는것을의미한다. 다시설명하면, 위 Add4블록은매수행마다한개의입력을받고네번째수행마다한개의출력을내보낸다.
240 정보과학회논문지 : 시스템및이론제 32 권제 5 호 (2005.6) 5. 실험 실험에서도그림 3의예제를그대로사용하였다. 합성을위해서는 Synopsys Design Compiler를사용하였으며 clock 주기는 20ns로고정하였다. 실험결과, DCT1D 블록한개의수행시간 (propagation delay) 은 30.2ns로 2사이클을차지하였다. 본논문의접근방식의효율성을입증하기위해서그림 5(a) 와같은구조를가지는하드웨어를손으로직접작성하여비교하였다. 이구현은한개의 DCT1D리소스와 64 16비트레지스터를가지는 Transpose 메모리로구성되어있으며, 콘트롤러와 MUX, 카운터등과같은부가회로가포함되어있다. 그림 4에서소개한다른접근방식의합성결과들도표 2에비교하여놓았다. GRAPE 시스템의경우는구할수가없어서논문에소개되어있는방식을예상하여하드웨어를수동으로구현하였다. 그러므로실제 GRAPE 시스템의결과와는차이가있을수있음을미리밝혀둔다. 표 2를보면자동으로하드웨어를생성했을때, 버퍼와콘트롤러가생성규칙에따라보수적으로이루어지므로손으로생성한것보다조금더많은하드웨어면적을차지함을알수있다. 그림 10에는다양한하드웨어구현의성능 / 면적트레이드오프관계를볼수있도록그래프로나타내었다. 그림 5(a) 의예제를수동으로구현한것과자동으로구현것을표 2에서비교하여보면, 면적면에서는 21%, 성능면에서는 6% 정도의오버헤드를가지는것을확인할수있다. 이는버퍼를제어하는코드를생성할때에, 리소스가공유되는경우와루프를돌면서각기다른버퍼에결과를적는경우, 블록간의데이타레이트가 2대3 등으로서로맞지않는경우를일반적으로해결하기위하여, 각각의버퍼마다따로따로조건문을넣어제어하기때문이다. 그림 5(a) 의예에서는 DCT1D의 8개출력 그림 10 표 2의면적-수행시간그래프을모두하나의제어신호로제어할수있음에도불구하고자동생성된코드에서는이신호들이따로따로생성되어표 2에서와같이면적상의오버헤드를가지게되었다. 이러한경우는대부분의예제들에서발생할수있기때문에, 다음연구에서는같은조건들을검사하여제어코드를보다간결하게생성할계획이며이를통해보다최적화된결과를얻을수있을것으로기대하고있다. 성능면에서는, 안전한버퍼링과다음블록의수행을보장하기위해서자동생성할때블록사이에서 1 사이클의마진을두었기때문에, 그림 5(a) 의구현에서 2 사이클의차이가나게되었다. 또다른실험으로는 H.263 디코더알고리즘의일부를사용하였다. 이예제는 Dequantize, IDCT, MC(motion cmpensation) 블록을포함하고있다. 이명세 ( 그림 11) 에서는배열타입과사용자정의타입을사용하였으며자동으로하드웨어신호정의와포트매핑을위한코드, 콘트롤러등의모든부가회로를생성하였다. 그리고 MC 블록은수행중에프레임메모리접근을위한메모리접근회로가필요하기때문에블록정의시에메모리 Design type (number of DCT1D resource) Manual (1) 그림 5(a) Auto (1) 그림 5(a) Auto (2) 그림 4(b) Auto (4) 그림 5(b) Ptolemy(16) 그림 4(a) GRAPE (2) 그림 4(c) Area (gates) 표 2 실험결과 : 2 차원 DCT Clock period (ns) Latency Cycles Total (ns) Throughput (sample/ms) 31,431 20 32 640 1562.5 38,265 20 34 680 1470.6 53,252 20 34 680 2941.2 83,130 20 18 360 5555.6 242,944 20 4 80 12500.0 79,832 20 52 1040 2083.3
빠른하드웨어 / 소프트웨어통합합성을위한데이타플로우명세로부터의하드웨어합성241 Design Type Area (gates) 표 3 실험결과 (H.263 디코더 ) Latency (1 Macro Block) Clock period (ns) Cycles Total (us) Throughput (frame/ms) (CIF format) Manual 124,762 20 1170 23.40 108 Auto 186,084 20 1188 23.76 106 를접근하는데이타입출력포트의속성을 SRAM 으로하였다. 이속성은메모리접근에필요한포트를자동으로생성하고블록들간의프레임전달은메모리주소인포인터로만이루어지게만들어준다. 또한프레임데이타와 mode, dx, dy등의파라미터들은 FRDF로명세하여버퍼크기를줄이도록구현하였다. 이실험에서는그림 11의데이타플로우명세로부터자동생성된하드웨어와같은블록라이브러리로같은기능을수동으로구현한하드웨어를비교하였다. 표 3을통해서, 두하드웨어설계의성능은매우비슷하고자동으로생성된하드웨어가면적이조금더큰것을알수있다. 표 2와 3의내용에서본바와같이제안하는방법을통해서다양한하드웨어구현이스케줄정보파일만수정하면간단히자동으로생성될수있다. 그리고자동으로생성된하드웨어구현이질적으로수동설계에매우가까워졌다. 성능면에서는미미한수준의오버헤드를가지고있으며, 면적면에서는버퍼콘트롤러의오버헤드가존재하지만제어조건코드를자동생성후에손으로손쉽게최적화할수있으며, 이부분의자동화는가까운미래에이루어질것이다. 그림 11 H.263 디코더알고리즘일부의데이타플로우명세 6. 결론이논문에서는하나의데이타플로우명세로부터다양한하드웨어구조를합성하는방법을다루고있다. 이과정에서공유하드웨어리소스와루프 (Loop) 로이루어진스케줄을고려하였으며, 성능과면적면에서실제설계에적용할수있을만큼의하드웨어를자동으로생성하였다. 이논문에는포함되지않았지만시스템설계과 정에서하드웨어리소스의자동할당및스케줄이주요한이슈이며그과정은분할단계에서이루어진다. 이논문에서는그스케줄정보를바탕으로실제하드웨어를구현하는내용을다루었다. 실험예제로서는 2차원 DCT알고리즘과 H.263 디코더를사용하여제안하는기법이실제 VHDL코드를생성함을보여주었으며, 이 VHDL 코드들은 Synopsys 툴을통해검증하였다. 남은과제로서생성되는하드웨어면적을좀더줄이기위해버퍼콘트롤러를최적화하고버퍼들을공유하는방법이필요하며, 실험결과를보면자동생성오버헤드의대부분이이버퍼콘트롤러에기인하고있기때문에버퍼의최적화기법이적용될경우수동설계에거의근접할수있을것으로예상한다. 참고문헌 [1] Synopsys Inc., 700 E. Middlefield Rd., Mountain View, CA 94043, USA. COSSAP User s Manual : VHDL Code Generation. [2] J. T. Buck, S. Ha, E. A. Lee and D. G. Messerschmitt. Ptolemy: A framework for simulating and prototyping heterogeneous systems. Int l Journal of Computer simulation, special issues on "Simulation software development," vol.4, pp. 155-182, April, 1994. [3] M. Ade, R. Lauwereins, and J. A. Peperstraete. Hardware-software codesign with GRAPE. IEEE Int l Workshop on Rapid System Prototyping, pp. 40-47, June, 1995. [4] G. De Micheli. Synthesis and Optimization of Digital Circuits. New York, McGraw-Hill, Inc., 1994. [5] E. A. Lee and D. G. Messerschmitt. Synchronous data flow. Proc. of the IEEE, September, 1987. [6] H. Oh and S. Ha. Fractional rate dataflow model and efficient code synthesis for multimedia applications. ACM SIGPLAN Notice Vol. 37, pp. 12-17, July 2002. [7] H. Oh and S. Ha. Hardware-software cosynthesis of multi-mode multi-task embedded systems with real-time constraints. International Workshop on Hardware/Software Codesign, pp. 133-138, May 2002. [8] P. Zepter and T. Groker and H. Meyr. Digital receiver design using VHDL generation from data
242 정보과학회논문지 : 시스템및이론제 32 권제 5 호 (2005.6) flow graphs. Proceedings of the Design Automation Conference 1995. [9] J. Horstmannshoff and H. Meyr. Optimized system synthesis of complex RT level building blocks from multirate dataflow graphs. International Symposium on System Synthesis, pp. 38-43, Nov, 1999. [10] M. C. Williamson and E. A. Lee. Synthesis of parallel hardware implementations from synchronous dataflow graph specifications. In 30th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, California, USA, November 1996. [11] Y.-L. Lin. Recent Devleopments in High-Level Synthesis. ACM Transactions on Design Automation of Electronic Systems, Vol. 2, No. 1, pp 2-21, Jan. 1997. [12] D. W. Knapp. Behavioral Synthesis: Digital System Design Using the Synopsys Behavioral Compiler. Prentice Hall, 1996. [13] L. Semeria, K. Sato, and G. De Micheli. Synthesis of Hardware Models in C With Pointers and Complex Data Structures. IEEE Transactions on VLSI Systems Vol. 9, pp. 743-756, Dec. 2001. [14] L. Semeria and G. De Micheli. Resolution, Optimization, and Encoding of Pointer Variables for the Behavioral Synthesis from C. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems Vol. 20, pp. 213-233, Feb. 2001. [15] N. Vanspauwen, E. Barros, S. Cavalcante, and C. Valderrama. On the Importance, Problems and Solutions of Pointer Synthesis. 15th Symposium on Integrated Circuits and Systems Design, pp. 317-322, Sept. 2002. [16] F. Slomka, M. Dorfel, and R. Munzenberger. Generating Mixed Hardware/Software systems from SDL Specifications. 9 th International Symposium on Hardware/Software Codesign, pp. 116-121, April 2001. [17] O. Bringmann, W. Rosenstiel, A. Muth, G. Farber, F. Slomka, and R. Hofmann. Mixed Abstraction Level Hardware Synthesis from SDL for Rapid Prototyping. IEEE Int l Workshop on Rapid System Prototyping, pp. 114-119, June 1999. [18] J. Horstmannshoff, T. Grotker, and H. Meyr. Mapping multi-rate dataflow to complex RT level hardware models. In ASAP. IEEE, 1997. [19] J. Dalcolmo, R. Lauwereins, M. Ade. Code generation of data dominated DSP applications for FPGA targets. IEEE Int l Workshop on Rapid System Prototyping, pp. 162-167, 1998. [20] G. Bilsen, M.Engels, R. Lauwereins and J. Peperstraete. Cyclo-static dataflow. IEEE Transactions on Signal Processing Vol. 44, pp.397-408, Feb. 1996. [21] H. Jung, K. Lee, and S. Ha. Efficient hardware controller synthesis for synchronous dataflow graph in system level design. IEEE Transactions on VLSI Systems Vol. 10, pp. 423-428, August 2002. 정현욱 1998년 2월서울대학교컴퓨터공학과학사. 2000년 2월서울대학교컴퓨터공학과석사. 2000년 3월~현재서울대학교전기컴퓨터공학부박사과정. 관심분야는하드웨어- 소프트웨어통합설계, 시스템수준설계, 하드웨어자동합성 하순회 1985 년 2 월서울대학교전자공학과학사 1987 년 2 월서울대학교전자공학과석사 1992 년미국 UCB 전기컴퓨터공학과박사. 1993 년 ~1994 년현대전자근무. 1994 년 ~ 현재서울대학교컴퓨터공학부교수관심분야는하드웨어 - 소프트웨어통합설계, 내장형시스템을위한설계방법론