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

安全关键系统在部署前应正确验证;可验证性分析是验证此类系统的时序属性的过程。本专题将探讨如何使用非线性规划（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.