Open access peer-reviewed chapter

Real-Time Systems

Written By

Ming Fan

Submitted: October 26th, 2015 Reviewed: March 22nd, 2016 Published: June 8th, 2016

DOI: 10.5772/63278

From the Edited Volume

Real-time Systems

Edited by Kuodi Jian

Chapter metrics overview

View Full Metrics

Abstract

Since 2004, most of chip vendors have begun to shift their major focus from single-core to multi-core architecture (W. Wolf. Signal Processing Magazine, IEEE, 26(6):50–54, 2009). One major reason of this shift is that it reaches a physical limit by scaling transistor size and increasing the clock frequency to improve the computing performance on a single-core architecture (Agarwal et al. Proceedings of the 27th International Symposium on, pages 248–259, June 2000), that is, the overall chip cannot be reached within a single clock cycle. Multi-core architecture, however, brings innovative and promising opportunities to further improve the computing performance. By providing multiple processing cores on a single chip, multi-core systems can dramatically increase the computing performance and mitigate the power and thermal issues with the same performance achievement as single-core systems. As multi-core architecture has been more and more dominant in the industrial market, there is an urgent demand for effective and efficient techniques for the design of multi-core systems.

Keywords

• Real-Time
• Multi-Core
• Thermal
• Power
• Energy
• Periodic Scheduling

1. Introduction

Today, multi-core architecture has been widely supported by most of major chip vendors, including Intel, AMD, IBM, Nvidia, ARM, Sum microsystems, Qualcomm, Broadcom, and so on. Some of the chip manufacturers have already launched 16-core chips into the market, that is, AMD OpteronTM 6300 Series [1]. It is not surprising that in the coming future, hundreds or even thousands of cores will be integrated into a single chip [22]. When moving toward multi-core architecture, it comes with new and critical challenges in design of multi-core systems, particularly multi-core real-time systems.

As architecture becomes more and more complicated, besides the timing constraint, many other design constraints are taken into consideration in real-time system design and development. Traditional approaches focus exclusively on timing constraints [3,4,6,7]. Today, many other design constraints (e.g. power/energy, thermal, and reliability) also need to be considered seriously in real-time system design [8,9,11,12,14].

1.1. Power/energy analysis in multi-core real-time systems

Catalyzed by continuous transistor scaling, hundreds of billions of transistors have been integrated on a single chip [13]. One of the immediate consequence caused by the tremendous increase of transistor density is the soaring power consumption [5], which further results in severe challenges in energy and temperature[11,17]. Today, power has become a critical and challenging design objective in front of system designers.

1.2. Thermal analysis in multi-core real-time systems

The continuously increased power consumption has resulted in a soaring chip temperature. Moreover, as design paradigm shifts to deep submicron domain, high chip temperature leads to a substantial increase in leakage power consumption [13], which in turn further deteriorates the power situation due to the interdependency between temperature and leakage power. For instance, with Intel core i5-2500K (32 nm Sandy Bridge), the leakage power roughly grows up to 2× from 55°C (13 W) to 105°C (26 W), see Figure 1. Furthermore, the soaring chip temperature adversely impacts the performance, reliability, and packaging/cooling costs [17]. As a result, power and thermal issues have become critical and significant for advanced multi-core system design. In next section, we introduce some necessary backgrounds of multi-core scheduling with power and thermal awareness, respectively.

The aggressive semiconductor technology scaling has pushed the chip power density doubled every two to three years [16,20], which immediately results in an exponential increasing in heat density. High temperature can degrade the performance of systems in various ways. Therefore, there is a great need of advanced techniques for thermal/temperature aware design of multi-core systems.

2. Preliminary

2.1. Multi-core platform and task model

The multi-core platform consists of Mprocessing cores, M≥ 2, denoted as P, P= {P1,P2,…,PM}. Each core Pihas N running modes, each of which is characterized by a 2-tuple set (vk, fk), where vk represents the supply voltage and fk represents the frequency under mode k, 1 ≤ k ≤ N.

Let S represent a static and periodic speed schedule, which indicates how to vary the supply voltage and working frequency for each core at different time instants. A speed schedule S is constituted by several state intervals, which is described as below:

Definition 1[25]: Given a speed schedule S for a multi-core system, an interval [tq−1, tq] is called a state interval if each core runs only at one mode during that interval.

Recall that speed schedule S is a periodic schedule, let L denote the length of one scheduling period. According to Definition 1, a speed schedule S essentially consists of a number of non-overlapped state intervals. Let Q represent the number of non-overlapped state intervals within one scheduling period of S, then we have that [25]

1. q=1Q[tq1,tq]=[0,L]

2. [tq1,tq][tp1,tp]=, if qp

For a single state interval [tq−1, tq], let Kqrepresent the interval mode, Kq= {k1,k2,…,kM}, where kidenotes the running mode of core Piin interval [tq−1, tq].

2.2. Power model

The overall power consumption (in Watt) of each core is composed of two parts: dynamic power Pdynand leakage power Pleak. We assume that: (1) Pdynis varied with respect of supply voltage but independent of temperature, (2) Pleakis sensitive to both temperature and supply voltage. Specifically, for the dynamic power, we know that it is proportional to the square of supply voltage and linearity of working frequency. We assume that the working frequency is linearly proportional to supply voltage, thus the power consumption of the i-th core (Pi) under running mode kican be formulated as below [18].

Pdyn,i=γki*vki3E1

where γkiis a constant value determined by the platform and running mode, and vkiis the supply voltage of core Pidetermined by the running mode.

For leakage power, although there is a very complicated relationship between leakage power and temperature from circuit level perspective, Liu et al. [23] found that a linear approximation of the leakage temperature dependency is fairly accurate. Work [12] further formulated the leakage power of core Pias below:

Pleak,i=(αki+βki*Ti(t))*vkiE2

where αkiand βkiare constants depending on the core running mode, that is, mode ki.

Consequently, the total power consumption of core Piat time t, denoted as Pi(t), can be formulated as:

Pi(t)=(αki+βki*Ti(t))*vki+γki*vki3E3

For convenience in our presentation, we rewrite the above formula by separating the elements into temperature independent/dependent parts such that

Pi(t)=ψi+ϕi*Ti(t)E4

whereψi=αki*vki+γki*vki3and ϕi=βki*vki.

[P1(t)PM(t)]=[ψ1ψM]+[ϕ100ϕM][T1(t)TM(t)]E5

Or

Ρ(t)=Ψ+ΦΤ(t)E6

Note that we use the bold text for a vector/matrix and the unbolded text for a value, for example, Trepresents a temperature vector while Trepresents a temperature value.

2.3. Thermal model

Figure 2 illustrates the thermal circuit model for a multi-core platform consisting of four processing cores. Cirepresents the thermal capacitance (in Watt/°C) of core Pi, and Rijrepresents the thermal resistance (in J/°C) between core Piand Pj. Note that the thermal model adopted here is similar to the one used in related work [19,21]. Let Tambrepresent the ambient temperature, then the thermal phenomena of core Piin Figure 2 can be formulated as

CidTi(t)dt+Ti(t)TambRii+jiTi(t)Tj(t)Rij=Pi(t)E7

Let

{δi=TambRiigij={k=1M1Rik, if j=i1Rij, otherwiseE8

Then the thermal model in equation (7) can be rewritten as

CidTi(t)dt+j=1MgijTj(t)=Pi(t)+δiE9

Accordingly, for the entire system, the thermal model can be represented as

CdT(t)dt+gT(t)=P(t)+δE10

where Cand gare MxM matrices

C=[C100CM],g=[g11g1MgM1gMM]E11

and δis an Mx1vector

δ=[δ1δM]E12

Note that C, g, and δare all constants that are determined by the multi-core platform only. Moreover, Cis the thermal capacitance matrix with none zero values only on the diagonal, and gis a thermal conductance matrix. The thermal model adopted here is a generic model which takes the heat transfer among different cores into consideration. Thus, it can be directly applied on thermal analysis for both temperature transient state and temperature stable state.

3. Temperature analysis in multi-core real-time systems

There is an interactive effect between power and temperature, that is, high power leads to high temperature, which in turn further aggravates the power consumption. In order to calculate the energy consumption accurately and efficiently, it is necessary to develop an efficient solution to calculate the temperature first.

In this section, we first present a temperature formulation within thermal transient state for a constant speed schedule interval. Then we present an analytical solution to calculate the temperature within thermal steady state for a periodic speed schedule.

3.1. Temperature analysis in system thermal transient state

In this subsection, we will formulate the temperature variation [26] within one state interval [tq−1, tq] in the system thermal transient state.

First, by applying power model given by equation (6) into thermal model given by equation (10), we can derive that

CdT(t)dt+gT(t)=Ψ+ΦT(t)+δE13

Then we simplify the above equation by letting G=gΦ. Thus the above equation can be rewritten as

CdT(t)dt+GT(t)=Ψ+δE14

Since Crepresents the capacitance matrix, according to the circuit nature, we know that matrix Ccontains no zero values only on its diagonal. Thus, we can see matrix Cis non-singular. Therefore, the inverse of C, that is, C1exists. Then we can further simplify equation (14) into below

dT(t)dt=AT(t)+BE15

where A=C1Gand B=C1(Ψ+δ). The system thermal model formulated by equation (15) has a form of first order Ordinary Differential Equations (ODE). Particularly, if all coefficients are constant, then there exists a solution which can be formulated as

T(t)=etAT0+A1(etAI)BE16

For a state interval [tq−1,tq], it is important to point out that all coefficients in the above are constant. Specifically, let Kqbe the corresponding interval mode, and let T(tq−1) be the temperature at the starting point of that interval. Then according to equation (16), the ending temperature of that interval, that is, T(tq−1), can be directly formulated as

T(tq)=eΔtqAKqT(tq1)+AKq1(eΔtqAKqI)BKqE17

where Δtq=tqtq1.

3.2. Temperature analysis in system thermal steady state

In this subsection, we will formulate the temperature variation [26] within one state interval [tq−1, tq] in the system thermal steady state.

Consider a periodic speed schedule S, and let T(0) be the initial temperature at time instant 0. For an arbitrary state interval [tq−1, tq] within speed schedule S, to obtain its steady-state temperature, one intuitive way is to trace the entire schedule S by consecutively calculating the temperature from the first scheduling period until system reaches its thermal steady state.

Although this approach works from theoretical point of view, when considering the practical computational time cost (which would be extremely expensive), it turns out that this intuitive approach would be inefficient or even impractical. Thus, it would be desirable and useful to develop an efficient solution to rapidly calculate steady-state temperatures for a periodic speed schedule.

Let us first consider the temperature variation at the end of each scheduling period, that is, t= nL, where n≥ 1. Let the scheduling points of S(t) in the first period be t0,t1,…,ts, respectively. After repeating S(t), let the corresponding points in the second scheduling period be t0',t1',…,ts', respectively (see Figure 3). Note that

t0 = 0, t0' = ts= L, and ts'= 2L. According to equation (17), at time t1 and t1', we have

T(t1)=eΔt1AK1T(t0)+AK11(eΔt1AK1I)BK1E18
T(t1')=eΔt1'AK1T(t0')+AK11(eΔt1'AK1I)BK1E19

Subtract equation (18) from (19) on both sides, and simplify the result by applying Δt1=Δt1', t0=0and t0'=L, we get

T(t1')T(t1)=eΔt1AK1(T(L)T(0))E20

Follow the same trace of the above derivation, we have that

T(t2')T(t2)=eΔt2AK2eΔt1AK1(T(L)T(0))T(ts')T(ts)=eΔtsAKseΔt2AK2eΔt1AK1(T(L)T(0))E21

Since ts=L,ts'=2L, and let eΔtsAKseΔt2AK2eΔt1AK1=K, the last equation in (21) can be rewritten as

T(2L)T(L)=K(T(L)T(0))E22

In the same way, we can construct that

T(xL)T((x1)L)=Kx1(T(L)T(0))E23

where x = 1,2, …,n. Sum up the above n equations, we get

T(nL)=T(0)+x=1nKx1(T(L)T(0))E24

In the above, {Kx−1|x = 1,2,…,n} forms a matrix geometric sequence. If (IK) is invertible, then we have

T(nL)=T(0)+(IK)1(IKn)(T(L)T(0))E25

Next, we consider the temperature variation for an arbitrary time instant when repeating a periodic speed schedule. Given a periodic speed schedule S(t), let tq(tq∈[0,L]) be an arbitrary time instant within schedule S(t). Moreover, let's repeat S(t) for n times, where n≥ 1. Let T(nL+ tq) denote the temperature of T(tq) in the n-th scheduling period, by following the similar way of the above derivation, we can get that

T(nL+tq)=T(tq)+Kq(IK)1(IKn)(T(L)T(0))E26

where Kq=eΔtqAKqeΔt2AK2eΔt1AK1.

Until now, we have been able to formulate the temperature variation of an arbitrary time instant in the n-th scheduling period. Next, we will further formulate the temperature variation of an arbitrary time instant in the system steady state. Consider an arbitrary time instant, that is, tq, 0 ≤ tqL, within the first scheduling period. The brief idea of calculating the steady-state temperature corresponding to tqis to let n go to infinity in equation (27). We formally describe our method in Theorem 1.

Theorem 1[25]: Given a periodic speed schedule S(t), let T(L) and T(tq) be the temperatures at time instant Land tq, tq∈ [0,L], respectively. If for each eigenvalue λi of K, we have |λi| < 1, then the steady-state temperature corresponding to tq can be formulated as

Tss(tq)=T(tq)+Kq(IK)1(T(L)T(0))E27

Proof:

First, based on equation (26), by letting n→+∞, the steady-state temperature of the q-th scheduling point in S(t) can be represented as

Tss(tq)=T(tq)+Kq(IK)1(IlimnKn)(T(L)T(0))E28

When n→+∞, the matrix sequence Knconverges if and only if |λi|< 1, for each eigenvalue λi of K[14]. Under this condition, we have limnKn=0. Moreover, if |λi|< 1 holds, then (I-K) is invertible. Thus, the steady-state temperature of the q-th scheduling point in S(t) can be further formulated as

Tss(tq)=T(tq)+Kq(IK)1(T(L)T(0))E29

Note that as n→+∞, unless the temperature runs away and causes the system to break down, we know that the system could eventually achieve its thermal steady state. That means for each eigenvalue λi of K, the condition of |λi|< 1 should always hold. Therefore, it is reasonable and practical to make such assumption shown in Theorem 1.

4. Energy analysis in multi-core real-time systems

Besides temperature, energy consumption is another important and challenging issue in the design of multi-core real-time systems. We have now been able to formulate the temperature variation in a multi-core system in the previous section. In this section, we will discuss how to formulate the energy consumption on multi-core systems with consideration of the interdependence between leakage power and temperature.

In the rest of this section, we first present an analytical solution to calculate energy consumption of an arbitrary state interval. Then we present a solution to calculate the total energy consumption of the entire speed schedule.

4.1. Energy analysis for one scheduling state interval

Consider a state interval, that is, [tq−1, tq] with initial temperature of T(tq−1). The energy consumption of all cores within that interval can be simply formulated as

E(tq1,tq)=tq1tqP(t)dtE30

Based on our system power model, given by equation (6), we have

E(tq1,tq)=ΔtqΨ+Φtq1tqT(t)dtE31

Theorem 2 given below is targeted to solve the above energy calculation problem.

Theorem 2[25]: Given a state interval [tq−1, tq], let Tq−1be the temperature at time tq−1. Then the overall system energy consumption within interval [tq−1, tq] can be formulated as

E(tq1,tq)=ΔtqΨ+ΦG1HE32

where Δtq=tqtq1, andH=Δtq(Ψ+δ)C(T(tq)T(tq1)).

Proof:

In equation (31), let X=tq1tqT(t)dt, then the energy formula can be rewritten as

E(tq1,tq)=ΔtqΨ+ΦXE33

On the other hand, according to the system thermal model given by equation (10), we have

CdT(t)dt+GT(t)=Ψ+δE34

where G=gΦ. By integrating on both sides of the above equation with respect to time t, where t∈ [tq−1, tq], we can get

C(T(tq)T(tq1))+Gtq1tqT(t)=Δtq(Ψ+δ)E35

Note that X=tq1tqT(t)dt; thus from the above, we can derive that

X=G1HE36

where H=Δtq(Ψ+δ)C(T(tq)T(tq1))

Applying equation (36) into (33), we can see that

E(tq1,tq)=ΔtqΨ+ΦG1HE37

From Theorem 2, we can see that for an arbitrary state interval [tq−1, tq], once the beginning temperature T(tq−1) is known, the total energy consumption within [tq−1, tq] can be easily and directly calculated.

Subsequently, given a periodic speed schedule S and an initial temperature T0, we are able to calculate the energy consumption within an arbitrary state interval in any scheduling period.

Corollary 1[25]: Given a periodic speed schedule S(t) consisting of Q state intervals, let T0 be the initial temperature. Then the energy consumption within the q-th state interval in the n-th scheduling period, denoted as E(tq−1+ nL, tq+ nL), can be calculated as

E(tq1+nL,tq+nL)=ΔtqΨKq+ΦKqGKq1HKqE38

where Δtq=tqtq1, andHKq=Δtq(ΨKq+δ)C(T(tq+nL)T(tq1+nL)).

Corollary 1 can be easily derived from Theorem 2. With the help of Corollary 1, given any periodic speed schedule on a multi-core platform, when repeating that schedule, we can quickly calculate the energy consumption within any state interval.

Accordingly, given a periodic speed schedule, when analyzing the system thermal steady state, we can directly calculate the energy consumption of any state interval within the system steady state.

Corollary 2[25]: Given a periodic speed schedule S(t) consisting of Q state intervals, let T0 be the initial temperature. Then the energy consumption within the q-th state interval in the system steady state, denoted as Ess(tq−1, tq), can be calculated as

Ess(tq1,tq)=ΔtqΨKq+ΦKqGKq1HssKqE39

where Δtq=tqtq1, andHssKq=Δtq(ΨKq+δ)C(Tss(tq)Tss(tq1)).

Corollary 2 is directly derived from Corollary 1 by replacing the transient temperatures with steady-state temperatures.

References

1. 1. AMD. Amd server processor series. pages http://www.amd.com/US/PRODUCTS/SERVER/PROCESSORS/6000–SERIES–PLATFORM/6300/Pages/6300–series–processors.aspx, 2013.
2. 2. J.H. Anderson, V. Bud, and U.C. Devi. An EDF-Based Scheduling Algorithm for Multiprocessor Soft Real-Time Systems. In Proceedings of Euromicro Conference on Real-Time Systems (ECRTS), July 2005.
3. 3. B. Andersson, S. Baruah, and J. Jonsson. Static-Priority Scheduling on Multiprocessors. In Proceedings of IEEE Real-Time Systems Symposium (RTSS), December 2001.
4. 4. M. Bao, A. Andrei, P. Eles, and Z. Peng. On-line thermal aware dynamic voltage scaling for energy optimization with frequency/temperature dependency consideration. In Design Automation Conference, 2009. DAC ’09. 46th ACM/IEEE, pages 490–495, July 2009.
5. 5. V.N. Darera and L. Jenkins. Utilization bounds for rm scheduling on uniform multiprocessors. In Embedded and Real-Time Computing Systems and Applications, 2006. Proceedings of 12th IEEE International Conference on, pages 315–321, 0-0.
6. 6. M. Fan and G. Quan. Harmonic semi-partitioned scheduling for fixed-priority real-time tasks on multi-core platform. In Design, Automation Test in Europe Conference Exhibition (DATE), pages 503–508, March 2012.
7. 7. Q. Han, M. Fan, and G. Quan. Energy minimization for fault tolerant real-time applications on multiprocessor platforms using checkpointing. In Low Power Electronics and Design (ISLPED), 2013 IEEE International Symposium on, pages 76–81, September 2013.
8. 8. V. Hanumaiah and S. Vrudhula. Energy-efficient operation of multi-core processors by dvfs, task migration and active cooling. Computers (TC), IEEE Transactions on, pages 1–14, 2012.
9. 9. Henry. A comparison of intels 32nm and 22nm core i5 cpus: Power, voltage, temperature, and frequency. Intel Cor., pages http://blog.stuffedcow.net/2012/10/intel32nm–22nm–core–i5–comparison/, 2012.
10. 10. H. Huang and G. Quan. Leakage aware energy minimization for real-time systems under the maximum temperature constraint. In DATE, pages 1–6, 2011.
11. 11. H. Huang, G. Quan, J. Fan, and M. Qiu. Throughput maximization for periodic real-time systems under the maximal temperature constraint. In Design Automation Conference (DAC), 2011 48th ACM/EDAC/IEEE, pages 363–368, June 2011.
12. 12. ITRS. International Technology Roadmap for Semiconductors (2011 Edition). International SEMATECH, Austin, TX, http://public.itrs.net/.
13. 13. R. Jayaseelan and T. Mitra. Temperature aware task sequencing and voltage scaling. ICCAD, pages 618–623, 2008.
14. 14. S. Bell and J. Rosenblatt. Mathematical analysis for modeling, December 1998.
15. 15. G. Moore. Cramming more components onto integrated circuits. Electronics Magazine, 38(8):114–117, May 1965.
16. 16. G. Quan and V. Chaturvedi. Feasibility analysis for temperature-constraint hard real-time periodic tasks. Industrial Informatics, IEEE Transactions on, 6(3):329–339, 2010.
17. 17. J. Rabaey, A. Chandrakasan, and B. Nikolic. Digital Integrated Circuits: A Design Perspective. Englewood Cliffs, NJ: Prentice-Hall, 2003.
18. 18. S. Sharifi, R. Ayoub, and T.S. Rosing. Tempomp: Integrated prediction and management of temperature in heterogeneous mpsocs. In Design, Automation Test in Europe Conference Exhibition (DATE), 2012, pages 593–598, March 2012.
19. 19. K. Skadron, M.R. Stan, W. Huang, S. Velusamy, K. Sankaranarayanan, and D. Tarjan. Temperature-aware microarchitecture. ICSA, pages 2–13, 2003.
20. 20. I. Ukhov, M. Bao, P. Eles, and Z. Peng. Steady-state dynamic temperature analysis and reliability optimization for embedded multiprocessor systems. In Design Automation Conference, June 2012.
21. 21. D. Yeh, L.S. Peh, S. Borkar, J. Darringer, A. Agarwal, and W. Hwu. Thousand-core chips [roundtable]. Design Test of Computers, IEEE, 25(3):272–278, 2008.
22. 22. Y. Liu and Y. Huazhong. Temperature-aware leakage estimation using piecewise linear power models. IEICE transactions on electronics, 93(12):1679–1691, 2010.
23. 23. W. Wolf. Multiprocessor system-on-chip technology. Signal Processing Magazine, IEEE, 26(6):50–54, 2009.
24. 24. V. Agarwal, M.S. Hrishikesh, S. Keckler, and D. Burger. Clock rate versus ipc: the end of the road for conventional microarchitectures. In Computer Architecture, 2000. Proceedings of the 27th International Symposium on, pages 248–259, June 2000.
25. 25. M. Fan, R. Rong, S. Liu, and G. Quan. Energy calculation for periodic multi-core scheduling in system thermal steady state with consideration of leakage and temperature dependency. The Journal of Supercomputing, 71(7):2565–2584, 2015.
26. 26. M. Fan, V. Chaturvedi, S. Sha, and G. Quan. An analytical solution for multi-core energy calculation with consideration of leakage and temperature dependency, Low Power Electronics and Design (ISLPED), 2013 IEEE International Symposium on, Beijing, pages 353–358, 2013.

Written By

Ming Fan

Submitted: October 26th, 2015 Reviewed: March 22nd, 2016 Published: June 8th, 2016