Artículo

Méndez-Díaz, I.; Orozco, J.; Santos, R.; Zabala, P. "Energy-aware scheduling mandatory/optional tasks in multicore real-time systems" (2017) International Transactions in Operational Research. 24(1-2):173-198
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Reward-based scheduling of real-time systems of periodic, preemptable, and independent tasks with mandatory and optional parts in homogeneous multiprocessors with energy considerations is a problem that has not been analyzed before. The problem is NP-hard. In this paper, a restricted migration schedule is adopted in which different jobs of the same task may execute in different processors and at different power modes but no migration is allowed after the job has started its execution. An objective function to maximize the performance of the system considering the execution of optional parts, the benefits of slowing down the processor, and a penalty for changing the operation frequency is introduced together with a set of constraints that guarantee the real-time performance of the system. Different algorithms are proposed to find a feasible schedule maximizing the objective function and are compared using synthetic systems of tasks generated following guidelines proposed in previous papers. © 2016 The Authors. International Transactions in Operational Research © 2016 International Federation of Operational Research Societies Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148, USA.

Registro:

Documento: Artículo
Título:Energy-aware scheduling mandatory/optional tasks in multicore real-time systems
Autor:Méndez-Díaz, I.; Orozco, J.; Santos, R.; Zabala, P.
Filiación:Dep. de Computación, Fac. Cs. Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Dep. Ing. Eléctrica y Computadoras—IIIE, Universidad Nacional del Sur, CONICET, Buenos Aires, Argentina
Palabras clave:combinatorial optimization; heuristics; integer programming; scheduling; Combinatorial optimization; Integer programming; Interactive computer systems; Job shop scheduling; Power management; Scheduling; Energy considerations; Energy-aware scheduling; Heuristics; Independent tasks; Objective functions; Operation frequency; Real time performance; Synthetic systems; Real time systems
Año:2017
Volumen:24
Número:1-2
Página de inicio:173
Página de fin:198
DOI: http://dx.doi.org/10.1111/itor.12328
Título revista:International Transactions in Operational Research
Título revista abreviado:Int. Trans. Oper. Res.
ISSN:09696016
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09696016_v24_n1-2_p173_MendezDiaz

Referencias:

  • Albers, S., Antoniadis, A., Greiner, G., On multi-processor speed scaling with migration (2015) Journal of Computer and System Sciences, 81 (7), pp. 1194-1209
  • Andersson, B., Jonsson, J., Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition (2000) In Proceedings of the Seventh International Conference on Real-Time Computing Systems and Applications, pp. 337-346. , Cheju Island, Korea
  • Andersson, B., Jonsson, J., The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50% (2003) In EuroMicro Conference on Real-Time Systems, pp. 33-40. , Porto, Portugal
  • Astrom, K.J., Wittenmark, B., (1994) Adaptive Control, , 2nd edn, Addison-Wesley Longman, Boston, MA
  • Audsley, N., Burns, A., Richardson, M., Wellings, A., Real-time scheduling: the deadline-monotonic approach (1991) In Proceedings of the IEEE Workshop on Real-Time Operating Systems and Software, pp. 133-137. , Atlanta, GA
  • Aydin, H., Melhem, R., Mossé, D., Mejía-Alvarez, P., Optimal reward-based scheduling for periodic real-time tasks (2001) IEEE Transactions on Computers, 50 (2), pp. 111-130
  • Aydin, H., Melhem, R., Mossé, D., Mejía-Alvarez, P., Power-aware scheduling for periodic real-time tasks (2004) IEEE Transactions on Computers, 53 (5), pp. 584-600
  • Baruah, S., Carpenter, J., Multiprocessor fixed-priority scheduling with restricted interprocessor migrations (2003) In Proceedings of the 15th Euromicro Conference on Real-Time Systems, pp. 195-202. , Porto, Portugal
  • Bini, E., Buttazzo, G., Measuring the performance of schedulability tests (2005) Real-Time Systems, 30 (1-2), pp. 129-154
  • Chan, H.-L., Lam, T.-W., Li, R., Tradeoff between energy and throughput for online deadline scheduling (2011) Sustainable Computing: Informatics and Systems, 1 (3), pp. 189-195
  • Chung, J., Liu, J., Lin, K., Scheduling periodic jobs that allow imprecise results (1990) IEEE Transactions on Computers, 39 (9), pp. 1156-1174
  • Dertouzos, M., Mok, A., Multiprocessor online scheduling of hard-real-time tasks (1989) IEEE Transactions on Software Engineering, 15 (12), pp. 1497-1506
  • Fisher, N.W., The multiprocessor real-time scheduling of general task systems (2007) PhD thesis, University of North Carolina at Chapel Hill
  • Friedman, M., The use of ranks to avoid the assumption of normality implicit in the analysis of variance (1937) Journal of the American Statistical Association, 32, pp. 675-701
  • Gai, P., Di Natale, M., Lipari, G., Ferrari, A., Gabellini, C., Marceca, P., A comparison of MPCP and MSRP when sharing resources in the Janus multiple-processor on a chip platform (2003) In Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 189-198. , Toronto, Canada
  • Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W. H. Freeman, New York
  • Han, X., Lam, T., Lee, L., To, I., Wong, P., Deadline scheduling and power management for speed bounded processors (2010) Theoretical Computer Science, 411 (40-42), pp. 3587-3600
  • Heath, S., (2002) Embedded Systems Design, , 2nd edn, Butterworth-Heinemann, Newton, MA
  • Hong, K., Leung, J., On-line scheduling of real-time tasks (1988) R Proceedings of the Real-Time Systems Symposium, pp. 244-250. , In, Huntsville, AL
  • (2011), http://pic.dhe.ibm.com/infocenter/cplexzos/v12r4/index.jsp, Cplex optimizer for z/os; Karp, R., Reducibility among combinatorial problems (1972) Complexity of Computer Computations, pp. 85-103. , In, Miller, R.E., Thatcher, J.W., Bohlinger, J.D., (eds), The IBM Research Symposia Series, Springer, New York
  • Kumar, P., Palani, S., A dynamic voltage scaling with single power supply and varying speed factor for multiprocessor system using genetic algorithm (2012) In International Conference on Pattern Recognition, Informatics and Medical Engineering (PRIME), pp. 342-346. , Salem, Tamilnadu
  • Lam, T., Lee, L., To, I., Wong, P., Competitive non-migratory scheduling for flow time and energy (2008) Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, pp. 256-264. , In, SPAA '08, ACM, New York
  • Liu, C., Layland, J., Scheduling algorithms for multiprogramming in a hard-real-time environment (1973) Journal of the ACM, 20 (1), pp. 46-61
  • Liu, J.W.-S., Lin, K.-J., Shih, W.-K., Yu, A.C.-S., Chun, C., Yao, J., Zhao, W., Algorithms for scheduling imprecise computations (1991) IEEE Computer, 24 (5), pp. 58-68
  • Rizvandi, N.B., Taheri, J., Zomaya, A.Y., Some observations on optimal frequency selection in DVFS-based energy consumption minimization (2011) Journal of Parallel and Distributed Computing, 71 (8), pp. 1154-1164
  • Shih, W., Liu, J., Algorithms for scheduling imprecise computations with timing constraints to minimize maximum error (1995) IEEE Transactions on Computers, 44 (3), pp. 466-471
  • Stankovic, J., Misconceptions about real-time computing: a serious problem for next-generation systems (1988) Computer, 21 (10), pp. 10-19
  • Wilcoxon, F., Individual comparisons by ranking methods (1945) Biometrics, 1, pp. 80-83
  • Zhang, W., Xie, H., Cao, B., Cheng, A., Energy-aware real-time task scheduling for heterogeneous multiprocessors with particle swarm optimization algorithm (2014) Mathematical Problems in Engineering, , 2014
  • Zhang, Y., Guo, R., Power-aware fixed priority scheduling for sporadic tasks in hard real-time systems (2014) Journal of Systems and Softwares, 90, pp. 128-137

Citas:

---------- APA ----------
Méndez-Díaz, I., Orozco, J., Santos, R. & Zabala, P. (2017) . Energy-aware scheduling mandatory/optional tasks in multicore real-time systems. International Transactions in Operational Research, 24(1-2), 173-198.
http://dx.doi.org/10.1111/itor.12328
---------- CHICAGO ----------
Méndez-Díaz, I., Orozco, J., Santos, R., Zabala, P. "Energy-aware scheduling mandatory/optional tasks in multicore real-time systems" . International Transactions in Operational Research 24, no. 1-2 (2017) : 173-198.
http://dx.doi.org/10.1111/itor.12328
---------- MLA ----------
Méndez-Díaz, I., Orozco, J., Santos, R., Zabala, P. "Energy-aware scheduling mandatory/optional tasks in multicore real-time systems" . International Transactions in Operational Research, vol. 24, no. 1-2, 2017, pp. 173-198.
http://dx.doi.org/10.1111/itor.12328
---------- VANCOUVER ----------
Méndez-Díaz, I., Orozco, J., Santos, R., Zabala, P. Energy-aware scheduling mandatory/optional tasks in multicore real-time systems. Int. Trans. Oper. Res. 2017;24(1-2):173-198.
http://dx.doi.org/10.1111/itor.12328