uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Transforming real-time task graphs to improve schedulability
Univ Notre Dame, Notre Dame, IN 46556 USA.
Hong Kong Polytech Univ, Hong Kong, Hong Kong, Peoples R China.
Northeastern Univ, Shenyang, Peoples R China.
Northeastern Univ, Shenyang, Peoples R China.
Show others and affiliations
2016 (English)In: Proc. 22nd International Conference on Embedded and Real-Time Computing Systems and Applications, IEEE Computer Society, 2016, 29-38 p.Conference paper (Refereed)
Abstract [en]

Real-time task graphs are used to describe complex real-time systems with non-cyclic timing behaviors. The workload of such systems are typically bursty, which may degrade their schedulability even with sufficient resource in the long term. In this paper, we propose to use task graph transformation to improve system schedulability. The idea is to insert artificial delays to the release times of certain vertices of a task graph to get a new graph with a smoother workload, while still meeting the timing constraints of the original task graph. Delaying the release time of a vertex may smoothen the workload of some paths of the task graph, but at the same time make the workload of other paths even more bursty. We developed efficient techniques to search for an appropriate release time delay for each vertex. Experiments with randomly generated task systems show that the proposed transformation method can make a significant number of task systems that was originally unschedulable to become schedulable, and the transformation procedure is very efficient and can easily handle large-scale task graph systems in very short computation time.

Place, publisher, year, edition, pages
IEEE Computer Society, 2016. 29-38 p.
Series
IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, ISSN 1533-2306
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:uu:diva-310107DOI: 10.1109/RTCSA.2016.13ISI: 000387085600004ISBN: 9781509024797OAI: oai:DiVA.org:uu-310107DiVA: diva2:1054953
Conference
RTCSA 2016, August 17–19, Daegu, South Korea
Projects
UPMARC
Available from: 2016-10-03 Created: 2016-12-09 Last updated: 2016-12-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Guan, NanYi, Wang
By organisation
Computer Systems
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 33 hits
ReferencesLink to record
Permanent link

Direct link