Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs

Che-Wei Chang; Jian-Jia Chen; Waqaas Munawar; Tei-Wei Kuo; Heiko Falk

doi:10.1145/2380356.2380384

Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs

Che-Wei Chang
, Jian-Jia Chen
, Waqaas Munawar
, Tei-Wei Kuo
, Heiko Falk

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

5 Citations (Scopus)

Abstract

This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2 - 2/M+1)-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, MediaBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm.

Original language	English
Title of host publication	Proceedings of the 12th International Conference on Embedded Software
Publisher	Association for Computing Machinery
Pages	153-162
ISBN (Print)	9781450314251
DOIs	https://doi.org/10.1145/2380356.2380384
Publication status	Published - Oct 2012
Externally published	Yes
Event	12th International Conference on Embedded Software (EMSOFT 2012) Co-located with 8th Embedded Systems Week (ESWEEK 2012) - Tampere Hall, Tampere, Finland Duration: 7 Oct 2012 → 12 Oct 2012 https://esweek.org/archive/esweek2012/ESWEEK2012Program.pdf https://esweek.org/archive/esweek2012/emsoft/

Publication series

Name	EMSOFT - Proceedings of the ... ACM International Conference on Embedded Software, Co-located with ESWEEK

Conference

Conference	12th International Conference on Embedded Software (EMSOFT 2012) Co-located with 8th Embedded Systems Week (ESWEEK 2012)
Abbreviated title	EMSOFT 2012
Place	Finland
City	Tampere
Period	7/10/12 → 12/10/12
Internet address	https://esweek.org/archive/esweek2012/ESWEEK2012Program.pdf https://esweek.org/archive/esweek2012/emsoft/

Research Keywords

Approximation algorithms
Multiprocessor partitioned scheduling
Real-time systems
Shared SRAM

Access Output

10.1145/2380356.2380384

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chang, C.-W., Chen, J.-J., Munawar, W., Kuo, T.-W., & Falk, H. (2012). Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs. In Proceedings of the 12th International Conference on Embedded Software (pp. 153-162). (EMSOFT - Proceedings of the ... ACM International Conference on Embedded Software, Co-located with ESWEEK). Association for Computing Machinery. https://doi.org/10.1145/2380356.2380384

Chang, Che-Wei ; Chen, Jian-Jia ; Munawar, Waqaas et al. / Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs. Proceedings of the 12th International Conference on Embedded Software. Association for Computing Machinery, 2012. pp. 153-162 (EMSOFT - Proceedings of the ... ACM International Conference on Embedded Software, Co-located with ESWEEK).

@inproceedings{676e1ee45cf348daaca24640c41226c0,

title = "Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs",

abstract = "This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2 - 2/M+1)-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, MediaBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm. ",

keywords = "Approximation algorithms, Multiprocessor partitioned scheduling, Real-time systems, Shared SRAM",

author = "Che-Wei Chang and Jian-Jia Chen and Waqaas Munawar and Tei-Wei Kuo and Heiko Falk",

year = "2012",

month = oct,

doi = "10.1145/2380356.2380384",

language = "English",

isbn = "9781450314251",

series = "EMSOFT - Proceedings of the ... ACM International Conference on Embedded Software, Co-located with ESWEEK",

publisher = "Association for Computing Machinery",

pages = "153--162",

booktitle = "Proceedings of the 12th International Conference on Embedded Software",

address = "United States",

note = "12th International Conference on Embedded Software (EMSOFT 2012)<br/>Co-located with 8th Embedded Systems Week (ESWEEK 2012), EMSOFT 2012 ; Conference date: 07-10-2012 Through 12-10-2012",

url = "https://esweek.org/archive/esweek2012/ESWEEK2012Program.pdf, https://esweek.org/archive/esweek2012/emsoft/",

}

Chang, C-W, Chen, J-J, Munawar, W, Kuo, T-W & Falk, H 2012, Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs. in Proceedings of the 12th International Conference on Embedded Software. EMSOFT - Proceedings of the ... ACM International Conference on Embedded Software, Co-located with ESWEEK, Association for Computing Machinery, pp. 153-162, 12th International Conference on Embedded Software (EMSOFT 2012)
Co-located with 8th Embedded Systems Week (ESWEEK 2012), Tampere, Finland, 7/10/12. https://doi.org/10.1145/2380356.2380384

Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs. / Chang, Che-Wei; Chen, Jian-Jia; Munawar, Waqaas et al.
Proceedings of the 12th International Conference on Embedded Software. Association for Computing Machinery, 2012. p. 153-162 (EMSOFT - Proceedings of the ... ACM International Conference on Embedded Software, Co-located with ESWEEK).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs

AU - Chang, Che-Wei

AU - Chen, Jian-Jia

AU - Munawar, Waqaas

AU - Kuo, Tei-Wei

AU - Falk, Heiko

PY - 2012/10

Y1 - 2012/10

N2 - This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2 - 2/M+1)-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, MediaBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm.

AB - This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2 - 2/M+1)-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, MediaBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm.

KW - Approximation algorithms

KW - Multiprocessor partitioned scheduling

KW - Real-time systems

KW - Shared SRAM

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84869014229&origin=recordpage

U2 - 10.1145/2380356.2380384

DO - 10.1145/2380356.2380384

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781450314251

T3 - EMSOFT - Proceedings of the ... ACM International Conference on Embedded Software, Co-located with ESWEEK

SP - 153

EP - 162

BT - Proceedings of the 12th International Conference on Embedded Software

PB - Association for Computing Machinery

T2 - 12th International Conference on Embedded Software (EMSOFT 2012)<br/>Co-located with 8th Embedded Systems Week (ESWEEK 2012)

Y2 - 7 October 2012 through 12 October 2012

ER -

Chang CW, Chen JJ, Munawar W, Kuo TW, Falk H. Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs. In Proceedings of the 12th International Conference on Embedded Software. Association for Computing Machinery. 2012. p. 153-162. (EMSOFT - Proceedings of the ... ACM International Conference on Embedded Software, Co-located with ESWEEK). doi: 10.1145/2380356.2380384

Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared SRAMs

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this