An FPTAS for Interface Selection in the Periodic Resource Model

Abstract : The periodic resource model of Shin and Lee [19] provides a °exible, simple framework for design- ing compositional real-time systems. Each compo- nent in the periodic resource model has an inter- face which speci¯es the period and capacity of the resource used to schedule the component. Unfortu- nately, the best-known exact algorithms for determin- ing the interface parameters for a component in the periodic resource model potentially require exponential or pseudo-polynomial time. In this paper, we obtain an FPTAS for the problem of selecting an interface period given a capacity-determination algorithm. We also apply our approach to obtain an FPTAS for the problem of selecting both a period and capacity for components consisting of sporadic task systems. Our algorithms obtain interface parameters with interface bandwidth at most (1 + ²) times the optimal for any ² > 0.
Type de document :
Communication dans un congrès
Laurent George and Maryline Chetto andMikael Sjodin. 17th International Conference on Real-Time and Network Systems, Oct 2009, Paris, France. pp.127-136, 2009
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00441996
Contributeur : Alain Monteil <>
Soumis le : jeudi 17 décembre 2009 - 17:55:58
Dernière modification le : mardi 22 décembre 2009 - 15:34:50
Document(s) archivé(s) le : jeudi 17 juin 2010 - 22:00:46

Fichier

DesignOptimization_Fisher.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00441996, version 1

Collections

Citation

Nathan Fisher. An FPTAS for Interface Selection in the Periodic Resource Model. Laurent George and Maryline Chetto andMikael Sjodin. 17th International Conference on Real-Time and Network Systems, Oct 2009, Paris, France. pp.127-136, 2009. 〈inria-00441996〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

67