Rethinking Tractability for Schedulability Analysis
Rethinking Tractability for Schedulability Analysis
复制标题
重新思考可调度性分析的易处理性
DOI：
10.1109/rtss59052.2023.00011
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Pontus Ekberg
中科院分区：
文献类型：
--
作者：
Kunal Agrawal;Sanjoy K. Baruah;Pontus Ekberg
已经开发的用于解决计算上难以处理的可扩展性分析问题的算法可以分为两大类：在指数时间内运行的精确算法和提供近似解的多项式时间算法。如果寻求精确的算法，传统上要求这些算法具有伪多项式运行时间。最近，具有多项式运行时间但允许调用ILP求解器的可扩展性分析算法越来越被认为是易处理的。当近似算法是可接受的，一个目标是获得完全多项式时间近似方案，这是“可调”算法，通过让算法的用户为参数设置适当的值，提供多项式时间和指数时间之间的平滑过渡。在本文中，我们采取了一个新的观点之间的联系，各种观点被认为是易于处理的可解释性分析。我们试图确定何时不同形式的易处理的分析是适用于一个特定的问题，什么问题的功能排除它们，并证明我们的研究结果后，具体的调度问题。我们还建议，“伪多项式时间”也许是一个相当广泛的类别，并提出了一个细粒度的分类类的伪多项式时间算法。
Algorithms that have been developed for solving computationally intractable schedulability analysis problems may be classified into two broad categories: exact algorithms that run in exponential time, and polynomial-time algorithms that provide approximate solutions. If exact algorithms are sought, it has traditionally been required that these algorithms have pseudo-polynomial running time. More recently, schedulability analysis algorithms that have polynomial running time but are allowed to make calls to an ILP solver have increasingly been considered tractable. When approximation algorithms are acceptable, an objective has been to obtain Fully Polynomial-Time Approximation Schemes, which are ‘tunable’ algorithms that provide a smooth transition between polynomial time and exponential time by letting the user of the algorithm set an appropriate value for a parameter. In this paper we take a fresh view on the connections between the various perspectives on what is considered to be tractable schedulability analysis. We seek to determine when the different forms of tractable analyses are applicable to a particular problem and what problem features rules them out, and demonstrate our findings upon concrete scheduling problems. We also suggest that ‘pseudo-polynomial time’ is perhaps a rather broad category, and propose a finer-grained classification of the class of pseudo-polynomial time algorithms.
DOI：
10.4230/lipics.ecrts.2021.9
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Sanjoy Baruah;Pontus Ekberg
通讯作者：
Sanjoy Baruah;Pontus Ekberg
实现实时系统中可调度性属性的有效解释
DOI：
--
发表时间：
2023
期刊：
Proceedings of the EuroMicro Conference on Real-Time Systems (ECRTS 2023
影响因子：
--
作者：
Sanjoy Baruah;Pontus Ekberg
通讯作者：
Pontus Ekberg
DOI：
10.1109/rtss55097.2022.00025
发表时间：
2022-12
期刊：
2022 IEEE Real-Time Systems Symposium (RTSS)
影响因子：
--
作者：
Sanjoy Baruah;Abhishek Singh
通讯作者：
Sanjoy Baruah;Abhishek Singh