当前位置:首页 >> >> Delay Analysis in Temperature-Constrained Hard Real-Time Systems with General Task Arrivals

Delay Analysis in Temperature-Constrained Hard Real-Time Systems with General Task Arrivals

Appeared in:

Proceedings of the 2006 IEEE Real-Time Systems Symposium (RTSS 2006), Rio de Janeiro, BRAZIL, December 2006.

Delay Analysis in Temperature-Constrained Hard Real-Time Systems with General Task Arrivals
Shengquan Wang The University of Michigan - Dearborn Dearborn, MI 48128, USA shqwang@umd.umich.edu Riccardo Bettati Texas A&M University College Station, TX 77843, USA bettati@cs.tamu.edu

Abstract
In this paper, we study temperature-constrained hard realtime systems, where real-time guarantees must be met without exceeding safe temperature levels within the processor. Dynamic speed scaling is one of the major techniques to manage power so as to maintain safe temperature levels. As example, we adopt a simple reactive speed control technique in our work. We design a methodology to perform delay analysis for general task arrivals under reactive speed control with First-In-First-Out (FIFO) scheduling and Static-Priority (SP) scheduling. As a special case, we obtain a close-form delay formula for the leakybucket task arrival model. Our data show how simple reactive speed control can decrease the delay of tasks compared with any constant-speed scheme.

such approaches inappropriate. A number of dynamic thermal management approaches to control the temperature at run time have been proposed, ranging from clock throttling to dynamic voltage scaling (DVS) to in-chip load balancing: ? The Pentium 4 Series processors uses Clock Throttling [3] or Clock Gating [4] to stall the clock and so allow the processor to cool during thermal overload. ? Dynamic Voltage Scaling (DVS) [1] is used in a variety of modern processor technologies and allows to switch between different frequency and voltage operating points at run time in response to the current thermal situation. In the Enhanced Intel SpeedStep mechanism in the Pentium M processor, for example, a low-power operating point is reached in response to a thermal trigger by ?rst reducing the frequency (within a few microseconds) and then reducing the voltage (at a rate of one mV per microsecond) [3]. ? A number of architecture-level mechanisms for thermal control have been proposed that turn off components inside the processor in response to thermal overload. Skadron et al. [4] for example argue that the microarchitecture should distribute the workload in response to the thermal situation by taking advantage of instruction-level parallelism. The performance penalty caused by this “local gating” would not be excessive. On a coarser level, the Pentium Core Duo Architecture allows the OS or the BIOS to disable one of the cores by putting it into sleep mode [5]. As high-performance embedded systems become increasingly temperature-constrained, the question of how the thermal behavior of the system and the thermal control mechanisms affect real-time guarantees must be addressed. In this paper we describe delay analysis techniques in temperatureconstrained hard real-time systems, where deadline constraints for tasks have to be balanced against temperature constraints of the system.

1

Introduction

With the rapidly increasing power density in processors the problem of thermal management in systems is becoming acute. Methods to manage heat to control its dissipation have been gaining much attention by researchers and practitioners. Techniques are being investigated for thermal control both at design time through appropriate packaging and active heat dissipation mechanisms, and at run time through various forms of dynamic thermal management (DTM) (e.g., [1]). Thermal management through packaging (that improves air?ow, for example) and active heat dissipation will become increasingly challenging in the near future, due to the high levels of peak power involved and the extremely high power density in emerging systems-in-package [2]. In addition, the packaging requirements and operating environments of many high-performance embedded devices render
This work was funded by NSF under Grant No. CNS-0509483, while Dr. Wang was at Texas A&M University.

Dynamic speed scaling allows for a trade-off between these two performance metrics: To meet the deadline constraint, we run the processor at a higher speed; To maintain the safe temperature levels, we run the process at a lower speed. The work on dynamic speed scaling techniques to control temperature in real-time systems was initiated in [6] and further investigated in [7]. Both [6] and [7] focus on online algorithms in real-time systems, where the scheduler learns about a task only at its release time. In contrast, in our work we assume a deterministic task model (e.g., periodic tasks) and so allows for design-time delay analysis. We distinguish between proactive and reactive speed scaling schemes. Whenever the temperature model is known, the scheduler could in principle use a proactive speed-scaling approach, where – similarly to a non-work-conserving scheduler – resources are preserved for future use. In this paper, we limit ourselves to reactive schemes, and propose a simple reactive speed scaling technique for the processor, which will be discussed in Section 2. We focus on reactive schemes primarily because they are simple to integrate with current processor capabilities through the ACPI power control framework [8, 9]. In our previous paper [10], we motivate the reactive scheme and perform delay analysis for identical-period tasks. In this paper, we extend it to general task arrivals with First-in First-out (FIFO) scheduling and Static-Priority (SP) scheduling. The rest of the paper is organized as follows. In Section 2, we introduce the thermal model, speed scaling schemes, and task model and scheduling algorithms. After introducing two important lemmas in Section 3, we design the methodology to perform delay analysis for FIFO and SP scheduling algorithms in Sections 4 and 5 respectively. We measure the performance in Section 6. Finally, we conclude our work with ?nal remarks and give an outlook on future work in Section 7.

as speed-scaling. In addition, existing processors typically have well-de?ned hotspots, and accurate placement of sensors allows alleviates the need for ?ne-granularity temperature modeling. The Intel Core Duo processor, for example, has a highly accurate digital thermometer placed at the single hotspot of each die, in addition to a single legacy thermal diode for both cores [5]. More accurate thermal models can be derived from this simple one by more closely modeling the power dissipation (such as the use of active dissipation devices) or by augmenting the input power by a stochastic component, etc. We de?ne s(t) as the processor speed (frequency) at time t. Then the input power P (t) at time t is usually represented as P (t) = κsα (t), (1) for some constant κ and α > 1. Usually, it is assumed that α = 3 [6, 7]. We assume that the ambient has a ?xed temperature, and that temperature is scaled so that the ambient temperature is zero. We de?ne T (t) as the temperature at time t. We adopt Fourier’s Law as shown in the following formula [6, 7, 12]: P (t) T (t) (2) ? , Cth Rth Cth where Rth is the thermal resistance and Cth is the thermal capacitance of the chip. Applying (1) into (2), we have T (t) = T (t) = asα (t) ? bT (t), (3) where a and b are positive constants and de?ned as follows: κ 1 (4) a= ,b = . Cth Rth Cth Equation (3) is a classic linear differential equation. If we assume that the temperature at time t0 is T0 , i.e., T (t0 ) = T0 , (3) can be solved as
t

2
2.1

Models
Thermal Model

T (t) =
t0

asα (τ )e?b(t?τ ) dτ + T0 e?b(t?t0 ) .

(5)

We observe that we can always appropriately scale the speed to control the temperature: ? If we want to keep the temperature constant at a value TC during a time interval [t0 , t1 ], then for any t ∈ [t0 , t1 ], we can set s(t) = ( bTC 1 )α . a (6)

A wide range of increasingly sophisticated thermal models for integrated circuits have been proposed in the last few years. Some are comparatively simple, chip-wide models, such as developed by Dhodapkar et al. [11] in TEMPEST. Other models, such as used in HotSpot [4], describe the thermal behavior at the granularity of architecture-level blocks or below, and so more accurately capture the effects of hotspots. In this paper we will be using a very simple chip-wide thermal model previously used in [6, 7, 11, 12]. While this model does not capture ?ne-granularity thermal effects, the authors in [4] for example agree that it is somewhat appropriate for the investigation of chip-level techniques, such

? If, on the other hand, we keep the speed constant at s(t) = sC during the same interval, then the temperature develops as follows: asα asα (7) T (t) = C + (T (t0 ) ? C )e?b(t?t0 ) . b b This relation between processor speed and temperature is the basis for any speed scaling scheme.

2.2

Speed Scaling

The effect of many dynamic thermal management schemes (most prominently DVS and clock throttling) can be described by the speed/temperature relation depicted in (6) and (7). The goal of dynamic thermal management is to maintain the processor temperature within a safe operating range, and not exceed what we call the highest-temperature threshold TH , which in turn should be at a safe margin from the maximum junction temperature of the chip. Temperature control must ensure that T (t) ≤ TH . (8)

using the following formula: ? ? ?sH , (W (t) > 0) ∧ (T (t) < TH ) s(t) = sE , (W (t) > 0) ∧ (T (t) = TH ) ? ? 0, W (t) = 0

(11)

Figure 1 shows an example of how temperature changes under reactive speed scaling.
s (t ) sH sE
t

On the other hand, we can freely set the processor speed, up to some maximum speed sH , i.e., 0 ≤ s(t) ≤ sH . (9)

T (t ) TH t

In the absence of dynamic speed scaling we have to set a constant value of the processing speed so that the temperature will never exceed TH . Assuming that the initial temperature is less than TH , we can de?ne equilibrium speed sE as
1 b sE = ( TH ) α . a

Figure 1. Illustration of reactive speed scaling. It is easy to show that in any case the temperature never exceeds the threshold TH . By using the full speed sometime, we aim to improve the processor utilization compared with the constant-speed scaling. The reactive speed scaling is very simple: whenever the temperature reaches the threshold, an event is triggered by the thermal monitor, and the system throttles the processor speed.

(10)

For any constant processor speed not exceeding sE , the processor does not exceed temperature TH . Note that the equilibrium speed sE is the maximum constant speed that we can set to maintain the safe temperature level. A dynamic speed scaling scheme would take advantage of the power dissipation during idle times. It would make use of periods where the processor is “cool”, typically after idle periods, to dynamically scale the speed and temporarily execute tasks at speeds higher than sE . As a result, dynamic speed scaling would be used to improve the overall processor utilization. In de?ning the dynamic speed scaling algorithm we must keep in mind that (a) it must be supported by existing power control frameworks such as ACPI [8,9], and (b) it must lead to tractable design – time delay analysis. We therefore use the following very simple reactive speed scaling algorithm: The processor will run at maximum speed sH when there is backlogged workload and the temperature is below the threshold TH . Whenever the temperature hits TH , the processor will run at the equilibrium speed sE , which is de?ned in (10). Whenever the backlogged workload is empty, the processor idles (runs at the zero speed). If we de?ne W (t) as the backlogged workload at time t, the speed scaling scheme described before can be expressed

2.3

Task Model and Scheduling Algorithms

The workload consists of a set of tasks {Γi : i = 1, 2, . . . , n}. Each task Γi is composed of a sequence of jobs. For a job, the time elapsed from the release time tr to the completion time tf is called the delay of the job, and the worst-case delay of all jobs in Task Γi is denoted by di . Jobs within a task are executed in a ?rst-in ?rst-out order. We characterize the workload of Task Γi by the workload function fi (t), the accumulated requested processor cycles of all the jobs from Γi released during [0, t]. Similarly, to characterize the actual executed processor cycles received by Γi , we de?ne gi (t), the service function for Γi , as the total executed processor cycles rendered to jobs of Γi during [0, t]. A time-independent representation of fi (t) is the workload constraint function Fi (I ), which is de?ned as follows. De?nition 1 (Workload Constraint Function). Fi (I ) is a workload constraint function for the workload function fi (t), if for any 0 ≤ I ≤ t, fi (t) ? fi (t ? I ) ≤ Fi (I ). (12)

For example, if a task Γi is constrained by a leaky bucket with a bucket size σi and an average rate ρi , then Fi (I ) = σi + ρi I. (13)

Once tasks arrive in our system, a scheduling algorithm will be used to schedule the service order of jobs from different tasks. Both the workload and the scheduling algorithm will determine the delay experienced by jobs. In this paper, we consider two scheduling algorithms: First-in Firstout (FIFO) scheduling and Static Priority (SP) scheduling.

Lemma 2. In a system under our reactive speed scaling, we consider two jobs Jk ’s (k = 1, 2), each of which has a release time tk,r and the completion time tk,f . We assume t1,f < t2,f . If we take either of the following actions as shown in Figure 3:
t1, r t1, f t 2, r t2, f
* t2 ,f

t1, r t1, r

t1, f
t1*, f

t0

t 2, r t 2, r t1*, r
t2,r t1*, f

(A) (B)

3

Important Lemmas

* t2 ,f

The dif?culty for delay analysis in a system with reactive speed scaling lies in the speed of the processor not being constant. Moreover the changes in processing speed are triggered by the thermal behavior, which follows (11). As a result, as we will show, simple busy-period analysis does not work. The following two lemmas show how the change of temperature, job arrival, job execution will affect the temperature at a later time or the delay of a later job. Lemma 1. In a system under our reactive speed scaling, given a time instance t, we consider a job with a release time tr and a completion time tf such that tr < t and tf < t. We assume that the processor is idle during [tf , t]. If we take either of the following actions as shown in Figure 2:
tr t0 tr tr tf t* f t* f
* r

* t2 ,f

(C)

Figure 3. Delay effect. ? Action A: Increasing the temperature at t0 (t0 ≤ t2,r ) such that Job J2 has the same release time t2,r but a new completion time t? 2,f ; ? Action B: Increasing the processor cycles of Job J1 such that Job Jk (k = 1, 2) has the same release time tk,r but a new completion time t? k,f ; ? Action C: Shifting Job J1 such that Job J1 has a new ? release time t? 1,r and a new completion time t1,f , and Job J2 has the same release time t2,r and a new com? ? pletion time t? 2,f satisfying t1,r ≤ t1,r and t1,f ≤ ? t2,f ,
? then t2,f ≤ t? 2,f . If we de?ne d2 and d2 as the delay of Job J2 in the original and the modi?ed scenarios respectively, then d2 ≤ d? 2.

t t t
(A) (B)

t

t* f

t

(C)

The proofs of Lemmas 1 and 2 can be found in [13]. Here we summarize the three actions de?ned in the above two lemmas as follows: ? Action A: Increasing the temperature at some time instances; ? Action B: Increasing the processor cycles of some jobs; ? Action C: Shifting some jobs to a later time. By the lemmas, with either of the above three actions, we can increase the temperature at a later time and the delay of the later job. The above two lemmas together with the three actions are important to our delay analysis under reactive speed scaling, which will be our focus in the next two sections.

Figure 2. Temperature effect. ? Action A: Increasing the temperature at time t0 (t0 ≤ tr ) such that the job has the same release time tr but ? a new completion time t? f satisfying tf < t; ? Action B: Increasing the processor cycles for this job such that the job has the same release time tr but a ? new completion time t? f satisfying tf < t; ? Action C: Shifting the job such that the job has a new ? release time t? r and a new completion time tr satisfy? ? ing tr < tr < t and tf < tf < t, then we have Tt ≤ Tt? , where Tt and Tt? are the temperatures at time t in the original and the modi?ed scenarios respectively.

4

Delay Analysis of FIFO Scheduling

Recall that the speed of the processor is triggered by the thermal behavior and varies over time under reactive speed scaling. Simple busy-period analysis will not work in this environment. In simple busy-period analysis, the jobs arriving before the busy period will not affect the delay of jobs arriving during the busy period. However, under reactive speed scaling, the execution of a job arriving earlier will heat up the processor and so affect the delay of a job arriving later as shown in Lemma 2. Therefore, in the busy-period analysis under reactive speed scaling, we have to take this effect into consideration. We start our delay analysis in the system with FIFO scheduling. Under FIFO scheduling, all tasks experience the same worst-case delay as the aggregated task does. Therefore, we consider the aggregated task, whose workload conn straint function can be written as F (I ) = i=1 Fi (I ). First, we investigate the worst-case delay for the aggregated task. Delay Constraint We consider a busy period [t1 , t0 ] with length δ1 during which a job will experience the longest delay and immediately before which the processor is idle. The processor runs at high speed sH in Interval [t1 , t1,h ] with length δ1,h and at equilibrium speed sE in Interval [t1,h , t0 ] with length δ1,e as shown in the right side of Figure 4(a).
δ1,h δ1,e

First, we study the right side of (15). Recall that the processor runs at high speed sH in Interval [t1 , t1,h ] with length δ1,h and at equilibrium speed sE in Interval [t1,h , t0 ] with length δ1,e . If we de?ne I = t ? t1 , then we have g (t + τ ) ? g (t1 ) = G(I + τ ), (16)

where G(I ), a service constraint function of g (t), is de?ned as G(I ) = min{(sH ? sE )δ1,h + sE I, sH I }. (17)

Next, we study the left side of (15). With Action B, the job will experience a longer delay with more workload released and completed before the completion of this job. Therefore, if we set f (t) ? f (t1 ) = F (I ), (18)

together with (16), then the worst-case delay in (15) can be written as (see Figure 5) d = sup{inf {τ : F (I ) ≤ G(I + τ )}}.
I ≥0

(19)

F (I ) G( I )

d

δ1,h
(a) t0

δ1,e

I

tm
δm,0 δm,h

tm-1

t3
δ3,0 δ3,h

t2
δ2,0 δ2,h

t1
δ1,h

t1,h
δ1,e

Figure 5. Delay constraint.
(b)

tm

tm,0 tm-1

t3

t3,0 t2

t2,0

t1

t1,h

t0

As we can see, the undetermined service constraint function G(I ) is the key in the worst-case delay formula (19). Next, we will focus on obtaining G(I ). Service Constraint As de?ned in (17), G(I ) is a function of δ1,h , which depends on the temperature at time t1 . Instead of determining the exact temperature at t1 , we aim to obtain a tight upper-bound of t1 , which will result in an upper-bound of the worst-case delay according to Lemma 2. To achieve this, we introduce extra intervals [tk+1 , tk ]’s (k = 1, . . . , m ? 1), as shown in Figure 4(a). By Lemma 1, we can use the three actions mentioned above to upperbound the temperature at t1 . With Action A, we upperbound the temperature at tm to be TH . With Action C, for each Interval δk (k = 2, . . . , m), we shift all parts of job execution to the end of this interval, such that the beginning part is idle with length δk,0 and the ending part is busy with length δk,h , as shown in Figure 4(b). We assume that the temperature will not hit TH during [tm , t1 ] 1 , then
1 If there is an interval [t k0 +1 , tk0 ] during which the temperature hits TH , then the temperature at tk0 is TH . In this case, we can set m = k0 and remove all intervals on the left.

Figure 4. Job executions. We de?ne d as the worst-case delay experienced by a job in the busy period [t1 , t0 ]. Then, by the de?nition of worstcase delay, we have d = sup {inf {τ : f (t) ≤ g (t + τ )}}},
t≥t1

(14)

where f (t) and g (t) are the workload function and the service function of the aggregated task respectively, as de?ned in Section 2. In other words, if by time t + τ , the service received by the task is no less than its workload function f (t), then all jobs of the task arriving before time t should have been served, with a delay no more than τ . Since the processor is idle at time t1 , we have f (t1 ) = g (t1 ). Therefore, f (t) ≤ g (t + τ ) in (14) can be written as f (t) ? f (t1 ) ≤ g (t + τ ) ? g (t1 ). (15)

the processor will run at high speed sH during each interval [tk+1,0 , tk ]. We consider the service received in each interval [tk , t0 ], k = 1, . . . , m. As shown in Figure 4(b), the executed processor cycles in [tk , t0 ] can be written as
k

g (t0 ) ? g (tk ) = sH
j =1

δj,h + sE δ1,e .

(20)

constraint conditions (19), (21), (22), (24), and (25), we can obtain an upper-bound of the worst-case delay, which we denote as d(δ1,h , δ1,e , δ2,0 , δ2,h , . . . , δm,0 , δm,h ). Note that d(δ1,h , δ1,e , δ2,0 , δ2,h , . . . , δm,0 , δm,h ) can always bound the worst-case delay. In order to ?nd a tight upper-bound of the worst-case delay, we can choose a set of δk,0 ’s and δk,h ’s to minimize d(δ1,h , δ1,e , δ2,0 , δ2,h , . . . , δm,0 , δm,h ) as summarized in the following theorem: Theorem 1. In a system with FIFO scheduling under reactive speed scaling, the worst-case delay d can be obtained by the following formula d = min{d(δ1,h , δ1,e , δ2,0 , δ2,h , . . . , δm,0 , δm,h )} subject to (19), (21), (22), (24), and (25). (26)

For k = 1, we have g (t0 ) ? g (t1 ) = f (t0 ) ? f (t1 ). Following the delay analysis in the above delay constraint, we consider the worst-case workload f (t0 ) ? f (t1 ) = F (t0 ? t1 ). Therefore, by (20) we have sH δ1,h + sE δ1,e = F (δ1,h + δ1,e ). (21)

For k = 2, . . . , m, by the de?nition of the worst-case delay, the number of processor cycles in Interval [tk , t0 ] is bounded as g (t0 ) ? g (tk ) ≤ f (t0 ) ? f (tk ? d). By Lemma 2, the delay becomes longer when g (t0 ) ? g (tk ) = f (t0 ) ? f (tk ? d) = F (t0 ? tk + d) by either shifting the job execution or increasing the processor cycles of jobs. Therefore, by (20) we have
k k

As a case study, in the following, we consider a leakybucket task workload and have the following theorem for the worst-case delay with FIFO scheduling: Corollary 1. In a system with FIFO scheduling under reactive speed scaling, we consider tasks with leaky-bucket workload and the workload constraint function of the agsE gregated task is F (I ) = σ + ρI . De?ne χ1 = s and H ρ χ2 = sH . A tight bound of the worst-case delay d is expressed as follows: d= where V = V (X ? Y ), χ2 ≤ χα 1 V (X ? Y ? Z ), otherwise Y =
1 b

sH
j =1

δj,h + sE δ1,e = F (
j =1

δj,h + δ1,e + d).

(22)

Note that the service received by jobs depends on the processing speed, which changes with the thermal behavior. Next we want to see how the temperature changes in each interval. Temperature Constraint First, we consider each interval [tk+1 , tk ], k = 1, . . . , m ? 1, which is composes of an idle period with length δk+1,0 and a busy period with length δk+1,h . De?ne Tk as the temperature at tk , then following the temperature formula (7), we have asα asα Tk = H + (Tk+1 e?bδk+1,0 ? H )e?bδk+1,h . b b (23)

(27)
1?χ2 ln 1 ?χα ,
1

and Z = dE as the delay when the processor always runs at sH and sE respectively, and dE = sσ . The worst-case delay d is also i.e., dH = sσ H E constrained by dH ≤ d ≤ dE . The proof is given in Appendix A. (28)

(1?χ1 )(1?χ2 ) χ1 , X = 1? χ1 ?χ2 χ1 dE , χ2 1 χ2 ln . De?ne d H and b 1?χ2 χα 1

5

Delay Analysis of SP Scheduling

Together with the assumption that Tk ≤ TH and Tm = TH , we have Tk TH = sH α ) e?b r =k+1 sE Pm +e?b l=k+1 δl ≤ 1. (
m P r ?1
l=k+1

δl

(1 ? e?bδr,h ) (24)

In order to perform delay analysis in the system with SP scheduling, we introduce the following lemma: Lemma 3. No matter what scheduling (FIFO or SP) is used in a system under reactive speed scaling de?ned in (11), the service function g (t) of the aggregated task will be uniquely determined by the workload function f (t) of the aggregated task, not by the scheduling algorithm. Proof: The service function g (t) can be written as
t

Next, considering Interval [t1 , t1,h ], we have T1 sH sH = ( )α ? (( )α ? 1)ebδ1,h . TH sE sE (25)

Therefore, for any given values of δ1,h , δ1,e , δk,0 , and δk,h , k = 2, . . . , m, which are constrained by the above

g (t) =
0

s(τ )dτ.

(29)

According to (11), s(t) is determined by W (t) and T (t) under reactive speed scaling, where W (t) is the backlogged workload at time t (i.e., W (t) = f (t) ? g (t)) and T (t) is determined by s(t) according to (5). Therefore, the service function g (t) will be uniquely determined by the workload function f (t) of the aggregated task. We have no assumption of the scheduling algorithm. Hence the lemma is proved. Based on this lemma, we are able to obtain the worstcase delay under SP scheduling as shown in the following theorem 2 : Theorem 2. In a system with SP scheduling under reactive speed scaling, the worst-case delay di for Task Γi can be obtained by the following formula di = sup{inf {τ :
I ≥0 i?1 j =1

Similarly, in the following we consider the leaky-bucket task workload as a case study. We have the following theorem on the worst-case delay for SP scheduling: Corollary 2. In a system with SP scheduling under reactive speed scaling, we assume that Task Γi has a workload constraint function Fi (I ) = σi + ρi I . The worst-case delay di for Task i can be written as di = max{dE,i ? ?, dH,i }, where dE,i =
i j =1 σj , i?1 sE ? j =1 ρj i j =1 σj , i?1 sH ? j =1 ρj

(32)

(33) (34) (35)

Fj (I + τ ) + Fi (I ) ≤ G(I + τ )}}, (30)

dH,i ?

= =

σ ? sE d sE ?
i?1 j =1

where G(I ) is de?ned in (17) and δ1,h in G(I ) can be obtained by minimizing d(δ1,h , δ1,e , δ2,0 , δ2,h , . . . , δm,0 , δm,h ) in Theorem 1. Proof: We consider a busy interval [t1 , t0 ], during which at least one job from Tasks Γj (j ≤ i) is running, and immediately before which no jobs from Tasks Γj (j ≤ i) are running. We know that the delay of a job J of Task Γi is introduced by two arrival stages of jobs in the queue: all queued jobs at J ’s release time and the higher-priority ones coming between J ’s release time and completion time. Then we have the worst-case delay for a job of Task Γi as follows: di = sup {inf {τ :
t≥t1 i?1 j =1

ρj

.

and d in (35) can be obtained by Corollary 1. The proof is given in Appendix B.

6

Performance Evaluation

fj (t + τ ) + fi (t)
i j =1



gj (t + τ )}},

(31)

where fi (t) and gi (t) are the workload function and the service function of Task Γi respectively. By our assumption about Interval [t1 , t0 ], we have fj (t1 ) = gj (t1 ), j = 1, . . . , i, and gj (t) = gj (t1 ), j = i + i?1 i 1, . . . , n. Therefore, j =1 fj (t + τ )+ fi (t) ≤ j =1 gj (t + τ ) in the above formula can be written as j =1 (fj (t + τ ) ? n fj (t1 ))+(fi (t) ? fi (t1 )) ≤ j =1 (gj (t + τ ) ? gj (t1 )). With the similar analysis for FIFO scheduling, the worst-case dei?1 lay happens when j =1 (fj (t + τ ) ? fj (t1 )) + (fi (t) ? fi (t1 )) = j =1 Fj (I + τ ) + Fi (I ). De?ne I = t ? t1 and then (30) holds. In (30), G(I ) is de?ned in (17). By Lemma 3, the service function under SP scheduling is same as the one under FIFO scheduling. Then δ1,h in G(I ) can be obtained by minimizing d(δ1,h , δ1,e , δ2,0 , δ2,h , . . . , δm,0 , δm,h ) in Theorem 1.
2 In the following,

i?1

i?1

the smaller index of a task indicates a higher priority.

In this section we evaluate the bene?t of using simple reactive speed scaling scheme by comparing the worst-case delay with that of a system without speed scaling. We adopt as the baseline a constant-speed processor that runs at equilibrium speed sE . We choose the same setting as [4] for a silicon chip. The thermal conductivity of the silicon material per unit volume is kth = 100 W/mK and the thermal capacitance per unit volume is cth = 1.75 × 106 J/m3 K . The chip is tth = 0.55 mm thick. Therefore, the thermal RC time constant cth 2 RC = k t = 0.0044 sec [4]. Hence by Equation (4) th th b ≈ 228.6 sec?1 . The ambient temperature is 45? C and the maximum temperature threshold is 85? C, then TH = 40? C. The equilibrium speed sE will be ?xed by the system, but sH can be freely chosen. We arbitrarily pick sH = 10 7 sE and assume α = 3. We consider three tasks Γi ’s (i = 1, 2, 3). As a case study, we consider a leaky-bucket workload and assume each task Γi has a leaky bucket arrival with Fi (I ) = σi + ρi I . The aggregate task has an arrival with F (I ) = σ + ρI , 3 3 where σ = i=1 σi and ρ = i=1 ρi . In our evaluation, we vary σ/sE and ρ/sE in the ranges of [0, 0.005] and [0, 0.5] respectively. We compare the worst-case delay of jobs in the system under reactive speed scaling and the baseline one in the systems the processor always run at the equilibrium speed.

5

x 10

?3

5

x 10

?3

Γ1
0.08
0.01

0.15 2 0.2

0.0 66
4
0.01

0.0

4
0.

94

0.0 38

0.2

0.

σ/sE sec

2

0.2

9

0. 1 0. 78 20 0.2 6 62

σ/s sec

3

23 4

3

E

2 12 15 0.
0.2 34
0. 09
06 0.

9

2
52 .2 .1 00

1

4

1

6

0.2
0.35

9

0

0. 00 0 1 03 ..1 .0 2 1 7 . 2 0 5 2 8 . 8 2 0 6 6 2

0. 08

0.

0.

0.

29

01
0 0
?3

01

0

0.05

0.1

0.15

0.2

0.25 ρ/sE

0.3

0.4

0.45

0.5

0.05

0.1

0.15

0.2

0.25 ρ/sE

0.3

0.35

0.4

0.45

0.5

5

x 10

Figure 6. A contour plot of delay decrease ratio |d ? dE |/dE for the aggregated task under reactive speed scaling for FIFO scheduling.
σ/s sec
E

Γ2
4 0.301 0.303
0.0 66

22 78 0.1 0.1 4 23 0. 5 30 0. 903 .2 .3 00 1 30

0.01

0.

3

2

First we consider FIFO scheduling. We evaluate the worstcase delay decrease ratio |d ? dE |/dE for the aggregated task. 3 Figure 6 shows a contour plot of |d ? dE |/dE in terms of σ/sE and ρ/sE . We observe that the delay decrease ratio changes from a minimum 0 (as d = dE ) to a sE maximum of 1 ? s = 0.300 (as d = dH ). The delay H decrease ratio will decrease as either σ or ρ increases. Next we consider SP scheduling. We assume that σ1 : σ2 : σ3 = ρ1 : ρ2 : ρ3 = 1 : 2 : 3. We evaluate the worst-case delay decrease ratio |di ? dE,i |/dE,i for Task Γi . Each individual picture in Figure 7 shows contour plots of |di ? dE,i |/dE,i in terms of σ/sE and ρ/sE , for the three tasks separately. We observe that the delay decrease ratio changes from a minimum of 0 (as di = dE,i ) to a maximum sE of 1 ? s = 0.300 for Task Γ1 , to a maximum of (1 ? H sE 1 sE sH )/(1 ? 6 sH ) = 0.316 for Task Γ2 , and to a maximum of sE 1 sE (1 ? s )/(1 ? 2 sH ) = 0.353 for Task Γ3 (as di = dE,i ). H As if the delay decrease ratio is not larger than 0.3, the ratio will decrease as either σ or ρ increases for any task. As if it becomes larger than 0.3, we have different observation results for the lower-priority tasks. In particular, considering the lower-priority task, for small σ and ρ, the delay dei sE crease ratio can be written as (1 ? s )/(1 ? s1 j =1 ρj ). H H Therefore, as shown at the left-bottom corner of the last two contour plots in Figure 7, the delay decrease ratio will keep constant as σ increases and ρ keeps constant, but increase as ρ increases and σ keeps constant.

0.307

1

0.3 07 0 0. 0 .30 0 12 .0 0 0 ... 0 1 2 6 3 3 0 .3 9 00 0 1 32 6.1 0.0 . .3 1 0 .2 1 3 7 3 0 4 1 8 1 5 9 5
0.3 0.35 0.4 0.45 0.5

0.309

0

0
?3

0.05

0.1

0.15

0.2

0.25 ρ/sE

5

x 10

Γ3

0.0 66

0.01

0.0

4

38

0.0

8 15 7 0. 0.1

σ/sE sec

3

0. 2

34

0. 20

0.

94

2 12

6

2

0.2 02 62 0. .39 11
0.316

0.306

0.3
0.321

0.301 0

0.

01
6 0. 32

6 06

1

0.3 06

0

0.2 0. 0.2 3406 15 0.1 0 .. 0 78 0 1 0 92 0 0.341 .3 .3 0 0 42 0 .3 0 3 ..2 0 3 .3 .2 1 6 1 3 6 4 9 6 1 6 21
03 0. 01 8

0.

0.05

0.1

0.15

0.2

0.25 ρ/sE

0.3

0.35

0.4

0.45

0.5

Figure 7. Contour plots of delay decrease ratio |di ? dE,i |/dE,i for Task Γi (i = 1, 2, 3) under reactive speed scaling for SP scheduling.

7

Conclusion and Future Work

Delay analysis in systems with temperature-constrained speed scaling is dif?cult, as the traditional de?nition of “busy
3 The alert reader has noticed that we did not de?ne a value for parameter a. This is because a appears only in the computation of sE , which cancels out in the delay decrease ratio.

period” does not apply and it becomes dif?cult to separate the execution of jobs from the interference by ones arriving earlier or having low priorities because of dynamic speed scaling triggered by the thermal behavior. In this paper we have shown how to compute bounds on the worst-case delay for tasks with arbitrary job arrivals for both FIFO and SP scheduling algorithms in a system with a very simple speed scaling algorithm, which simply runs at maximum speed until the CPU becomes idle or reaches a critical temperature. In the latter case the processing speed is reduced (through DVS or appropriate clock throttling) to an equilibrium speed that keeps the temperature constant. We have shown that such a scheme reduces worst-case delays. In order to further improve the performance of speed scaling, one would have to ?nd ways to partially isolate jobs

from the thermal effects of ones arriving earlier or having low priorities. One weakness of the proposed speed-scaling algorithm is its inability to pro-actively process low-priority tasks at lower-than-equilibrium speeds. At this point we don’t know how to perform delay analysis for non-trivial speed scaling algorithms, however.

[11] A. Dhodapkar, C.H. Lim, G. Cai, and W.R. Daasch, “TEMPEST: A thermal enabled multimodel power/performance estimator,” in Workshop on Power-Aware Computer Systems, ASPLOS-IX, 2000. [12] A. Cohen, L. Finkelstein, A. Mendelson, R. Ronen, and D. Rudoy, “On estimating optimal performance of CPU dynamic thermal management,” in Computer Architecture Letters, 2003. [13] S. Wang and R. Bettati, “Delay analysis in temperature-constrained hard real-time systems with general task arrivals,” Tech. Rep. tamu-cs-tr-20065-3, Department of Computer Science, Texas A&M University, 2006, http://www.cs.tamu.edu/ academics/tr/tamu-cs-tr-2006-5-3.

References
[1] D. Brooks and M. Martonosi, “Dynamic thermal management for high-performance microprocessors,” in Proceedings of the 7th International Symposium on High-Performance Computer Architecture, 2001. [2] Semiconductor Industry Association, “2005 international technology roadmap for semiconductors,” http://public.itrs.net. [3] E. Rotem, A. Naveh, M. Mof?e, and A. Mendelson, “Analysis of thermal monitor features of the Intel Pentium M processor,” in Proceedings of the First Workshop on Temperature-Aware Computer Systems, 2004. [4] K. Skadron, M. Stan, W. Huang, S. Velusamy, K. Sankaranarayanan, and D. Tarjan, “Temperatureaware microarchitecture: Extended discussion and results,” Tech. Rep. CS-2003-08, Department of Computer Science, University of Virginia, 2003. [5] S. Gochman, A. Mendelson, A. Naveh, and E. Rotem, “Introduction to Intel Core Duo processor architecture,” Intel Technology Journal, vol. 10, no. 2, pp. 89 – 97, 2006. [6] N. Bansal, T. Kimbrel, and K. Pruhs, “Dynamic speed scaling to manage energy and temperature,” in IEEE Syposium on Foundations of Computer Science, 2004. [7] N. Bansal and K. Pruhs, “Speed scaling to manage temperature,” in Symposium on Theoretical Aspects of Computer Science, 2005. [8] H. Sanchez, B. Kuttanna, T. Olson, M. Alexander, G. Gerosa, R. Philip, and J. Alvarez, “Thermal management system for high performance powerpc microprocessors,” in IEEE International Computer Conference, 1997. [9] E. Rotem, A. Naveh, M. Mof?e, and A. Mendelson, “Analysis of thermal monitor features of the intel pentium m processor,” in Workshop on Temperatureaware Computer Systems, 2004. [10] S. Wang and R. Bettati, “Reactive speed control in temperature-constrained real-time systems,” in Euromicro Conference on Real-Time Systems, 2006.

A

Proof of Corollary 1

We follow the analysis in Section 4, we consider the three constraints as follows: Delay Constraint Since F (I ) = σ + ρI , by (19) we can obtain the delay d as d = max{ sH σ σ , ?( ? 1)δ1,h }. sH sE sE (36)

Therefore, we have δ1,h = as d≥ σ . sH (38)
σ sE sH sE

?d ?1

,

(37)

Service Constraint To simplify the service analysis, we consider equal intervals and assume δk = δ for k = 3, . . . , m. We investigate the service received in each interval [tk , t0 ], k = 1 , . . . , m. As k = 1, by (21) we have sH δ1,h + sE δ1,e = σ + ρ(δ1,h + δ1,e ). Hence, (sH ? ρ)δ1,h + (sE ? ρ)δ1,e = σ. As k = 2, . . . , m, by (22), we have sH
k j =1

(39)

(40)

δj,h + sE δ1,e (41)

= σ + ρ((k ? 2)δ + (δ2 + δ1 ) + d).

If k = 2, together with (40), we have δ2,h = If k ≥ 3, we have δk,h = ρ δ. sH (43) δ 2 ,0 + d . sH ρ ?1 (42)

sE , and χ2 = sρ . where χ1 = s H H Equation (48) shows that d is a function of δ2,0 . Since the above analysis works for any chosen δ2,0 , we want to obtain a minimum d in terms of δ2,0 . There are two cases:

? χ2 ≤ χα 1 : d will be minimized at δ2,0 = 0, therefore d = V (X ? Y ), ? χ2 > χα 1 : d will be minimized at δ2,0 = therefore d = V (X ? Y ? Z ),
1 b

(49)
χ2 ln χ α,
1

Temperature Constraint By (37) and (43), we can rewrite the temperature constraint condition (24). As k = 2, . . . , m ? 1, Tk = e?b(m?k)δ (1 ? ξ ) + ξ, TH where ξ=( sH α 1 ? e . ) sE 1 ? e?bδ
?b sρ H δ

(50)

(44)

where V, X, Y, Z are de?ned in Corollary 1. On the other hand, in the temperature constraint, as k = 1, by (25) and the constraint that T1 /TH ≤ 1, we have δ1,h ≥ 0. (51) Therefore, by (37), we have d≤ σ . sE (52)

(45)

By (44), T2 is a function of δ and m. It is easy to know that the smaller T2 is, the short delay d is. Therefore, we want to ?nd δ and m to minimize T2 so that we a tight upper-bound d of the original worst-case delay. If ξ ≤ 1, then Tk /TH ≤ 1. By (44), T2 is a decreasing function in terms of (m?2)δ , then T2 /TH ≥ lim(m?2)δ→∞ T2 /TH = ξ . 4 Furthermore, ξ is an increasing function H α ρ of δ , then T2 /TH ≥ limδ→0 ξ = ( s sE ) sH . Therefore, H α ρ we choose the minimum and set T2 /TH = ( s sE ) sH as sH α ρ ( s E ) s H ≤ 1. If ξ > 1, then T2 /TH is the maximum among all Tk /TH ’s. Therefore, we only need to consider bound T2 /TH ≤ 1. By (44), T2 /TH is an increasing function in terms of m, then T2 /TH will be minimized at m = 2. Hence, we set T2 /TH = 1 in this case. Therefore, with the analysis above, we can set T2 TH = sH ρ min{( )α , 1}. sE sH (46)

and dE = sσ , then by (38) and (52), Recall that dH = sσ H E the worst-case delay is also constrained by dH ≤ d ≤ dE . (53)

B

Proof of Corollary 2

By Theorem 2, G(I ) = min{(sH ? sE )δ1,h + sE (I + di ), sH (I + di )} depends on δ1,h . For the leaky bucket task H workload, by (37) we have δ1,h = ( sσ ?d)/( s sE ? 1), where E d can be obtained by Corollary 1. By (30), the delay formula can written as
i?1 j =1

σj + ρj (I + di ) + σi + ρi I = (54)

min{(sH ? sE )δ1,h + sE (I + di ), sH (I + di )} Then, as di > δ1,h , we have di =
i?1 j =1 (σj

At the same time, by (23) and (25), we have δ1,h + δ2,h = 1 ln b
T2 ?bδ2,0 H α (s sE ) ? TH e sH α ( sE ) ? 1

+ ρj d i ) + σ i sE
i?1 j =1 (σj

?(

sH ? 1)δ1,h , sE

(55)

.

(47)

otherwise di = + ρj d i ) + σ i sH . (56)

Therefore, by (37), (42), (46), and (47), we can obtain the worst-case delay d as follows: d = (1 ? χ1 )(1 ? χ2 ) χ1 σ χ2 ( + δ 2 ,0 χ1 ? χ2 1 ? χ1 sE 1 ? χ2 ?bδ2,0 1 1 ? min{χ2 , χα 1 }e ? ln ), (48) α b 1 ? χ1

Therefore, by (37), (55), and (56), we have di = max{dE,i ? ?, dH,i }, (57)

where dE,i and dH,i are de?ned in Corollary 2, and d can be obtained by Corollary 1. The worst-case delay di is constrained by dH,i ≤ di ≤ dE,i . (58)

4 We assume that at time zero the system is at lowest temperature. Therefore, we can pick the intervals with overall length up to in?nity.


更多相关文档:

Brushless DC Generator Controlled by Constrained Predictive ....pdf

Brushless DC Generator Controlled by Constrained Predictive Algorithm_能源/化工_工程科技_专业资料。JunlfnryadPweEgnei 2 17078orao eg n ornierg5(0 5-5 E...

...for Time-constrained Speech Processing and Generati.pdf

Time-constrained Speech Processing and Generati_...Proceedings of the 8th Real-Time Systems Natural ...Delay Analysis in Temp... 10页 免费 Abstract ...

CoSMIC An MDA Generative Tool for Distributed Real-time and ....pdf

Real-time and Embdedded Component Middleware_专业... such as conventional general-purpose programming ...such as components for memory constrained systems....

Analysis of a soft real-time random access protocol.pdf

A hard real-time system requires that all ...The obvious disadvantage to using a general ...protocol for transmission of time-constrained ...

...window-constrained scheduling of real-time strea....pdf

Analysis of a Window-Con... 暂无评价 10页 ... Dynamic window-constrained scheduling of real-time... the delay of service to real-time streams is ...

...Message Delivery Time on Real-Time Transputer Systems.pdf

hard real-time systems: failure to meet a ...The routing algorithm in general can be static ...[8], the authors use a constrained version of ...

温湿度控制中英文.doc

good realtime characteristic and wide ...General measurement precision. In a certain ...systems which have constrained sensors distributed ...

先进过程控制-模型预测控制简介_图文.pdf

Process Adjustments One hour to one day delay !...real-time process data Process Samples Analysis ...Constrained Nonlinear Dynamics Model Predictive ...

...of the Slave Loop in Cascade Temperature Control of Batch_....pdf

Z reactor temperature K3 + + T1,T2 DT K KAR Time constant Time-delay ...variables are constrained because of the physical limitations of the system)....

A Virtual Time CSMA Protocol for Hard Real Time Communication....pdf

performed in such systems are time constrained. ...of the general virtual remainder of this paper ... hard delay-throughput a virtual behavior time ...

...Virtual-Time CSMACD Protocols for Real-Time Systems.pdf

A delay constraint on a message speci es a ...time-constrained messages real-time communication ...that is a random variable with general ...

...Virtual-Time CSMACD Protocols for Real-Time Systems.pdf

A delay constraint on a message speci es a ...time-constrained messages real-time communication ...that is a random variable with general ...

...Large Time- Constrained Heterogeneous Adaptive S....pdf

Time- Constrained Heterogeneous Adaptive Systems... Real-time and embedded systems General Terms: ...To guide our synthesis process, we use delay/...

Real-time contour propagator for high temperature dimensional....pdf

Real-time contour propagator for high temperature ...constrained generating functional W [Φ, Π; j ...[13] by integrating φ 2 out hard modes, k ...

Scalable QoS Guaranteed Communication Services for Real-Time ....pdf

Communication Services for Real-Time Applications_...ow. We assume that the ?ow is constrained by ...In general, we have a circular dependency, as ...

Analysis of Clock Tracking Performances for a Software-only ....pdf

communications which are strongly time-constrained. ... Screen shot of measured system response delay (...As a general trend, every test can be divided ...

...based delay-constrained least-cost routing in wi....pdf

To guarantee the real-time delivery of pack隐藏>> Preferred Link Based ...The general problem of determining a least cost delay-constrained route in ...

A Distributed Algorithm for Delay-Constrained Unicast Routing....pdf

we study the NP-hard delay-constrained least-...the problem of unicast routing of real-time traf...the occurrence of loops complicates the analysis....

Delay Analysis of Fair Queueing Algorithms with the ....pdf

In order to analyze the worst-case delays of FQ policies in a general ... the activation instants are constrained to occur when virtual time takes ...

steel annealing processes as hybrid systems.doc

Neural-optimal control algorithm for real-time ...divides the general problem into smooth subproblems...constrained by system and thermal space transient ...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com