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

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

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.