The dynamic power management for embedded system with Poisson process

Chen et al. /J Zhejiang Univ sCI 2005 6A(Suppl. 1):70-74Jourmal of Zhejiang University SCIENCEISSN 1009-3095htp://ww.zju.edu.cn/jzusJzuSE-mail: jzus@zju.edu.cnThe dynamic power management for embeddedsystem with Poisson processCHEN Tian- zhou (陈天洲), HUANG Jiang-wei (黄江伟), DAI Hong-jun (戴鸿君)(Schoo of Computer Science, Zhejiang University, Hangzhou 310027, China)E-mail: tzchen@zju.edu.cn; hjw@zju.edu.cn; dahogn@zju.edu.cnReceived Nov. 15, 2004; revision accepted Feb. 3, 2005Abstract: The mass of the embedded systems are driven by second batteries, not by wired power supply. So saving energy is oneof the main design goals for embedded system. In this paper we present a new technique for modelling and solving the dynamicpower management (DPM) problem for embedded systems with complex behavioural characteristics. First we model apower-managed embedded computing system as a controllable Flow Chart. Then we use the Poisson process for optimisation, andgive the power management algorithm by the help of Dynamic Voltage Scaling (DVS) technology. At last we built the experi-mental model using the PXA 255 Processors. The experimental results showed that the proposed technique can achieve more than12% power saving compared to other existing DPM techniques.Key words: DPM, Flow Chart, Poisson processdoi: 10.1631/jzus.2005.AS0070Document code: ACLC number: TP303+.3INTRODUCTIONand careful debugging and validation (Huang et al,2004a; 2004b).Embedded systems are driven by second batter-A simple and widely-used technique is theies, not by wired power supply. Many methods have“time-out” technique, which turms on the componentbeen proposed for reducing the energy consumption when it is to be used and turns off the componentof individual components. These methods predict thewhen it will not be used for some pre-specified lengthperiods when a component is idle or under-utilized of time. Srivastava et al. proposed a predictive power(Cai and Lu, 2004). The idling component is turned management strategy, which uses a regression equa-off or the performance scaled down to reduce energytion based on the previous“on”and“off' times of theconsumption during these periods. This is called en- component to estimate the next “turn-on” timeergy management or dynamic power management. (Viredaz and Wallach, 2003). Some past researchersHigh power consumption reduces the battery serviceintroduced a more complex predictive shut downlife. The goal of low-power design for bat- strategy with better performance. However, thesetery-powered devices is thus to extend the battery heuristic techniques could not handle componentsservice life while meeting performance requirements.with more than two ("ON"" and“OFF") power modes,Incorporating a dynamic power management scheme not handle complex system behaviors; and they can-in the design of an already-complex system is a dif- not guarantee optimality. Qiu et al.(2000) has pre-ficult process that may require many design iterations sented a new modelling method using GeneralizedStochastic Petri Nets to solve this problem.As proposed in (Paleologo et al, 1998), a"Project (No. 2003AA1Z2120) supported by the Hi-Tech Research power-managed system, can be modelled as a dis-and Development Program (863) of Chinacrete-time Markov中国煤化工ing theYHCNMHGChen et al.1J Zhejiang Univ SCI 2005 6A(Suppl. D):70-7471The complexity of the modelling problem for theand its parameters are determined, an optimal power above system is high not only because of the in-management policyfor achievingthe bestcreased number of components, but also because ofpower-delay trade-off in the system can be generated. the complex system behaviors that are present. ForQiu and Pedram (1999) improved it by modelling the example, we need to consider the synchronization ofpower managed system using a continuous-timeLSQs and SPs, the synchronization of the SRs and RQ,Markov decision process (CTMDP).the synchronization of the RQ and LSQs, the dispatchPrevious works based on Markov decision behavior of the RD, and so on. In this situation, theprocesses only describe modelling and policy opticomplex system's behaviors are a major part of themization techniques for a simple power managed system model. The modelling techniques introducedsystem containing one Service Provider (SP) provid- above become powerless because they only offering services (e.g. computing, file access, etc.), onestochastic models for individual components anService Queue (SQ) that buffers the service requests require that global system behaviors be capturedfor the SP, and one Service Requestor (SR) generating manually. Obviously, we need new DPM modellingrequests for SP. It is relatively easy to construct the techniques for large systems with complex behaviors.stochastic models of the individual components be- (Qiu et al., 2000).cause their behavior is rather simple, but a significantWe analyze the whole process of Request Dis-effort is required to construct the joint model of SP patch. After some research, we break the wholeand SQ mainly because of the required synchroniza- process into three major parts as shown in Fig.2tion between state transitions of SP and SQ (Qiu et al, (Huang et al, 2004a; 2004b).2000).In this paper, we target the more complexpower-managed systems as shown in Fig.1 (Huang et|Control nal, 2004a; 2004b). The example depicts a typicalmulti-server (distributed computing) system. NoteRequest| RequestRequestthat we are only interested in the system behaviorProducerRequest Dispatcher sp numbeiL Consumerrelated to the power management. The system con-SP infotains multiple SPs with their own Local SQs (LSQ).RGSUSSThere are multiple SRs generating the tasks (requests)that need to be serviced. The Request Queue (RQ)Fig.2 Three major parts of the whole processbuffers the requests generate by SRs. The RequestDispatcher (RD) decides about which SP should ser-vice which request. Different SPs may have differentThe first part is Request Producer (RP) whichpower/performance parameters. In real applications, includes the SRs and RQ used for producing request.the RD and LSQs can be part of the operating system,The RP's behaviors cannot be controlled by us. Thewhile SPs can be multiple processors in asecond part of the process includes the Request Dis-multi-processor computing system or number of patcher (RD) used for dispatching the request to anetworked computers of a distributed computing suitable SP. We name this part Request Transfer (RT).system.The last part called Request Consumer (RC), includesthe SPs and LSQs, used for offering service. We canSR1LSQ1P1|send the request to the suitable SP and adjust the SP'sSR2LSQ2SP2states. Because of the buffer between RP and RT isRQ|-计RDlimited, we can find that the relationship of RP andRT is that of producer and consumer, such as RT andLSQm卜F =\厂 SPn]RC. The core part of this model is the RD, whosework of RD is finding the suitable SP, and sending theFig.1 Multi-server and multi-requester/distributed-com-request to it. In this work, we will introduce a newputing systemtransferring policy中国煤化Ibution.TYHCNMH G72Chen et al.1J Zhejiang Univ SCI 2005 6A(Suppl 1):70-74MODEL ANALYSIS AND OPTIMIZATIONLetting the sample size N become infinity, thdistribution then approaches:As the processor may not be fully utilized all thetime, the variation in system load can be exploited toP(n)= lim P,(n)reduce power dissipation. The processor can be turnedoff or made to operate at lower speed when theN(N-1...(N-n+1) v"processor has no or litle work to do. Some poresors Nm(-号)(一allow the voltage to be dynamic adjusted. This iscalled Dynamic Voltage Scaling (DVS). The rela- = limN(N-1)...(N-n+1)v"(-)(一4)”tionship among the power consumption rate (P),supply voltage (V) and clock frequency (/) can be =1(4described by the following formula:nP=CxfxV21)which is known as the Poisson distribution (Papoulis,1984; Pfeiffer and Schum, 1973), in the limit of thewhere C is the switched capacitance (Zhang andnumber of trials is infinity. Note that the sample sizeChanson, 2003). It fllows that if we decrease the N has completely dropped out of the probilityswitched capacitance (C), the power consumptionfunction, which has the same functional form for allwill be reduced.values of V.Analyze the Request Producer; the numbers ofIn the Poisson distribution, the A is the prob-requests in non-overlapping intervals are independent ability that the event occurred. We cannot get λ at thefor all intervals. The probability of exactly one re- beginning. We should adjust the λ dynamics by thequest change in a sufficiently small interval h=l/n is data we had gathered. Then we can use the equationp= = vh=v/n, where v is the probability of one changeand n is the number of trials. The probability of two orw.n=E(x)=之kAe(5more requests change in a sufficiently small interval hλ!is essentially 0 (Huang et al, 2004a; 2004b).We define generated type A as success and N() to adjust h.as the sum of event that occur. Given a PoissonFor example, when the system is starting, weprocess, the probability of obtaining exactly n suC- give the probability that the event occurred (generat-cesses (ype A) in N trials is given by the limit ofa ing request) as 0.5 (2=0.5). By the timne, we can adjustbinomial distribution (Balakrishnan and Basu, 1996)the A base the data the system has collected. Then wecan adjust the hardware and software environment ofNP(1|N)=(n)"q~~=nl(N-n)!"(1-p)~-" (2)SP to improve the response rate, reduce the stateschanging of modules and improve the power utiliza-tion (Huang et al, 2004a; 2004b).Every request in the request queue R= {Ri, R2, ....where binomial coefficient isThe equationRv} has two associated parameters, F, and V. F is the(nlowest frequency the task needs, and V is the lowestthe expected number of successes v=np. Instead of thevoltage the task needs. Each task can be describedsample size N for fixed p, the equation becomesWhen one request with the associated parameters(Weisstein, 2000)(F, V) has been finished, the system needs to select arequest to the SP. The selecting algorithm is explained( N)P:(n|N)=(n,p"qN-nin detail after we introduce a few definitions.3)Definition 1 If F;>Fj and V;>V;, then we said (F,V)>(Fj, V).:(v/n)"(1-v/n)~-nn!(N-n)!'Definition2 We d中国煤化工)is(F,YHCNM HGChen et al. 1J Zhejiang Univ SCI 2005 6.A(Suppl. ):70-747:V)-(F, V)=(Fr- F)x(V? -v3.quency and Core voltage can be dynamic adjust byDefinition 3 We define the (Fi, V)=(F, V) when instructions.F=Fjand V=V.In this setup, we compare the following methods:When the queue was not empty, the RD selectOptimal USS power management+heuristicthe request R;with (F, V) that (F, V)>(F, V) and the dispatch policy (Li et al, 2003), Time -out+heursticresult of(F, V)- (F, V) is the minimal in all requests dispatch. Greedy+heuristic dispatch (Qiu et al,to run on the SP.2000).When the queue is empty, the RD will calculateThe comparisons of experimental results for thethe h using Eq.(5) for all requests that had happened.four methods described above are in the Table 1.If the request has the maximal a, we think that requestTable 1 Comparisons of experimental resultswill be happened in the next sufficiently small inter-val.VS.If(F, V)>=(F, V), the system can maintains theGreedyTimeout LocalAveragestatus until the next request occurs. If(F, V)<(F, V),DPMpolicyoptimalsavedthe system can adjust the frequency and core voltagepA=0.2,22.75%13.49% 26.33% 20.856%to F and V; ahead. The algorithm is shown in Fig.3.pB-0.8DA=04, 2391%14.99%23.55% 20.816% .pB=0.6if is _empty(RQ) {for (all requests that had happened) {pA=0.5,24.15%15.87%26.63% 22.21%pB=0.5Calculate (2))A-=0.6,23.01%14.94% 25.9% 21 .28%pB=0.4Find the request; with max2pA=0.8,if((F,V)>=(F, )){pB-0.219.62%13.65% 44.83% 26.03%Return; //Kcep_ statuselse {Adjust_ status(F, V); /adjust the statusCONCLUSIONFrom the experimental results, we can prove thatfor (all the requests in the RQ)the Flow Charting mechanism can save more thanif((F;,V)-(Faureont small,, VCurrent. smal)=<0)12% power compared to all the three methods. TheCurrent_ small=i;improvement shows the importance of building anAdjust_ status(F, V); //adjust the statusaccurate system model and obtaining an optimalDispatch (R);dispatch policy and power management policy for theSP's for the target distributed computing system.We use the Flow Chart to model and solve theFig.3 The algorithm of RDDPM problem for embedded systems with complexbehavioral characteristics. It gives a new and easyway to solve the DPM problem with 12% powerEXPERIMENTAL MODELsaved. The reality indicates that our approach hasOur experimental model is very simple. Ourrelatively better performance.target system is a simple distributed computing sys-Referencestem. The MSS (Multi-USS) contains two USSs and Balakrishnan, N., Basu, A.P.,. 1996. The Exponential Ditri-two RGSs. The RGSs generate requests in the requestbution: Theory, Methods, and Applications. Gordon andqueue. The RQ capacity is 6. The two USS have dif-Breach, New York.ferent power consumptions and (different serviceai, L., Lu, Y.H, 2004. Dynamic Power Management UsingData Buffers. School of Electrical and Computerspeeds. The sQ capacity is 2.We use the Sistang board as SP and RP. TheHuang, J.W., Chen,ai. HJL. 2004a. DynamicSistang Board processor is Xscale PXA 255. Its fre-Power Managem中国煤化工g FlowYHCNMHG74Chen et al. /J Zhejiang Univ SCI 2005 6A(Suppl 1):70-74Model and Passion Process. IASTED International Con-Peiffer, P.E, Schum, D.A., 1973. Introduction to Appliedference on Power and Energy Systems (PES 2004).Probability. Academic Press, New Y ork.Huang, J.W., Chen, T.Z., Ye, M.J., Yi, L, 2004b. Dynamic Qiu, Q.R, Pedram, M., 1999. Dynamic Power ManagementPower Management of Complex Systems Using FlowBased on Continuous-Time Markov Decision Processes.Model. The First International Conference on EmbeddedAnnual ACM IEEE Design Automation Conference,Software and System (ICESS 2004).Proceedings of the 36th ACM/IEEE Conference on De-Li, D.X., Xie, Q, Pai, H, 2003. Scalable Modeling and Op-sign Automation. New Orleans, Louisiana, United States,timization of Mode Transitions Based on Decoupledp.555-561.Power Management Architecture. Irvine, Chou Center for Qiu, Q.R, Wu, Q, Massoud, P., 2000. Dynamic Power Man-Embedded Computer Systems University of California.agement of Complex Systems Using Generalized Sto-Paleologo, G.A, Benini, L, Bogliolo, A., Micheli, G.D., 1998.chastic Petri Nets. Department of Electrical Engineering -Policy Optimization for Dynamic Power Management.Systems, University of Southern California.Proceedings of Design Automation Conference,Viredaz, M.A, Wallach, D.A., 2004. Power evaluation of ap.182-187.handheld computer. IEEE Micro, 23(1):2003.Papoulis, A., 1984. Poisson Process and Shot Noise. Ch.16 in Weisstein, E.W，PoissonDistribution.Probability, Random Variables, and Stochastic Processes,http://mathworld. wolfram.com/PoissonDistribution.html.2nd Ed. McGraw-Hill, New York, p.554-576.Welcome contributions from all over the worldhttp://www.zju.edu.cn/jzus◆The Journal aims to present the latest development and achievement in scientific research inChina and overseas to the world's scientific community;◆JZUS is edited by an international board of distinguished foreign and Chinese scientists. Andan internationalized standard peer review system is an essential tool for this Journal'sdevelopment;JZUS has been accepted by CA, Ei Compendex, SA, AJ, ZM, CABI, BIOSIS (ZR),IMMEDLINE，CSA (ASF/CE/CIS/Corr/EC/EM/ESPM/MD/MTE/O/SSS*WR) for ab-stracting and indexing respectively, since started in 2000;◆JZUS will feature Science & Engineering subjects in Vol. A. 12 issues/year, and Life Science& Biotechnology subiects in Vol. B. 12 issues/year;◆JZUS has launched this new column“Science Letters" and warmly welcome scientists all overthe world to publish their latest research notes in less than 3- 4 pages. And assure themthese Letters to be published in about 30 days;◆JZUS has linked its website (http://www.zju.edu.cn/jzus) to CrossRef: http://www.crossref.org(doi: 10.1631/jzus.2005.xxx); MEDLINE: htp://www.ncbi.nlm.nih.gov/PubMed; High-Wire: http://highwire.stanford.edu/top/journals.dtl; Princeton University Library:http://ibweb5.princeton.edu/ejournals/.中国煤化工MHCNM HG