Hyperbolic utilization bounds for rate monotonic scheduling on homogeneous multiprocessors

Hongya Wang, Lih Chyun Shu, Wei Yin, Yingyuan Xiao, Jiao Cao

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

The utilization bounds for partitioned multiprocessor scheduling are a function of task allocation algorithms and the schedulability conditions selected for uniprocessor scheduling algorithms. In this paper, we use rate-monotonic scheduling on each processor and present the lower and upper limits of the utilization bounds for all reasonable task allocation heuristics. Unlike previous work, the hyperbolic bound due to Bini, instead of the Liu & Layland bound, is adopted to do the schedulability test on uniprocessors. We also derive the utilization bounds with respect to the worst fit allocation algorithm and reasonable allocation decreasing heuristics, and the two bounds are found to coincide with the worst and best achievable multiprocessor utilization bounds, respectively. Analytical and experimental results show that the proposed utilization bound performs better than the existing bound under quite a lot of parameter settings, and combining these two bounds together can significantly (up to 3 times) increase the number of schedulable task sets with little extra overhead.

Original languageEnglish
Article number6585233
Pages (from-to)1510-1521
Number of pages12
JournalIEEE Transactions on Parallel and Distributed Systems
Volume25
Issue number6
DOIs
Publication statusPublished - 2014 Jun

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Hyperbolic utilization bounds for rate monotonic scheduling on homogeneous multiprocessors'. Together they form a unique fingerprint.

Cite this