Embedded operating system energy analysis and macr

T.K.Tan,A.Raghunathan,and N.K.Jha

Dept.of Electrical Eng.,Princeton University,NJ08544

NEC,C&C Research Labs,Princeton,NJ08540

Abstract

A large and increasing number of modern embedded sys-

tems are subject to tight power/energy constraints.It has

been demonstrated that the operating system(OS)can have

a significant impact on the energy efficiency of the embed-

ded system.Hence,analysis of the energy effects of the OS

is of great importance.Conventional approaches to energy

analysis of the OS(and embedded software,in general)re-

quire the application software to be completely developed

and integrated with the system software,and that either

measurement on a hardware prototype or detailed simula-

tion of the entire system be performed.Since this process

requires significant design effort,unfortunately,it is typi-

cally too late in the design cycle to perform high-level or

architectural optimizations on the embedded software,re-

stricting the scope of power savings.

Our work recognizes the need to provide embedded soft-

ware designers with feedback about the effect of differ-

ent OS services on energy consumption early in the de-

sign cycle.As afirst step in that direction,this paper

presents a systematic methodology to perform energy anal-

ysis and macro-modeling of an embedded OS.Our energy

macro-models provide software architects and developers

with an intuitive model for the OS energy effects,since

they directly associate energy consumption with OS ser-

vices and primitives that are visible to the application soft-

ware.Our methodology consists of(i)an analysis stage,

where we identify a set of energy components,called energy

characteristics,which are useful to the designer in making

OS-related design trade-offs,and(ii)a subsequent macro-

modeling stage,where we collect data for the identified en-

ergy components and automatically derive macro-models

for them.We validate our methodology by deriving en-

ergy macro-models for two state-of-the-art embedded OS’s,

C/OS and Linux OS.

Figure1.A typical embedded system directed power management in Linux and showed that it can save more than50%power compared to traditional

hardware-centric shut-down techniques.Bellosa[2]pre-

sented thread-specific online analysis of energy-usage pat-terns that are fed back to the scheduler to control the CPU

clock speed.

Performance analysis of the OS has been investigated in the past[12,18].In addition,other work has been

done to analyze the energy consumption of the OS.En-

ergy analysis of a real-time OS wasfirst performed by Dick et al.[4],who developed an energy simulation and analy-

sis framework for C/OS-SPARClite based embedded sys-tems.Cignetti et al.[3]modeled the power consumption

of the family of devices based on discrete de-vice states,and provided an energy simulator based on this power model.Li et al.[8]presented issues concerning the

implementation of a low power OS and demonstrated the

energy advantage of the event-driven TinyOS over a gen-eral purpose OS(eCos).Acquaviva et al.[1]characterized the energy consumption of eCos,focusing in particular on the relationship between energy consumption and processor frequency.

2Motivation for OS Energy Characteriza-tion

Consider an embedded system consisting of many com-ponents,one of which is a microprocessor that hosts all the software tasks.The software tasks use an OS as the run-time engine.A conceptual diagram for such a system is shown in Fig.1.Assume that the software for this embed-ded system has the task configuration shown in thefigure. Task T1through task T4deal with background processing such as managing the memory,controlling the LCD,etc. Task T5looks out for new data coming from the A/D con-verter,performs some preprocessing,and passes the data to task T4.Given this multi-task specification,there are sev-eral ways to actually implement the system.In particular, for task T5,we have two options:

C1:In this case,task T5is implemented as an actual software process.After performing preprocessing,it

passes the data to task T4through inter-process com-

munication(IPC).

C2:In this case,task T5is implemented as an interrupt service routine(ISR)or signal handler for task T4.

The ISR or signal handler is activated periodically us-

ing a hardware timer.Since tasks T4and T5share the

same process space,passing data from task T5to task

T4does not incur any IPC overhead.

Designers acquainted with the underlying implementa-tion of an OS will know that the C2implementation has less overhead(delay and energy)compared to C1.However,C1 is a cleaner(in terms of ease of programming)implemen-tation compared to C2.Therefore,some trade-off has to be made.Apart from that,choosing the actual mechanism for IPC also requires a trade-off between various objectives.A decision can be made intelligently only if the metric under consideration(the energy overhead)is quantified.One ap-proach for quantifying the energy overhead of C1over C2is to actually implement both and compare them in a simula-tion environment.However,this is very time-consuming.If some type of energy characteristic data for the chosen OS are made available,the comparison can be made much more efficiently.This is especially so if the energy characteristic data are provided in the form of energy macro-models.Our work in this paper is afirst step towards making this possi-ble.

3Overall Methodology for OS Energy Char-acterization

Fig.2illustrates the overall methodology for OS energy characterization.There are four steps involved,namely:

1.In the energy effect analysis step,we identify the es-

sential components of the embedded OS one should

characterize.

2.After identifying the energy components to charac-

terize,we generate directed test programs that isolate

these components from each other.

3.In this step,the test program is compiled and linked

with the OS,and fed into an energy simulation

tool.This step requires a low-level energy simula-

tion framework that is capable of executing the ap-

plication software together with the OS and reporting

Energy

effect

analysis

Test program generation

Energy simulation

Model fitting

1

2

3

4

OS source

Energy components

Test program

Execution profiles Energy profiles

Macro-model templates

Energy macro-model

Figure 2.Overall methodology for OS energy characterization

the energy consumption on a function instance basis.Such simulators exist,and were reported in [4,13].4.The execution and energy profiles generated from the previous step is subject to further analysis and model fitting to obtain the energy macro-models.Step 1is the energy analysis stage,whereas Step 2to Step 4belong to the energy macro-modeling stage.We dis-cuss these two stages of our methodology in the next two sections.

4OS Energy Analysis

For the purpose of energy analysis,we can view an OS as a multi-entry multi-exit program (MEME-P).Such a view is depicted in Fig.3,where the big circle is a conceptual rep-resentation of the OS-application interface.Dotted lines in the circle represent (conceptually)possible execution paths in the OS.Notice that some paths overlap in some sections,depicting the common fact of program modularity.Some of the entry-exit pairs belong to system call interfaces,whereas others belong to implicit paths of execution within the OS,i.e.,they do not directly correspond to system calls in the application code.Examples of implicit execution paths in-clude those triggered by interrupts.In the following discus-sion,we shall call the entry-exit pairs belonging to the sys-tem call interfaces SCEEP (system call entry-exit pair),and

the entry-exit pairs belonging to implicit execution paths IEEP (implicit entry-exit pair).

M1: First mode of operation for SCEEP1M2: Second mode of operation for SCEEP1

Figure 3.An MEME-P view of an OS

In a typical OS,a SCEEP can be overloaded with a few groups of paths because the system function it represents is overloaded with many modes of operations.For example,the read()system function in the Linux OS can be used to read from a file,from the network,or from a terminal.These different modes of operations correspond to very dif-ferent groups of paths for the SCEEP of the read()func-tion.Similarly,IEEP could also be overloaded in the sense that different groups of paths may be traversed,depending on the state of the OS.

Guided by the MEME-P view,the objective of OS en-ergy analysis is to identify a useful set of SCEEP’s and IEEP’s,and to classify the paths between them into groups amenable to macro-modeling.The energies consumed while traversing these paths are the energy characteristics of the OS.We broadly classify the energy characteristic data into two categories,namely the explicit group and the implicit group .We discuss each group separately in the fol-lowing sub-sections.

4.1Explicit Energy Characteristics

By explicit ,we mean the energy data that is directly re-lated to the OS primitives (system functions).Using the MEME-P view,it basically relates to the energy consumed while traversing the paths between SCEEP’s.An OS typi-cally comprises many SCEEP’s.A comprehensive set of ex-plicit energy characteristic data should,in principle,cover all the SCEEP’s.However,in most practical applications,a selected set of the SCEEP’s should suffice in providing useful data for the designers.For system functions that are overloaded with multiple modes of operation,each mode of operation should have its own energy macro-model,even though all the modes of operations share the same SCEEP.Making energy macro-models available for system func-

4.2Implicit Energy Characteristics

In contrast to explicit energy,implicit energy character-istics are not directly related to any OS primitive.That is, the energy is not incurred when exercising an OS primitive, but comes as a result of running the OS engine.Using the MEME-P view,this energy basically relates to the energy consumed while traversing the paths between IEEP’s.Sim-ilar to the SCEEP,there are usually a few groups of paths for a single IEEP,each of them requiring a separate energy macro-model.The energy consumption along the different groups of paths between the IEEP is characteristic of an OS, and they are called implicit energy characteristics.Some of them are:

Timer interrupt energy:This is the energy

overhead incurred by the timer interrupt tied to

the scheduler.

Scheduling energy:This is the energy over-

head of performing rescheduling in the pre-

emptive scheduler.

Context switch energy:This is the energy

overhead incurred when a context switch oc-

curs.Note that a call to the scheduler may not

always result in a context switch,hence,we

separately characterize the context switch and

scheduling energy.

Signal handling energy:A signal depicts an

OS emulation of a low-level interrupt.Since it

is commonly used,its energy overhead should

be characterized.

Making energy macro-models available for the above en-ergy components allows the designers to efficiently com-pute the relative energy cost of different software architec-tures.

5OS Energy Macro-modeling

We adopt a white-box analysis and black-box measure-ment philosophy for OS energy macro-modeling.White-box analysis refers to the fact that we identify and analyze the energy components of interest by studying the internal operation of the OS.Black-box measurement refers to the fact that we measure the energy components by devising ex-periments that isolate the OS energy of interest by only in-strumenting the application code.Black-box measurement and macro-modeling enable the energy models to be used without any knowledge of the OS’s internal implementa-tion.

In the following sub-sections,wefirst discuss step2(see Fig.2)of our methodology for both explicit and implicit en-ergy characteristics.After that,steps3and4of our method-ology are illustrated.

5.1Approach to Measure Explicit Energy Char-

acteristics

The energy consumption of an OS primitive(system function)can be characterized by repeatedly calling it in a test program.Care must be taken to extract the“pure”energy cost of the system function,isolating it from the im-plicit energy.For example,in measuring the cost of a mes-sage queue read,one must make sure that the energy data collected does not include context switch energy.This is achieved by arranging to have both read and write parts of the experiment in the same software process.Moreover, spurious data resulting from timer interrupt,rescheduling and pre-emptive context switch must be isolated and elim-inated.For example,to avoid pre-emptive context switch, the test program must not execute for more than in the case of Linux OS.

Using this approach,we present some characterization results for some commonly used OS primitives in Section6.

5.2Approach to Measure Implicit Energy Char-

acteristics

As described in Section4.2,there are a few key parame-ters one should measure to obtain the implicit energy char-acteristics.Measuring these parameters is not as straight-forward as for explicit energy characteristics.We discuss them one-by-one in the following sub-sections.

5.2.1Context Switch Energy

Context switch energy is a good measure of the chosen OS’s ability to perform multi-tasking energy-efficiently.Due to its importance,we present two different approaches to ob-tain values for this key parameter.Whether both approaches result in similar energy values is an indicator of their accu-racy.

Thefirst approach is to arrange two separate experi-ments,A and B.Experiment A consists of two tasks,con-nected together by two separate IPC channels going in op-posite directions,with a single byte repeatedly being passed back and forth through the two IPC channels.Since two tasks are involved in the activity(reading and writing of the

Figure 4.A test program for revealing context switch energy

240000

244000248000252000256000

1

10

100

1000

(4)

(3)

(2)

(1)

C o u n t

Energy consumption of sub_function1()

Figure 5.Histogram for the energy consump-tion of sub

function1()that does nothing,expecting to be preempted by the OS.This test program is shown in Fig.4.Function sub

function1()reveals

the energy incurred by the timer interrupt,rescheduling,and context switch.Such a plot is shown in Fig.5.Knowing the underlying scheduling mechanism of the OS,we can deduce the origin of each energy cluster in Fig.5(de-noted by (1)–(4)in the figure).The first cluster from the left,i.e.,cluster (1),is the nominal energy consumption of

function2()

sub

function1()during which an actual con-text switch occurs.To extract the context switch energy from the histogram,we only have to calculate the differ-ence between the fourth and the first energy clusters.As we will show in Section 6,this value turns out to be very close to the value obtained using the first approach.5.2.2Timer Interrupt and Rescheduling Energy Knowing that the second cluster should be attributed to the timer interrupt,we obtain the timer interrupt energy to be the difference between the second cluster and first.Sim-ilarly,the scheduling energy is the energy difference be-tween the third cluster and first.

5.2.3Signal Handling Energy

Signal handling energy needs to be extracted using another experiment.In this experiment,we reuse sub

function2()in this experiment.However,the

main test program also sets up an alarm that generates a signal periodically.An alarm signal handler that does noth-ing (just return)is also established in the main test pro-gram.While sub

function2()in the experiment.Knowing that this setup is the same as the setup in Section 5.2.1except for

5.3Energy Simulation and Macro-model Fitting

After devising the test programs required to extract the

energy characteristics,we use a low-level energy simula-tion framework to collect the data.Such low-level energy

simulation frameworks exist[4,13],and are able to report

energy consumption of a software function on an instance-by-instance basis.

Macro-modelfitting is the last step in our methodology.

We use a regression technique developed in[14].Basically, for the energy characteristics of interest,wefirst collect a

series of data,,...,using the low-level energy simulator.At the same time,we also choose a macro-model

template for this energy characteristics.’s are the macro-model parameters and ’s are the unknown coefficients to be determined.Given the collection of energy data,we form a matrix equation using the macro-model template:

..

.

Solution of this matrix equation using the pseudo-inverse method yields the values for’s such that the macro-model bestfits the energy data[11].

We next illustrate this macro-modelfitting step using an example.Consider the case of building an energy macro-model for the Linux system function msgsnd().Knowing the functionality of this system function,it is straightfor-ward to propose an energy macro-model template expressed as,where is the number of bytes processed by this system function,and and are the unknown co-efficients to be determined.Running the test program gen-erated in the previous step yields a series of energy data, ,...,,corresponding to a series of’s,,,...,. The corresponding matrix equation used to solve for the un-known coefficients and is given by:

(1)

Since it is regression based,the macro-model we propose will have somefitting error with respect to the lower-level energy values it is based on.Evaluation of the error is im-portant to justify the applicability of the macro-models.We use the following relative error metric:

(2) where’s are the energy data values and’s are the val-ues given by the macro-model.This error metric is an un-biased measure of the statistical significance of the macro-models if the sample size is much larger than the number of parameters.

6Experimental Results

To validate our methodology,this section presents ex-perimental results for energy characterization of two well-known OS’s,namely,C/OS[7]and Linux OS(arm-linux v2.2.2).We use energy simulators[4,13]for embedded sys-tem platforms based on the Fujitsu’s SPARClite processor, and the Intel StrongARM processor,to collect low-level en-ergy data for C/OS and Linux OS,respectively.Discus-sions of the use and accuracy of such simulators can be found in[4,13].

Table1shows the implicit energy characteristic data for both C/OS and Linux OS.Since the energy data for C/OS were derived for a SPARClite-based platform,whereas the energy data for Linux OS were derived for a StrongARM-based platform,the energy characteristic data for C/OS were also normalized to the StrongARM-based platform so that a meaningful comparison can be made with the Linux OS energy characteristic data.Since two approaches were used to determine the context switch energy,we report for both C/OS and Linux two context switch energy values, indicated as(1)and(2).The two context switch energy val-ues derived using the two approaches turn out to be very close to each other,thereby providing an empirical vali-dation of the approaches.Note that timer interrupt and rescheduling are inseparable in C/OS.Therefore,there is a common entry for both in Table1.Also,there is no concept of signal handler in C/OS,therefore the entry on signal handling energy for C/OS is omitted.

Explicit energy characteristic data for C/OS are re-ported in Table2.Data for Linux OS are reported in Ta-ble3.The tables list the energy macro-models for selected sets of system functions that span various sub-systems.For those system functions overloaded with multiple modes of operations,such as read()and write()in Linux,sep-arate energy macro-models for each mode of operation are reported.

Even though is large in some cases,such macro-models can still be very useful in providing relatively accurate en-ergy estimation to help with system-level energy optimiza-tion.For example,in the context of choosing a proper Linux OS system function for the IPC between task T4and task

Table2.Energy macro-models for selected system functions in C/OS Sub-systems System Functions Normalized(nJ)

Table1.Implicit energy characteristic data for

C/OS and Linux OS

C/OS Energy Overhead

Linux OS Energy Overhead

T5described in Section2,energy macro-models for all the available IPC system functions come in handy.Knowing the typical amount of data being passed,the designer can calculate the energy consumption of all the possible IPC system functions and choose the one with the lowest energy consumption.Even for system functions which do not have alternatives,energy macro-models give designers a quick way of estimating the energy consumption overhead of the system functions.

7Limitations

Though we have tried to be as comprehensive as possible in our approach to OS energy characterization,the scope of our work has to be limited in some ways.First of all,we target embedded operating systems that are monolithic[16] and run on a single processor.This group of OS’s includes Linux,C-Linux,C/OS,eCos,etc.Second,although the overall methodology should be applicable across multiple OS’s,the details of test program generation is nevertheless implementation-dependent.In our case,we used Linux OS as the target OS and leveraged the approach for C/OS. Third,the focus of this paper is only on OS energy char-acterization.Though we have pointed out some possible uses of the energy characteristic data,systematically using this information in a system-level software energy reduction framework is a topic for future work.

Our methodology involves the use of low-level energy simulators to provide the required energy data as a basis of macro-modeling.Accuracy of the macro-modelfitting was discussed in Section5.3.The aggregate error as a result of macro-modeling and simulation is discussed in[15].

8Conclusions

We presented a systematic approach to analyze and macro-model the energy consumption of various compo-nents in an embedded OS.In the energy analysis stage,we dissected a typical OS and described an approach to identify the essential components of the embedded OS one should characterize.In the macro-modeling stage,we described the experiments we performed to measure the energy character-istics,and the approach we took to obtain the corresponding macro-models.We validated our methodology on two well-known OS’s,C/OS and Linux OS.Energy macro-models obtained using our approach can be very helpful for guided OS-related design trade-offs.

References

[1] A.Acquaviva,L.Benini,and B.Ricco.Energy character-

ization of embedded real-time operating systems.In Proc.

Workshop Compilers&Operating Systems for Low Power, Sept.2001.Table3.Energy macro-models for selected system functions in Linux Sub-systems System Functions Remarks Process Manager fork()

Process Manager getpid()

IPC msgrcv(bytes)

IPC pipe read(bytes)

Timer Functions gettimeofday()

Memory Manager calloc(blocks,size)

Memory Manager free()

File System open()

File Systemfile read(bytes)