Abstract
We propose an off-line scheduling heuristics which, from a given software application graph and a given multiprocessor architecture (homogeneous and fully connected), produces a static multiprocessor schedule that optimizes three criteria: its length (crucial for real-time systems), its reliability (crucial for dependable systems), and its power consumption (crucial for autonomous systems). Our tricriteria scheduling heuristics, TSH, uses the active replication of the operations and the data-dependencies to increase the reliability, and uses dynamic voltage and frequency scaling to lower the power consumption.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baleani, M., Ferrari, A., Mangeruca, L., Peri, M., Pezzini, S., Sangiovanni-Vincentelli, A.: Fault-tolerant platforms for automotive safety-critical applications. In: International Conference on Compilers, Architectures and Synthesis for Embedded Systems, CASES 2003, San Jose (CA), USA. ACM, New-York (2003)
Benoit, A., Dufossé, F., Girault, A., Robert, Y.: Reliability and performance optimization of pipelined real-time systems. In: International Conference on Parallel Processing, ICPP 2010, San Diego (CA), USA (September 2010)
Burd, T.D., Brodersen, R.W.: Energy efficient CMOS micro-processor design. In: Hawaii International Conference on System Sciences, HICSS 1995, Honolulu (HI), USA. IEEE, Los Alamitos (1995)
Dogan, A., Özgüner, F.: Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing. IEEE Trans. Parallel and Distributed Systems 13(3), 308–323 (2002)
Elnozahy, E., Kistler, M., Rajamony, R.: Energy-efficient server clusters. In: Workshop on Power-Aware Computing Systems, WPACS 2002, Cambridge (MA), USA, pp. 179–196 (February 2002)
Girault, A., Kalla, H.: A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate. IEEE Trans. Dependable Secure Comput. 6(4), 241–254 (2009)
Girault, A., Saule, E., Trystram, D.: Reliability versus performance for critical applications. J. of Parallel and Distributed Computing 69(3), 326–336 (2009)
Grandpierre, T., Lavarenne, C., Sorel, Y.: Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors. In: International Workshop on Hardware/Software Co-Design, CODES 1999, Rome, Italy. ACM, New York (1999)
Knight, J.C., Leveson, N.G.: An experimental evaluation of the assumption of independence in multi-version programming. IEEE Trans. Software Engin. 12(1), 96–109 (1986)
Leung, J.Y.-T. (ed.): Handbook of Scheduling. Algorithms: Models, and Performance Analysis. Chapman & Hall/CRC Press (2004)
Lloyd, D., Lipow, M.: Reliability: Management, Methods, and Mathematics. ch.9. Prentice-Hall, Englewood Cliffs (1962)
Melhem, R., Mossé, D., Elnozahy, E.N.: The interplay of power management and fault recovery in real-time systems. IEEE Trans. Comput. 53(2), 217–231 (2004)
Pering, T., Burd, T.D., Brodersen, R.W.: The simulation and evaluation of dynamic voltage scaling algorithms. In: International Symposium on Low Power Electronics and Design, ISLPED 1998, Monterey (CA), USA, pp. 76–81. ACM, New York (August 1998)
Pop, P., Poulsen, K., Izosimov, V.: Scheduling and voltage scaling for energy/reliability trade-offs in fault-tolerant time-triggered embedded systems. In: International Conference on Hardware-Software Codesign and System Synthesis, CODES+ISSS 2007, Salzburg, Austria. ACM, New York (October 2007)
Shatz, S.M., Wang, J.-P.: Models and algorithms for reliability-oriented task-allocation in redundant distributed-computer systems. IEEE Trans. Reliability 38(1), 16–26 (1989)
Souyris, J., Pavec, E.L., Himbert, G., Jégu, V., Borios, G., Heckmann, R.: Computing the worst case execution time of an avionics program by abstract interpretation. In: International Workshop on Worst-case Execution Time, WCET 2005, Mallorca, Spain, pp. 21–24 (July 2005)
T’kindt, V., Billaut, J.-C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Heidelberg (2006)
Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckmann, R., Mueller, F., Puaut, I., Puschner, P., Staschulat, J., Stenström, P.: The determination of worst-case execution times — overview of the methods and survey of tools. ACM Trans. Embedd. Comput. Syst. 7(3) (April 2008)
Zhu, D., Melhem, R., Mossé, D.: The effects of energy management on reliability in real-time embedded systems. In: International Conference on Computer Aided Design, ICCAD 2004, San Jose (CA), USA, pp. 35–40 (November 2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Assayad, I., Girault, A., Kalla, H. (2011). Tradeoff Exploration between Reliability, Power Consumption, and Execution Time. In: Flammini, F., Bologna, S., Vittorini, V. (eds) Computer Safety, Reliability, and Security. SAFECOMP 2011. Lecture Notes in Computer Science, vol 6894. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24270-0_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-24270-0_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24269-4
Online ISBN: 978-3-642-24270-0
eBook Packages: Computer ScienceComputer Science (R0)