Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(Slack Reclamation). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Wayne State University

1. Dewan, Farhana. Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems.

Degree: PhD, Computer Science, 2014, Wayne State University

Compositional real-time research has become one of the emerging trends in embedded and real-time systems due to the increasing scale and complexity of such systems. In this design paradigm, a large system is decomposed into smaller and simpler components, each of which abstracts their temporal requirements via interfaces. Such systems are mostly implemented by resource partitions to ensure that the components receive resources according to their interfaces. Potential implementations of a resource partition are via server-based interfaces or demand-based interfaces. In this context, our thesis in this dissertation is as follows: Currently, server-based interfaces ensure strong temporal isolation among components at the cost of resource over-provisioning whereas demand-based interfaces precisely model the resource demand of a component without the guarantee of temporal isolation. For both these models, efficient and effective resource allocation as well as strict temporal isolation among components can be achieved. Specifically, we can obtain efficient and near-optimal bandwidth allocation schemes and admission controllers for periodic resource model and arbitrary demand-based interface respectively. Furthermore, efficient slack reclamation technique can be obtained to allocate unused processing resources at runtime while still enforcing the given interface. To support our thesis, we address efficient resource allocation among components with server-based interfaces by providing fully-polynomial-time approximation schemes (FPTAS) for allocating processing resource to components scheduled by earliest-deadline-first (EDF) or fixed-priority (FP) scheduling algorithm. For enforcing temporal isolation of demand-based interfaces, we provide a parametric approximate admission control algorithm, which has polynomial-time complexity in terms of number of active jobs in the system and the approximation parameter. Finally, to address efficient reclamation of unused processing resources, we give a novel technique to optimally and efficiently determine maximum allowable runtime slack for a component with arbitrary interface, considering active jobs in the system and guaranteeing system schedulability even for worst-case future job arrival scenarios. We expect that these techniques can ultimately be used to minimize the size, weight, and power requirements of real-time and embedded systems by reducing the processing resource requirements of such systems. Advisors/Committee Members: Nathan W. Fisher.

Subjects/Keywords: Admission Control; Approximation Algorithm; Compositional Real-Time Systems; Real-Time Interface; Resource Allocation; Slack Reclamation; Computer Sciences

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Dewan, F. (2014). Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems. (Doctoral Dissertation). Wayne State University. Retrieved from https://digitalcommons.wayne.edu/oa_dissertations/880

Chicago Manual of Style (16th Edition):

Dewan, Farhana. “Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems.” 2014. Doctoral Dissertation, Wayne State University. Accessed December 08, 2019. https://digitalcommons.wayne.edu/oa_dissertations/880.

MLA Handbook (7th Edition):

Dewan, Farhana. “Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems.” 2014. Web. 08 Dec 2019.

Vancouver:

Dewan F. Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems. [Internet] [Doctoral dissertation]. Wayne State University; 2014. [cited 2019 Dec 08]. Available from: https://digitalcommons.wayne.edu/oa_dissertations/880.

Council of Science Editors:

Dewan F. Efficient Allocation And Enforcement Of Interfaces In Compositional Real-Time Systems. [Doctoral Dissertation]. Wayne State University; 2014. Available from: https://digitalcommons.wayne.edu/oa_dissertations/880

2. Renaud-Goud, Paul. Energy-aware scheduling : complexity and algorithms : Ordonnancement sous contrainte d'énergie : complexité et algorithmes.

Degree: Docteur es, Informatique, 2012, Lyon, École normale supérieure

Dans cette thèse, nous nous sommes intéressés à des problèmes d'ordonnancement sous contrainte d'énergie, puisque la réduction de l'énergie est devenue une nécessité, tant sur le plan économique qu'écologique. Dans le premier chapitre, nous exhibons des bornes strictes sur l'énergie d'un algorithme classique qui minimise le temps d'exécution de tâches indépendantes. Dans le second chapitre, nous ordonnançons plusieurs applications chaînées de type « streaming », et nous étudions des problèmes contraignant l'énergie, la période et la latence. Nous effectuons une étude de complexité exhaustive, et décrivons les performances de nouvelles heuristiques. Dans le troisième chapitre, nous étudions le problème de placement de répliques dans un réseau arborescent. Nous nous plaçons dans un cadre dynamique, et nous bornons à minimiser l'énergie. Après une étude de complexité, nous confirmons la qualité de nos heuristiques grâce à un jeu complet de simulations. Dans le quatrième chapitre, nous revenons aux applications « streaming », mais sous forme de graphes série-parallèles, et nous tentons de les placer sur un processeur multi-cœur. La découverte d'un algorithme polynomial sur un problème simple nous permet la conception d'heuristiques sur le problème le plus général dont nous avons établi la NP-complétude. Dans le cinquième chapitre, nous étudions des bornes énergétiques de politiques de routage dans des processeurs multi-cœurs, en comparaison avec le routage classique XY, et développons de nouvheuristiques de routage. Dans le dernier chapitre, nous étudions expérimentalement le placement d'applications sous forme de DAG sur des machines réelles.

In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the…

Advisors/Committee Members: Benoit, Anne (thesis director).

Subjects/Keywords: Minimisation d'énergie; Puissance; Ordonnancement; Complexité; Heuristique; Algorithmes optimaux; Algorithme glouton; Travaux indépendants; Processeurs parallèles; Placement; Applications concurrentes; Plate-forme hétérogène; Partage de ressources; Énergie; Latence; Période; Placement de répliques; Réseau arborescent; Stratégies de mise à jour; Algorithme de programmation dynamique; Graphe série-parallèle; Routage; Multiprocesseur; Manhattan; Chemin unique; Chemin multiples; DAG; Energy minimization; Power; Scheduling; Complexity; Makespan; Heuristics; Optimal algorithms; Greedy algorithm; Independent jobs; Parallel processors; Mapping; Concurrent streaming applications; Heterogeneous platforms; Resource sharing; Energy; Latency; Period; Workflow; Replica placement; Tree networks; Update strategies; Dynamic programming algorithms; Series-parallel graph; Routing; Chip multiprocesseur; Manhattan; Single path; Multiple paths; Slack reclamation; DAG

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Renaud-Goud, P. (2012). Energy-aware scheduling : complexity and algorithms : Ordonnancement sous contrainte d'énergie : complexité et algorithmes. (Doctoral Dissertation). Lyon, École normale supérieure. Retrieved from http://www.theses.fr/2012ENSL0727

Chicago Manual of Style (16th Edition):

Renaud-Goud, Paul. “Energy-aware scheduling : complexity and algorithms : Ordonnancement sous contrainte d'énergie : complexité et algorithmes.” 2012. Doctoral Dissertation, Lyon, École normale supérieure. Accessed December 08, 2019. http://www.theses.fr/2012ENSL0727.

MLA Handbook (7th Edition):

Renaud-Goud, Paul. “Energy-aware scheduling : complexity and algorithms : Ordonnancement sous contrainte d'énergie : complexité et algorithmes.” 2012. Web. 08 Dec 2019.

Vancouver:

Renaud-Goud P. Energy-aware scheduling : complexity and algorithms : Ordonnancement sous contrainte d'énergie : complexité et algorithmes. [Internet] [Doctoral dissertation]. Lyon, École normale supérieure; 2012. [cited 2019 Dec 08]. Available from: http://www.theses.fr/2012ENSL0727.

Council of Science Editors:

Renaud-Goud P. Energy-aware scheduling : complexity and algorithms : Ordonnancement sous contrainte d'énergie : complexité et algorithmes. [Doctoral Dissertation]. Lyon, École normale supérieure; 2012. Available from: http://www.theses.fr/2012ENSL0727

.