Dynamic voltage scaling under EDF revisited
Identifieur interne : 001D74 ( Istex/Corpus ); précédent : 001D73; suivant : 001D75Dynamic voltage scaling under EDF revisited
Auteurs : Bruno Gaujal ; Nicolas NavetSource :
- Real-Time Systems [ 0922-6443 ] ; 2007-10-01.
English descriptors
Abstract
Abstract: Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.
Url:
DOI: 10.1007/s11241-007-9029-y
Links to Exploration step
ISTEX:7FF63E63888E0357D43CC0368590E27BB1341736Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Dynamic voltage scaling under EDF revisited</title><author><name sortKey="Gaujal, Bruno" sort="Gaujal, Bruno" uniqKey="Gaujal B" first="Bruno" last="Gaujal">Bruno Gaujal</name><affiliation><mods:affiliation>INRIA and ID-IMAG Laboratory, 51 avenue Jean Kuntzmann, 38330, Montbonnot, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: bruno.gaujal@imag.fr</mods:affiliation></affiliation></author><author><name sortKey="Navet, Nicolas" sort="Navet, Nicolas" uniqKey="Navet N" first="Nicolas" last="Navet">Nicolas Navet</name><affiliation><mods:affiliation>INRIA-LORIA, Campus Scientifique, BP-139, 54506, Vandoeuvre-lès-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: nicolas.navet@loria.fr</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7FF63E63888E0357D43CC0368590E27BB1341736</idno><date when="2007" year="2007">2007</date><idno type="doi">10.1007/s11241-007-9029-y</idno><idno type="url">https://api.istex.fr/ark:/67375/VQC-87HWSTGW-H/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">001D74</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001D74</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Dynamic voltage scaling under EDF revisited</title><author><name sortKey="Gaujal, Bruno" sort="Gaujal, Bruno" uniqKey="Gaujal B" first="Bruno" last="Gaujal">Bruno Gaujal</name><affiliation><mods:affiliation>INRIA and ID-IMAG Laboratory, 51 avenue Jean Kuntzmann, 38330, Montbonnot, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: bruno.gaujal@imag.fr</mods:affiliation></affiliation></author><author><name sortKey="Navet, Nicolas" sort="Navet, Nicolas" uniqKey="Navet N" first="Nicolas" last="Navet">Nicolas Navet</name><affiliation><mods:affiliation>INRIA-LORIA, Campus Scientifique, BP-139, 54506, Vandoeuvre-lès-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: nicolas.navet@loria.fr</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Real-Time Systems</title><title level="j" type="sub">The International Journal of Time-Critical Computing Systems</title><title level="j" type="abbrev">Real-Time Syst</title><idno type="ISSN">0922-6443</idno><idno type="eISSN">1573-1383</idno><imprint><publisher>Springer US; http://www.springer-ny.com</publisher><pubPlace>Boston</pubPlace><date type="published" when="2007-10-01">2007-10-01</date><biblScope unit="volume">37</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="77">77</biblScope><biblScope unit="page" to="97">97</biblScope></imprint><idno type="ISSN">0922-6443</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0922-6443</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Complexity</term><term>Dynamic voltage scaling</term><term>Low-power design</term><term>Real-time systems</term><term>Scheduling</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.</div></front></TEI><istex><corpusName>springer-journals</corpusName><author><json:item><name>Bruno Gaujal</name><affiliations><json:string>INRIA and ID-IMAG Laboratory, 51 avenue Jean Kuntzmann, 38330, Montbonnot, France</json:string><json:string>E-mail: bruno.gaujal@imag.fr</json:string></affiliations></json:item><json:item><name>Nicolas Navet</name><affiliations><json:string>INRIA-LORIA, Campus Scientifique, BP-139, 54506, Vandoeuvre-lès-Nancy, France</json:string><json:string>E-mail: nicolas.navet@loria.fr</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Real-time systems</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Low-power design</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Scheduling</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Complexity</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Dynamic voltage scaling</value></json:item></subject><articleId><json:string>9029</json:string><json:string>s11241-007-9029-y</json:string></articleId><arkIstex>ark:/67375/VQC-87HWSTGW-H</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.</abstract><qualityIndicators><score>9.028</score><pdfWordCount>8135</pdfWordCount><pdfCharCount>40665</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>21</pdfPageCount><pdfPageSize>439.37 x 666.142 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>169</abstractWordCount><abstractCharCount>1056</abstractCharCount><keywordCount>5</keywordCount></qualityIndicators><title>Dynamic voltage scaling under EDF revisited</title><genre><json:string>research-article</json:string></genre><host><title>Real-Time Systems</title><language><json:string>unknown</json:string></language><publicationDate>2007</publicationDate><copyrightDate>2007</copyrightDate><issn><json:string>0922-6443</json:string></issn><eissn><json:string>1573-1383</json:string></eissn><journalId><json:string>11241</json:string></journalId><volume>37</volume><issue>1</issue><pages><first>77</first><last>97</last></pages><genre><json:string>journal</json:string></genre><subject><json:item><value>Control Engineering</value></json:item><json:item><value>Performance and Reliability</value></json:item><json:item><value>Special Purpose and Application-Based Systems</value></json:item><json:item><value>Communications Engineering, Networks</value></json:item><json:item><value>Computer Systems Organization and Communication Networks</value></json:item></subject></host><ark><json:string>ark:/67375/VQC-87HWSTGW-H</json:string></ark><publicationDate>2007</publicationDate><copyrightDate>2007</copyrightDate><doi><json:string>10.1007/s11241-007-9029-y</json:string></doi><id>7FF63E63888E0357D43CC0368590E27BB1341736</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-87HWSTGW-H/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-87HWSTGW-H/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/VQC-87HWSTGW-H/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Dynamic voltage scaling under EDF revisited</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher scheme="https://scientific-publisher.data.istex.fr">Springer US; http://www.springer-ny.com</publisher><pubPlace>Boston</pubPlace><availability><licence><p>Springer Science+Business Media, LLC, 2007</p></licence><p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</p></availability><date>2007</date></publicationStmt><notesStmt><note type="research-article" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</note><note type="journal" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Dynamic voltage scaling under EDF revisited</title><author xml:id="author-0000" corresp="yes"><persName><forename type="first">Bruno</forename><surname>Gaujal</surname></persName><email>bruno.gaujal@imag.fr</email><note type="biography">Bruno Gaujal is a research director at INRIA Rhone-Alpes since 2003 where he is the leader of the group on large scale networks. He has held several positions in INRIA Sophia-Antipolis, Loria and ENS-Lyon before. His main interest are performance evaluation and control of discrete event dynamic systems.</note><affiliation>Bruno Gaujal is a research director at INRIA Rhone-Alpes since 2003 where he is the leader of the group on large scale networks. He has held several positions in INRIA Sophia-Antipolis, Loria and ENS-Lyon before. His main interest are performance evaluation and control of discrete event dynamic systems.</affiliation><affiliation>INRIA and ID-IMAG Laboratory, 51 avenue Jean Kuntzmann, 38330, Montbonnot, France</affiliation></author><author xml:id="author-0001"><persName><forename type="first">Nicolas</forename><surname>Navet</surname></persName><email>nicolas.navet@loria.fr</email><note type="biography">Nicolas Navet received the M.S. in Computer Science from the University of Berlin (Germany) in 1994 and the PhD in Computer Science from the University of Nancy in 1999. Before joining the INRIA (LORIA Lab.) in November 2000, he was research scientist at Gemplus Software. His research interests include scheduling theory, probabilistic risk evaluation and computational intelligence with applications to real-time systems. More information at url http://www.loria.fr/~nnavet .</note><affiliation>Nicolas Navet received the M.S. in Computer Science from the University of Berlin (Germany) in 1994 and the PhD in Computer Science from the University of Nancy in 1999. Before joining the INRIA (LORIA Lab.) in November 2000, he was research scientist at Gemplus Software. His research interests include scheduling theory, probabilistic risk evaluation and computational intelligence with applications to real-time systems. More information at url http://www.loria.fr/~nnavet .</affiliation><affiliation>INRIA-LORIA, Campus Scientifique, BP-139, 54506, Vandoeuvre-lès-Nancy, France</affiliation></author><idno type="istex">7FF63E63888E0357D43CC0368590E27BB1341736</idno><idno type="ark">ark:/67375/VQC-87HWSTGW-H</idno><idno type="DOI">10.1007/s11241-007-9029-y</idno><idno type="article-id">9029</idno><idno type="article-id">s11241-007-9029-y</idno></analytic><monogr><title level="j">Real-Time Systems</title><title level="j" type="sub">The International Journal of Time-Critical Computing Systems</title><title level="j" type="abbrev">Real-Time Syst</title><idno type="pISSN">0922-6443</idno><idno type="eISSN">1573-1383</idno><idno type="journal-ID">true</idno><idno type="issue-article-count">3</idno><idno type="volume-issue-count">3</idno><imprint><publisher>Springer US; http://www.springer-ny.com</publisher><pubPlace>Boston</pubPlace><date type="published" when="2007-10-01"></date><biblScope unit="volume">37</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="77">77</biblScope><biblScope unit="page" to="97">97</biblScope></imprint></monogr></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2007</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.</p></abstract><textClass xml:lang="en"><keywords scheme="keyword"><list><head>Keywords</head><item><term>Real-time systems</term></item><item><term>Low-power design</term></item><item><term>Scheduling</term></item><item><term>Complexity</term></item><item><term>Dynamic voltage scaling</term></item></list></keywords></textClass><textClass><keywords scheme="Journal Subject"><list><head>Computer Science</head><item><term>Control Engineering</term></item><item><term>Performance and Reliability</term></item><item><term>Special Purpose and Application-Based Systems</term></item><item><term>Communications Engineering, Networks</term></item><item><term>Computer Systems Organization and Communication Networks</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2007-10-01">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-87HWSTGW-H/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-journals not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer US</PublisherName><PublisherLocation>Boston</PublisherLocation><PublisherURL>http://www.springer-ny.com</PublisherURL></PublisherInfo><Journal OutputMedium="All"><JournalInfo JournalProductType="ArchiveJournal" NumberingStyle="Unnumbered"><JournalID>11241</JournalID><JournalPrintISSN>0922-6443</JournalPrintISSN><JournalElectronicISSN>1573-1383</JournalElectronicISSN><JournalTitle>Real-Time Systems</JournalTitle><JournalSubTitle>The International Journal of Time-Critical Computing Systems</JournalSubTitle><JournalAbbreviatedTitle>Real-Time Syst</JournalAbbreviatedTitle><JournalSubjectGroup><JournalSubject Type="Primary">Computer Science</JournalSubject><JournalSubject Type="Secondary">Control Engineering</JournalSubject><JournalSubject Type="Secondary">Performance and Reliability</JournalSubject><JournalSubject Type="Secondary">Special Purpose and Application-Based Systems </JournalSubject><JournalSubject Type="Secondary">Communications Engineering, Networks</JournalSubject><JournalSubject Type="Secondary">Computer Systems Organization and Communication Networks</JournalSubject></JournalSubjectGroup></JournalInfo><Volume OutputMedium="All"><VolumeInfo TocLevels="0" VolumeType="Regular"><VolumeIDStart>37</VolumeIDStart><VolumeIDEnd>37</VolumeIDEnd><VolumeIssueCount>3</VolumeIssueCount></VolumeInfo><Issue IssueType="Regular" OutputMedium="All"><IssueInfo TocLevels="0"><IssueIDStart>1</IssueIDStart><IssueIDEnd>1</IssueIDEnd><IssueArticleCount>3</IssueArticleCount><IssueHistory><OnlineDate><Year>2007</Year><Month>8</Month><Day>6</Day></OnlineDate><PrintDate><Year>2007</Year><Month>8</Month><Day>6</Day></PrintDate><CoverDate><Year>2007</Year><Month>10</Month></CoverDate></IssueHistory><IssueCopyright><CopyrightHolderName>Springer Science+Business Media, LLC</CopyrightHolderName><CopyrightYear>2007</CopyrightYear></IssueCopyright></IssueInfo><Article ID="s11241-007-9029-y" OutputMedium="All"><ArticleInfo ArticleType="OriginalPaper" ContainsESM="No" Language="En" NumberingStyle="Unnumbered" TocLevels="0"><ArticleID>9029</ArticleID><ArticleDOI>10.1007/s11241-007-9029-y</ArticleDOI><ArticleSequenceNumber>3</ArticleSequenceNumber><ArticleTitle Language="En">Dynamic voltage scaling under EDF revisited</ArticleTitle><ArticleFirstPage>77</ArticleFirstPage><ArticleLastPage>97</ArticleLastPage><ArticleHistory><RegistrationDate><Year>2007</Year><Month>6</Month><Day>11</Day></RegistrationDate><OnlineDate><Year>2007</Year><Month>8</Month><Day>3</Day></OnlineDate></ArticleHistory><ArticleCopyright><CopyrightHolderName>Springer Science+Business Media, LLC</CopyrightHolderName><CopyrightYear>2007</CopyrightYear></ArticleCopyright><ArticleGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ArticleGrants></ArticleInfo><ArticleHeader><AuthorGroup><Author AffiliationIDS="Aff1" CorrespondingAffiliationID="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Bruno</GivenName><FamilyName>Gaujal</FamilyName></AuthorName><Contact><Email>bruno.gaujal@imag.fr</Email></Contact><Biography><FormalPara RenderingStyle="Style1"><Heading>Bruno Gaujal</Heading><Para><Figure Category="Standard" Float="No" ID="Figa"><MediaObject><ImageObject Color="BlackWhite" Format="JPEG" Rendition="HTML" Type="Halftone" FileRef="MediaObjects/11241_2007_9029_Figa_HTML.jpg"></ImageObject></MediaObject></Figure> is a research director at INRIA Rhone-Alpes since 2003 where he is the leader of the group on large scale networks. He has held several positions in INRIA Sophia-Antipolis, Loria and ENS-Lyon before. His main interest are performance evaluation and control of discrete event dynamic systems.
</Para></FormalPara></Biography></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Nicolas</GivenName><FamilyName>Navet</FamilyName></AuthorName><Contact><Email>nicolas.navet@loria.fr</Email></Contact><Biography><FormalPara RenderingStyle="Style1"><Heading>Nicolas Navet</Heading><Para><Figure Category="Standard" Float="No" ID="Figb"><MediaObject><ImageObject Color="BlackWhite" Format="JPEG" Rendition="HTML" Type="Halftone" FileRef="MediaObjects/11241_2007_9029_Figb_HTML.jpg"></ImageObject></MediaObject></Figure> received the M.S. in Computer Science from the University of Berlin (Germany) in 1994 and the PhD in Computer Science from the University of Nancy in 1999. Before joining the INRIA (LORIA Lab.) in November 2000, he was research scientist at Gemplus Software. His research interests include scheduling theory, probabilistic risk evaluation and computational intelligence with applications to real-time systems. More information at url <ExternalRef><RefSource>http://www.loria.fr/~nnavet</RefSource><RefTarget Address="http://www.loria.fr/~nnavet" TargetType="URL"></RefTarget></ExternalRef>.
</Para></FormalPara></Biography></Author><Affiliation ID="Aff1"><OrgName>INRIA and ID-IMAG Laboratory</OrgName><OrgAddress><Street>51 avenue Jean Kuntzmann</Street><Postcode>38330</Postcode><City>Montbonnot</City><Country Code="FR">France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>INRIA-LORIA</OrgName><OrgAddress><Street>Campus Scientifique</Street><Postbox>BP-139</Postbox><Postcode>54506</Postcode><City>Vandoeuvre-lès-Nancy</City><Country Code="FR">France</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>
Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.
</Para></Abstract><KeywordGroup Language="En"><Heading>Keywords</Heading><Keyword>Real-time systems</Keyword><Keyword>Low-power design</Keyword><Keyword>Scheduling</Keyword><Keyword>Complexity</Keyword><Keyword>Dynamic voltage scaling</Keyword></KeywordGroup></ArticleHeader><NoBody></NoBody></Article></Issue></Volume></Journal></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Dynamic voltage scaling under EDF revisited</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Dynamic voltage scaling under EDF revisited</title></titleInfo><name type="personal" displayLabel="corresp"><namePart type="given">Bruno</namePart><namePart type="family">Gaujal</namePart><affiliation>INRIA and ID-IMAG Laboratory, 51 avenue Jean Kuntzmann, 38330, Montbonnot, France</affiliation><affiliation>E-mail: bruno.gaujal@imag.fr</affiliation><role><roleTerm type="text">author</roleTerm></role><description>Bruno Gaujal is a research director at INRIA Rhone-Alpes since 2003 where he is the leader of the group on large scale networks. He has held several positions in INRIA Sophia-Antipolis, Loria and ENS-Lyon before. His main interest are performance evaluation and control of discrete event dynamic systems.</description></name><name type="personal"><namePart type="given">Nicolas</namePart><namePart type="family">Navet</namePart><affiliation>INRIA-LORIA, Campus Scientifique, BP-139, 54506, Vandoeuvre-lès-Nancy, France</affiliation><affiliation>E-mail: nicolas.navet@loria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role><description>Nicolas Navet received the M.S. in Computer Science from the University of Berlin (Germany) in 1994 and the PhD in Computer Science from the University of Nancy in 1999. Before joining the INRIA (LORIA Lab.) in November 2000, he was research scientist at Gemplus Software. His research interests include scheduling theory, probabilistic risk evaluation and computational intelligence with applications to real-time systems. More information at url http://www.loria.fr/~nnavet .</description></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</genre><originInfo><publisher>Springer US; http://www.springer-ny.com</publisher><place><placeTerm type="text">Boston</placeTerm></place><dateIssued encoding="w3cdtf">2007-10-01</dateIssued><copyrightDate encoding="w3cdtf">2007</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.</abstract><subject lang="en"><genre>Keywords</genre><topic>Real-time systems</topic><topic>Low-power design</topic><topic>Scheduling</topic><topic>Complexity</topic><topic>Dynamic voltage scaling</topic></subject><relatedItem type="host"><titleInfo><title>Real-Time Systems</title><subTitle>The International Journal of Time-Critical Computing Systems</subTitle></titleInfo><titleInfo type="abbreviated"><title>Real-Time Syst</title></titleInfo><genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre><originInfo><publisher>Springer</publisher><dateIssued encoding="w3cdtf">2007-08-06</dateIssued><copyrightDate encoding="w3cdtf">2007</copyrightDate></originInfo><subject><genre>Computer Science</genre><topic>Control Engineering</topic><topic>Performance and Reliability</topic><topic>Special Purpose and Application-Based Systems</topic><topic>Communications Engineering, Networks</topic><topic>Computer Systems Organization and Communication Networks</topic></subject><identifier type="ISSN">0922-6443</identifier><identifier type="eISSN">1573-1383</identifier><identifier type="JournalID">11241</identifier><identifier type="IssueArticleCount">3</identifier><identifier type="VolumeIssueCount">3</identifier><part><date>2007</date><detail type="volume"><number>37</number><caption>vol.</caption></detail><detail type="issue"><number>1</number><caption>no.</caption></detail><extent unit="pages"><start>77</start><end>97</end></extent></part><recordInfo><recordOrigin>Springer Science+Business Media, LLC, 2007</recordOrigin></recordInfo></relatedItem><identifier type="istex">7FF63E63888E0357D43CC0368590E27BB1341736</identifier><identifier type="ark">ark:/67375/VQC-87HWSTGW-H</identifier><identifier type="DOI">10.1007/s11241-007-9029-y</identifier><identifier type="ArticleID">9029</identifier><identifier type="ArticleID">s11241-007-9029-y</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer Science+Business Media, LLC, 2007</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</recordContentSource><recordOrigin>Springer Science+Business Media, LLC, 2007</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-87HWSTGW-H/record.json</uri></json:item></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001D74 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001D74 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:7FF63E63888E0357D43CC0368590E27BB1341736
|texte= Dynamic voltage scaling under EDF revisited
}}
| This area was generated with Dilib version V0.6.33. |  |