uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A Capacity Augmentation Bound for Real-Time Constrained-Deadline Parallel Tasks Under GEDF
Northeastern Univ, Sch Comp Sci & Engn, Shenyang 110004, Liaoning, Peoples R China;Hong Kong Polytech Univ, Dept Comp, Hong Kong, Hong Kong, Peoples R China.
Hong Kong Polytech Univ, Dept Comp, Hong Kong, Hong Kong, Peoples R China.
Hong Kong Polytech Univ, Dept Comp, Hong Kong, Hong Kong, Peoples R China.
Northeastern Univ, Sch Comp Sci & Engn, Shenyang 110004, Liaoning, Peoples R China.
Vise andre og tillknytning
2018 (engelsk)Inngår i: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, ISSN 0278-0070, E-ISSN 1937-4151, Vol. 37, nr 11, s. 2200-2211Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

Capacity augmentation bound is a widely used quantitative metric in theoretical studies of schedulability analysis for directed acyclic graph (DAG) parallel real-time tasks, which not only quantifies the suboptimality of the scheduling algorithms, but also serves as a simple linear-time schedulability test. Earlier studies on capacity augmentation bounds of the sporadic DAG task model were either restricted to a single DAG task or a set of tasks with implicit deadlines. In this paper, we consider parallel tasks with constrained deadlines under global earliest deadline first policy. We first show that it is impossible to obtain a constant bound for our problem setting, and derive both lower and upper bounds of the capacity augmentation bound as a function with respect to the maximum ratio of task period to deadline. Our upper bound is at most 1.47 times larger than the optimal one. We conduct experiments to compare the acceptance ratio of our capacity augmentation bound with the existing schedulability test also having linear-time complexity. The results show that our capacity augmentation bound significantly outperforms the existing linear-time schedulability test under different parameter settings.

sted, utgiver, år, opplag, sider
2018. Vol. 37, nr 11, s. 2200-2211
Emneord [en]
Capacity augmentation bound, directed acyclic graph (DAG), global earliest deadline first (GEDF), parallel tasks, real-time scheduling, schedulability analysis
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-370013DOI: 10.1109/TCAD.2018.2857362ISI: 000447854500003OAI: oai:DiVA.org:uu-370013DiVA, id: diva2:1275695
Konferanse
Embedded Syst Week (ESWEEK) / Int Conf on Compilers, Architecture, and Synthesis for Embedded Syst (CASES) / Int Conf on Hardware/Software Codesign and Syst Synthesis (CODES+ISSS) / ACM SIGBED Int Conf on Embedded Software (EMSOFT), MAR 27-APR 03, 2018, Torino, ITALY
Tilgjengelig fra: 2019-01-07 Laget: 2019-01-07 Sist oppdatert: 2019-01-07bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Wang, Yi

Søk i DiVA

Av forfatter/redaktør
Guo, ZhishanWang, Yi
Av organisasjonen
I samme tidsskrift
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 11 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf