논문 06-31-4A-03 한국통신학회논문지 '06-4 Vol.31 No.4A 실시간시스템에서효율적인동적전력관리를위한태스크스케줄링알고리듬에관한연구 준회원이원규 *, 정회원황선영 * An Improved Task Scheduling Algorithm for Efficient Dynamic Power Management in Real-Time Systems Won-Gyu Lee* Associate Member, Sun-Young Hwang* Regular Member 요 약 배터리로동작하는휴대용임베디드시스템에서에너지소모는중요한설계파라미터이며, 동적전력관리는잘알려진저전력설계기법중의하나이다. 본논문에서는실시간시스템에서에너지를고려한태스크스케줄링알고리듬을제안한다. 제안한스케줄링알고리듬은시스템에여유시간이존재할경우장치중첩도가높은태스크가우선적으로수행되도록스케줄링하여장치의전력상태전환횟수를줄여준다. 전력상태전환횟수가줄어들경우상태전환에따른전력소모가감소하고, 동적전력관리의기회를더욱얻을수있다. 실험결과 EDF 알고리듬으로동작하는시스템에서동적전력관리를한경우와비교하였을때에너지소모가약 23% 감소하였다. Key Words : DPM, real-time scheduling, low-power systems ABSTRACT Energy consumption is an important design parameter for battery-operated embedded systems. Dynamic power management is one of the most well-known low-power design techniques. This paper proposes an online realtime scheduling algorithm, which we call energy-aware realtime scheduling using slack stealing (EARSS). The proposed algorithm gives the highest priority to the task with the largest degree of device overlap when the slack time exists. Scheduling result enables an efficient power management by reducing the number of state transitions. Experimental results show that the proposed algorithm can save the energy by 23% on average compared to the DPM-enabled system scheduled by the EDF algorithm. Ⅰ. 서론배터리로동작하는휴대용전자기기의설계에서배터리용량의한계로인해시스템에서사용될수있는에너지는한정되어있기때문에시스템의수명을최대한연장하기위해서는시스템의에너지소모를줄이는것이바람직하다. 휴대용전자기기가 고성능, 고집적화되어감에따라전력소모량이지수적으로증가하는반면에배터리의에너지용량은산술적인증가에그치고있어, 배터리자체개량보다는시스템의전력소모를줄이는저전력기법이중점적으로연구되고있다 [1, 2]. 저전력기법은크게정적인기법과동적인기법으로분류된다 [2]. 정적인기법은설계혹은컴파일 본연구는정보통신부및정보통신연구진흥원의대학 IT 연구센터육성지원사업의연구결과로수행되었음 * 서강대학교전자공학과 CAD & Embedded System 연구실 (hwang@sogang.ac.kr) 논문번호 :KICS2005-12-490, 접수일자 :2005 년 12 월 8 일, 최종논문접수일자 : 2006 년 3 월 28 일 393
한국통신학회논문지 '06-4 Vol.31 No.4A 시에적용하는것으로전력소모가적도록하드웨어를합성하는방법, 소프트웨어를컴파일할때코드의재구성을통해전력소모가적도록하는방법등이있다. 동적인기법은실행시간에적용하는것으로작업부하량의변동을이용하여시스템의전력소모를줄여준다. 정적인기법을통해서도시스템의에너지소모를상당히줄일수있으나시스템이실행되는가운데계속해서변하는수행환경에대처할수없기때문에최근에는동적인기법에더욱초점이맞추어지고있다 [3]. 동적전력관리 (Dynamic Power Management: DPM) 는시스템의실행시간중작업부하량의변동을이용하여하드웨어의동작전압을동적으로조절하는방법이다. 프로세서의경우동적으로전압과동작주파수를변경하여전력소모를줄이는기법을사용하는동적전압조절 (Dynamic Voltage Scaling: DVS) 이제안되었다. Transmeta의 Crusoe 프로세서 [4] 와 Intel의 Xscale 프로세서 [5] 는 DVS를지원하기위해여러동작전압을제공한다. 동적전력관리는하드디스크나네트워크카드또는디스플레이장치와같은입출력장치의전력소모를줄일수있다 [6]. 입출력장치는프로세서에비해적은전력상태를제공하며전력상태전환시긴시간을요구한다. 동적전력관리는입출력장치가사용되지않는 idle 상태에있을때저전력상태인 sleep 상태로전환하여전력소모를줄일수있다. 최근에는운영체제수준에서동적전력관리를하려는연구가주목을받고있다 [7]. 운영체제는시스템자원과실행되는태스크에대한총체적인정보를알고있어하드웨어수준에서의동적전력관리보다사용하기편리하고유연하므로, 보다효율적인전력관리에대한결정을통해더욱효율적으로에너지를감소시킬수있다. 전력관리기능이포함된시스템의설계주기를단축하기위해 Intel, Microsoft, Toshiba가함께전력관리기능의표준화작업을하였으며수행결과로 ACPI(Advanced Configuration and Power Interface) 가제안되었다 [8]. ACPI는전력관리자와입출력장치나 VLSI 칩과같은하드웨어장치사이의인터페이스를유연성있게정의한다. 동적전력관리기법에있어서중요한문제의하나는마감시간 (deadline) 을지키면서전력소모를최소화하는것이다. 임베디드시스템의경우대부분마감시간제약조건이존재하는실시간시스템이며, 동적전력관리를적용할경우전력상태전환 에따른시간적오버헤드가존재하기때문에마감시간을어기지않도록주의를하여야한다. 본논문의구성은다음과같다. Ⅱ절에서는기존의동적전력관리에대한연구에대해설명하고, Ⅲ절에서는제안한에너지를고려한실시간스케줄링알고리듬 (EARSS) 에대하여자세히설명한다. Ⅳ 절에서는제안된알고리듬을 EDF 알고리듬과비교하며, 끝으로 Ⅴ절에서는결론을제시한다. Ⅱ. 관련연구 CMOS 회로의전력소모는동적전력 (dynamic power) 소모가대부분이다. 동적전력소모는공급전압의제곱에비례하기때문에공급전압을낮추는것은전력소모를줄이는데매우효과적인방법이다. DVS 기법은태스크의동작상태를살펴가면서프로세서의클록과전압을조절하여에너지소모를줄인다. 실시간시스템의경우, 각태스크의실제수행시간은최대수행시간 (Worst Case Execution Time: WCET) 보다작은경우가많으며이로인해작업부하량변동에따른여유시간 (slack time) 이발생한다. 동적전압조절알고리듬은이여유시간을활용하여가변전압프로세서 (variable voltage processor) 의동작전압과동작주파수를낮추어줌으로써에너지소모를줄인다 [9, 10]. 프로세서는여러동작전압을제공하는반면입출력장치는보통동작상태와 sleep 상태의두가지전력상태를제공한다. 장치 가 sleep 상태에서동작상태로의전환하는시간을, 동작상태에서 sleep 상태로의전환하는시간을 로표현한다. 또한 sleep 상태에서동작상태로전환할때소모되는전력을, 동작상태에서 sleep 상태로전환할때소모되는전력을 로표현하며, 동작상태에서소모되는전력을, sleep 상태에서소모되는전력을 로표현한다. 입출력장치는특성상전력상태전환시시간과전력이많이필요하다. 입출력장치의전력상태를부적절하게전환하게되면오히려입출력장치에서의에너지소모가더늘어날수있다. 만약입출력장치 의 idle 시간 가 와 의합보다작다면입출력장치는 sleep 상태에있지못하게된다. 이경우입출력장치의전력상태를전환하지않는것이오히려에너지를덜소비하게되는데, 전력상태를언제전환할것인가에대한기준으로 break-even 394
논문 / 실시간시스템에서효율적인동적전력관리를위한태스크스케줄링알고리듬에관한연구 그림 1. breakeven time 에대한설명. (a) 와 (b) 에서에너지소모가같게되는시간을 breakeven time 이라고한다. time 가쓰인다 [11]. 그림 1은 breakeven time의개념을제시한다. 여기서 는식 (1)~식(3) 으로부터구할수있다. (1) (2) (3) 입출력장치에대한동적전력관리알고리듬의대부분은비실시간시스템에서입출력장치의전압을조절한다. 입출력장치에대한동적전력관리알고리듬은크게 timeout 기반방식, predictive 방식, stochastic 방식으로분류된다 [11-14]. Timeout 기반의동적전력관리 [12] 알고리듬은입출력장치가일정시간동안 idle 상태를유지하면장치를 sleep 상태로전환시키는방식으로, 장치는다음요청이있기전까지 sleep 상태에머무른다. 이때 timeout은고정된값으로설정하거나동적으로변경할수있다. 이알고리듬은간단하므로프로세서나모니터, 하드디스크등에적용된다. 이알고리듬의단점은 timeout 시간동안전력을소비하고있으므로에너지를낭비한다는점이다. Predictive 동적전력관리알고리듬 [11, 13] 은장치의 idle 시간을예측하여그길이가 breakeven time보다길면장치의전원을차단하는방식으로, 이알고리듬은 idle 주기가시작되면장치의전원을바로차단하므로위의 timeout 기반에서와같은에너지낭비가없다. 이알고리듬은 idle 시간에대한정확한예측을필요로하며, 예측방식은오프라인방식과온라인방식으로나뉜다. 오프라인방식은시스템이실행을시작하기전에과거의정보로부터 idle 시간을예측하고, 온라인방식은시스템이실행중에 idle 시간을예측을한다. Srivastava [13] 는과거의장치 사용내역을오프라인으로분석하여 idle주기를예측하였다. Hwang과 Wu [11] 는과거의 idle 시간에대한기하급수적가중평균 (exponentially weighted average) 을온라인으로계산하여 idle 주기를예측하였다. Stochastic 동적전력관리알고리듬 [14] 은시스템을확률적으로모델링하여입출력장치의전력스케줄을구하는방식으로, 입출력장치, 장치사용요청, 전력관리자등을 Markov chain으로모델링하여시스템의에너지소모가최소가되도록입출력장치의전력상태를결정한다. 이들알고리듬은비실시간시스템에서에너지소모를상당히줄일수있으나마감시간제약조건을보장하지못하므로실시간시스템에서는사용될수없다. 실시간시스템에서는마감시간제약조건을고려한새로운전력관리알고리듬이필요하다. Swaminathan [15] 은태스크에대한 lookahead를이용한실시간동적전력관리알고리듬을제안하였다. 여기서는미리결정된태스크스케줄과입출력장치사용목록을입력받는다. 실시간시스템에서는마감시간을만족시키기위하여, 장치의전력상태전환을하기전에미래에수행될태스크의장치사용목록을살펴보아야한다. 저자는미리살펴봐야하는태스크의최소개수를 lookahead라정의하고, 이를사용하여스케줄링시각에각장치의전력상태를결정하였다. 이알고리듬은시스템의에너지를상당히줄일수있었으나, 태스크의스케줄링과전력관리알고리듬이독립적이기때문에에너지소모를줄이는데한계가있다. 이한계를해결하기위해같은저자는최대장치중첩 (Maximum Device Overlap: MDO) 을이용한오프라인태스크스케줄링알고리듬을제시하였다 [16]. 장치중첩은현재 job 에서사용하는장치중인접한 job이사용하는장치의개수이다. 이알고리듬은우선 EDF(Earlist Deadline First) 나 RM(Rate Monotonic) 스케줄링알고리듬으로가능한스케줄 (feasible schedule) 을구한다. EDF는마감시간이가장빠른 job을먼저수행되도록스케줄하고, RM은주기가가장작은 job을먼저수행되도록스케줄한다. 제안된알고리듬은미리계산된스케줄을장치중첩이최대가되도록 job을스왑하여스케줄을변경한다. 위알고리듬은오프라인으로스케줄을결정하기때문에, 시스템실행환경이변하거나새로운태스크가추가되는경우시스템이동작할수없으므로유연성이떨어진다. 395
한국통신학회논문지 '06-4 Vol.31 No.4A Ⅲ. 제안된 EARSS 알고리듬본절에서는제안된에너지를고려한실시간스케줄링알고리듬 (EARSS) 에대하여자세히설명한다. 제안된스케줄링알고리듬은시스템에존재하는여유시간을활용하여에너지를줄일수있다. 3.1 용어및문제정의시스템에서스케줄되고수행되는기본단위를 job이라하고, 특정한시스템함수를구성하는관련된 job의집합이태스크이며, job이수행가능하게된시각이 release time이고, 실시간시스템의특성상 job의실행이끝나야하는시각을마감시간이라정의한다. Job의 release time부터수행을끝마치는시각까지의시간을응답시간, 특정 job에허용되는응답시간의최대값을상대마감시간 (relative deadline) 이라정의한다. 개의태스크로이루어진태스크집합 이존재할때 인각각의태스크에대해주기는, 마감시간은, 최대수행시간은, 태스크가사용하는장치목록을 로표현한다. 모든태스크가가지는주기의최소공배수를 hyperperiod라정의하고, 각태스크의상대마감시간은주기와같다고가정한다. Job 는주기 의시간중 의시간동안프로세서를사용하고그비율이이용도 (utilization) 가되며, 이용도는 가된다. 시스템이용도 (system utilization) 은시스템에존재하는모든태스크의이용도를합친값이다. 또한앞서정의한태스크를수행하는시스템은 개의입출력장치 를사용하며, 각각의장치 는두전력상태 (sleep 상태와동작상태 ) 를지원한다고가정한다. 각장치 가 sleep 상태에서동작상태로의전환하는시간을, 동작상태에서 sleep 상태로의전환하는시간을 로표현한다. 또한 sleep 상태에서동작상태로전환할때소모되는전력을, 동작상태에서 sleep 상태로전환할때소모되는전력을 로표현하며, 동작상태에서소모되는전력을, sleep 상태에서소모되는전력을 로표현한다. 입출력장치는동작상태에있을때만 job을수행할수있으며, job이수행을시작하기전에 job에의해사용되는모든입출력장치는동작상태로되어있어야한다. 이때입출력장치 에의해서소 모되는에너지는식 (4) 와같다. (4) 이때 은입출력장치 가전력상태를전환한총횟수이며, 는 가동작상태로있던총시간, 그리고 는저전력상태로있던총시간이다. 본논문에서는다음과같이문제를정의한다. 입출력장치 의집합을사용하는실시간태스크 의집합이존재하고태스크 가소모한에너지를 라고할때, 모든태스크들이마감시간을만족하면서 가최소가되도록하는태스크의스케줄을 구한다. 3.2 알고리듬의동기주기가 인하나의태스크가존재하며, 이태스크는하나의입출력장치를사용한다고가정한다. 태스크의마감시간은주기와일치한다고할때, EDF(Earliest Deadline First) 스케줄링알고리듬으로스케줄을하게되면그림 2 (a) 와같이시스템이동작하게된다. 운영체제에서동적전력관리기능을지원해준다고가정하면그림 2 (b) 와같이입출력장치의전압이변화하게된다. 입출력장치의경우전력상태를전환 (shutdown/wakeup) 할때동작상태에서소모하는전력보다더욱많은전력이소모되며전환시간도상당하기때문에되도록전력상태의변화가적게일어나도록하는것이에너지소모를줄이는데에효과적이다. 따라서, 새로운 job 이 release 되었을때, 입출력장치가 idle 상태에있고시스템여유시간 (slack) 이존재한다면, 그 job 의수행을여유시간만큼연기해주는것이효과적이다. 반대로새로운 job이 release 되었을때, 입출력장치가동작상태에있다면전에수행되던 job 이끝나고바로이어서새로운 job을수행하는것이효과적이다. 이런아이디어를적용하여스케줄링을하게되면그림 3 (a) 와같이시스템이동작하게될것이며, 그림 3 (b) 와같이입출력장치의전력상태변화가줄어들게된다. 주기적인태스크의주기를 15, 최대수행시간 (WCET) 을 3이라하자. 태스크가사용하는입출력장치가전력상태를전환할때소모하는전력을 6, 396
논문 / 실시간시스템에서효율적인동적전력관리를위한태스크스케줄링알고리듬에관한연구 시간계산이수행되는시각을 로표시하며, 의시각에서 job 의여유시간을 로표시한다. 시스템의여유시간 는각 job의 중최소값으로정의한다. Hyperperiod가시작될때먼저 hyperperiod내에있는모든 job 에대해초기여유시간 을구해야하며그수식은식 (5) 와같다. 그림 2. EDF 알고리듬으로스케줄링된시스템에동적전력관리를적용한경우. (a) 스케줄링결과. (b) 입출력장치의전력상태변화 (5) 시스템이동작하면서각 job의여유시간은변하게된다. 실행중에여유시간을계산하기위해서는다음과같은과거의시스템정보를저장해야한다. 총 idle 시간 : hyperperiod의시작시점이후로발생한시스템 idle 시간의총합 실행시간 : hyperperiod내의모든 job 의수행된시간 그림 3. 제안된 EARSS 알고리듬으로스케줄링된시스템에동적전력관리를적용한경우. (a) 스케줄링결과. (b) 입출력장치의전력상태변화 동작상태에있을때소모하는전력을 3, idle 상태에서소모하는전력은 0이라고하자. 또한 wakeup 시걸리는시간을 3, shutdown시 1.5의시간이걸린다고하자. 이러한조건으로 EDF 스케줄링알고리듬을적용한그림 2와같은시스템에서 3 주기동안에너지소모를계산해보면 108 unit이된다. 하지만제안된 EARSS 스케줄링알고리듬을적용한그림 3과같은시스템에서 3 주기동안에너지소모를계산해보면 64 unit이된다. 이예에서제시한바와같이스케줄링단계에서동적전력관리를고려할때상당한에너지이득을기대할수있다. 3.3 여유시간 (slack time) 계산본논문에서시스템의여유시간은시스템의어떠한 job도마감시간을어기지않으면서현재시스템의실행을연기시킬수있는최대시간으로정의한다. 여유시간을계산할때각각의 job이어느태스크에속하는지는무시한다. Hyperperiod 내에존재하는모든 job의수가 개라고할때, 각각의 job을 라고표시한다. Job 의마감시간을 라하고, job 의마감시간을 라한다. 임의의두 job에대해 이면, 이도록마감시간순서대로 job을나열한다. 여유 미리계산된초기여유시간은위의정보를고려하지않았기때문에이를반영하여여유시간을재계산해주어야한다. 위의정보를이용하여 에구한각 job의여유시간은식 (6) 이된다. (6) 시스템의여유시간은각 job의여유시간중최소값이므로식 (7) 이된다. (7) 실시간시스템에서비주기적인 (aperiodic) 태스크에대한평균응답시간을줄이기위하여여유시간스틸링 (slack stealing) 기법을사용한다 [17]. 여유시간스틸링은시스템에여유시간이존재할경우마감시간이존재하지않는비주기태스크가실행되도록하여비주기태스크의평균응답시간을줄인다. 이때여유시간은식 (8) 과같이구한다. 는비주기태스크에게빼앗긴총시간이다. (8) 본논문의알고리듬에서는비주기태스크에의해여유시간을빼앗긴것이아니기때문에 와 는같은의미이다. 따라서여유시간을식 397
한국통신학회논문지 '06-4 Vol.31 No.4A (6) 과같이구한다. 3.4 EARSS 알고리듬 EDF 스케줄링알고리듬은가장마감시간이빠른 job이수행되도록스케줄하며, 대기큐 (ready queue) 에 job이존재하는한 job의수행을연기하지않는다. 제안된 EARSS 스케줄링의경우현재시스템에서수행을끝마친 job이입출력장치 를사용하였고시스템에여유시간이존재한다면, 마감시간이가장빠른 job을스케줄하는대신대기큐에서장치 를사용하는 job을선택하여여유시간동안실행한다. 반대로새로운 job이 release되어스케줄러가호출되었는데장치 가 idle 상태에있고시스템에여유시간이존재한다면, idle 상태를최대한유지하기위하여 job의수행을여유시간만큼연기한다. 이런방법으로입출력장치의전력상태전환횟수를최소화하여에너지의소모를줄인다. 하나의입출력장치관점에서보면장치의현재상태를최대한유지하도록하여장치의전력상태전환횟수를최소화함으로써전력소모를감소시킬수있으나, 시스템의여러입출력장치를사용하며수행되는 job의관점에서보면장치사용목록이가장비슷한 job을연달아스케줄해주어장치전체의전력상태전환횟수를최소화한다. 따라서시스템에여유시간이존재할때가장빠른마감시간을가진 job의수행을뒤로미루고대기큐에서장치중첩 (device overlap) 이가장큰 job을여유시간동안수행한다. 여유시간이 0이되면다시가장빠른마감시간을가진 job으로스위칭해주어마감시간을위반하지않도록한다. 입출력장치의경우전력상태전환시간및전환시소모되는전력의양이모두다르기때문에단지장치중첩의개수가가장많은 job으로여유시간을빼앗는방법은효율성이떨어진다. 전환시간과전환시소모되는전력이큰장치일수록전력상태전환이적게일어나도록해주어더욱큰에너지이득을기대할수있다. 따라서장치고유의전력소모특징을표현하기위하여식 (9) 와같이상태전환전력특성 (state transition power characteristic) 를정의한다. 는동작상태전력을나타낸다. 시스템에여유시간이존재할경우전력소모를줄일수있는 job을대기큐로부터선택하여스케줄링을해주게되는데이때선택의기준으로장치중첩도 (degree of device overlap: ) 를사용하며식 (10) 과같이정의한다. 양방향중첩인경우 단방향중첩인경우 중첩이없을경우 (10) 그림 4에서 job 가실행을마치는시점을스케줄링시간이라고하고, 여유시간후에실행될 job 을 로, 장치중첩도를구하고자하는 job을 이라표현한다. 와 가입출력장치 를사용하며 이 를사용한다면장치 는계속동작상태를유지할수있다. 반대로 와 가입출력장치 를사용하지않으며 도 를사용하지않는다면장치 는계속 sleep 상태를유지할수있다. 이와같이여유시간을빼앗는 job이전후에존재하는 job과같은장치를사용한다면양방향중첩이라고표현한다. 입출력장치 가양방향중첩이라면상태전환이일어나지않으므로중첩도가가장높은경우이며 2의가중치를준다. 같은방식으로 와 중하나와장치의사용이겹치는경우단방향중첩이라하며, 상태전환이한번일어나므로양방향중첩가중치의반에해당하는 1의가중치를준다. 양방향으로모두중첩이없을경우 -2의가중치를준다. 중첩이없을경우는여유시간을빼앗는 job에의해상태전환이두번일어나게되고, 오히려에너지소모를증가시킬가능성이있기때문에 -2의가중치를주어장치중첩도를떨어뜨린다. 그림 5는제안된 EARSS 알고리듬의 pseudo 코드를보인다. 스케줄러가호출되면식 (5)~식 (7) 을 J i Slack J slack J k (9) Scheduling instance 그림 4. 장치중첩도계산을위한표현 398
논문 / 실시간시스템에서효율적인동적전력관리를위한태스크스케줄링알고리듬에관한연구 Scheduler () { Compute slack ; if ( ) perform EDF_schedule; else perform EARSS_schedule; } 표 1. 실험에쓰인장치목록 (W) (W) (W) (W) (sec) (sec) HDD [18] 0.95 0.13 0.54 1.61 0.67 2.72 1.47 DSP [19] 0.63 0.2 0.4 0.4 0.5 0.5 0.63 Flash [20] 0.125 0.001 0.05 0.05 0.01 0.01 0.4 EARSS_schedule () { if (system is in idle state) Keep in idle state until ; else { Find a job with max value; if () perform EDF_schedule; else Schedule the job with max value until ; } 그림 5. Pseudo 코드 이용하여시스템에존재하는여유시간을계산한다. 여유시간이 보다적을경우마감시간이가장빠른 job이수행되도록한다. 여유시간이 보다크면이를활용하기위하여제안된 EARSS_Schedule 을호출한다. 제안된 EARSS 알고리듬은스케줄링시점전에수행되던 job이없고각입출력장치도 sleep 상태에있었다면여유시간동안새로운 job의수행을연기한다. 스케줄링시점전에수행되던 job 이있다면식 (9) 와식 (10) 을이용하여장치중첩도가가장높은 job이여유시간동안수행되도록한다. 만약최대장치중첩도가 0보다작다면여유시간을빼앗는것이오히려에너지소모를증가시킬수있기때문에마감시간이가장빠른 job이수행되도록한다. Ⅳ. 실험제안된 EARSS 알고리듬의에너지효율성을평가하기위하여 C++ 로시뮬레이터를구현하여사용하였다. 보다현실적인시뮬레이션환경을구축하기위하여입출력장치는 Fujitsu사의하드디스크 [18] 와 TI사의 DSP [19], 그리고 SST사의 flash [20] 를모델링하였다. 표 1은각장치의동작상태전력 ( ) 과 sleep 상태전력 ( ), shutdown과 wakeup시의전력 ( 와 ), 그리고전력상태전환시소모되는시간 ( 와 ) 을보인다. 장치의전력소모특징 그림 6. 시뮬레이터의구조을표현하기위해정의한상태전환전력특성 도함께표시하였다. 값의경우의도한바와같이상태전환시전력과시간이많이소모되는장치일수록큰값을가지는것을확인할수있다. 그림 6 은시뮬레이터의구조를보인다. 서비스요청기는시뮬레이터에서사용되는태스크를생성하고생성된 job은시스템의큐 (Job Queue) 에입력된다. 스케줄러는시에존재하는여유시간을계산하고큐에대기중인 job에대해스케줄링을수행하며, 스케줄링결과를전력관리자 (Power Manager) 에게넘겨준다. 전력관리자는스케줄링결과를받아각입출력장치의전력상태를조절한다. 전력관리자는입출력장치에게 GO_TO_SLEEP과 GO_TO_ACTIVE 명령을보낸다. GO_TO_SLEEP 명령은입출력장치의전력상태를 sleep 상태로전환하며, GO_TO_ACTIVE 는장치의전력상태를동작상태로전환한다. 실험에사용된태스크의집합과입출력장치사용목록은무작위로생성되었다. 각태스크는하나이상의입출력장치를사용한다고가정하였으며시스템이용도 (system utilization) 는 20% 부터 90% 까지변화시키며알고리듬의성능을평가하였다. 100 개의태스크집합에대해시뮬레이션을수행하였으며, 시뮬레이션결과의평균값으로알고리듬을평가하였다. 399
한국통신학회논문지 '06-4 Vol.31 No.4A 표 2. 실험결과 System Utilization (%) EDF 적용시에너지소모 (J) EARSS 적용시에너지소모 (J) 감소율 (%) 20 160.4 103.7 35.3 30 166.4 119.1 28.4 40 172.4 133.7 22.5 50 182.7 142.2 22.2 60 184.0 145.3 21.1 70 194.0 150.0 22.7 80 195.4 154.8 20.8 90 201.4 165.0 18.1 평균감소율 23.6 제안된알고리듬은장치의전력상태전환횟수를줄여줌으로써에너지소모를줄인다. 제안한태스크스케줄링알고리듬은스케줄링시간에시스템에존재하는여유시간을계산하여시스템이 idle 상태로있었다면여유시간만큼 idle 시간을유지하고, job 이실행되고있었다면대기큐에서장치중첩도가가장높은 job을여유시간동안스케줄해주어에너지소모의감소를가능하게한다. 시뮬레이션을통한실험결과, EDF 알고리듬으로스케줄링된시스템에서동적전력관리를적용한경우에비해서평균적으로약 23% 에너지소모가감소하는것을확인할수있었다. 참고문헌 Energy consumption (J). 300 250 200 150 100 50 0 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 System utilization (%) EDF EARSS Non-DPM 그림 7. EDF와 EARSS의비교표 2는 EDF로스케줄링된시스템에서동적전력관리를수행했을때소모되는평균에너지와제안된 EARSS 알고리듬으로스케줄링된시스템에서동적전력관리를수행했을때소모되는평균에너지를보인다. 그림 7은표 2의결과를그래프로보인다. 표 2를통해제안한알고리듬으로동작하는시스템이 EDF로동작하는시스템에비해약 23% 정도에너지소모가적은것을볼수있다. 표 2와그림 7을통해시스템의이용도가높아짐에따라에너지소모가커지는것을확인할수있으며, 시스템의이용도가높아짐에따라에너지감소율이줄어드는것을확인할수있다. 이는시스템의이용도가높아지면그만큼동적전력관리를수행할수있는기회가줄어드는것을의미한다. Ⅴ. 결론본논문에서는실시간시스템에서여유시간이존재할경우장치중첩도가높은 job을우선적으로수행하는태스크스케줄링알고리듬을제안하였다. [1] A. Chandrakasan and R. Brodersen, Low Power Digital CMOS Design. Kluwer Academic Pub., 1995. [2] J. Rabaey and M. Pedram, Eds., Low Power Design Methodologies. Kluwer Academic Pub., 1996. [3] L. Benini and G. De Micheli, Dynamic Power Management: Design Techniques and CAD Tools. Kluwer Academic Pub., 1997. [4] Crusoe processor. http://www.transmeta.com/crusoe/ [5] Xscale Processor. http://developer.intel.com/ design/intelxscale/index.htm [6] L. Benini, A. Bogliolo, and G. De Micheli, A survey of design techniques for system-level dynamic power management, IEEE Trans. Computer-Aided Design, vol. 8, no. 3, pp. 299-316, June 2000. [7] Y. Lu, L. Benini, and G. De Micheli, Power aware operating systems for interactive systems, IEEE Trans. VLSI Systems, vol. 10, no. 2, pp. 119-134, April 2002. [8] Advanced Configuration and Power Interface (ACPI) http://www.acpi.info [9] D. Shin and J. Kim, Intra-task voltage scheduling on DVS-enabled hard real-time systems, IEEE Trans. Computer-Aided Design, vol. 24, no. 10, pp. 1530-1549, Oct. 2005. [10] J. Seo, T. Kim, and J. Lee, Optimal intra-task dynamic voltage scaling technique 400
논문 / 실시간시스템에서효율적인동적전력관리를위한태스크스케줄링알고리듬에관한연구 and its practical extensions, IEEE Trans. Computer-Aided Design, vol. 25, no. 12, pp. 1-9, Dec. 2005. [11] C. Hwang and A. C.-H. Wu, A predictive system shutdown method for energy saving of event-driven computation, ACM Trans. Design Automation of Electronic Systems, vol. 5, no. 2, pp. 226-241, 2000. [12] R. Golding, P. Bosh, and J. Wilkes, Idleness is not sloth, in Proc. Winter USENIX Technical Conf., pp. 201-212, 1995. [13] M. Srivastava, A. Chandrakasan, and R. Brodersen, Predictive system shutdown and other architectural techniques for energy efficient programmable computation, IEEE Trans. VLSI Systems, vol. 4, no. 1, pp. 42-55, Mar. 1996. [14] L. Benini, A. Bogliolo, G. Paleologo, and G. De Micheli, Policy optimization for dynamic power management, IEEE Trans. Computer-Aided Design, vol. 18, no. 6, pp. 813-833, June 1999. [15] V. Swaminathan and K. Chakrabarty, Energyconscious, deterministic I/O device scheduling in hard real-time systems, IEEE Trans. Computer-Aided Design, vol. 22, no. 7, pp. 847-858, July 2003. [16] V. Swaminathan and K. Chakrabarty, Pruning based, energy-optimal, deterministic I/O device scheduling for hard real-time systems, ACM Trans. Embedded Computing Systems, vol. 4, no. 1, pp. 141-167, Feb. 2005. [17] J. W. S. Liu, Real-Time Systems. Prentice- Hall: Englewood Cliffs, 2000. [18] Fujitsu, MHL2300AT Hard Disk Drive Product Manual. http://www.fujitsu.com/downloads/au/mhl_mhm2_2.5inch_ide.pdf [19] TMS320C6411 Power Consumption Summary. http://focus.ti.com/lit/an/spra373a/ spra373a.pdf [20] SST multi-purpose flash SST39LF020. http:// www.sst.com/downloads/datasheet/ S71150.pdf 이원규 (Won-Gyu Lee) 준회원 2004년 2월서강대학교전자공학과졸업 2006년 2월서강대학교전자공학과석사학위취득 2006년 3월 ~ 현재삼성전자근무중 < 관심분야 > 저전력설계, 시스템수준설계황선영 (Sun-Young Hwang) 정회원 1976년 2월서울대학교전자공학과졸업 1978년 2월한국과학원전기및전자공학과공학석사취득 1986년 10월미국 Stanford 대학교전자공학박사학위취득 1976년 ~1981년삼성반도체 ( 주 ) 연구원, 팀장 1986년 ~1989년 Stanford대학 Center for Integrated Systems 연구소책임연구원및 Fairchild Semiconductor Palo Alto Research Center 기술자문 1989년 ~1992년삼성전자 ( 주 ) 반도체기술자문 2002년 4월 ~2004년 3월서강대학교정보통신대학원장 1989년 3월 ~ 현재서강대학교전자공학과교수 < 관심분야 > SoC 설계및 framework 구성, CAD시스템, Com. Architecture 및 DSP System Design 등 401