nach oben

Real-Time Systems

Erschienen in:

23.09.2016

Optimizing resource speed for two-stage real-time tasks

verfasst von: Alessandra Melani, Renato Mancuso, Daniel Cullina, Marco Caccamo, Lothar Thiele

Erschienen in: Real-Time Systems | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Multiple resource co-scheduling algorithms and pipelined execution models are becoming increasingly popular, as they better capture the heterogeneous nature of modern architectures. The problem of scheduling tasks composed of multiple stages tied to different resources goes under the name of “flow-shop scheduling”. This problem, studied since the ‘50s to optimize production plants, is known to be NP-hard in the general case. In this paper, we consider a specific instance of the flow-shop task model that captures the behavior of a two-resource (DMA-CPU) system. In this setting, we study the problem of selecting the optimal operating speed of the two resources with the goal of minimizing power usage while meeting real-time schedulability constraints. In particular, we derive an algorithm that finds the optimal speed of one resource while the speed of the other resource is kept constant. Then, we discuss how to extend the proposed approach to jointly optimize the speed of the two resources. In addition, applications to multiprocessor systems and energy minimization are considered. All the proposed algorithms run in polynomial time, hence they are suitable for online operation even in the presence of variable real-time workload.

Vorheriger Artikel Real-time scheduling algorithm for safety-critical systems on faulty multicore environments

Nächster Artikel Deterministic delay analysis of AVB switched Ethernet networks using an extended Trajectory Approach

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Reasoning in terms of clock period \(T_{ck}\) describes well the performance of CPUs; however, it is more appropriate to reason in terms of bandwidth when describing the performance of memory subsystems. Since a dualism exists between the two concepts, we will adopt the notation \(T_{ck}\) when referring to either resource type.

Computation is performed over data that has been preloaded into local memory, while memory operations do not involve computation. Thus computation time scales linearly with clock speed as long as CPU speed and local memory are tied to the same clock. Similarly, performance of memory-only operations scales linearly with the configured transfer bandwidth.

See http://www.nvidia.com/object/tegra-k1-processor.html.

See http://ark.intel.com/products/75123/Intel-Core-i7-4770K.

See http://cache.freescale.com/files/32bit/doc/fact_sheet/MPC5777MFS.

See http://cache.freescale.com/files/32bit/doc/prod_brief/P4080PB.

We recall that \(\hat{\sigma }^{t}_1, \ldots , \hat{\sigma }^{t}_n\) is the permutation of jobs corresponding to the minimum makespan when \(T_{ck} = t\).

For the last element of \(\mathcal {P}_s\), we consider the interval \([\mathcal {P}_{s, i}, +\infty )\).

Here, we refer to the complete list of changing points of \(F_C(t)\), i.e., including all changing points in the interval \(T_{ck} \in (0^+, +\infty )\). This means that, when running Algorithm 1, the function Reinit at line 22 should not be executed.

In this section, we reason in terms of clock speed instead of clock period for ease of understanding, and assume \(s \in (0, 1]\).

Note that the set \(\mathcal {P}^k_{s}\) constructed in this way is a superset of the actual schedule changing points of \(\mathcal {T}_k\), hence the slope of \(F^*_{C, k}(t)\) does not necessarily change for all points in \(\mathcal {P}^k_{s}\). As we will see next, this simplification makes our results directly applicable to the multiprocessor case with no modifications.

This value can be found by applying Algorithm 3 with no modifications.

ARM Cortex-A9 CPUs implement a clock cycle counter that is accessible on a dedicated per-core register (ARM Holdings 2016).

Alhammad A, Pellizzoni R (2014) Schedulability analysis of global memory-predictable scheduling. In: 14th international conference on embedded software (EMSOFT)

Alhammad A, Wasly S, Pellizzoni R (2015) Memory efficient global scheduling of real-time tasks. In: 21st IEEE real-time and embedded technology and applications symposium (RTAS)

ARM Holdings (2016) ARM Cortex-A9—technical reference manual. http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0388e/index.html

Barcelo N, Kling P, Nugent M, Pruhs K, Scquizzato M (2015) On the complexity of speed scaling. In: Mathematical foundations of computer science 2015. Springer, New York, pp 75–89

Baruah S (2014) Improved multiprocessor global schedulability analysis of sporadic dag task systems. In: 2014 26th Euromicro conference on real-time systems, pp 97–105

Benini L, De Micheli G (2012) Dynamic power management: design techniques and CAD tools. Springer, New YorkMATH

Bonifaci V, Marchetti-Spaccamela A, Stiller S, Wiese A (2013) Feasibility analysis in the sporadic dag task model. In: 2013 25th Euromicro conference on real-time systems, pp 225–233

Chen B (1995) Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. J Oper Res Soc 46(2):234–244CrossRefMATH

Cox MG (1971) An algorithm for approximating convex functions by means by first degree splines. Comput J 14(3):272–275CrossRefMATH

De Vogeleer K, Memmi G, Jouvelot P, Coelho F (2014) The energy/frequency convexity rule: modeling and experimental validation on mobile devices. In: Parallel processing and applied mathematics (Lecture notes in computer science), vol 8384. Springer, New York, pp 793–803

Devadas V, Aydin H (2012) On the interplay of voltage/frequency scaling and device power management for frame-based real-time embedded applications. IEEE Trans Comput 61(1):31–44MathSciNetCrossRef

Edelsbrunner H, Guibas LJ, Sharir M (1989) The upper envelope of piecewise linear functions: algorithms and applications. Discret Comput Geom 4(1):311–336MathSciNetCrossRefMATH

Egger B, Lee J, Shin H (2008) Scratchpad memory management in a multitasking environment. In: 8th ACM international conference on embedded software (EMSOFT)

Garey M, Johnson D, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1(2):117–129MathSciNetCrossRefMATH

Hoogeveen J, Lenstra J, Veltman B (1996) Preemptive scheduling in a two-stage multiprocessor shop is NP-hard. Eur J Oper Res 89:172–175CrossRefMATH

Imamoto A, Tang B (2008) Optimal piecewise linear approximation of convex functions. In: World Congress on engineering and computer science (WCECS)

Ishihara T, Yasuura H (1998) Voltage scheduling problem for dynamically variable voltage processors. In: International symposium on power electronics and design (InLow)

Jejurikar R, Pereira C, Gupta R (2004) Leakage aware dynamic voltage scaling for real-time embedded systems. In: 41st design automation conference (DAC)

Jia Z, Li Y, Wang Y, Wang M, Shao Z (2015) Temperature-aware data allocation for embedded systems with cache and scratchpad memory. ACM Trans Embed Comput Syst 14(2):30CrossRef

Johnson S (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res Logist Q 1:61–68CrossRefMATH

Kaup F, Melnikowitsch S, Hausheer D (2014) Measuring and modeling the power consumption of openflow switches. In: 2014 10th international conference on network and service management (CNSM), pp 181–186

Melani A, Mancuso R, Cullina D, Caccamo M, Thiele L (2016) Speed optimization for tasks with two resources. In: 19th international conference on design, automation and test in Europe (DATE)

Melani A, Bertogna M, Bonifaci V, Marchetti-Spaccamela A, Buttazzo G (2015) Memory-processor co-scheduling in fixed priority systems. In: 23rd international conference on real-time networks and systems (RTNS)

Pellizzoni R, Betti E, Bak S, Yao G, Criswell J, Caccamo M, Kegley R (2011) A predictable execution model for COTS-based embedded systems. In: 17th IEEE real-time and embedded technology and applications symposium (RTAS)

Rabaey JM, Chandrakasan A, Nikolic B (2003) Digital integrated circuits, 2nd edn., Prentice Hall electronics and VLSI seriesPrentice Hall, Upper Saddle River

Schranzhofer A, Chen JJ, Thiele L (2010) Timing analysis for TDMA arbitration in resource sharing systems. In: 16th IEEE real-time and embedded technology and applications symposium (RTAS)

Schuurman P, Woeginger GJ (2000) A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem. Theor Comput Sci 237(1–2):105–122MathSciNetCrossRefMATH

Serrano MA, Melani A, Bertogna M, Quinones E (2016) Response-time analysis of DAG tasks under fixed priority scheduling with limited preemptions. In: 2016 design, automation test in Europe conference exhibition (DATE), pp 1066–1071

Tabish R, Mancuso R, Wasly S, Alhammad A, Phatak SS, Pellizzoni R, Caccamo M (2016) A real-time scratchpad-centric OS for multi-core embedded systems. In: 2016 IEEE real-time and embedded technology and applications symposium (RTAS), pp 1–11

Vandewalle J (1975) On the calculation of the piecewise linear approximation to a discrete function. IEEE Trans Comput 8:843–846CrossRefMATH

Venkata S, Ahn I, Jeon D, Gupta A, Louie C, Garcia S, Belongie S, Taylor M (2009) SD-VBS: the San Diego vision benchmark suite. In: IEEE international symposium on workload characterization, 2009. IISWC 2009, pp 55–64

Vogelsang T (2010) Understanding the energy consumption of dynamic random access memories. In: 2010 43rd annual IEEE/ACM international symposium on microarchitecture (MICRO), pp 363–374

Wang Y, Shao Z, Chan HCB, Liu D, Guan Y (2014) Memory-aware task scheduling with communication overhead minimization for streaming applications on bus-based multiprocessor system-on-chips. IEEE Trans Parallel Distrib Syst 25(7):1797–1807CrossRef

Wasly S, Pellizzoni R (2013) A dynamic scratchpad memory unit for predictable real-time embedded systems. In: 25th Euromicro conference on real-time systems (ECRTS)

Wasly S, Pellizzoni R (2014) Hiding memory latency using fixed priority scheduling. In: 20th IEEE real-time and embedded technology and applications symposium (RTAS)

Yao G, Pellizzoni R, Bak S, Betti E, Caccamo M (2011) Memory-centric scheduling for multicore hard real-time systems. In: Real-time systems. Springer, New York

Titel: Optimizing resource speed for two-stage real-time tasks
verfasst von: Alessandra Melani
Renato Mancuso
Daniel Cullina
Marco Caccamo
Lothar Thiele
Publikationsdatum: 23.09.2016
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 1/2017
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-016-9259-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner