| Compositional real-time research has become one of the emerging trends in embedded real-time systems due to the increasing scale and complexity of such systems. In the design paradigm, a large system is decomposed into smaller and simpler components, and developed independently. To hide internal complexity from the entire system, components abstract their temporal requirements via interfaces. Resource (or bandwidth) allocation in such systems is done in two steps: system level (global) and component level (local); introducing the idea of hierarchical scheduling. Efficient bandwidth allocation among components is a fundamental problem in compositional real-time systems. State-of-the-art algorithms for bandwidth allocation use either exponential-time or pseudo-polynomial-time techniques for exact allocation, or linear-time, utilization-based techniques which may over-provision bandwidth. In this thesis, we propose research into a third possible approach: parametric approximation algorithms for bandwidth allocation in compositional real-time systems. Our goal is to devise parametric algorithms that allow a component designer to specify an arbitrary level of accuracy for bandwidth computation, and trade increased accuracy for increased computational complexity. For this purpose, we develop a fully-polynomial-time approximation scheme (FPTAS) for allocating bandwidth for sporadic task systems scheduled by earliest-deadline first (EDF) upon an Explicit-Deadline Periodic (EDP) resource. Our algorithm takes, as parameters, the task system and an accuracy parameter epsilon > 0, and returns a bandwidth which is guaranteed to be at most a factor (1 + epsilon) more than the optimal minimum bandwidth required to successfully schedule the task system. Furthermore, the algorithm has time complexity that is polynomial in the number of tasks and 1=epsilon. Via simulations over randomly-generated task systems, we have observed a several orders of magnitude decrease in runtime and a small relative error when comparing our proposed algorithm with the exact algorithm, even for medium-sized values of epsilon (e.g., epsilon ≈ .3). |
