License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2019.20
URN: urn:nbn:de:0030-drops-107578
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10757/
Go to the corresponding LIPIcs Volume Portal

Peng, Bo ; Fisher, Nathan ; Chantem, Thidapat

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

pdf-format:
LIPIcs-ECRTS-2019-20.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{peng_et_al:LIPIcs:2019:10757,
  author =	{Bo Peng and Nathan Fisher and Thidapat Chantem},
  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 =	{Sophie Quinton},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10757},
  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 sc}
}

Keywords: generalized multiframe task model (GMF), generalized multiframe task model with parameter adaptation (GMF-PA), self-suspending tasks, uniprocessor sc
Collection: 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)
Issue Date: 2019
Date of publication: 02.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI