Abstract:
Low energy consumptions are extremely important in real-time embedded systems. Due to the uncertainties in execution time of some tasks, this paper models each varied execution time as a probabilistic random variable and incorporating applications&#39; performance requirements to explore real-time embedded systems and avoid over-designing them. We propose a practical algorithm to minimize the expected value of total energy consumption while satisfying the timing constraint with a guaranteed confidence probability. The experimental results show that our approach achieves significant energy saving than previous work. For example, our algorithm achieves an average improvement of 61.2% on total energy consumption compared with the algorithm in previous work.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     Embedded systems, such as battery-operated PDAs, mobile phones, etc., are everywhere in our daily lives. Many of these systems can tolerate occasional deadline misses and some tasks in them may not have fixed execution time. Such tasks usually contain conditional instructions and/or operations that could have different execution times for different inputs. It is possible to obtain the execution time distribution for each task by sampling or profiling. Prior approaches for hardware/software co-design of embedded systems guarantee no deadline missing by considering worst-case execution time of each task. These approaches are pessimistic and only suitable for hard real-time systems, where any deadline miss will be catastrophic. They are not suitable for soft real-time systems, which can tolerate occasional violations of timing constraints. Using probabilistic approach, we can deliver higher performance with less energy consumption. Our probabilistic approach can be applied to both hard real-time systems and soft real-time systems. Hard real-time is a special case when the probability equals one. Dynamic voltage scaling (DVS) is one of the most effective techniques to reduce energy consumption. We use probabilistic approach and DVS to avoid over-designing systems.  
         [0002]     We propose a novel optimal algorithm, VAP_Opt, to minimize expected value of total energy consumption while satisfying timing constraints with guaranteed probabilities for real-time applications. We prove our algorithm gives voltage assignment with the minimum energy consumption. We conduct experiments on a set of benchmarks, and compare our algorithm with previous work. Experiments show that our algorithm VAP Opt has an average of 61.2% energy saving compared with previous work.  
         [0003]     Our contributions are listed as the following: 1) Our algorithm VAP_Opt gives the optimal solution and achieves significant energy saving compared to previous algorithm. 2) Algorithm VAP_Opt not only is optimal, but also provides more choices of smaller expected total energy consumption with guaranteed confidence probabilities satisfying timing constraints. In many situations, previous algorithm cannot find a solution, while VAP_Opt can find satisfactory results. 3) Algorithm VAP_Opt is practical and quick.  
       SUMMARY OF THE INVENTION  
       [0004]     Our target is to solve the VAP (voltage assignment with probability) problem which defined as follows: Given M different voltage levels: R 1 , R 2 , . . . , R M , a PDFG (Probability Data Flow Graph) G=&lt;V.E&gt;, where V is node set and E is edge set, with time T, probability P, and energy consumption C for each node executed on each voltage R i , a timing constraint L and a confidence probability P, find the voltage for each node in assignment that gives the minimum expected total energy consumption C with confidence probability P under timing constraint L.  
         [0005]     To solve the VAP problem, we use dynamic programming method traveling the graph in a bottom up fashion. Thus, the complexity of the algorithm VAP_Opt is O(|V|*L*M*K), where |V| is the number of nodes and L is the given timing constraint. Usually, the execution time of each node is upper-bounded by a constant. In this case, VAP_Opt is polynomial. Note that if L is not upper bounded, this problem is NP-hard which can be proved by 0-1 Knapsack problem. In practice, when the timing constraint is polynomial to the size of PDFG, the running time of our algorithm is very small and our experiments are always finished in very short time. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]      FIG. 1  ( a ) An Input PDFG. ( b ) The times, probabilities, and energy consumptions of its node. ( c ) The scheduling graph.  
         [0007]      FIG. 2  The Minimum Total Energy Consumption Under Various Timing Constraints For Voltera Filter.  
         [0008]      FIG. 3  The impact of timing constraints on energy consumption. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0000]     Architecture  
         [0009]     System Model: Probabilistic Data-Flow Graph (PDFG) is used to model a DSP application. A PDFG G=&lt;V, E, T, R&gt; is a directed acyclic graph (DAG), where V is the set of nodes; R is a voltage set; the execution time T is a random variable; E is the edge set that defines the precedence relations among nodes in V. There is a timing constraint L and it must be satisfied for executing the whole PDFG.  
         [0010]     Energy Model: Dynamic power, which is the dominant source of power dissipation in CMOS circuit, is proportional to N×C ap ×V dd   2 , where N represent the number of computation cycles for a node, C ap  is the effective switched capacitance, and V dd  is the supply voltage. Reducing the supply voltage can result in substantial power and energy saving. Roughly speaking, system&#39;s power dissipation is halved if we reduce V dd  by 30% without changing any other system parameters. However, this saving comes at the cost of reduced throughput, slower system clock frequency, or higher cycle period time (gate delay). The cycle period time T c  is proportional to V dd /(V dd −V th ) a , where V th  is the threshold voltage and aε( 1.0, 2.0] is a technology dependent constant.  
         [0011]     Let T represent the execution time of a node and C stand for energy consumption Given the number of cycles N of node v, the supply voltage V dd  and the threshold voltage V th , its computation time T and the energy C for node v are calculated as follows:
 
 T   c   =k×V   dd /( V   dd   −V   th ) a   (1)
 
 T=N×T   c   =N×k×V   dd /( V   dd   −V   th ) a   (2)
 
 C=N×C   ap   ×V   dd   2   (3)
 
         [0012]     In Equation (1), k is a device related parameter. From Equations (2) and (3), we can see that the lower voltage will prolong the execution time of a node but reduces its energy consumption. We assume that there is no energy or delay penalty associated with voltage switching.  
         [0013]     In our model, under the same voltage (R), the execution time (T) of a task is a random variable, which is usually due to condition instructions or operations that could have different execution times for different inputs. The number of computation cycles (N) for a task is proportional to the execution time. The energy consumption (C) depends on not only the voltage level R, but also the number of computation cycles N. We use the expected value of energy consumption (Exp(C)) as the energy consumption C under a certain voltage level R. Under different voltage levels, a task has different expected energy consumptions. The higher the voltage level is, the faster the execution time is, and the more expected energy is consumed. This paper shows how to assign a proper voltage level to each node of a Probabilistic Data-Flow Graph (PDFG) such that the expected total energy consumption is minimized while satisfying the timing constraint with a guaranteed confidence probability.  
         [0014]     An exemplary PDFG is shown in  FIG. 1 ( a ). Each node can select one of the two different voltage levels: R 1  and R 2 . The execution times (T), corresponding probabilities (P), and energy consumption (C) of each node under different voltage levels are shown in  FIG. 1 ( b ). The execution time T of each node is modeled as a random variable. For example, when choosing R 1 , node  1  will be finished in 1 time unit with probability 0.9 and will be finished in 2 time units with probability 0.1.  FIG. 1 ( c ) shows an example schedule on uni-processor.  
         [0000]     Basic Concepts and Data Structures  
         [0015]     To solve the VAP problem, we use dynamic programming method traveling the graph in a bottom up fashion. For the easiness of explanation, we will index the nodes based on bottom up sequence. For example,  FIG. 1  ( c ) shows nodes indexed in a bottom up sequence, that is, v1-&gt;v2-&gt;v3.  
         [0016]     Given the timing constraint L, a PDFG G, and an assignment A, we first give several definitions as follows:  
         [0017]     1) G i : The sub-graph rooted at node v i , containing all the nodes reached by node v i . In our algorithm, each step will add one node which becomes the root of its sub-graph. For example, G 3  is the graph containing nodes  1 ,  2 , and  3  in  FIG. 1 ( a ).  
         [0018]     2) In our algorithm, table D i,j  will be built. Each entry of table D i,j  will store a link list of (Probability, Consumption) pairs sorted by probability in an ascending order. Here we define the (Probability, Consumption) pair (P i,j , C i,j ) as follows: C i,j  is the minimum energy consumption of C A (G i ) computed by all assignments A satisfying T A (G i )≦j with probability≧P i,j .  
         [0019]     We introduce the operator “⊕” in this paper. For two (Probability, Consumption) pairs H 1  and H 2 , if H 1  is (P i,j   1 , C i,j   1 ), and H 2  is (P i,j   2 , C i,j   2 ), then after applying the ⊕ operation between H 1  and H 2 , we get pair (P′, C′), where P′=P i,j   1 *P i,j   2  and C′=C i,j   1 +C i,j   2 . We denote this operation as “H 1 ⊕H 2 ”.  
         [0020]     D i,j  is the table in which each entry has a link list that stores pair (P i,j , C i,j ) sorted by P i,j  in an ascending order. Here, i represents a node number, and j represents time. For example, a link list can be (0.1, 2)-&gt;(0.3, 3)-&gt;(0.8, 6)-&gt;(1.0, 12). Usually, there are redundant pairs in a link list. We use Lemma 1 to cancel redundant pairs.  
         [0021]     Lemma 1: Given (P i,j   1 , C i,j   1 ) and (P i,j   2 , C i,j   2 ) in the same list:  
         [0022]     1) If P i,j   1 =P i,j   2 , then the pair with minimum C i,j  is selected to be kept.  
         [0023]     2) If P i,j   1 &lt;P i,j   2  and C i,j   1 ≧C i,j   2 , then C i,j   2  is selected to be kept.  
         [0024]     In every step of our algorithm, one more node will be included for consideration. The information of this node is stored in local table E i,j , which is similar to table D i,j , but with accumulative probabilities only on node v i . A local table only store information, such as probabilities and consumptions, of a node itself. Table E i,j  is the local table only storing the information of node v i . In more detail, E i,j  is a local table of link lists that store pair (p i,j , c i,j ) sorted by p i,j  in an ascending order; c i,j  is the energy consumption only for node v i  with timing constraint j, and p i,j  is CDF (cumulative distributive function) F(j).  
         [0025]     Algorithm  
         [0026]     In this section, the algorithms of our approach are presented.  
         [0027]     Algorithm: Optimal algorithm for the VAP problem (VAP_Opt)  
         [0028]     Input: M different types of voltages, a scheduling graph, and the timing constraint L.  
         [0029]     Output: An optimal voltage assignment.  
                                                                                                                                                                                                     1) Build local table E ij  for each node of PDFG.            2)    1: let D 1j  = E 1j                   2: for each node v i , i&gt; 1 do                 3:   for each time j do                 4:   for each time k in E i,k  do                 5:   if D i−1j−k  != = NULL then                 6:   D ij  = = D i−1 j−k  ⊕ E i,k                   7:   else                 8:   continue                 9:   end if                10:   end for           11:   insert D ij−1  to D ij  and remove redundant pairs using                Lemma 1                12:    end for                13: end for            3) return D Nj                    
 
         [0030]     Algorithm VAP_Opt first builds a local table E i,j  for each node. Next, in step 2 when i=1, G 1  has only one node. We set D 1,j =E 1,j . Then using dynamic programming method, we build the table D i,j . For each node v i  under each time j, we try all the times k (1≦k≦j) in table E i,j . We use “⊕” on the two tables D i−1,j−k  and E i,k . Since k+(j−k)=j, the total time of nodes from v 1  to v i  is j. The “⊕” operation adds the energy consumptions of two tables together and multiply the probabilities of two tables with each other. Finally, we use Lemma 1 to remove the redundant pairs. The new energy consumption in each pair obtained in table D i,j  is the energy consumption of current node v i  at time k plus the energy consumption in each pair obtained in D i−1,j−k . Since we have used Lemma 1 to cancel redundant pairs, the energy consumption of each pair in D i,j  is the minimum expected total energy consumption for graph G i  with confidence probability P i,j  under timing constraint j.  
         [0031]     Theorem 1: For each pair (P i,j , C i,j ) in D i,j  (1≦i≦N) obtained by algorithm VAP_Opt, C i,j  is the minimum total energy consumption for graph G i  with confidence probability P i,j  under timing constraint j.  
         [0032]     Proof: By induction. Basic Step: When i=1, there is only one node, so it is true. Induction Step: In step 2 of the algorithm, we try all the possible. Then we use operator to add the energy consumptions of two tables and multiply the probabilities of two tables. Finally, redundant pair will be removed by using Lemma 1. The new energy consumption in each pair obtained in table D i+1,j  is the energy consumption of current node v i+1  at time k plus the energy consumption in each pair obtained in D i,j−k . Thus, Theorem 1 is true for any i (1≦i≦N).  
         [0033]     It is clear any execution sequence will generate the same D N,j .  
         [0034]     Theorem 2: Given a PDFG, for any legal uni-processor scheduling, the final D N,j  will be the same.  
         [0035]     Experiments  
         [0036]     We present the experimental results of our algorithms. We conduct experiments on a set of benchmarks including 4-stage lattice filter, 8-stage lattice filter, voltera filter, differential equation solver, RLS-languerre lattice filter, and elliptic filter. Among them, the PDFG for first three filters are trees and those for the others are DAGs. Three different voltage levels, R 1 , R 2 , and R 3 , are used in the experiment, in which the node is executed quickest with the highest energy consumption under R 1  and is executed slowest with the lowest energy consumption under R 3 . The execution times, probabilities, and energy consumptions for each node are randomly assigned. The experiments are performed on a Dell PC with a P4 2.1 G processor and 512 MB memory running Red Hat Linux 7.3.  
         [0037]     The experimental results for voltera filter are shown in  FIG. 2 , which are finished in less than one second. In these experiments, we compare our algorithm with the heuristic algorithm HUA of Hua et al. from University of Maryland. In each table, column “TC” represents the given timing and “Ours” represents our optimal algorithm VAP_Opt. The minimum total energy consumption obtained from different algorithms: VAP_Opt and the heuristic HUA, are presented in each entry. Columns “1.0”, “0.9”, and “0.8”, represent that the confidence probability is 1.0, 0.9, and 0.8, respectively. Column “%” shows the percentage of reduction on the total energy consumption, compared with the results of algorithm HUA. The average percentage reduction is shown in the last row “Ave. Redu. (%)” of  FIG. 2 . An entry with “_” means no solution available. From the  FIG. 2 , we found in many situations, algorithm VAP_Opt has significant energy consumption reduction than algorithm HUA. For example, in  FIG. 2 , under the timing constraint  200 , for probability 0.8, the entry under “HUA” is  708 . The entry under “Ours” is  186 , which means by using VAP_Opt algorithm, we can achieve minimum total energy consumption  186  with confidence probability 0.8 under timing constraint  100 , and the energy reduction is 73.7%. On average, algorithm VAP_Opt gives an energy consumption reduction of 64.1% with 1.0 confidence probability, and energy consumption reductions of 61.4% and 58.0% with 0.9 and 0.8 confidence probabilities respectively. Compared with HUA, the expected total average energy consumption improvement of our algorithm VAP_Opt is 61.2%.  
         [0038]      FIG. 3  depicts the impact of timing constraints on energy consumption for voltera filter. We fixed the guaranteed probability as 0.80. The solid line with “+” stands for the results from algorithm VAP_Opt. The dashed line stands for the results from algorithm HUA. The dot dashed line with “_” is the result curve of energy saving percentage of algorithm VAP_Opt to HUA. This shows the design space exploration can be well explored by using our optimal algorithm.