Exploring the interplay between computation and communication in distributed real-time scheduling

Xinfa Hu, Guoliang Xing, Joseph Leung

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

In Distributed Real-Time Systems (DRTSs), computation and communication are the main operations contained in activities. The timeliness of activities depends on that of computations and communications. Furthermore, the timeliness of computations relies on that of communications, and vice versa. Hence, the interplay between computation and communication is inherently a key factor in determining the timeliness of activities. This paper proposes a class of general utility functions under the utility accrual model UAM + to capture and characterize this interplay. Accordingly, a technique called Dynamic Deadline Adjustment (DDA) is proposed to fully explore such interplay and help resource managers proceed toward utility accrual. An online algorithm called IDRSA, which integrates the DDA technique, is developed to perform resource scheduling for DRTSs. IDRSA adopts a two-level scheduling framework to decompose resource scheduling into subprocesses and distribute them to processing nodes so as to reduce the cost of resource scheduling through parallel processing. In addition, IDRSA incorporates a new data structure called testing interval tree to effectively reduce the costs of schedulability tests for tasks and messages. Simulation results reveal the effectiveness of IDRSA, especially when the load of computation is heavy and/or the interplay between computation and communication is tight.

Original languageEnglish (US)
Article number5560641
Pages (from-to)1759-1771
Number of pages13
JournalIEEE Transactions on Computers
Volume60
Issue number12
DOIs
StatePublished - Dec 1 2011

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Distributed real-time system
  • interplay between computation and communication
  • resource scheduling
  • utility accrual model

Fingerprint Dive into the research topics of 'Exploring the interplay between computation and communication in distributed real-time scheduling'. Together they form a unique fingerprint.

Cite this