Efficient Feasibility Analysis for Graph-Based Real-Time Task Systems

Jinghao Sun, Rongxiao Shi, Kexuan Wang, Nan Guan, Zhishan Guo

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

The demand bound function (DBF) is a powerful abstraction to analyze the feasibility/schedulability of real-time tasks. Computing the DBF for expressive system models, such as graph-based tasks, is typically very expensive. In this article, we develop new techniques to drastically improve the DBF computation efficiency for a representative graph-based task model, digraph real-time tasks (DRT). First, we apply the well-known quick processor-demand analysis (QPA) technique, which was originally designed for simple sporadic tasks, to the analysis of DRT. The challenge is that existing analysis techniques of DRT have to compute the demand for each possible interval size, which is contradictory to the idea of QPA that aims to aggressively skip the computation for most interval sizes. To solve this problem, we develop a novel integer linear programming (ILP)-based analysis technique for DRT, to which we can apply QPA to significantly improve the analysis efficiency. Second, we improve the task utilization computation (a major step in DBF computation for DRT) efficiency from pseudo-polynomial complexity to polynomial complexity. Experiments show that our approach can improve the analysis efficiency by dozens of times.

Original languageEnglish
Article number9211560
Pages (from-to)3385-3397
Number of pages13
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume39
Issue number11
DOIs
Publication statusPublished - Nov 2020

Keywords

  • Demand bound function (DBF)
  • digraph real-time tasks (DRT)
  • feasibility
  • linear program (LP)

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this