混合关键性系统寿命优化的任务调度算法
|
摘要
为延长混合关键性系统的设备寿命,考虑瞬时性、永久性2种故障并采取容错方案满足安全需求,提出一种两阶段解决方案。利用动态电压频率调整技术为每个任务确定运行频率,确保热循环对设备寿命的损害最小。使用重执行技术,在可靠性约束和可调度性约束下对设备寿命进行分析,构建一个多目标非线性规划问题,从而得到最优解。仿真结果表明,与RAND、MFPR、MRPF、DPAS 4种算法相比,该算法在保证系统可调度与可靠性的前提下,可使系统寿命最多延长47%。
In order to extend the life of equipment for mixed-critical systems,considering instantaneous and permanent errors and taking fault-tolerant solutions to meet safety requirements,a two-stage solution is proposed. The Dynamic Voltage Frequency Scaling( DVFS) technique is used to determine the operating frequency for each task,ensuring that thermal cycling minimizes damage to equipment life. By using the re-execution technology,the equipment life is analyzed under the constraint of reliability constraint and schedulability,and a multi-objective nonlinear programming problem is constructed to obtain the optimal solution. Simulation results show that compared with the four algorithms such as RAND、MFPR、MRPF and DPAS,this algorithm can extend the life of the system by up to 47% under the premise of ensuring system scheduling and reliability.
In order to extend the life of equipment for mixed-critical systems,considering instantaneous and permanent errors and taking fault-tolerant solutions to meet safety requirements,a two-stage solution is proposed. The Dynamic Voltage Frequency Scaling( DVFS) technique is used to determine the operating frequency for each task,ensuring that thermal cycling minimizes damage to equipment life. By using the re-execution technology,the equipment life is analyzed under the constraint of reliability constraint and schedulability,and a multi-objective nonlinear programming problem is constructed to obtain the optimal solution. Simulation results show that compared with the four algorithms such as RAND、MFPR、MRPF and DPAS,this algorithm can extend the life of the system by up to 47% under the premise of ensuring system scheduling and reliability.
引文
[1]HINCHEY M,COYLE L.Evolving critical systems:a research agenda for computer-based systems[C]//Proceedings of the 17th IEEE International Conference and Workshops on Engineering of Computer Based Systems.Washington D.C.,USA:IEEE Press,2010:430-435.
[2]BARUAH S,LI H,STOUGIE L.Towards the design of certifiable mixed-criticality systems[C]//Proceedings of the 16th IEEE Real-time and Embedded Technology and Applications Symposium.Washington D.C.,USA:IEEEPress,2010:13-22.
[3]MASRUR A.A probabilistic scheduling framework for mixed-criticality systems[C]//Proceedings of ACM/EDAC/IEEE Design Automation Conference.Washington D.C.,USA:IEEE Press,2016:1-6.
[4]VESTAL S.Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[C]//Proceedings of the 28th IEEE International Real-time Systems Symposium.Washington D.C.,USA:IEEE Press,2007:239-243.
[5]LI X,ADVE S V,BOSE P,et al.Online estimation of architectural vulnerability factor for soft errors[C]//Proceedings of the 35th Annual International Symposium on Computer Architecture.Washington D.C.,USA:IEEE Press,2008:341-352.
[6]SRIDHARAN V,KAELI D R.Using hardware vulnerability factors to enhance AVF analysis[J].ACMSIGARCH Computer Architecture New s,2010,38(3):461-472.
[7]DUQUE L A R,DIAZ J M M,YANG C.Improving M PSoC reliability through adapting runtime task schedule based on time-correlated fault behavior[C]//Proceedings of Design,Automation&Test in Europe Conference&Exhibition.San Jose,USA:EDAConsortium,2015:818-823.
[8]AL-BAYATI Z,CAPLAN J,MEYER B H,et al.A fourmode model for efficient fault-tolerant mixed-criticality systems[C]//Proceedings of Design,Automation&Test in Europe Conference&Exhibition.San Jose,USA:EDAConsortium,2016:97-102.
[9]HENKEL J,PAGANI S,KHDR H,et al.Towards performance and reliability-efficient computing in the dark silicon era[C]//Proceedings of Design,Automation&Test in Europe Conference&Exhibition.San Jose,USA:EDA Consortium,2016:1-6.
[10]AMROUCH H,SANTEN V M,EBI T,et al.Towards interdependencies of aging mechanisms[C]//Proceedings of International Conference on ComputerAided Design.Washington D.C.,USA:IEEE Press,2014:478-485.
[11]HUANG L,YUAN F,XU Q.On task allocation and scheduling for lifetime extension of platform-based M PSoC designs[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(12):2088-2099.
[12]CHOU C L,MARCULESCU R.FARM:fault-aware resource management in NoC-based multiprocessor platforms[C]//Proceedings of Design,Automation&Test in Europe Conference&Exhibition.San Jose,USA:EDA Consortium,2011:1-6.
[13]HUANG J,BLECH J O,RAABE A,et al.Analysis and optimization of fault-tolerant task scheduling on multiprocessor embedded systems[C]//Proceedings of the International Conference on Hardw are/Softw are Codesign and System Synthesis.Washington D.C.,USA:IEEE Press,2011:247-256.
[14]谷传才,关楠,于金铭,等.多处理器混合关键性系统中的划分调度策略[J].软件学报,2014,25(2):284-297.
[15]ZHAO B,AYDIN H,ZHU D.On maximizing reliability of real-time embedded applications under hard energy constraint[J].IEEE Transactions on Industrial Informatics,2010,6(3):316-328.
[16]ZHOU J,WEI T,CHEN M,et al.Thermal-aware task scheduling for energy minimization in heterogeneous real-time M PSoC systems[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2016,35(8):1269-1282.
[17]王科特,王力生,廖新考.基于多核处理器的K线程低能耗的任务调度优化算法[J].计算机科学,2015,42(2):18-23.
[18]DAMPER R I.Failure mechanisms and fault models for M OS testing[EB/OL].[2017-10-18].https://eprints.soton.ac.uk/256249/.
[19]JOHNSON L A.Software considerations in airborne systems and equipment certification[EB/OL].[2017-10-18].http://sesam.smart-lab.se/IG_Prgsak/Publikat/ED12B_DO178B.pdf.
[20]LIU D,SPASIC J,CHEN G,et al.EDF-VD scheduling of mixed-criticality systems w ith degraded quality guarantees[C]//Proceedings of IEEE Real-time Systems Symposium.Washington D.C.,USA:IEEEPress,2016:35-46.
[21]ALI I,SEO J H,KIM K H.A dynamic power-aware scheduling of mixed-criticality real-time systems[C]//Proceedings of IEEE International Conference on Computer and Information Technology;Ubiquitous Computing and Communications;Dependable,Autonomic and Secure Computing;Pervasive Intelligence and Computing.Washington D.C.,USA:IEEE Press,2015:438-445.
[2]BARUAH S,LI H,STOUGIE L.Towards the design of certifiable mixed-criticality systems[C]//Proceedings of the 16th IEEE Real-time and Embedded Technology and Applications Symposium.Washington D.C.,USA:IEEEPress,2010:13-22.
[3]MASRUR A.A probabilistic scheduling framework for mixed-criticality systems[C]//Proceedings of ACM/EDAC/IEEE Design Automation Conference.Washington D.C.,USA:IEEE Press,2016:1-6.
[4]VESTAL S.Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[C]//Proceedings of the 28th IEEE International Real-time Systems Symposium.Washington D.C.,USA:IEEE Press,2007:239-243.
[5]LI X,ADVE S V,BOSE P,et al.Online estimation of architectural vulnerability factor for soft errors[C]//Proceedings of the 35th Annual International Symposium on Computer Architecture.Washington D.C.,USA:IEEE Press,2008:341-352.
[6]SRIDHARAN V,KAELI D R.Using hardware vulnerability factors to enhance AVF analysis[J].ACMSIGARCH Computer Architecture New s,2010,38(3):461-472.
[7]DUQUE L A R,DIAZ J M M,YANG C.Improving M PSoC reliability through adapting runtime task schedule based on time-correlated fault behavior[C]//Proceedings of Design,Automation&Test in Europe Conference&Exhibition.San Jose,USA:EDAConsortium,2015:818-823.
[8]AL-BAYATI Z,CAPLAN J,MEYER B H,et al.A fourmode model for efficient fault-tolerant mixed-criticality systems[C]//Proceedings of Design,Automation&Test in Europe Conference&Exhibition.San Jose,USA:EDAConsortium,2016:97-102.
[9]HENKEL J,PAGANI S,KHDR H,et al.Towards performance and reliability-efficient computing in the dark silicon era[C]//Proceedings of Design,Automation&Test in Europe Conference&Exhibition.San Jose,USA:EDA Consortium,2016:1-6.
[10]AMROUCH H,SANTEN V M,EBI T,et al.Towards interdependencies of aging mechanisms[C]//Proceedings of International Conference on ComputerAided Design.Washington D.C.,USA:IEEE Press,2014:478-485.
[11]HUANG L,YUAN F,XU Q.On task allocation and scheduling for lifetime extension of platform-based M PSoC designs[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(12):2088-2099.
[12]CHOU C L,MARCULESCU R.FARM:fault-aware resource management in NoC-based multiprocessor platforms[C]//Proceedings of Design,Automation&Test in Europe Conference&Exhibition.San Jose,USA:EDA Consortium,2011:1-6.
[13]HUANG J,BLECH J O,RAABE A,et al.Analysis and optimization of fault-tolerant task scheduling on multiprocessor embedded systems[C]//Proceedings of the International Conference on Hardw are/Softw are Codesign and System Synthesis.Washington D.C.,USA:IEEE Press,2011:247-256.
[14]谷传才,关楠,于金铭,等.多处理器混合关键性系统中的划分调度策略[J].软件学报,2014,25(2):284-297.
[15]ZHAO B,AYDIN H,ZHU D.On maximizing reliability of real-time embedded applications under hard energy constraint[J].IEEE Transactions on Industrial Informatics,2010,6(3):316-328.
[16]ZHOU J,WEI T,CHEN M,et al.Thermal-aware task scheduling for energy minimization in heterogeneous real-time M PSoC systems[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2016,35(8):1269-1282.
[17]王科特,王力生,廖新考.基于多核处理器的K线程低能耗的任务调度优化算法[J].计算机科学,2015,42(2):18-23.
[18]DAMPER R I.Failure mechanisms and fault models for M OS testing[EB/OL].[2017-10-18].https://eprints.soton.ac.uk/256249/.
[19]JOHNSON L A.Software considerations in airborne systems and equipment certification[EB/OL].[2017-10-18].http://sesam.smart-lab.se/IG_Prgsak/Publikat/ED12B_DO178B.pdf.
[20]LIU D,SPASIC J,CHEN G,et al.EDF-VD scheduling of mixed-criticality systems w ith degraded quality guarantees[C]//Proceedings of IEEE Real-time Systems Symposium.Washington D.C.,USA:IEEEPress,2016:35-46.
[21]ALI I,SEO J H,KIM K H.A dynamic power-aware scheduling of mixed-criticality real-time systems[C]//Proceedings of IEEE International Conference on Computer and Information Technology;Ubiquitous Computing and Communications;Dependable,Autonomic and Secure Computing;Pervasive Intelligence and Computing.Washington D.C.,USA:IEEE Press,2015:438-445.