1 Search Results for "Chantem, Thidapat"


Document
Fast and Effective Multiframe-Task Parameter Assignment Via Concave Approximations of Demand

Authors: Bo Peng, Nathan Fisher, and Thidapat Chantem

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)


Abstract
Task parameters in traditional models, e.g., the generalized multiframe (GMF) model, are fixed after task specification time. When tasks whose parameters can be assigned within a range, such as the frame parameters in self-suspending tasks and end-to-end tasks, the optimal offline assignment towards schedulability of such parameters becomes important. The GMF-PA (GMF with parameter adaptation) model proposed in recent work allows frame parameters to be flexibly chosen (offline) in arbitrary-deadline systems. Based on the GMF-PA model, a mixed-integer linear programming (MILP)-based schedulability test was previously given under EDF scheduling for a given assignment of frame parameters in uniprocessor systems. Due to the NP-hardness of the MILP, we present a pseudo-polynomial linear programming (LP)-based heuristic algorithm guided by a concave approximation algorithm to achieve a feasible parameter assignment at a fraction of the time overhead of the MILP-based approach. The concave programming approximation algorithm closely approximates the MILP algorithm, and we prove its speed-up factor is (1+delta)^2 where delta > 0 can be arbitrarily small, with respect to the exact schedulability test of GMF-PA tasks under EDF. Extensive experiments involving self-suspending tasks (an application of the GMF-PA model) reveal that the schedulability ratio is significantly improved compared to other previously proposed polynomial-time approaches in medium and moderately highly loaded systems.

Cite as

Bo Peng, Nathan Fisher, and Thidapat Chantem. Fast and Effective Multiframe-Task Parameter Assignment Via Concave Approximations of Demand. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{peng_et_al:LIPIcs.ECRTS.2019.20,
  author =	{Peng, Bo and Fisher, Nathan and Chantem, Thidapat},
  title =	{{Fast and Effective Multiframe-Task Parameter Assignment Via Concave Approximations of Demand}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{20:1--20:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.20},
  URN =		{urn:nbn:de:0030-drops-107578},
  doi =		{10.4230/LIPIcs.ECRTS.2019.20},
  annote =	{Keywords: generalized multiframe task model (GMF), generalized multiframe task model with parameter adaptation (GMF-PA), self-suspending tasks, uniprocessor scheduling, mixed-integer linear programming, concave approximation, linear programming}
}
  • Refine by Author
  • 1 Chantem, Thidapat
  • 1 Fisher, Nathan
  • 1 Peng, Bo

  • Refine by Classification
  • 1 Computer systems organization → Real-time systems

  • Refine by Keyword
  • 1 concave approximation
  • 1 generalized multiframe task model (GMF)
  • 1 generalized multiframe task model with parameter adaptation (GMF-PA)
  • 1 linear programming
  • 1 mixed-integer linear programming
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail