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

安全关键系统在部署前应进行正确验证；可调度性分析是验证这类系统的时序特性的过程。该项目将研究使用整数线性规划（ILP）求解器来开发可调度性分析算法，这些算法在实践中足够有效。它将通过确定实时可调度性分析中出现的基本问题的固有计算复杂性与ilp求解器有效解决的ilp表示的适用性之间的关系来实现这一目标。将制定一种一般方法，以确定特定的可调度性分析问题是否可以有效地表示为这种ilp；该方法将应用于常见的可调度性分析问题；和基于ilp的算法将开发和评估那些被确定以这种方式有效表示的问题。近年来，ilp求解器的性能有了很大的改进。因此，这个项目的成功完成将极大地扩展实时系统的类别，在此基础上进行可调度性分析在计算上是可行的。这将有助于开发更安全的安全关键系统，如飞机、汽车和医疗设备，这些系统能够提供比目前可能的更先进的功能。项目结果将通过参加会议讲习班和小组以及组织有工业界参与的跨学科活动来传播。将为华盛顿大学的研究生课程开发包含这些发现的新教材，并与其他地方感兴趣的教师分享。基于该项目的本科生研究将被整合到华盛顿大学完善的夏季REU项目中，该项目将广泛的研究参与与参与者的技术和社会活动相结合。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.