Monotonicity and Run-Time Scheduling

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

44 Downloads (Pure)

Abstract

Modern embedded multi-processors can execute several stream processing applications concurrently. Typically, these applications are partitioned into tasks that communicate over buffers together forming a task graph. The fact that these applications are started and stopped by the user combined with the knowledge that not all applications are necessarily completely characterised makes it attractive to use run-time scheduling. We define and characterise a class of budget schedulers that by construction bound the interference from other applications. Furthermore, we will show that the worst-case effects of these schedulers can be included in dataflow process networks. The execution of the resulting dataflow process network is shown to result in tight and conservative bounds on the end-to-end temporal behaviour of the execution of the task graph on a cycle-true simulator. Given that the inter-task synchronisation of the application allows for a dataflow model that is functionally deterministic, this enables exploration of various buffer capacities and scheduler settings at a high level of abstraction.
Original languageUndefined
Title of host publicationBerkeley EECS Annual Research Symposium, BEARS 2010
Place of PublicationBerkeley, CA, USA
PublisherCenter for Hybrid and Embedded Software Systems, Chess
Pages-
Number of pages1
ISBN (Print)not assigned
Publication statusPublished - 11 Feb 2010

Publication series

Name
PublisherCenter for Hybrid and Embedded Software Systems, Chess

Keywords

  • METIS-277818
  • EWI-19113
  • IR-75579

Cite this

Wiggers, M. H., Bekooij, M. J. G., & Smit, G. J. M. (2010). Monotonicity and Run-Time Scheduling. In Berkeley EECS Annual Research Symposium, BEARS 2010 (pp. -). Berkeley, CA, USA: Center for Hybrid and Embedded Software Systems, Chess.
Wiggers, M.H. ; Bekooij, Marco Jan Gerrit ; Smit, Gerardus Johannes Maria. / Monotonicity and Run-Time Scheduling. Berkeley EECS Annual Research Symposium, BEARS 2010. Berkeley, CA, USA : Center for Hybrid and Embedded Software Systems, Chess, 2010. pp. -
@inproceedings{571f0559053b4919a6ba8d4e827829a2,
title = "Monotonicity and Run-Time Scheduling",
abstract = "Modern embedded multi-processors can execute several stream processing applications concurrently. Typically, these applications are partitioned into tasks that communicate over buffers together forming a task graph. The fact that these applications are started and stopped by the user combined with the knowledge that not all applications are necessarily completely characterised makes it attractive to use run-time scheduling. We define and characterise a class of budget schedulers that by construction bound the interference from other applications. Furthermore, we will show that the worst-case effects of these schedulers can be included in dataflow process networks. The execution of the resulting dataflow process network is shown to result in tight and conservative bounds on the end-to-end temporal behaviour of the execution of the task graph on a cycle-true simulator. Given that the inter-task synchronisation of the application allows for a dataflow model that is functionally deterministic, this enables exploration of various buffer capacities and scheduler settings at a high level of abstraction.",
keywords = "METIS-277818, EWI-19113, IR-75579",
author = "M.H. Wiggers and Bekooij, {Marco Jan Gerrit} and Smit, {Gerardus Johannes Maria}",
year = "2010",
month = "2",
day = "11",
language = "Undefined",
isbn = "not assigned",
publisher = "Center for Hybrid and Embedded Software Systems, Chess",
pages = "--",
booktitle = "Berkeley EECS Annual Research Symposium, BEARS 2010",

}

Wiggers, MH, Bekooij, MJG & Smit, GJM 2010, Monotonicity and Run-Time Scheduling. in Berkeley EECS Annual Research Symposium, BEARS 2010. Center for Hybrid and Embedded Software Systems, Chess, Berkeley, CA, USA, pp. -.

Monotonicity and Run-Time Scheduling. / Wiggers, M.H.; Bekooij, Marco Jan Gerrit; Smit, Gerardus Johannes Maria.

Berkeley EECS Annual Research Symposium, BEARS 2010. Berkeley, CA, USA : Center for Hybrid and Embedded Software Systems, Chess, 2010. p. -.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

TY - GEN

T1 - Monotonicity and Run-Time Scheduling

AU - Wiggers, M.H.

AU - Bekooij, Marco Jan Gerrit

AU - Smit, Gerardus Johannes Maria

PY - 2010/2/11

Y1 - 2010/2/11

N2 - Modern embedded multi-processors can execute several stream processing applications concurrently. Typically, these applications are partitioned into tasks that communicate over buffers together forming a task graph. The fact that these applications are started and stopped by the user combined with the knowledge that not all applications are necessarily completely characterised makes it attractive to use run-time scheduling. We define and characterise a class of budget schedulers that by construction bound the interference from other applications. Furthermore, we will show that the worst-case effects of these schedulers can be included in dataflow process networks. The execution of the resulting dataflow process network is shown to result in tight and conservative bounds on the end-to-end temporal behaviour of the execution of the task graph on a cycle-true simulator. Given that the inter-task synchronisation of the application allows for a dataflow model that is functionally deterministic, this enables exploration of various buffer capacities and scheduler settings at a high level of abstraction.

AB - Modern embedded multi-processors can execute several stream processing applications concurrently. Typically, these applications are partitioned into tasks that communicate over buffers together forming a task graph. The fact that these applications are started and stopped by the user combined with the knowledge that not all applications are necessarily completely characterised makes it attractive to use run-time scheduling. We define and characterise a class of budget schedulers that by construction bound the interference from other applications. Furthermore, we will show that the worst-case effects of these schedulers can be included in dataflow process networks. The execution of the resulting dataflow process network is shown to result in tight and conservative bounds on the end-to-end temporal behaviour of the execution of the task graph on a cycle-true simulator. Given that the inter-task synchronisation of the application allows for a dataflow model that is functionally deterministic, this enables exploration of various buffer capacities and scheduler settings at a high level of abstraction.

KW - METIS-277818

KW - EWI-19113

KW - IR-75579

M3 - Conference contribution

SN - not assigned

SP - -

BT - Berkeley EECS Annual Research Symposium, BEARS 2010

PB - Center for Hybrid and Embedded Software Systems, Chess

CY - Berkeley, CA, USA

ER -

Wiggers MH, Bekooij MJG, Smit GJM. Monotonicity and Run-Time Scheduling. In Berkeley EECS Annual Research Symposium, BEARS 2010. Berkeley, CA, USA: Center for Hybrid and Embedded Software Systems, Chess. 2010. p. -