Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization
International audience In this paper, we study an efficient approximate integer linear programming formulation of the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in [8] a theoretical framework t...
Main Authors: | , |
---|---|
Other Authors: | , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2008
|
Subjects: | |
Online Access: | https://inria.hal.science/inria-00637210 https://inria.hal.science/inria-00637210/document https://inria.hal.science/inria-00637210/file/Efficient_Method_for_Periodic_Task.pdf https://doi.org/10.1007/978-3-540-85097-7_41 |
id |
ftuniversailles:oai:HAL:inria-00637210v1 |
---|---|
record_format |
openpolar |
spelling |
ftuniversailles:oai:HAL:inria-00637210v1 2024-06-23T07:54:46+00:00 Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization Deschinkel, Karine Touati, Sid Parallélisme, Réseaux, Systèmes, Modélisation (PRISM) Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS) St. John's, Newfoundland and Labrador, Canada 2008-08-21 https://inria.hal.science/inria-00637210 https://inria.hal.science/inria-00637210/document https://inria.hal.science/inria-00637210/file/Efficient_Method_for_Periodic_Task.pdf https://doi.org/10.1007/978-3-540-85097-7_41 en eng HAL CCSD Springer info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-540-85097-7_41 inria-00637210 https://inria.hal.science/inria-00637210 https://inria.hal.science/inria-00637210/document https://inria.hal.science/inria-00637210/file/Efficient_Method_for_Periodic_Task.pdf doi:10.1007/978-3-540-85097-7_41 info:eu-repo/semantics/OpenAccess Second International Conference, COCOA 2008 https://inria.hal.science/inria-00637210 Second International Conference, COCOA 2008, Aug 2008, St. John's, Newfoundland and Labrador, Canada. pp.438-447, ⟨10.1007/978-3-540-85097-7_41⟩ http://www.springerlink.com/content/1560012151250kh5/ [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] info:eu-repo/semantics/conferenceObject Conference papers 2008 ftuniversailles https://doi.org/10.1007/978-3-540-85097-7_41 2024-05-24T03:23:11Z International audience In this paper, we study an efficient approximate integer linear programming formulation of the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in [8] a theoretical framework that allows an optimal optimization of periodic storage requirement in a periodic schedule. This problem is used to optimise processor register usage in embedded systems. Our storage optimisation problem being NP-complete [7], solving an exact integer linear programming formulation as proposed in [8] is too expensive in practice. In this article, we give an efficient approximate model that allows fast resolution times while providing nearly optimal results. Our solution has been implemented and included inside a compiler for embedded processors. Conference Object Newfoundland Université de Versailles Saint-Quentin-en-Yvelines: HAL-UVSQ Newfoundland Canada 438 447 Berlin, Heidelberg |
institution |
Open Polar |
collection |
Université de Versailles Saint-Quentin-en-Yvelines: HAL-UVSQ |
op_collection_id |
ftuniversailles |
language |
English |
topic |
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] |
spellingShingle |
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] Deschinkel, Karine Touati, Sid Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization |
topic_facet |
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] |
description |
International audience In this paper, we study an efficient approximate integer linear programming formulation of the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in [8] a theoretical framework that allows an optimal optimization of periodic storage requirement in a periodic schedule. This problem is used to optimise processor register usage in embedded systems. Our storage optimisation problem being NP-complete [7], solving an exact integer linear programming formulation as proposed in [8] is too expensive in practice. In this article, we give an efficient approximate model that allows fast resolution times while providing nearly optimal results. Our solution has been implemented and included inside a compiler for embedded processors. |
author2 |
Parallélisme, Réseaux, Systèmes, Modélisation (PRISM) Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS) |
format |
Conference Object |
author |
Deschinkel, Karine Touati, Sid |
author_facet |
Deschinkel, Karine Touati, Sid |
author_sort |
Deschinkel, Karine |
title |
Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization |
title_short |
Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization |
title_full |
Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization |
title_fullStr |
Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization |
title_full_unstemmed |
Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization |
title_sort |
efficient method for periodic task scheduling with storage requirement minimization |
publisher |
HAL CCSD |
publishDate |
2008 |
url |
https://inria.hal.science/inria-00637210 https://inria.hal.science/inria-00637210/document https://inria.hal.science/inria-00637210/file/Efficient_Method_for_Periodic_Task.pdf https://doi.org/10.1007/978-3-540-85097-7_41 |
op_coverage |
St. John's, Newfoundland and Labrador, Canada |
geographic |
Newfoundland Canada |
geographic_facet |
Newfoundland Canada |
genre |
Newfoundland |
genre_facet |
Newfoundland |
op_source |
Second International Conference, COCOA 2008 https://inria.hal.science/inria-00637210 Second International Conference, COCOA 2008, Aug 2008, St. John's, Newfoundland and Labrador, Canada. pp.438-447, ⟨10.1007/978-3-540-85097-7_41⟩ http://www.springerlink.com/content/1560012151250kh5/ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-540-85097-7_41 inria-00637210 https://inria.hal.science/inria-00637210 https://inria.hal.science/inria-00637210/document https://inria.hal.science/inria-00637210/file/Efficient_Method_for_Periodic_Task.pdf doi:10.1007/978-3-540-85097-7_41 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1007/978-3-540-85097-7_41 |
container_start_page |
438 |
op_container_end_page |
447 |
op_publisher_place |
Berlin, Heidelberg |
_version_ |
1802647030914351104 |