CNS Core: Small: Schedulability Analysis of Safety-Critical Real-Time Systems: Beyond Pseudo-polynomial Time Algorithms

CNS 核心：小型：安全关键实时系统的可调度性分析：超越伪多项式时间算法

基本信息

批准号：
2141256
负责人：
Sanjoy Baruah
金额：
$ 49.98万
依托单位：
Washington University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-07-15 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2141256&HistoricalAwards=false
关键词：
CNS Core Small Schedulability Analysis

项目摘要

Safety-critical systems should be validated correct prior to their deployment; schedulability analysis is the process of validating timing properties of such systems. This project will investigate the use of Integer Linear Program (ILP) solvers for developing schedulability analysis algorithms that are efficient enough for use in practice. It will do so by identifying the relationships between the inherent computational complexity of fundamental problems that arise in real-time schedulability analysis and their suitability for representation as ILPs that are efficiently solvable by ILP-solvers. A general methodology will be developed for determining whether particular schedulability analysis problems can be efficiently represented as such ILPs; this methodology will be applied to common schedulability analysis problems; and ILP-based algorithms will be developed and evaluated for those problems that are determined to be efficiently representable in this manner.There have been vast improvements in the performance of ILP-solvers in recent years. Hence, successful completion of this project will greatly expand the class of real-time systems upon which it is computationally feasible to do schedulability analysis. This will enable the development of safer safety-critical systems, such as airplanes, cars, and medical devices, which are able to offer more advanced features than is currently possible. Project findings will be disseminated via participation in conference workshops and panels and the organization of cross-disciplinary events with industrial participation. New teaching materials incorporating such findings will be developed for graduate courses at Washington University and shared with interested instructors elsewhere. Undergraduate research based upon this project will be integrated into Washington University's well-established summer REU program, which incorporates extensive research engagement with technical and social activities for participants.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

安全 - 关键系统应在部署之前正确验证；可调度性分析是验证此类系统的定时属性的过程。该项目将调查使用整数线性程序（ILP）求解器的使用，以开发足够有效使用的计划分析算法。它将通过确定在实时可调度性分析中出现的基本问题的固有计算复杂性与它们作为ILP可通过ILP-Solvers有效解决的ILP的适用性之间的固有计算复杂性之间的关系。将开发一种一般方法来确定是否可以有效地表示特定的可调查性分析问题；该方法将应用于常见的可调查性分析问题；对于那些确定以这种方式有效表示的问题，将开发和评估基于ILP的算法。近年来，ILP-Solvers的性能有了很大的改善。因此，该项目的成功完成将大大扩展实时系统类别的计算可行性以进行计划分析。这将使更安全的安全至关重要系统（例如飞机，汽车和医疗设备）的开发，这些系统能够提供比目前更多的高级功能。项目调查结果将通过参加会议研讨会和小组，以及与工业参与的跨学科活动的组织进行传播。结合此类发现的新教材将为华盛顿大学的研究生课程开发，并与其他地方有兴趣的讲师共享。基于该项目的本科研究将纳入华盛顿大学良好的夏季REU计划，该计划将广泛的研究参与与参与者的技术和社交活动结合在一起。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和广泛影响的评估来获得支持的。

项目成果

期刊论文数量（20）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The Computational Complexity of Feasibility Analysis for Conditional DAG Tasks

DOI：
10.1145/3606342
发表时间：
2023-07
期刊：
ACM Transactions on Parallel Computing
影响因子：
1.6
作者：
Sanjoy Baruah;A. Marchetti-Spaccamela
通讯作者：
Sanjoy Baruah;A. Marchetti-Spaccamela

Certificates of Real-Time Schedulability. Proceedings of the Workshop on Explainability of Real-Time Systems and their Analysis (ERSA), December 2022

实时可调度性证书。

DOI：
发表时间：
2022
期刊：
Proceedings of the Workshop on Explainability of Real-Time Systems and their Analysis (ERSA
影响因子：
0
作者：
Baruah, Sanjoy;Ekberg, Pontus
通讯作者：
Ekberg, Pontus

Multi-Model Specifications and their Application to Classification Systems

DOI：
10.1145/3575757.3575760
发表时间：
2023-06
期刊：
Proceedings of the 31st International Conference on Real-Time Networks and Systems
影响因子：
0
作者：
Alan Burns;Sanjoy Baruah
通讯作者：
Alan Burns;Sanjoy Baruah

Towards Efficient Explainability of Schedulability Properties in Real-Time Systems

实现实时系统中可调度性属性的有效解释