Lars Wehmeyer

Influence of Memory Hierarchies on Predictability for Time Constrained Embedded Software*

Safety-critical embedded systems having to meet real-time constraints are to be highly predictable in order to guarantee at design time that certain timing deadlines will always be met. This requirement usually prevents designers from utilizing caches due to their highly dynamic, thus hardlypredictable The integration of scratchpad memories represents an alternative approach whichallows the system to a performance gain comparable to that of caches while at the same time maintaining predictability. In this work, we compare the impact of scratchpad memories and caches on worst case execution time (WCET) anulysis results. We show that caches, despite requiring complex techniques, can have a negative impact on the predicted while the WCET for scratchpadmemories scales with the achievedPerformance gain at no extra analysis cost.

Introduction

The growing gap between increasing processor speeds and the slower main memory, also known as the "memory wall" has become a bottleneck for computer designers. In traditional computer systems like desktop caches are usually introduced in order to hide the high latencies of main memory accesses. Especially for real-timeembedded systems, predictability is an important issue: even during the design phase of such a system it must be guaranteed that certain deadlines will always be met. The use of caches, however, tends to improve only the average-case performance, not necessarily the worstcase execution time (WCET). Estimating a cache's contribution to WCET requires complex analysis techniques to model its dynamic behavior which is hard to predict in a safe, yet not over-pessimistic way.

An alternative approach that has been investigated with respect to performance and energy consumption is the use of socalled scratchpad memories, also known as "tightly coupled memories" (TCM). They are small memories mapped into the processor's address space. Due to their small size, scratchpad memories are extremely fast and require very little energy per access. They are more efficientthan caches since the hardware logic required to control a cache is not required for a scratchpad. The organization and utilization of the 'This work has been sponsored in part by EU-project ARTIST2 pad is rather left to the programmer or to the compiler. However, a comprehensive methodology for the efficient utilization of scratchpad memories is surprisingly still missing in industry.

Previous work proposed mapping the hot-spots of an application to the scratchpad memory in order to gain performance and to save energy. Apart from improvements concerning these optimization goals, the mentioned methods also have a beneficial effect on worst case execution time. In contrast to a cache, all decisions concerning the layout of memory objects during execution of the application are fixed at compile time, making all memory accesses inherently predictable. In this paper, we assume different sizes of scratchpad memories and unified caches. For each configuration, we determine the performance of several benchmarksby simulation using a typical input data set. Additionally, we perform WCET analysis on the applications, once for scratchpads and once for caches. The results obtained for scratchpad memories and caches are then compared.

The rest of this paper is structured as follows: the next section considers some of the previous work on scratchpad allocation algorithms as well as WCET analysis, which form the basis of this work. In section 3, we describe the workflow used to generate application executables for use with scratchpadmemories and caches and show how the WCET analysis was performed. Results are presented in section 4. A summary and possible future work conclude the paper.

Related Work

Today's markets expect computer systems to show a steady increase in computing power. Since the limitations concerning miniaturization and ever faster gigahertz processors are starting to show, computer architects are forced to include performance enhancing features so as to meet the customers' demand for high performance. Examples for such features are the use of pipelines or speculative execution using branch prediction units. The growing speed gap between processors and the slower memory is the main reason for the widespread integration of caches.

All the above techniques help increase the average case performance of a system. In embedded systems, however, it is often necessary to be able to guarantee that timing deadlines will never be violated. The required worst case execution time analysis techniques become increasingly difficult when many of the above-mentioned architectural features are present in the 1 processor. Their highly dynamic behavior makes it hard or even impossible to effectively predict the worst case timing at design time A general overview over available analysis techniques for the architectural features mentioned above can be found in Of particuar interest is the work by et al. who consider the presence of a direct mapped instruction cache in the WCET analysis of embedded systems. A cache conflict graph is used to approximate the behavior of the cache and to determine the total number of hits and misses. A follow-up paper [START_REF] Yau-Tsun Steven Sharad | Cache Modeling for Real-Time Software: Beyond Direct Mapped Instruction Caches[END_REF] extends the work to also cover set associative instruction caches as well as data and unified caches. One solution to the problem of data caches presented in is the introduction of predictable data structures, which should be used by the programmer for timing critical code. Tan et al. [START_REF] Tan | Integrated Intra-and Inter-task Cache Analysis for Preemptive Multi-tasking Real-Time Systems[END_REF] extended the considerationof caches to also cover the case of multi systems. In this case, the preemption of tasks can lead to additional cache miss overhead which has to be considered and evaluated, further complicating cache analysis.

A conceptfor separating program path analysis and microarchitectural analysis into two steps in order to reduce the complexity of WCET analysis is presented in Results are reported to be comparable to combined analysistechniques. This approach is also used in a commercial WCET analysis tool that is available for several processor and cache architectures.

is actively used in industry, by Airbus France in order to determine upper bounds for the execution times of critical avionics software. As input, the tool takes an executable for a specific platform along with user supplied annotation data concerning loop bounds and access addresses as well as architectural information concerning the memory layout. It then generates a safe upper bound for the expected WCET. Using the elaborate (if at all feasible) task of finding input sets for which a simulationrun yields the maximum execution time is no longer required. The commercially available version of for ARM7 is currently not equipped with a cache analysis. provided us with a simple experimental cache analysis for the ARM7 cache that uses only a subset of the analysis techniques available with commercial versions of One of the difficulties with caches integrated into ARM processor cores is the fact that they use a random replacement policy, making precise estimates for cache behavior difficult. For caches that use an LRU replacement, WCET analysis can yield tighter bounds.

In contrast to a cache, no extra analysis module is required in order to investigate the effect of a scratchpad memory on WCET, since it is simply introduced as a new, distinct memory region.

In general, scratchpad memories are an effective replacement for caches since they can help bring down energy consumption and at the same time offer performance benefits comparable to those of caches 113. For this reason, scratchpad memories are becoming more popular and are widely available in the ARM9 processor series under the name Tightly Coupled Memory (TCM). The one drawback of scratchpad memories is the fact that they need to be actively exploited by the programmer or the compiler. Since the scratchpad does not have any logic to dynamically control its contents at runtime, memory objects have to be allocated to the scratchpad by the compiler. The handling of memory allocation during the compilation process is advantageous since the compiler has detailed knowledge about execution and access frequencies. This information is used to distributememory objects among the available different memories in an optimal way instead of using dynamic ad-hoc decisions as in a cache.

Memory allocation can be performed either in a static or in a dynamic way. In the former approach, the scratchpad is preloaded with a set of memory objects which stay on the scratchpad throughout the application's execution time. This static approach was first used in to allocate data objects like arrays to a scratchpad memory. In both instructions and data are allocated to the scratchpad in order to save energy by exploiting the scratchpadmemory's low power dissipation.

The dynamic approach allows memory objects to be copied to the scratchpad at runtime. Dynamic allocation techniques presented in consider data and instructions, respectively. These approaches are of particular benefit when large programs with several and changing sets are used. A new paper uses a technique based on register allocation for CISC architectures to allocate both instructions and data to the scratchpad in a dynamic way. Considerable savings of up to 38% concerning energy consumption compared to a static approach are reported. Note that the objects and the points in time at which they are copied to the scratchpad are all fixed at compile time. Thus, both static and dynamic scratchpad usage are under full control of the compiler or the programmer, making the methods inherently predictable. Concerning WCET, this means that using a scratchpad and a compiler-based algorithm to utilize it, no additional analysis is required for WCET analysis. Despite the additional overhead at compile time for application analysis and object allocation to the different memories, using a scratchpad offers an advantage over caches which generally show a dynamicbehavior that is hard to predict at compile time and require complex analysis techniques in order to determinea tight upper bound for WCET.

In this paper, we will use the static allocation technique presented in to allocate functions and global data to the scratchpad in an energy-optimal way using the energy model for the processor described in The energy consumption of caches and scratchpad memories is modelled according to

The problem of finding an optimal mapping of memory objects to the scratchpad and main memory is solved by formulating it as a variant of the knapsack problem and using a commercial ILP solver [ This is repeated for different scratchpad memory capacities. The resulting executables are simulated with instruction set simulator using a typical input data set leading to an average case runtime.

To determine the effect of using scratchpad memories on WCET, the executables using different sizes of scratchpads are also analyzed using Information about the used memory architecture, including main memory and scratchpad memory timing and address information, has to be provided to the tool. Apart from this annotation, no further information or analysis is required compared to a system that only uses main memory.

To compare scratchpads with caches, an executable generated without using the scratchpad optimization in the compiler is simulated using unified, direct mapped caches of different sizes. These parameters are configurable in ARMulator. WCET analysis is performed using the available cache analysis tool for the ARM7 processor integrated into

The determined WCET using a cache is then compared to the scratchpad case.

Workflow

The workflow used to compare the impact of scratchpads and caches on WCET analysis results is shown in Figure 1. The benchmark programs, written in the C programming language, were compiled into executables assuming either a cache or a scratchpad in the target system. Our compiler generates instructions in the 16bit THUMB mode of the ARM7 processor. Because of the higher code density, this instruction set is recommended for energy-and size-constrained systems

ARMulator ARMulator

Figure 1:

The left branch of Figure 1 shows the scratchpad setup. To generate simulation results for a scratchpad based system, the compiler takes as input the size and the access costs of the scratchpad to be used. This information is used to solve the corresponding knapsack problem. It is formulated in ILP notation using a benefit function which associates each memory object (function or global data element) with a certain energy gain if this object is statically allocated to the scratchpad memory instead of main memory. This benefit is maximized in the objective function under the constraint that the capacity of the scratchpad is not exceeded. For details of the used algorithm, please refer to [ which also describes how to treat basic blocks and basic blocks, an extension not used for the results in this work.

The generated executablethen contains address information for all memory objects, which means their static location in main memory or scratchpad is known. The executable is simulated using ARMulator, which in turn receives information about the size and the address range of the used scratchpad memory. ARMulator can thus determine the number of cycles required to execute the benchmark using a typical example input data set, taking into account the reduced access latencies of the scratchpad memory compared to main memory. The result of this step is a simulated average case execution time. This code generation and simulation was repeated in our workflow for scratchpad sizes from 64 bytes to

The influence of using a scratchpad on WCET was determined using

Even though no additional software module is required in order to investigate this effect, the use of a pad requires an annotation in the configurationfiles. supports the specification of memory regions with different attributes. As shown in table 1, the scratchpad region always requires one cycle per access. Annotating the timing of the scratchpad region is actually the only additional effort required in order to support scratchpad memories in the WCET analysis.

Access Width

Main Memory Scratchpad Byte (8 Bit) (16 Bit) Word (32 Bit) 4

Table 1: Cycles per memory access (access + waitstates)

In our model, which is based on the evaluation board by ATMEL Corp., the access times to main memory depend on the width of the access. Since does not currently allow the definition of access times depending on the bit width, the waitstates for the different regions in main memory have to be annotated in order to obtain valid results concerning WCET. Since our compiler generates 16 bit THUMB mode instructions,but integer data elements occupy 32 bit, the different access times for instruction and data fetches shown in table 1 have to be accounted for. An instruction fetch from main memory causes one cycle for the actual access and one additional waitstate. Accessing a 32 bit data element from main memory requires four cycles, since three additional waitstates occur. This is reflected in the annotation file shown in Figure 2 for one benchmark and one particular scratchpad configuration: The first memory area represents the scratchpad memory: Each access takes 1 cycle with no additionalwaitstates, independent of the of the access. The "1: indicates that the memory runs at the same clock speed as the processor. For main memory, we need to differentiate between 16 and 32 bit accesses. The second region contains 16 bit instructions, requiring two cycles per access. The next region represents a socalled literal pool, 32 bit data elements within the instruction region used to load large constants into a register. Accessing a 32 bit value from a literal pool requires four cycles. The specification of the memory areas requires some annotation overhead, but it should be noted that this is always necessary if memories with different access times are used. The scratchpadmemory with its uniform access times actually simplifies the annotation process since scratchpad regions are not divided depending on the bit width of the memory objects. Most of the regions and addresses can be determined automatically from address information provided by the linker.

One more requirement for a scratchpad memory is the annotation of function calls that jump from main memory to the scratchpad or vice versa, since the relative branch offsets within the executable do not reflect the actual execution time addresses after the program has been loaded into memory.

We will now consider the workflow employed when a cache is used in the memory hierarchy (right branch of Figure 1). Since a cache is in general transparent to software, it does not need to be considered during code generation. Therefore, generating one executable for use with all cache sizes is sufficient. Of course, there are cache-based optimizations that can help prevent cache conflicts through techniques like array partitioning or loop tiling but these are not considered in our approach since it is doubtful that the benefits will also reflect in improvedWCET estimates.

The executables generated by the compiler are simulated us- ing ARMulator. The instruction set simulator requires information about the cache size and organization in order to be able to determine the number of cycles required for executing the benchmarks for the different cache capacities from 64 bytes to 8k. For our experiments, we assumed a simple direct mapped unified cache architecture found in ARM processors. Each cache line holds four 32 bit words.

To determine the WCET using caches, the executables are also analyzed using the WCET analysis tool

The cache analysis feature for the ARM7 is used to estimate the WCET of the benchmarks using different cache sizes. Despite the fact that the used cache analysis only includes a MUST-analysis and no persistence considerations, we would like to stress that for a scratchpad, no additional analysis technique is required at all.

Like for the scratchpad case, information about the timing of cache hits and misses has to be annotated in the configuration files. The differentiation between 16 an 32 bit accesses required above for main memory accesses is not necessary in this case, since the cache always performs 32 bit accesses to fill an entire cache line on a miss. Assuming a cache line length of four, the loading of an entire cache line requires four 32 bit accessesto the main memory. Accordingto table 1, this means 12 additional waitstates, assuming the used memory does not support burst transfers. A cache hit only requires one cycle to retrieve the accessed word from the cache. This timing information is annotated in configurationfile. In addition to the memory region annotations mentioned above, the user also needs to specify the bounds of loops that did not detect automatically, as well as the range of possible addresses for those array accesses that could not be determined by This can happen within our framework because starting addresses of arrays may be allocated to a different memory region to scratchpad), which is not directly reflected in the executable analyzed by Array access annotation is of particular interest for the cache analysis, since it is in general not decidable which element of the array is actually being accessed at what time during execution of a benchmark. The generation of all of the annotations mentioned above is automated using information from the simulator and from the linker.

Once all annotations have been performed, can analyse the WCET of the application. The results of simulation and WCET analysis for scratchpad memories and caches are presented in the following section.

Results

The benchmarksused to explore the impact of scratchpadsand caches on WCET are given in table 2. They comprise two speech encoding and decoding algorithms from the mediabench benchmark suite and a mix of sorting algorithms commonly found in many algorithms.

Name Description G.721

Speech encoding and decoding, reference

AdautiveDiff. Code Table 2 Benchmarks

For all results presented in this section, there is always a certain difference between the WCET estimated by and the number of cycles determined using simulation. Please note that this overestimation is due to the comparison of an average case simulation using typical input data to the longest possible execution time. This approach was chosen since it is generally infeasible to determine a worst case input data set for an arbitrary application. Using a simple sorting algorithm with a known worst case input data set, the results obtained by simulation on one hand and by WCET on the other only differed by highlighting the high precision of the used WCET analysis tool.

First of all, the benchmark programs were compiled and simulated using ARMulator with a setup of varying scratchpad sizes. As expected, the simulated execution time decreases when the scratchpad capacity is increased. So does the estimated WCET determined by as can be seen for the G.721 benchmark in Figure

WCET decreases at the same rate as the actual cycles determined by simulation do. The step function appearanceof the scratchpad simulation cycle count is due to the consideration of only functions and global variables, as described above.

The next step comprises simulation and WCET analysis of a system employing a cache in the memory hierarchycf. Figure 3b). Simulation times using a cache are quite similar to the scratchpad values for the G.721 benchmark. For a very small cache, the execution times go up due to the high ber of conflict misses. After that, times decrease at roughly the same rate as they do for a scratchpad. The estimated WCET, however, shows a very different behavior: it stays at a very high level for all cache sizes instead of scaling with the average case performance improvements. Despite the fact that for ARM7 has only been equipped with a subset of the cache analysis techniques available with commercial versions of for other processors, it should be clear that the much better results concerning WCET analysis when using a scratchpad were achieved with an even simpler analysis technique not requiring any additional cache analyses. Figure4 shows the ratio of the WCET estimation to the simulated number of cycles for different scratchpad and cache sizes for the G.721 benchmark. The simulated number of cycles was normalized to the value 1. The main observation in this figure is that the difference between average case simulation and WCET analysis results remains constant for all scratchpad memory sizes, meaning the added performance obtained by including a scratchpad memory in a system translates directly to an improved estimated WCET. Using a cache, on the other hand, can lead to a strong WCET overestimation in particular for large cache sizes. Since the cache's behavior is hard to predict, it is difficult to provide a sufficiently tight upper bound for the WCET. A similar picture can be observed for the benchmark. Using a scratchpadmemory, the WCET is about 3 times as high as the simulationtime for the given input data set. Note again that this overhead of WCET over simulation stems from the fact that typical, not worst case input values were used to generate simulation results. For the scratchpad approach, the ratio of WCET to simulation cycles stays more or less constant over the considered range from 64 bytes to of scratchpad, whereas for the cache, the differencebetween WCET and simulation cycles increases strongly with the cache size. This is due to the ever largeruncertainty concerning cache misses when the cache size increases. Figure 6 for the ADPCM benchmark shows a clear performance benefit of the scratchpad compared to a cache, in particular for small sizes. For a cache that is too small, a lot of cache misses occur for this program, leading to a severe performance degradation.

It can furtherbe observed that the overall deviation of WCET and simulated cycles is always very low for this benchmark. This may either be due to the fact that the chosen input set is close to a worst case set, or that the program is not very control flow intensive and thus consistsmainly of the critical path. Despite the fact that the ratio of simulated average case time and WCET is indeed better for a cache of 128 bytes than for a scratchpad, it can be seen that both the performance and the WCET estimate for a scratchpad are better in absolute numbers. For larger cache and scratchpad sizes, the behavior seen for the other benchmarks also becomes apparent for ADPCM: the uncertainty concerning cache behavior prevents the WCET analysis results to be as close to the average simulation performance as they are for a scratchpad.

The results clearly show that using a scratchpad in a realtime embedded system is advantageous. Without further analysis effort, the WCET estimate reflects the actual average-case performance gain achieved by utilizing a scratchpad. The only necessary modification in the tool is to specify the memory regions and their access latencies.

Summary and Future Work

In this work, we compare the effect of using caches or scratchpad memories on WCET analysis results for time constrained embedded systems. We use a known scratchpad allocation algorithm to place functions and data onto the scratchpad memory and annotate the configuration files of the used WCET analysis tool accordingly. We show that for caches, the difference between simulated average case execution time and WCET can grow larger for increasing cache sizes. The magnitude of this difference depends on the cache architecture and the analysis techniques. Using scratchpad memories leads to a decrease of the estimated WCET for growing scratchpad sizes, with a near constant ratio between measured average case simulation time and the WCET analysis results throughout the range of considered scratchpad sizes. The benefit obtained by using a scratchpad memory directly translates to a reduced WCET estimate. Scratchpad memories should thus be considered as a feasible and worthwhile option during the design of time constrained systems, since their application improves not only the average case performance, but also helps reduce the predicted WCET.

This work is a first step of comparing scratchpad memories and caches in real time embedded systems. In the future, we will consider other cache configurations instruction caches instead of unified caches as well as set associative caches) to investigate their effect on WCET, and again compare the results to using scratchpadmemories.

We expect that using the full scale of cache analysis techniques as described in would probably lead to improved cache results with respect to WCET. However, despite the complexity of cache analysis tools available today, it is doubtful that the results achieved by using an inherently predictable scratchpad can be reached.

We will use the full featured allocation technique also considering basic blocks for allocation onto the scratchpad memory instead of just complete functions. This is expected to further improve results for the scratchpad case due to the finer allocation granularity. The dynamic memory allocationof instructions and data presented in [ will also be investigated under the aspect of worst case execution time.

Finally, the allocation technique will be extended to not optimize the allocation of objects to the scratchpad memory using an energy cost function, but rather to consider placing those objects onto the faster memory that lie on the critical path of the application. This is expected to lead to even better WCET estimates.

Acknowledgement

The authors would like to thank Angewandte matik GmbH for their support concerning WCET analysis using the framework.

Figure 2 :

 2 Figure 2: Example annotation for using scratchpad and main memory The remaining memory regions represent the data region of the executable. Arrays of 32 bit values require 4 cycles per

Figure 3 :

 3 Figure 3: Results for G.721 benchmark

Figure 4 :

 4 Figure 4: Ratio of WCET and Simulated Cycles for cache and scratchpad based systems

Figure

  Figure MultiSort: Ratio of WCET and Simulated Cycles for cache and scratchpad based systems

Figure 6 :

 6 Figure 6: Results for ADPCM benchmark

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Home.

available from:


Sharon Xiaobo
email: shu@cse.nd.edu

Exploiting Dynamic Workload Variation in Low Energy Preemptive Task Scheduling

A novel energy reduction strategy to maximally exploit the dynamic workload variation is proposed for the offline voltage scheduling of preemptive systems. The idea is to construct a fully-preemptive schedule that leads to minimum energy consumption when the tasks take on approximately the average execution cycles yet still guarantees no deadline violation during the worst-case scenario. End-time for each sub-instance of the tasks obtained from the schedule is used for the on-line dynamic voltage scaling (DVS) of the tasks. For the tasks that normally require a small number of cycles but occasionally a large number of cycles to complete, such a schedule provides more opportunities for slack utilization and hence results in larger energy saving. The concept is realized by formulating the problem as a Non-Linear Programming (NLP) optimization problem. Experimental results show that, by using the proposed scheme, the total energy consumption at runtime is reduced by as high as 60% for randomly generated task sets when comparing with the static scheduling approach only using worst case workload.

Introduction

Energy consumption is one of the critical design issues in real-time embedded systems (RTES), which are prevalent in many applications such as automobiles, and consumer electronics, etc. RTES are generally composed of a number of tasks to be executed on one or more embedded processors. Dynamic voltage scaling (DVS), varying the supply voltage and the corresponding clock frequency of a processor at runtime according to the specific performance constraints and workload, is proven to be very effective for reducing energy consumption [ Many modem embedded processors support both variable supply voltage and the controlled shutdown mode How to maximally exploit the benefit provided by such hardware has been an active research topic during the last several years. In this paper, we focus on real-time embedded preemptive systems using variable voltage processors. Having an effective voltage schedule, the voltage to be used at any given time is critical to harvest the DVS benefit. There are two main approaches to find a voltage schedule. One category of approaches [ 5 determines the schedule during runtime only. These results can work with either real-time or non-real-time tasks. The basic principle is that only the runtime workload information which is predicted during the online phase is used to determine the voltage schedules. Although such approaches have been shown to result in energy saving, they do not exploit the fact that much information about tasks in an RTES, such as task periods, deadlines, worst-case execution cycles (WCEC) and average workload, is available offline. It is not difficult to see that not using such information may lose opportunities to further reduce the energy consumption.

To complement the above runtime approaches, the other category of voltage scheduling work finds the desired voltage schedules offline based on the available task information, [ These techniques are generally applicable to real-time tasks with hard deadlines. To ensure that the schedule obtained in offline does not violate any timing constraint, the worst-case execution cycles (WCEC) of each task is always used in the offline analysis. Such offline voltage schedules can be altered to some extent at runtime by using the slacks resulted from the tasks not executing at the WCEC to lower the voltage obtained in the offline phase

The effectiveness of the offline approach together with the runtime approach is very much dependent on how the slacks are distributed, which in turn depends on the end-time obtained in the static schedule. Therefore, it is important to schedule the tasks in such a way that the potential slack times can be maximally exploited. For many real-time systems, most of the time the workload of the tasks are much smaller than the worst case and on average the execution cycles of the tasks are close to an average-case execution cycle value (ACEC) instead of the WCEC. In general, the schedules obtained from the WCEC values can greatly limit the flexibility and effectiveness of utilizing the slacks generated from the actual execution cycles during runtime.

In this work, a novel offline scheduling approach, which results in the best slack distribution in terms of energy saving for the ACEC scenarios yet guarantees no deadline violation when tasks assume WCEC, is introduced. We focus on preemptive systems, which are more complicated, and it is easily to transform the formulation for non-preemptive systems. To the best of our knowledge, this is the first work that incorporates the ACEC and the WCEC together during the offline variable voltage scheduling. Given that the workload distribution of many real-times can be estimated offline using profiling [ 1 our approach can achieve much higher energy saving. Experimental results show that significant energy reduction is achieved when the ACEC is considered during the offline scheduling phase.

Preliminaries and Motivation

System model

In this paper we assume a frame-based preemptive hard real time system in which a frame of length which is the period of the task-sets, is executed repeatedly. Rate monotonic (RM) scheduling policy is used to schedule the periodic tasks where the shorter the period of the task, the higher the priority. The priorities of two tasks are the same if they have the same period. A higher priority task will always preempt the current task. We assume no blocking section is available for a task and hence a higher priority task will preempt the lower priority tasks immediately once it is released. The tasks are assumed to be independent of each other. Our technique works for both dependent and independent tasks as well as for multiple processors. For simplicity, we only consider the single processor case in this paper.

Without loss of generality, a set of N periodic tasks is denoted as { with has a higher priority than if Each task has its own period the Execution-Cycles (WCEC) and the

Execution-Cycles (ACEC)

The ACEC is defined as the expected value of the execution cycle base on the workload distribution and it can be obtained by profiling techniques [ The relative deadline is assumed to be equal to the period Each task releases its instance periodically. The first instance of all the tasks is assumed to be released at time Also, each task instance has its own absolute release time and absolute deadline

The and the relative deadline of each instance of the task are assumed to be the same. For a lower priority task instance it may be preempted by others during execution and hence it will be divided into several instances and each sub-instance is denoted as where if is preempted into K sub-parts. When there is no preemption for the task the task instance itself is denoted as in order to have a consistent notation. Also, we denote the number of the task instances of be and the upper bound of the number of sub-instances be

Motivational example

In this sub-section, we use a non-preemptive system as a motivation example to illustrate the idea of exploiting the workload variation for voltage scheduling. The main idea for preemptive and non-preemptive system is the same except that the formulation of the problem is different. The problem formulation for the preemptive system will be discussed in Section 3. the supply voltage of task

The cycle time, and the task execution time can be computed as Let be the effective switching capacitance and be where is the threshold voltage, is a device related parameter and a is a process constant which is between 1 and 2.

The total energy consumption of executing task is given by

Voltage (V)
Table 1. It is clear that the dynamic slack redistribution indeed leads to more energy saving. However, if we know that the tasks most probably take the ACEC values during actual execution, can we do better?

Let's examine the static schedule in Figure 1 a little bit closer. In this schedule, each task is associated with a predetermined end time, end time is is etc. These end times are then used in the dynamic slack distribution process to compute a new voltage schedule. The static schedule essentially determines the end time for each task. (Note that this predetermined end time can be different from the actual end time when a task does not assume the WCEC. Since this predetermined end time is used frequently in our discussion, we simply call it the end time). Such end times are obtained so that the tasks will complete by their deadlines and the overall energy is minimum if tasks take on the WCEC. Now, consider a different schedule where the end times of each task is given as follows: the end times of and are 10, 15 and 20 ms, respectively. Using this schedule and the same greedy slack distribution as above, we obtain the runtime schedule as shown in Figure

The overall energy consumption of the schedule is a 24% improvement comparing with that of the schedule in Figure

Though the schedule used by Figure 2 leads to a bigger energy saving, it is important that the schedule can still meet the deadline requirement when tasks assume the WCEC. It is true that the schedule dictates that the end time of task is no later than its deadline. However, if the schedule is not carefully chosen, the tasks may not be able to finish by their deadlines during runtime. Figure

shows what happens under the schedule used in Figure if the tasks do take the WCEC during runtime. At time zero, a 2V is adopted for Since takes the WCEC, it will not finish until

The voltages for and can be computed accordingly. Note that 4V is for both and in order to meet the timing constraints. If the maximum voltage level for the processor is the schedule would not be feasible. Therefore, simply using the task deadlines as the desired end times does not always give a feasible schedule.

We would like to point out that the actual schedule in Figure when tasks happen to take the WCEC, consumes energy, a 33% increase over the schedule in Figure However, in general, actual execution cycles of a task tend to be close to an average case value and only rarely equal the WCEC value. Based on this observation, we would like to find a static schedule that result in better energy saving on average but still satisfy the timing requirements for the worst case. Even though the above example deals with the non-preemptive schedule only, the basic idea is the same with preemptive scheduling and we will discuss how to formulate the problem of preemptive schedule in the next sections.

In the preemptive system, a task will be preempted into several sub-instances and how to assign the optimal workload for each sub-instance to obtain overall minimum average energy consumption is a challenging problem. With the optimal workload assignment, we can find the corresponding end-time in the static schedule. The static end-time as well as the WCEC for each sub-instances will thus be used for the calculation of the runtime supply voltage.

Our Approach

From the discussion above, we can see that the greedy slack distribution (or any other slack distribution) relies heavily on the tasks' end time obtained in the static schedule. Existing static voltage scheduling techniques employ the WCEC in order to guarantee that no deadline violation occurs during runtime. Because of the use of the WCEC, the end time of each task is usually more conservative. If we could extend the end time of each task to as long as that allowed by the worst-case execution scenario, it will have more potential for the dynamic slack distribution to achieve more energy saving for the average cases. So our problem is that given the effective switching capacitance, the workload distribution, WCEC, release time and deadline of each task, find a desired schedule, the desired end time of each task, which strive to maximize the potential energy saving when the tasks are executing based on the workload distribution.

In this section, we show that this scheduling problem can be formulated as a mathematical programming problem. We ignore the voltage transition overhead in our formulation. In most RTES applications, the task execution time is much longer than the voltage transition time. As stated in the increase of energy consumption is negligible when the transition time is small comparing with the task execution time. In the rest of this section, we adopt the following convention: and the average and the worst case values of x, respectively. For example, and are the average execution cycles and the worst case execution cycles of task sub-instance , respectively.

Fully Preemptive Schedule

In our formulation, we want to find the static end-time for each sub-instance by optimally assigning the workload so that the average energy consumption is minimum while all the worst-case requirements are satisfied. In variable voltage scheduling, task's execution time varies inversely with the supply voltage by equation ( 2). With a longer execution time, the number of preemption by the other higher priority tasks, and hence the number of task sub-instances, is higher because the overlapping region with the higher priority tasks is larger. In order to ensure feasibility of the final schedule and to allow maximum flexibility for the mathematical programming to find the optimal assignment, we need to consider all the possible preemption and the maximum number of task sub-instances.

Here we construct a fully preemptive schedule which reflects all possible preemptions based on the periods and priorities of the tasks. All the possible sub-instances of the task instances are found in this schedule. Figures 3 and4 show an example of how to obtain the fully preemptive schedule. Suppose we have three tasks with and The initial task instances for a hyper-period are shown in Figure 3. All possible preemptions to a task instance are obtained and the original schedule is expanded to a fully preemptive schedule as shown in Figure 4.However, the actual run-time schedule may not be the same with this schedule because the lower priority task may finish execution before the higher priority released. Here, we want to deal with a more general case that the optimal workload required for each sub-instances are found during the mathematical programming formulation. From the fully preemptive schedule, we can obtain the order of the execution of the tasks' sub-instances which is based on the priority and the release time of each sub-instance. is preempted by and so Since and are originated from the same task instance, we have

The total order in Figure 4 is given by:

Problem Formulation

Determining the schedule that optimizes the energy consumption for a preemptive task-set based on the tasks workload distribution while satisfying the timing requirement in the worst case can be formulated as a Non-Linear Programming (NLP) problem. The model consists of an objective function that minimizes the average energy consumption of the system when the tasks take on some workload distribution while subject to a set of resource and timing constraints. The interesting part of this formulation is the way we relate the average execution cycle based on the probability density function of the workload and the worst case execution cycle. If the probability density function is not known, we can use the ACEC as an approximation. In it is shown that this is a good enough approximation of the average energy consumption. We assume the processor can use any voltage value within a specified range. In the following formulation, denotes the current task sub-instance and the previous task subinstance based on the order of the fully preemptive schedule. Next, we define the variables that we are going to find:

Average start-time of End-time of Average workload of Worst-case workload of supply voltage of on average workload Supply voltage of T,,, based on worst-case workload Among these variables, only the end-time and the worst-case workload variables will be passed to the online DVS phase to calculate the runtime supply voltage. In order to satisfy the worst-case requirements during runtime, the value of and will be determined suitably together with the other variables when solving the NLP. It is important to note that the average start-time depends only on the average workload of the previous task but not the average workload of itself since the start time depends on the slack available from the previous tasks. However, the end-times are the same for both the average-case and the worst-case workload conditions. The complete NLP formulation is described as follows.

The objective function of the NLP formulation is k=l

The probability weighted workload can be used in the objective function if the probability density function is known. Here, we use the average workload in the formulation. To meet the release time and deadline requirements as well as the voltage range requirement, the following constraints are used: Also, we need to make sure that there is enough allowable working time between the end time of and for to finish if both tasks use WCEC. We express this by the If we do not consider the dynamic slack distribution, we would need in order to ensure that no task executions are overlapped. Allowing the slacks of finished tasks to be utilized by the subsequent tasks can be thought of as the average start time of becomes earlier than the scheduled end time of if uses ACEC instead of WCEC. Assume that the greedy slack distribution is used, the difference between and bounded by the difference of the worst case execution time and the average case execution time, the slack of Therefore, we have the following constraint:

Now, we need to determine the workload assigned for each task sub-instance. The sum of the workloads of the instances is equal to the workload of the task instance because each sub-instance executes only part of the work of its parent task instance. We assume the workload of every instance of the task is the same and hence and we have

k = l
The average workload is always less than or equal to the worst-case workload. so we have:

From equations (1 and we can see that there are many combinations of and with the sums are equal to and . To find an optimal value for each of them, we divide the workload distribution of all the sub-instances into three cases. Here, we need to explain the meaning of the average workload of the sub-instances. It represents the amount of workload that should be executed on that particular instance when the task instance takes the ACEC. For example, the ACEC and WCEC of a task instance are equal to 15 and 30, respectively. Also, it is preempted into three sub-instances and all of them with WCEC equals to 10. This means that each of them can execute up to 10 units of execution cycles. During the average-case scenario, the first sub-instance will execute units but not 5 units units) because the next sub-instance will start execution only if the previous sub-instance already reaches the worst-case limit. With the same argument, the ACEC of the second and third sub-instances are 5 and 0 units, respectively. The ACEC of the third sub-instance is 0 unit means that this sub-instance does not need perform any execution during the average-case while it is still reserved with enough time slots when the actual execution needs the worstcase cycles. In this case, all the sub-instances need to perform units' execution cycles. Now we formulate the above idea in the form of mathematical programming. For each sub-instance falls into one of the following cases: (case 1) (case 2)

otherwise. From the above discussion, we can see that to satisfy the average workload distribution, we have = all task sub-instances that belong to case 1. For case 2 because the average workload will be automatically assigned a suitable value according to the constraint and the fact that the average workload of some of the case 1 task sub-instances have already been assigned. Considering the example shown in Figure 5 where has three sub-instances. The first subinstance belongs to case 1 because In the mathematical programming formulation, we deal with a more general case that more than three sub-instances are allowed. However each of the sub-instances still falls into either one of the two cases. The NLP formulation of the above idea is presented as follows. . Otherwise, constraint ( 14) is trivially true when Finally we need to define the worst-case workload for each of the task sub-instances to yield the best energy saving. However, it is already done since its values are already governed by equations ( 12) and ( 13). From the above formulation, solving the NLP problem will results in the optimal assignment of the workload to each sub-instance and the corresponding end-time of each sub-instance will also be obtained.

Experimental Results

To demonstrate the effectiveness of the proposed technique, which we denote as ACS, a series of experiments, including both randomly-generated task-sets and real-life applications, were carried out. For a given number of tasks, one hundred random task sets were constructed and each taskset results in maximum one thousand of sub-instances. We repeatedly simulated each taskset for one thousand hyper-period. Similar to the experimental settings in we consider the number of execution cycles of each task varying between the best case (BCEC) and worst case (WCEC) following a normal distribution with mean, = ACEC , and standard deviation, The WCEC of a particular task instance was adjusted such that the processor utilization is about 70% when all the tasks are running at the maximum speed

We compared the energy consumption using ACS with the energy consumption of the static scheduling method that only considers WCEC in obtaining the scheduling. We denote the later as WCS. The runtime energy consumption is the actual energy consumption after performing the Dynamic Voltage Scaling (DVS) based on either the ACS or WCS static schedules.

Figure 6 summarizes the experimental results. Figure shows the comparison between ACS and WCS for different number of tasks when the ratio varies between 0.1(highly flexible execution) and fixed execution). Y-axis is the percentage improvement in energy consumption of ACS over WCS. It shows that as the number of tasks increases, the energy efficiency of using ACS increases. This can be explained by the fact that as the number of tasks increases, more task sub-instances can use a lower supply voltage by exploiting the workload variation and utilize the slack time generated from the variation. It can be seen that comparing with WCS, the improvement in energy reduction reaches the highest value, about 60% when the value is 0.1 and number of tasks is ten. This is because there are a lot of slacks available when the is low and ACS provides a much better slack utilization in this scenario and minimizes the overall average energy consumption. However, when there is little slack available, when ratio is high, there is not much improvement as there is little room for both methods to reduce the energy consumption.

To further validate the proposed algorithm, we applied our algorithm to two real-life applications, computer numerical control CNC [ and GAP [ The comparisons of the energy reduction with WCS are shown in Figure

It can be seen that the improvements over WCS are as high as 41% and 30% when the ratio is 0.1 for CNC and GAP respectively. preemptive schedule. The potential slack generated by the later tasks can be utilized by the early tasks by considering the average execution workload during the static voltage scheduling. The problem is formulated as a Non-Linear Programming (NLP) and experimental results showed significant improvement in energy reduction.

Conclusions

A novel energy reduction strategy in the off-line static voltage scheduling phase was introduced. The preemptive nature of the scheduling is considered by using a fully

  Figure 1. A motivation exampleWe use a simple example to illustrate the effect of a static schedule on energy saving when dynamic slack redistribution is employed. Suppose an RTES contains three tasks with the parameters of each task specified in Table(assuming the release time of each task is 0). Figure shows the optimal static schedule if WCEC are taken by all tasks. For simplicity, we assume the clock cycle time is inversely proportional to the supply voltage and the minimum and maximum supply voltages are and respectively. Figure 1(b) gives the actual dynamic run-time schedule when greedy dynamic slack redistribution is carried out. The supply voltage value at runtime depends on both the WCEC and the end-time obtained in the static schedule and can be computed by equation (2). During runtime, tasks finish earlier since their actual execution cycles are smaller than the WCEC. Greedy slack distribution distributes all the slack obtained from the just-finished task to the next task. For example, slack obtained from task is as shown in Figure and is utilized fully by the next task The supply voltage of is re-calculated based on the WCEC of that is, Similarly, slack generated by task is 5ms and can adopt an even lower voltage. By using equation the overall energy consumption for executing the tasks based on the schedule given in Figure is It is clear that the dynamic slack redistribution indeed leads to more energy saving. However, if we know that the tasks most probably take the ACEC values during actual execution, can we do better? Let's examine the static schedule in Figure 1 a little bit closer. In this schedule, each task is associated with a predetermined end time, end time is is etc. These end times are then used in the dynamic slack distribution process to compute a new voltage schedule. The static schedule essentially determines the end time for each task. (Note that this

  Figure shows the optimal static schedule if WCEC are taken by all tasks. For simplicity, we assume the clock cycle time is inversely proportional to the supply voltage and the minimum and maximum supply voltages are and respectively. Figure 1(b) gives the actual dynamic run-time schedule when greedy dynamic slack redistribution is carried out. The supply voltage value at runtime depends on both the WCEC and the end-time obtained in the static schedule and can be computed by equation (2). During runtime, tasks finish earlier since their actual execution cycles are smaller than the WCEC. Greedy slack distribution distributes all the slack obtained from the just-finished task to the next task. For example, slack obtained from task is as shown in Figure and is utilized fully by the next task The supply voltage of is re-calculated based on the WCEC of that is, Similarly, slack generated by task is 5ms and can adopt an even lower voltage. By using equation the overall energy consumption for executing the tasks based on the schedule given in Figure is

Figure 2 .

 2 Figure 2. Another schedule for the system in Fig. 1.

  Figure 3. Task instances in the hyper-period of an example system.

  to carry out any computation on averageNote that all the worst-case workload ( ) are non-negative number and the sum of them is equal to .

Figure 5 .

 5 Figure 5. An example of a task with three instances.

kA

  dependent linear variable, is introduced to determine whether the current task sub-instance belongs to case 1 or case 2. If it belongs to case 1, k , . , > because the sum of the average workload of the already executed sub-instances (including the current sub-instance itself) is at most We have the task sub-instance belongs to case 2. In order to have for case 1, we have the following additional constraint:

6

 6

Figure 6 .

 6 Figure 6. Experimental results

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

'This work was in part by the Hong Kong Research Grant Grant CERG HKUST and HKUST grant work was in part by National Science grant CCR02-08992 and