The hyperbolic schedulability bound for multiprocessor RM scheduling

Hongya Wang; Lih Chyun Shu; Wei Yin; Jie Jin; Jiao Cao

doi:10.1109/RTCSA.2012.29

The hyperbolic schedulability bound for multiprocessor RM scheduling

Hongya Wang
, Lih Chyun Shu
, Wei Yin
, Jie Jin
, Jiao Cao

Department of Accountancy

Research output: Contribution to conference › Paper › peer-review

1 Citation (Scopus)

Abstract

To verify the feasibility of real-time task sets on homogeneous multiprocessor systems, Lopez et al. derived the utilization bound based on Best Fit Decreasing allocation algorithm and Rate-Monotonic scheduling, which coincides with the maximum achievable multiprocessor utilization bound, using Liu & Lyland bound as the uniprocessor schedulability condition. In this paper, a novel feasibility test for the same target problem is developed based on the hyperbolic bound due to Bini et al., instead of the Liu & Layland bound. 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 increase the number of schedulable task sets with little extra overhead.

Original language	English
Pages	124-133
Number of pages	10
DOIs	https://doi.org/10.1109/RTCSA.2012.29
Publication status	Published - 2012
Event	18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012 - Seoul, Korea, Republic of Duration: 2012 Aug 19 → 2012 Aug 22

Other

Other	18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012
Country/Territory	Korea, Republic of
City	Seoul
Period	12-08-19 → 12-08-22

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Hardware and Architecture
Computer Vision and Pattern Recognition

Access to Document

10.1109/RTCSA.2012.29

Cite this

@conference{c786506a9bf546e992c6c9f6f6f2e472,

title = "The hyperbolic schedulability bound for multiprocessor RM scheduling",

abstract = "To verify the feasibility of real-time task sets on homogeneous multiprocessor systems, Lopez et al. derived the utilization bound based on Best Fit Decreasing allocation algorithm and Rate-Monotonic scheduling, which coincides with the maximum achievable multiprocessor utilization bound, using Liu \& Lyland bound as the uniprocessor schedulability condition. In this paper, a novel feasibility test for the same target problem is developed based on the hyperbolic bound due to Bini et al., instead of the Liu \& Layland bound. 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 increase the number of schedulable task sets with little extra overhead.",

author = "Hongya Wang and Shu, \{Lih Chyun\} and Wei Yin and Jie Jin and Jiao Cao",

year = "2012",

doi = "10.1109/RTCSA.2012.29",

language = "English",

pages = "124--133",

note = "18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012 ; Conference date: 19-08-2012 Through 22-08-2012",

}

TY - CONF

T1 - The hyperbolic schedulability bound for multiprocessor RM scheduling

AU - Wang, Hongya

AU - Shu, Lih Chyun

AU - Yin, Wei

AU - Jin, Jie

AU - Cao, Jiao

PY - 2012

Y1 - 2012

N2 - To verify the feasibility of real-time task sets on homogeneous multiprocessor systems, Lopez et al. derived the utilization bound based on Best Fit Decreasing allocation algorithm and Rate-Monotonic scheduling, which coincides with the maximum achievable multiprocessor utilization bound, using Liu & Lyland bound as the uniprocessor schedulability condition. In this paper, a novel feasibility test for the same target problem is developed based on the hyperbolic bound due to Bini et al., instead of the Liu & Layland bound. 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 increase the number of schedulable task sets with little extra overhead.

AB - To verify the feasibility of real-time task sets on homogeneous multiprocessor systems, Lopez et al. derived the utilization bound based on Best Fit Decreasing allocation algorithm and Rate-Monotonic scheduling, which coincides with the maximum achievable multiprocessor utilization bound, using Liu & Lyland bound as the uniprocessor schedulability condition. In this paper, a novel feasibility test for the same target problem is developed based on the hyperbolic bound due to Bini et al., instead of the Liu & Layland bound. 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 increase the number of schedulable task sets with little extra overhead.

UR - https://www.scopus.com/pages/publications/84884726092

UR - https://www.scopus.com/pages/publications/84884726092#tab=citedBy

U2 - 10.1109/RTCSA.2012.29

DO - 10.1109/RTCSA.2012.29

M3 - Paper

AN - SCOPUS:84884726092

SP - 124

EP - 133

T2 - 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012

Y2 - 19 August 2012 through 22 August 2012

ER -

The hyperbolic schedulability bound for multiprocessor RM scheduling

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this