×

Energy-efficient real-time scheduling for two-type heterogeneous multiprocessors. (English) Zbl 1425.68048

Summary: We propose three novel mathematical optimization formulations that solve the same two-type heterogeneous multiprocessor scheduling problem for a real-time taskset with hard constraints. Our formulations are based on a global scheduling scheme and a fluid model. The first formulation is a mixed-integer nonlinear program, since the scheduling problem is intuitively considered as an assignment problem. However, by changing the scheduling problem to first determine a task workload partition and then to find the execution order of all tasks, the computation time can be significantly reduced. Specifically, the workload partitioning problem can be formulated as a continuous nonlinear program for a system with continuous operating frequency, and as a continuous linear program for a practical system with a discrete speed level set. The latter problem can therefore be solved by an interior point method to any accuracy in polynomial time. The task ordering problem can be solved by an algorithm with a complexity that is linear in the total number of tasks. The work is evaluated against existing global energy/feasibility optimal workload allocation formulations. The results illustrate that our algorithms are both feasibility optimal and energy optimal for both implicit and constrained deadline tasksets. Specifically, our algorithm can achieve up to 40% energy saving for some simulated tasksets with constrained deadlines. The benefit of our formulation compared with existing work is that our algorithms can solve a more general class of scheduling problems due to incorporating a scheduling dynamic model in the formulations and allowing for a time-varying speed profile.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

LPbook; SOCS; SCIP; SoPlex; Ipopt
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achterberg T (2009) SCIP: solving constraint integer programs. Math Program Comput 1(1):1-41 · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1
[2] ARM (2013) big.little technology: the future of mobile. http://www.arm.com/files/pdf/big_LITTLE_Technology_the_Futue_of_Mobile.pdf · Zbl 1309.93060
[3] Awan M, Petters S (2013) Energy-aware partitioning of tasks onto a heterogeneous multi-core platform. In: 2013 IEEE 19th Real-time and embedded technology and applications symposium (RTAS), pp 205-214. doi:10.1109/RTAS.2013.6531093
[4] Aydin H, Melhem R, Mosse D, Mejia-Alvarez P (2004) Power-aware scheduling for periodic real-time tasks. IEEE Trans Comput 53(5):584-600. doi:10.1109/TC.2004.1275298 · doi:10.1109/TC.2004.1275298
[5] Aydin H, Devadas V, Zhu D (2006) System-level energy management for periodic real-time tasks. In: 27th IEEE international real-time systems symposium, 2006. RTSS ’06, pp 313-322. doi:10.1109/RTSS.2006.48 · Zbl 0265.68013
[6] Baruah S (2004) Task partitioning upon heterogeneous multiprocessor platforms. In: 10th IEEE real-time and embedded technology and applications symposium, 2004. Proceedings. RTAS 2004, pp 536-543. doi:10.1109/RTTAS.2004.1317301
[7] Baruah SK, Cohen NK, Plaxton CG, Varvel DA (1993) Proportionate progress: a notion of fairness in resource allocation. In: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, STOC ’93. ACM, New York, pp 345-354. doi:10.1145/167088.167194 · Zbl 1310.68046
[8] Bemporad A, Borrelli F, Morari M (2002a) Model predictive control based on linear programming—the explicit solution. IEEE Trans Autom Control 47(12):1974-1985 · Zbl 1364.93697 · doi:10.1109/TAC.2002.805688
[9] Bemporad A, Morari M, Dua V, Pistikopoulos EN (2002b) The explicit linear quadratic regulator for constrained systems. Automatica 38(1):3-20 · Zbl 0999.93018 · doi:10.1016/S0005-1098(01)00174-1
[10] Betts J (2010) Practical methods for optimal control and estimation using nonlinear programming, 2nd edn. Society for Industrial and Applied Mathematics. doi:10.1137/1.9780898718577, http://epubs.siam.org/doi/abs/10.1137/1.9780898718577 · Zbl 1189.49001
[11] Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, New York · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[12] Chen JJ, Kuo CF (2007) Energy-efficient scheduling for real-time systems on dynamic voltage scaling (DVS) platforms. In: 13th IEEE international conference on embedded and real-time computing systems and applications, 2007. RTCSA 2007, pp 28-38. doi:10.1109/RTCSA.2007.37
[13] Chen JJ, Hsu HR, Kuo TW (2006) Leakage-aware energy-efficient scheduling of real-time tasks in multiprocessor systems. In: Proceedings of the 12th IEEE real-time and embedded technology and applications symposium, 2006, pp 408-417. doi:10.1109/RTAS.2006.25
[14] Chen JJ, Yang CY, Lu HI, Kuo TW (2008) Approximation algorithms for multiprocessor energy-efficient scheduling of periodic real-time tasks with uncertain task execution time. In: Real-time and embedded technology and applications symposium, 2008. RTAS ’08. IEEE, pp 13-23. doi:10.1109/RTAS.2008.24 · Zbl 1360.93235
[15] Chen JJ, Schranzhofer A, Thiele L (2009) Energy minimization for periodic real-time tasks on heterogeneous processing units. In: IEEE international symposium on parallel distributed processing, 2009. IPDPS 2009, pp 1-12. doi:10.1109/IPDPS.2009.5161024
[16] Cho H, Ravindran B, Jensen E (2006) An optimal real-time scheduling algorithm for multiprocessors. In: 27th IEEE international real-time systems symposium, 2006. RTSS ’06, pp 101-110. doi:10.1109/RTSS.2006.10 · Zbl 1233.68107
[17] Chwa HS, Seo J, Yoo H, Lee J, Shin I (2014) Energy and feasibility optimal global scheduling framework on big.little platforms. Tech. rep., Department of Computer Science, KAIST and Department of Computer Science and Engineering, Sungkyunkwan University, Republic of Korea. https://cs.kaist.ac.kr/upload_files/report/1407392146.pdf
[18] Chwa HS, Seo J, Lee J, Shin I (2015) Optimal real-time scheduling on two-type heterogeneous multicore platforms. In: 2015 IEEE real-time systems symposium, pp 119-129 · Zbl 1360.93235
[19] Funaoka K, Kato S, Yamasaki N (2008a) Energy-efficient optimal real-time scheduling on multiprocessors. In: 11th IEEE international symposium on object oriented real-time distributed computing (ISORC), 2008, pp 23-30. doi:10.1109/ISORC.2008.19
[20] Funaoka K, Takeda A, Kato S, Yamasaki N (2008b) Dynamic voltage and frequency scaling for optimal real-time scheduling on multiprocessors. In: International symposium on industrial embedded systems, 2008. SIES 2008, pp 27-33. doi:10.1109/SIES.2008.4577677
[21] Funk S, Berten V, Ho C, Goossens J (2012) A global optimal scheduling algorithm for multiprocessor low-power platforms. In: Proceedings of the 20th international conference on real-time and network systems. RTNS ’12. ACM, New York, pp 71-80. doi:10.1145/2392987.2392996
[22] Gerards M, Hurink J, Holzenspies P, Kuper J, Smit G (2014) Analytic clock frequency selection for global dvfs. In: 2014 22nd Euromicro international conference on parallel, distributed and network-based processing (PDP), pp 512-519. doi:10.1109/PDP.2014.103
[23] Gerdts M (2006) A variable time transformation method for mixed-integer optimal control problems. Optim Control Appl Methods 27(3):169-182. doi:10.1002/oca.778 · doi:10.1002/oca.778
[24] Goh LK, Veeravalli B, Viswanathan S (2009) Design of fast and efficient energy-aware gradient-based scheduling algorithms heterogeneous embedded multiprocessor systems. IEEE Trans Parallel Distrib Syst 20(1):1-12. doi:10.1109/TPDS.2008.55 · doi:10.1109/TPDS.2008.55
[25] Hei L, Nocedal J, Waltz RA (2008) A numerical study of active-set and interior-point methods for bound constrained optimization. In: Bock HG, Kostina E, Phu HX, Rannacher R (eds) Modeling, simulation and optimization of complex processes: proceedings of the third international conference on high performance scientific computing, March 6-10, 2006. Springer, Berlin, pp 273-292. doi:10.1007/978-3-540-79409-7_18 · Zbl 0313.68054
[26] Jerez JL, Goulart PJ, Richter S, Constantinides GA, Kerrigan EC, Morari M (2014) Embedded online optimization for model predictive control at megahertz rates. IEEE Trans Autom Control 59(12):3238-3251 · Zbl 1360.93235 · doi:10.1109/TAC.2014.2351991
[27] Kang J, Cao Y, Word DP, Laird CD (2014) An interior-point method for efficient solution of block-structured NLP problems using an implicit Schur-complement decomposition. Comput Chem Eng 71:563-573 · doi:10.1016/j.compchemeng.2014.09.013
[28] Kasture A (2017) Optimal control and scheduling of computing systems. Master’s thesis, Imperial College London
[29] Koch T (2004) Rapid mathematical prototyping. PhD thesis, Technische Universität, Berlin
[30] Lawler E (1983) Recent results in the theory of machine scheduling. In: Bachem A, Korte B, Grötschel M (eds) Mathematical programming the state of the art. Springer, Berlin, pp 202-234. doi:10.1007/978-3-642-68874-4_9 · Zbl 0547.90042
[31] Leung LF, Tsui CY, Ki WH (2004) Minimizing energy consumption of multiple-processors-core systems with simultaneous task allocation, scheduling and voltage assignment. In: Design automation conference, 2004. Proceedings of the ASP-DAC 2004. Asia and South Pacific, pp 647-652. doi:10.1109/ASPDAC.2004.1337672
[32] Levin G, Funk S, Sadowski C, Pye I, Brandt S (2010) DP-FAIR: a simple model for understanding optimal multiprocessor scheduling. In: 22nd Euromicro conference on real-time systems (ECRTS), pp 3-13. doi:10.1109/ECRTS.2010.34 · Zbl 1243.68106
[33] Li D, Wu J (2012) Energy-aware scheduling for frame-based tasks on heterogeneous multiprocessor platforms. In: 41st International conference on parallel processing (ICPP), pp 430-439. doi:10.1109/ICPP.2012.26
[34] Li D, Wu J (2013) Energy-aware scheduling on multiprocessor platforms. Springer briefs in computer science. Springer, New York · doi:10.1007/978-1-4614-5224-9
[35] Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46-61. doi:10.1145/321738.321743 · Zbl 0265.68013 · doi:10.1145/321738.321743
[36] Mayne DQ (2014) Model predictive control: recent developments and future promise. Automatica 50(12):2967-2986. doi:10.1016/j.automatica.2014.10.128 · Zbl 1309.93060 · doi:10.1016/j.automatica.2014.10.128
[37] McNaughton R (1959) Scheduling with deadlines and loss function. Mach Sci 6(1):1-12 · Zbl 1047.90504
[38] Miyoshi A, Lefurgy C, Van Hensbergen E, Rajamony R, Rajkumar R (2002) Critical power slope: Understanding the runtime effects of frequency scaling. In: Proceedings of the 16th international conference on supercomputing, ICS ’02. ACM, New York, pp 35-44. doi:10.1145/514191.514200 · Zbl 1171.90476
[39] Nelissen G, Berten V, Nelis V, Goossens J, Milojevic D (2012) U-edf: an unfair but optimal multiprocessor scheduling algorithm for sporadic tasks. In: 24th Euromicro conference on real-time systems (ECRTS), pp 13-23. doi:10.1109/ECRTS.2012.36
[40] Rabaey JM, Chandrakasan AP, Nikolic B (2003) Digital integrated circuits: a design perspective, 2nd edn. Prentice Hall electronics and VLSI series. Pearson Education, Upper Saddle River, NJ
[41] Regnier P, Lima G, Massa E, Levin G, Brandt S (2011) Run: optimal multiprocessor real-time scheduling via reduction to uniprocessor. In: IEEE 32nd real-time systems symposium (RTSS), pp 104-115. doi:10.1109/RTSS.2011.17 · Zbl 1291.68095
[42] Thammawichai M, Kerrigan E (2016) Feedback scheduling for energy-efficient real-time homogeneous multiprocessor systems. In: Proc. 55th IEEE conference on decision and control, Las Vegas, USA · Zbl 1425.68048
[43] Ullman J (1975) NP-complete scheduling problems. J Comput Syst Sci 10(3):384-393. doi:10.1016/S0022-0000(75)80008-0 · Zbl 0313.68054 · doi:10.1016/S0022-0000(75)80008-0
[44] Vanderbei RJ (2001) Linear programming: foundations and extensions. International series in operations research & management science. Kluwer Academic, Boston. http://opac.inria.fr/record=b1100407
[45] Wächter A, Biegler LT (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math Program 106(1):25-57. doi:10.1007/s10107-004-0559-y · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[46] Wu F, Jin S, Wang Y (2012) A simple model for the energy-efficient optimal real-time multiprocessor scheduling. In: IEEE international conference on computer science and automation engineering (CSAE), vol 3, pp 18-21. doi:10.1109/CSAE.2012.6272898
[47] Wunderling R (1996) Paralleler und objektorientierter simplex-algorithmus. PhD thesis, Technische Universität, Berlin · Zbl 0871.65048
[48] Xian C, Lu YH, Li Z (2007) Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution time. In: 44th ACM/IEEE design automation conference, 2007. DAC ’07, pp 664-669
[49] Yang CY, Chen JJ, Kuo TW, Thiele L (2009) An approximation scheme for energy-efficient scheduling of real-time tasks in heterogeneous multiprocessor systems. In: Design, automation test in Europe conference exhibition, 2009. DATE ’09, pp 694-699. doi:10.1109/DATE.2009.5090754
[50] Yu Y, Prasanna V (2002) Power-aware resource allocation for independent tasks in heterogeneous real-time systems. In: Ninth international conference on parallel and distributed systems, pp 341-348. doi:10.1109/ICPADS.2002.1183422
[51] Zhai B, Blaauw D, Sylvester D, Flautner K (2004) Theoretical and practical limits of dynamic voltage scaling. In: Proceedings of the 41st annual design automation conference, DAC ’04. ACM, New York, pp 868-873. doi:10.1145/996566.996798
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.