Parametric analysis is a powerful tool for designing modern embedded systems, because it permits to explore the space of design parameters, and to check the robustness of the system with respect to variations of some uncontrollable variable. In this paper, we address the problem of parametric schedulability analysis of distributed real-time systems scheduled by fixed priority. In particular, we propose two different approaches to parametric analysis: the first one is a novel technique based on classical schedulability analysis, whereas the second approach is based on model checking of Parametric Timed Automata (PTA). The proposed analytic method extends existing sensitivity analysis for single processors to the case of a distributed system, supporting preemptive and non-preemptive scheduling, jitters and unconstrained deadlines. Parametric Timed Automata are used to model all possible behaviours of a distributed system, and therefore it is a necessary and sufficient analysis. Both techniques have been implemented in two software tools, and they have been compared with classical holistic analysis on two meaningful test cases. The results show that the analytic method provides results similar to classical holistic analysis in a very efficient way, whereas the PTA approach is slower but covers the entire space of solutions.
Also based on PTA is the approach proposed by @cite_18 . Their work is based on the Inverse Method @cite_6 and it is very general because it permits to perform analysis on any system parameter. However, this generality can be paid in terms of complexity.
@cite_18 @cite_6
2057087699 1510609119
We present the first monotone randomized polynomial-time approximation scheme (PTAS) for minimizing the makespan of parallel related machines ( @math ), the paradigmatic problem in single-parameter algorithmic mechanism design. This result immediately gives a polynomial-time, truthful (in expectation) mechanism whose approximation guarantee attains the best-possible one for all polynomial-time algorithms (assuming @math ). Our algorithmic techniques are flexible and also yield a monotone deterministic quasi-PTAS for @math and a monotone randomized PTAS for max-min scheduling on related machines. An EPTAS (efficient PTAS) is an approximation scheme where e does not appear in the exponent of n, i.e., the running time is f(e)nc. We use parameterized complexity to investigate the possibility of improving the known approximation schemes for certain geometric problems to EPTAS. Answering an open question of Alber and Fiala [2], we show that Maximum Independent Set is W[1]-complete for the intersection graphs of unit disks and axis-parallel unit squares in the plane. A standard consequence of this result is that the @math time PTAS of [11] for Maximum Independent Set on unit disk graphs cannot be improved to an EPTAS. Similar results are obtained for the problem of covering points with squares.