논문 10-35-11-07 한국통신학회논문지 '10-11 Vol.35 No.11 멀티프로세서임베디드시스템에서여유시간예측에의한저전력태스크스케줄링 준회원서범식 *, 정회원황선영 * An Energy-Efficient Task Scheduling Algorithm for Multi Processor Embedded System by Laxity Estimation Beom-Sik Suh* Associate Member, Sun-Young Hwang* Regular Member 요약 본논문은멀티프로세서임베디드시스템에서사용하는어플리케이션을구성하는태스크를수행하는데필요한전력과태스크간의의존성에의해서발생하는통신비용을감소시킬수있는스케줄링알고리듬을제안한다. 제안된알고리듬은기존알고리듬에서는통신비용은고려하였으나스케줄링단계에서는동적전력관리결과를고려하지않는점을보완하여스케줄링단계에서여유시간 (Laxity) 사용을예측하여동적전압관리의효율을높이는방법을사용한다. 이를통해복잡한멀티미디어어플리케이션에동적전력관리를적용하여수행시에너지효율을높였다. 실험결과멀티미디어어플리케이션인 HD MPEG4, MotionJPEG codec, MP3, Wavelet 프로그램을멀티프로세서환경에서제안된알고리듬을이용하여저전력스케줄링결과기존방식에비해평균 11.2% 의에너지감소를얻었다. Key Words : Laxity, 태스크스케줄링, 동적전력관리, 동적전압스케일링, 멀티프로세서 ABSTRACT This paper proposes a scheduling algorithm that can reduce the power consumed for execution of application programs and the communication cost incurred due to dependencies among tasks. The proposed scheduling algorithm can increase energy efficiency of the DVS(Dynamic Voltage Scaling) by estimating laxity usage during scheduling, making up for conventional algorithms that apply the DVS after scheduling. Energy efficiency can be increased by applying the proposed algorithm to complex multimedia applications. Experimental results show that energy consumptions for executing HD MPEG4, MotionJPEG codec, MP3, and Wavelet have been reduced by 11.2% on the average, when compared to conventional algorithms. Ⅰ. 서론최근모바일기기들에집적되는임베디드시스템은멀티미디어어플리케이션에서대용량데이터를처리해야하는프로그램의실시간수행이요구되며, 사용자의더높은질에대한요구와다양한기능의결합으 로인해점점복잡해지고있다. 모바일기기에서이용하는멀티미디어어플리케이션중하나인영상신호처리는알고리듬이복잡하고대용량의데이터처리를수행하며, 이미지처리에대한사용자의요구가 HD 급화질이되면서영상신호처리는멀티프로세서를가진 MPSoC (Multi-Processor System on Chip) 환 본연구는교육과학기술부및한국연구재단의지원으로수행되었습니다 (#2010-0008043). * 서강대학교전자공학과 CAD & ES. 연구실 (sbs1986@sogang.ac.kr) 논문번호 :KICS2010-07-712, 접수일자 :2010 년 7 월 12 일, 최종논문접수일자 :2010 년 11 월 4 일 1631
한국통신학회논문지 '10-11 Vol.35 No.11 경에서수행될수밖에없다. 이러한어플리케이션이배터리동작을하는모바일기기에서수행되기위해서는많은에너지를소모하는 PE (Processing Element) 간의데이터통신과 PE에서의연산을에너지효율적으로수행하는것이중요하다. MPSoC를구성하는 PE에서소모되는에너지와 PE간데이터통신에서소모되는에너지를감소시키기위하여회로수준, 운영체제, 미들웨어, 응용수준에이르기까지다양한추상화단계에서저전력설계기법들이제안되었다 [1-4]. 지난몇년간두드러지게발전한고집적반도체기술은시스템내부에서저전력수행을가능하게함으로써위와같은문제점을해결한다. 그럼에도불구하고현재시스템에대한다양한요구를충족하기위해시스템내부전력소모를최소화할수있는저전력관리가중요하며, 저전력관리기법은크게정적인기법과동적인기법으로분류된다 [5]. 정적인기법은설계혹은컴파일시에적용하는것으로전력소모가적도록하드웨어를합성하는방법, 소프트웨어를컴파일할때코드의재구성을통해전력소모가적도록하는방법등이있다. 동적인기법은실행시간에적용하는것으로작업부하량의변동을이용하여시스템의전력소모를줄여준다. 정적인기법을통해서도시스템의에너지소모를상당히줄일수있으나시스템이실행되는가운데계속해서변하는수행환경에대처할수없는단점이있다. 그렇기때문에최근동적인기법에더욱초점이맞추어지고있으며, 하드웨어자원관리기능과수행할어플리케이션의총체적인정보를갖고운영체제관점에서전력관리를수행할수있도록하는연구가주목받고있다 [6,7]. PE간데이터통신시발생하는통신비용을줄이기위해서주파수조절이가능한병렬링크와직렬링크도제안되었다 [8,9]. 링크의데이터전송에너지를줄이기위하여데이터전송시간제약을넘지않는범위내에서주파수와전압을낮춤으로써대역폭을조절한다. 또한 PE 간데이터전송량을줄이기위하여어플리케이션의총체적인정보를갖고데이터의존성이큰태스크끼리같은 PE에맵핑하는방법이제안되었다 [10]. 동적전력관리 (DPM : Dynamic Power Management) 는시스템의실행시간중작업부하량의변동을이용하여하드웨어의동작전압을동적으로조절하는방법이다. 동적전압조절 (Dynamic Voltage Scaling: DVS) 기법이프로세서클록주파수와전압을동적으로변경하여프로세서에서소모되는전력을줄이는기법으로제안되었으며, 마이크로프로세서기반의시스템에서가장주목받는전력관리기술중 하나이다 [11]. 동적전압스케일링은여유시간을활용하여전압및동작주파수를낮춤으로써시스템의에너지효율성을높이는것이며이미많은모바일프로세서는전압조절기능을갖는다 [12]. 동적전력관리기법에있어서중요한문제의하나는마감시간 (deadline) 을지키면서전력소모를최소화하는것이다. 임베디드시스템의경우대부분마감시간제약조건이존재하는실시간시스템이므로, 동적전력관리를적용할경우전력상태전환에따른시간적오버헤드가존재하기때문에마감시간을어기지않도록주의하여야한다. 지금까지연구된동적전압조절기법 [13] 은단일프로세서시스템을모델로하여제안되었으며멀티프로세서시스템을대상으로한연구는진행이미비하였다. 최근에들어서야시작되고있으나기존의단일프로세서칩에서사용되던기법들을단순하게병렬처리가가능함을이용하여확대적용하는차원이어서, 태스크간의데이터의존성이높은멀티미디어어플리케이션을멀티프로세서시스템에에너지효율적으로적용할수있는동적전압조절기법이필요하게되었다. 본논문에서는기존에제안된동적전압조절과태스크간의의존성을고려하여계산한여유시간활용률을통하여멀티프로세서시스템에적용할수있는스케줄링알고리듬을제안한다. 먼저알고리듬을구현하는과정에서태스크의우선순위를정하기위해서여유시간활용률을계산하고, 이를활용하여여유시간활용률을최대로하는동적전압조절기법을이용하여스케줄링하였으며, PE간데이터통신비용을고려하여맵핑하였다. 시스템환경은동일한프로세서들과프로세서를연결하고있는버스로구성이되어있으며, 시스템의구조와위상은결정되어져있다고가정하였다. 또한실제시스템과유사한환경을구축하기위하여어플리케이션의모형은 data flow와 control flow를모두고려하였다. 본논문의구성은다음과같다. 제 2절에서는에너지모델과기존의연구를소개하고제 3절에서는여유시간활용률을이용한새로운동적전압조절알고리듬을기술하며제안한알고리듬과기존기법과의차이를보인다. 제 4절에서는제안한알고리듬의효율성에대한실험결과를제시하고, 마지막으로제 5절에서는결론을맺는다. Ⅱ. 관련연구최근복잡한멀티미디어어플리케이션을임베디드 1632
논문 / 멀티프로세서임베디드시스템에서여유시간예측에의한저전력태스크스케줄링 환경에서실시간으로처리하기위하여멀티프로세서환경의임베디드시스템을구성한다. 임베디드시스템에서는해당어플리케이션을수행하는데소모하는에너지를최소화할필요에따라동적전력관리기법을적용하여시스템에서소모되는에너지를최소화하는연구가진행되고있다 [13]. 동적전력관리방식의목적은프로세서의수행주파수를조절하여어플리케이션을에너지효율적으로수행시키는데있다. 동적에너지소비는시스템의총에너지소비의큰부분을차지하고있으며, 시스템의동적전력소비는크게 PE에서사용하는에너지와, PE간혹은 PE와메모리간의통신에사용되는에너지로구성된다. 식 (1) 은 PE에서의동적전력소비를나타낸다. 여기서 는전력소모, 는클록주파수, 는 switching activity, 는공급전압을의미한다. 식 (1) 에서보듯이동적전력소비는프로세서가소모하는동적전압값의지수함수에비례하여증가한다. 식 (2) 는공급전압과문턱전압 ( ) 의변화에따른클록주파수를구하는식으로, k는공정에서결정된상수이며지수 는 1과 2사이의값을가진다. 식 (2) 를통해프로세서의클록주파수는공급되는전압값에비례함을알수있다. 따라서동적전압관리를통하여프로세서에공급되는전압을조정함으로써시스템에서소모되는에너지를감소시킬수있다. 를이용하여태스크- 통신그래프 로모델링한다. SDF는각태스크의 control flow와 data path를효과적으로나타낼수있는방법이다 [15]. 여기서각 vertex 는태스크 를나타내며, 각각의 edge 는 source vertex 와 destination vertex 간의제어및데이터의존성을의미하고, edge의 weight는태스크간통신량을의미한다. 멀티프로세서환경에서 SDF를이용할때, 어플리케이션을구성하는태스크들중병렬화수행이가능한태스크들을병렬수행이가능하도록 SDF를재구성하여이용한다. 그림 1은입력으로받은 SDF와재구성된 SDF의예를보인다. 식 (3) 은전체통신에소모되는에너지를나타낸다. 와 간의통신비용은각 PE에맵핑된태스크가의존성이있을때 에서 로한비트를전송하는데필요한에너지이며 로나타낸다. 는그래프상 edge weight로통신의양을나타내는정도이다. 의존성이있는모든태스크들에대해서 의값을더하면전체통신비용이된다. (1) (2) (a) 각태스크가 PE에맵핑되어수행될때태스크들의의존성에따라서 PE간통신이발생한다. 프로세서간통신의경우많은전력소모를유발하기때문에데이터양이많은멀티미디어를시스템에서수행중인경우많은전력소모가데이터통신에서발생하게된다 [14]. 통신비용을감소시키기위해서는태스크를 PE에맵핑하는단계에서태스크간의의존성을고려해야한다. 각메모리를갖고있기때문에통신비용이큰태스크끼리는같은 PE에맵핑을함으로써통신비용을감소시켜전체시스템의에너지를감소시키는연구가수행되었다 [10]. 태스크간의의존성을고려하여동적전압관리기법을어플리케이션에적용하기위하여어플리케이션을 Synchronous Data Flow Graph(SDF) (b) 그림 1. 태스크수준의 SDF 모델의예. (a) 태스크수준의 SDF 모델예, (b) 재구성된태스크수준의 SDF 모델의예 1633
한국통신학회논문지 '10-11 Vol.35 No.11 (3) 기존연구로어플리케이션을태스크- 통신그래프로모델링하고하드웨어정보를이용하여태스크의의존성을고려하여통신비용을최소화하도록스케줄링을한후, 최적화이론을적용하여에너지효율적인태스크수행주파수를결정하는알고리듬이제안되었으며태스크의수행이병렬적으로이루어지기때문에이를고려하여최대병렬화수준을이용하여스케줄링시동적전압관리기술을적용할때에너지소모를최소화하는방법이제안되었다 [16,17]. 기존의방법에서는멀티프로세서환경에서사용하는프로세서의클록주파수가연속적이지않고이산적이라는것을고려하지않고스케줄링과맵핑을수행한후에동적전압관리를통하여태스크의수행주파수를정하였기때문에비효율적인부분이발생한다. 이를해결하기위하여스케줄링단계에서미리변화하는태스크의수행시간을고려하여맵핑함으로써에너지효율을최대화할 수있다. Ⅲ. 제안된동적전력관리기법제안된전력관리기법은시스템을구성하는하드웨어의정보와어플리케이션프로그램에관한정보를이용하여여유시간 (Laxity) 을예측하며, 여유시간사용예측을통하여에너지효율적인스케줄링결과를찾는다. 하드웨어정보는프로세서에서지원하는클록주파수정보와프로세서간통신에사용되는통신구조에관한정보이며, 어플리케이션정보는어플리케이션을구성하는각태스크들의수행시간과제어및데이터의존성정보이다. 하드웨어정보와어플리케이션정보를이용하여스케줄링단계에서미리동적전압관리를적용한경우의소요시간을예측하여고려한다. 그림 2는제안된동적전력관리기법의의사코드를보인다. 스케줄링시간 t에서수행가능한태스크집합 (Released_TS) 에서각태스크별여유시간활용도를계산하여가장여유시간활용도가큰태스크와태스 Procedure LP_Scheduler(SDF){ AvailPE = Set of available PEs; // 선택된태스크를수행할수있는 PE 집합 t = 0; // scheduling time Divide given SDF into sub_graphs for using parallelism; Laxity_usage = 0; // 여유시간사용율 Released_TS = Set of executable tasks; // 수행가능한태스크집합 AvailFreq= { ; // 프로세서에서지원하는클록주파수집합 clk_fs = { ; // 마감시간을만족하는클록주파수집합 for (t = 0 ; t Deadline ; t++){ Released_TS = Released task at t ; for each task T Released_TS { clk_fs = Applicable clock frequencies among the elements in AvailFreq ; for each clock frequency clk_fs { Laxity_Estimation( sub_graph, T, ); // Proposed laxity estimation Calculate Laxity_usage; = Select clock frequency with the highest Laxity_usage; = Select a task with the highest Laxity_usage; for each PE AvailPE { cost = commnunication_cost + estimation_power ; = Select the PE which has the least cost for executing the selected task ; Assign task to which runs at ; 그림 2. 제안된동적전력관리기법의의사코드. 1634
논문 / 멀티프로세서임베디드시스템에서여유시간예측에의한저전력태스크스케줄링 크의수행클록주파수를선택하고통신비용과태스크수행시소모되는에너지를고려하여 PE를선택한다. 선택된태스크가선택된 PE에서수행될때마감시간을고려하여마감시간을어기게되는경우는태스크의수행클록주파수를다시결정하게되며, 새로운여유시간활용도에따라서스케줄링하게된다. 어플리케이션이종료되는시점까지반복하면최종적으로최소의에너지소모를갖는태스크스케줄링결과를얻을수있다. 3.1 여유시간사용예측을이용한태스크선택우선순위에기반을둔태스크스케줄링은불필요한의존적인패스의길이를작게만드는장점이있다 [18-20]. 이를통하여태스크가이용할수있는여유시간을최대화함으로써동적전압스케일링을통하여태스크집합전체의에너지소모를감소시킬확률을높인다. 어플리케이션을태스크수준의 SDF로모델링한태스크 -통신그래프를이용하여스케줄링시발생하는태스크간의의존성문제를고려한다. 스케줄링시간 에서수행가능한태스크집합에서전체여유시간활용률을최대로되게하는태스크를선택하여스케줄링한다. 여유시간활용률을구하기위하여어플리케이션을 profiling하여만든태스크 -통신그래프를이용하여태스크 의가장늦은완료시간 (Latest Finish Time : ) 과가장이른시작시간 (Earliest Start Time : ) 을계산한다. 태스크 의가장늦은완료시간 는식 (4) 와같이정의된다. (4) 태스크 -통신그래프에서자식태스크는제어및데이터의존성으로인하여해당태스크가수행이완료된후에수행할수있는태스크이다. 태스크 의마감시간을, 의자식태스크를, 통신비용과수행시간의합은 로나타낸다. 태스크 의 는태스크- 통신그래프에서가장늦게끝나는태스크의마감시간을그태스크의 로하여통신에걸리는시간과수행시간을빼면이전태스크의 가나옴을이용하여태스크- 통신그래프상의모든태스크들의 를계산할수있다. 태스크 의가장이른시작시간 는식 (5) 와같이정의된다. (5) 태스크- 통신그래프에서부모태스크는해당태스크가수행되기위해서제어및데이터의존성으로인하여반드시수행이완료되어있어야하는태스크를뜻한다. 태스크 의준비완료시간 (Task Ready Time) 는태스크- 통신그래프에서 의모든부모태스크들의수행이완료된시점을뜻한다. 또한 의준비완료시간 (PE Ready Time) 는 가 PE에맵핑되어수행을시작할수있는시간을뜻한다. 각태스크의 는처음태스크의수행시작시간을 0으로놓고각태스크가최대클록주파수로수행될때의수행시간을의존성정보에맞추어더해나감으로써계산할수있다. 각태스크의, 와어플리케이션을 profiling 하여얻은태스크의수행시간과의존성정보를이용하여태스크- 통신그래프상의모든태스크에대하여의존성을고려하여활용가능한여유시간을계산할수있다. 병렬처리가가능한태스크들과의의존성이있는태스크의경우, 이태스크를높은클록주파수로수행하면병렬처리가능한태스크들은높은주파수로수행하는태스크에비하여병렬화정도만큼의전체여유시간활용도가올라간다. 따라서병렬화가능한태스크들을낮은클록주파수로수행하여에너지소모를감소시킬수있다. 최대여유시간은모든태스크가 PE의최대클록주파수로수행이될경우의어플리케이션의마감시간까지존재하는 PE들의여유시간의합이다. 스케줄링시간에수행가능한태스크집합 (released_ts) 에존재하는태스크들에대하여각태스크별로여유시간활용도를최대화할수있는주파수를계산한다. 한태스크를스케줄링하면다른태스크들의 와사용가능한여유시간이바뀌게되므로이를다시계산해주어야한다. 3.2 태스크맵핑태스크의 와, 그리고어플리케이션 profiling 작업을통하여얻은태스크의수행시간과의존성정보를이용하여선택한태스크를부모태스크와의통신비용과수행할때소모되는에너지를계산하여가장적은에너지를소모하게하는 PE에맵핑하게된다. PE 에태스크 를맵핑하여수행할때소모되는에너지는 가 를수행하는데소모되는에너지와 의의존성으로인해서발생하는데이터통신에소모되는에너지의합이다. PE 선택의과정은다음과같다. 하나의태스크 를스케줄링시간 t에서사용가능한 PE에맵핑하는 1635
한국통신학회논문지 '10-11 Vol.35 No.11 비용이현재다른태스크를수행중인 에해당태스크가종료된후에 를 에맵핑하는비용보다큰경우현재시간에스케줄링하지않고 의수행이끝나면 에맵핑한다. 이러한경우에는수행중 인태스크를기다리는시간을고려하여다시태스크를수행할클록주파수를계산한다. 이때새로운주파수와기존의주파수를비교하여더적은에너지를소비하는주파수로태스크가수행되며, PE를다시선택한다. PE 선택결과수행중인태스크의완료를기다렸다가해당 PE에서수행을하는경우에더높은주파수로태스크를수행해야하고, 다른 PE에서수행하는경우에는기존의주파수로수행해도마감시간을만족하는경우두경우의에너지소모를비교하여더적은에너지가드는 PE에맵핑하고, 태스크를수행할클록주파수를선택하게된다. 이결과마감시간제약조건만족여부를조사하여마감시간제약조건에걸리는경우는다시스케줄링과정을수행하며, 스케줄링과맵핑결과 break-even time 보다큰시간동안태스크의수행이없는 PE는 shutdown 시킨다. 그림 3은어플리케이션의 SDF에대하여기존의알고리듬을적용하여스케줄링한결과와제안한알고리듬을적용한결과와의차이를보인다. SDF 그래프에서 vertex 내부의숫자는동적전압스케일링이적용되지않은태스크의단위수행시간을의미한다. 시스템을구성하는프로세서에서지원가능한클록 주파수가 와 만있는경우에참고문헌 [16] 에서제안한방법의결과는그림 3(b) 와같다. 태스크의의존성을고려하여스케줄링과맵핑을한후, ILP 솔루션을이용하여최적의주파수를선택한결과, 태스크가 의클록주파수로수행되며, 나머지태스크들은 의클록주파수로수행되어 6단위시간만큼의여유시간을사용한다. 참고문헌 [16] 에서제안한방법의경우태스크의수행클록주파수를구하기위해 ILP 솔루션을이용할때각 PE에수행될태스크가정해져있기때문에태스크간의의존성과마감시간제약조건으로인하여동적전압스케일링을적용할수없는태스크가발생한다. 본논문에서제안한동적전압스케일링기법을적용한경우의스케줄링결과 는그림 3(c) 와같다.,, 태스크가 의클록주파수로수행되며, 나머지태스크들은 의클록주파수로수행되어 9단위시간만큼의여유시간을사 (a) (b) (c) 그림 3. 태스크맵핑및스케줄링의예. (a) 어플리케이션의 SDF 의예, (b) 참고문헌 [16] 에서제안한스케줄링을적용한결과, (c) 제안한스케줄링을적용한결과. 용한다. 스케줄링단계에서전체여유시간을계산하고각태스크의수행시간이늘어나는것을예상하여동적전압관리기법을사용할수있는다른 PE에맵핑을하는동작이있기때문에더효율적인동적전압스케일링할수있다. Ⅳ. 실험결과 제안된알고리듬은 C언어를이용하여구현되었으며, 어플리케이션은 MPEG4, MP3, Wavelet, Motion- JPEG reference code [21-24] 와 GNU profiler를이용하여태스크그래프를구성하고, 기존논문 [25,26] 에근거하여태스크그래프의노드를분할하여병렬화하였으며, 각어플리케이션의마감시간은멀티미디어어플리케이션의특성을반영하여설정했다. MPEG4, 1636
논문 / 멀티프로세서임베디드시스템에서여유시간예측에의한저전력태스크스케줄링 MotionJPEG은 HD 30 frame/s를만족할수있도록마감시간을설정하였으며, MP3는 1.7Mbyte의음악파일을수행할수있도록, Wavelet 은 1628 1024 이미지를실시간으로변환할수있도록마감시간을설정하였다. 연산장치로 ARM11 프로세서 4개를사용하였고각각의프로세서는개별메모리소자를가지며버스구조를이용하여프로세서간통신이이루어지게구성하였다. 전체어플리케이션의소스코드가저장될글로벌메모리를갖는다. 멀티프로세서에채택된 PE의에너지소모에관련된데이터는참고문헌 [19] 에언급된 ARM11 프로세서의데이터에기반한다. 이경우전압에따른클록주파수가달라지면서수행시간과소모전력이각각달라진다. high frequency 모드의경우와 low frequency 모드의경우각각 40pJ/cycle과 13.3pJ/cycle의에너지가소모된다. 또한정적에너지의경우 low frequency 모드의 20% 만큼을소모한다. 태스크가새로맵핑되는경우의오버헤드는 10단위시간으로가정한다. 그림 4는참고문헌 [16] 에서제안한알고리듬과본논문에서제안한알고리듬을이용하여각각의어플리케이션을수행할때의에너지소모를보인다. 표 1은기존의알고리듬과제안된알고리듬의에너지소모차이를보인다. 멀티미디어어플리케이션에대하여제안한알고리듬을이용하여수행한결과, 기존의알고리듬을이용한결과에비하여소모되는에너지가평균 11.2% 감소함을보인다. 실험결과가장큰에너지효율감소를보인어플리케이션은 MotionJPEG으로 12.8% 의에너지소모감소를보이며, 가장적은에너지효율감소를보인어플리케이션은 MP3로 9.8% 의에너지소모감소를보인다. 복잡한어플리케이션일수록의존성이크고, 병렬화수준이높기때문에스케줄링단계에서동적전력관리기법을이용하지않고, 스케줄링이후에동적전력관리기법을적용하게되 그림 4. 어플리케이션에기존및제안된알고리듬을적용한결과에너지소모. 표 1. 어플리케이션별기존알고리듬과제안된알고리듬의에너지소모비교 어플리케이션 기존알고리듬 (mw) 제안한알고리듬 (mw) 비고 MPEG4 135.3 120.1-11.2 % MotionJPEG 242.5 219.9-12.8 % MP3 23.2 20.7-9.8 % Wavelet 18.8 16.4-10.8 % Average - - -11.2 % 면낮은클록주파수를선택하지못하는경우가많이발생하기때문에더많은에너지감소율을얻었다. 제안된알고리즘은스케줄링단계에서동적전력관리기법을적용하며, 여유시간예측과태스크의의존성과병렬화정보를이용하여태스크수행시간변화를종합적으로분석하여스케줄링한다. 그결과불필요한에너지소모를감소시킬수있는기회가증가하여기존의알고리듬을적용한결과에비하여어플리케이션을수행하는데필요한에너지가감소하였다. Ⅴ. 결론및추후과제 본논문에서는멀티프로세서시스템에서복잡한멀티미디어어플리케이션을수행할때에너지효율을높이기위하여기존에제안된동적전압조절기법과태스크간의의존성을이용하여멀티프로세서시스템에적용할수있는스케줄링알고리즘을제안하였다. 어플리케이션을 profiling하여얻은태스크들의수행시간과의존성정보를이용하여여유시간사용을예측하여여유시간활용률을최대로하는태스크를선택하고, 이를수행할클록주파수는여유시간예측을바탕으로하여결정하였다. 이후선택된태스크를통신비용을고려하여여유시간활용도를최대로할수있는 PE에맵핑하는방식을사용하였다. 제안된스케줄링알고리듬을이용하여 MPEG4, MotionJPEG, MP3, Wavelet과같은멀티미디어어플리케이션에기반한태스크그래프를대상으로한실험결과에서에너지소모를효율적으로줄일수있음을확인하였다. 추후연구로동종프로세서들로구성된멀티프로세서환경을타겟으로하는제안된알고리듬을이종프로세서들로구성된멀티프로세서환경도지원할수있도록확장하는연구가필요하다. 1637
한국통신학회논문지 '10-11 Vol.35 No.11 참고문헌 [1] M. Pedram and J. Rabaey, Power Aware Design Methodologies, Kluwer Academic Pub., 2002. [2] International Technology Roadmap for Semiconductors 2002, http://public.itrs.net. [3] Berkeley Predictive TechnologyModels and BSIM4, http://www-device.eeecs.berkeley.edu/ research.html. [4] R. Jejurikar, C. Pereira, and R. Gupta, Leakage Aware Dynamic Voltage Scaling for Real-time Embedded Systems, in Proc. Design Automation Conference, San Diego, CA, pp.275-280, June, 2004. [5] J. Rabaey and M. Pedram, Low Power Design Methodologies, Kluwer Academic Pub., 1996. [6] Y. Lu, L. Benini, and G. DeMicheli, Power-Aware Operating Systems for Interactive Systems, IEEE Trans. on VLSI Systems, Vol.10, No.2, pp.119-134, Apr. 2002, [7] Y. Lu, L. Benini, and G. DeMicheli, Operating-system Directed Power Reduction, in Proc. Int. Symp. Low Power Electronics and Design, Rapallo, Italy, pp.37-42, July 2000. [8] G. Wei, J. Kim, D. Liu, S. Sidiropoulos, and M. Horowitz, A Variable-frequency Parallel I/O Interface with Adaptive Power-supply Regulation, IEEE Journal of Solid-State Circuits. Vol.35, No.11, pp.1600-1610, Nov. 2000. [9] L. Shang, L. Peh, and N. Jha, Dynamic Volotage Scaling of Processors and Communication Links in Real-Time Distributed Embedded Systems, IEEE Trans. on VLSI Systems, Vol.15, No.4, pp.427-437, Nov. 2000. [10] S. H. Lee, Y. C. Yoon, and S. Y. Hwang, Communication-Aware Task Assignment Algorithm for MPSoC Using Shared Memory, Journal of Systems Architecture, Vol.56, No.7, pp.233-241, July 2010. [11] A. Chandrakasan, A. Sheng, and R. Brodersen, Low-Power CMOS Degital Design, IEEE Journal of Solid-State Circuits, Vol.27, No.4, pp.473-484, Apr. 1992. [12] Y. Shin, K. Choi, and T. Sakurai, Power Optimization of Real-Time Embedded Systems on Variable Speed Processors, in Proc. Int. Conf. Computer-Aided Design, San Jose, CA, pp.365-368, Nov. 2000. [13] M. Pedram and J. Rabaey, Power Aware Design Methodologies, Kluwer Academic Pub., 2002. [14] A. Jerraya and W. Wolf, Multiprocessor Systems-on-Chips, Morgan Kaufmann Pub., 2005. [15] W. Wolf, High-Performance Embedded Computing, Morgan Kaufmann Pub., 2007. [16] 김현진, 홍혜정, 김홍식, 강성호, 멀티프로세서상의에너지소모를고려한동적전압스케일링및전력셧다운을이용한태스크스케줄링, 한국통신학회논문지, 46권 7호, pp.22-28, 2009년 7월. [17] 노경우, 박창우, 김석윤, 멀티프로세서시스템을위한동적전압조절기반의효율적인스케줄링기법, 대한전기학회논문지, 제 57권제3호, pp.421-428, 2008년 3월. [18] Y. Zhang, X. Hu, and D. Chen, Task Scheduling and Voltage Selection for Energy Minimization, in Proc. Design Automation Conference, New Orleans, LA, pp.183-188, June. 2008. [19] G. Varatkar and R. Marculescu, Communication-aware Task Scheduling and Voltage Selection for Total Systems Energy Minimization, in Proc. Int. Conf. Computer-Aided Design, San Jose, CA, pp.510-517, Nov. 2003. [20] H. Kim, H. Hong, H. S. Kim, J. H. Ahn, and S. Kang, Total Energy Minimization of Real-time Tasks in an On-chip Multiprocessor Using Dynamic Voltage Scaling Efficiency Metric, IEEE Trans. on CAD, Vol.27, No.11, pp.2088-2092, Nov. 2008. [21] 2D Fast Wavelet Transform Library for Image Processing, The Code Project, http://www.code project.com. [22] Mpeg3Play (Release 0.9.6). MP3 Tech., http:// www.mp3-tech.org/programmer/decoding.html. [23] H.264/AVC Software Coordination, Fraunhofer, Institut Nachrichtentechnik Heinrich-Hertz-Institut, http://iphome.hhi.de/suehring/tml. [24] Motion JPEG decoder Application. JPEG Committee, Standardized in ISO/IEC IS 10918-1/2, 1638
논문 / 멀티프로세서임베디드시스템에서여유시간예측에의한저전력태스크스케줄링 http://www.jpeg.org. [25] E. Tol, E. Jaspers, and R. Gelderblom, Mapping of H.264 Decoding on Multiprocessor Architecture, in Proc. SPIE Conf. Image and Video Communications and Processing, Santa Clara, CA, Vol.5022, pp.707 718, Jan. 2003. [26] O. Lehtoranta, E. Salminen, A. Kulmala, M. Hannikainen, and T. Hamalainen, A Parallel MPEG-4 Encoder for FPGA based Multiprocessor SoC, in Proc. Int. conf. Field Programmable Logic and Application, Tampere, Finland, pp.380 385, Aug. 2005. 황선영 (Sun-Young Hwang) 정회원 1976년 2월서울대학교전자공학과 1978년 2월한국과학원전기및전자공학과공학석사 1986년 10월미국 Stanford대학전자공학박사 1976~1981 삼성반도체주식회사연구원, 팀장 1986~1989 Stanford 대학 Center for Integrated System 연구소책임연구원 Fairchild Semiconductor Palo Alto Research Center 기술자문 1989~1992 삼성전자 ( 주 ) 반도체기술자문 1989년 3월~현재서강대학교전자공학과교수 < 관심분야 > SoC 설계및 framework 구성, CAD시스템, Com. Architecture 및 DSP System Design 등 서범식 (Beom-Sik Suh) 준회원 2009년 2월서강대학교전자공학과 2009년 3월~~ 현재서강대학교전자공학과대학원 CAD&Embedded Systems 연구실석사과정 < 관심분야 > 저전력임베디드시스템설계, 저전력 SoC 설계. 1639