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 Dec 1
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	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

Fingerprint Dive into the research topics of 'The hyperbolic schedulability bound for multiprocessor RM scheduling'. Together they form a unique fingerprint.

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 Lih-Chyun Shu and Wei Yin and Jie Jin and Jiao Cao",

year = "2012",

month = dec,

day = "1",

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",

}

The hyperbolic schedulability bound for multiprocessor RM scheduling. / Wang, Hongya; Shu, Lih-Chyun; Yin, Wei; Jin, Jie; Cao, Jiao.

2012. 124-133 Paper presented at 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2012, Seoul, Korea, Republic of.

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

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/12/1

Y1 - 2012/12/1

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 - http://www.scopus.com/inward/record.url?scp=84884726092&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84884726092&partnerID=8YFLogxK

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 -