Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow

Pieter H. Hartel, T.C. Ruys, M.C.W. Geilen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
46 Downloads (Pure)

Abstract

Synchronous Data flow (SDF) graphs have a simple and elegant semantics (essentially linear algebra) which makes SDF graphs eminently suitable as a vehicle for studying scheduling optimisations. We extend related work on using SPIN to experiment with scheduling optimisations aimed at minimising buffer requirements.We show that for a benchmark of commonly used case studies the performance of our SPIN based scheduler is comparable to that of state of the art research tools. The key to success is using the semantics of SDF to prove when using (even unsound and/or incomplete) optimisations are justified. The main benefit of our approach lies in gaining deep insight in the optimisations at relatively low cost.
Original languageUndefined
Title of host publication8th Int. Conf. on Formal Methods in Computer Aided Design (FMCAD)
EditorsA. Cimatti, R. Jones
Place of PublicationPiscataway
PublisherIEEE Computer Society
Pages161-170
Number of pages10
ISBN (Print)978-1-4244-2735-2
DOIs
Publication statusPublished - Nov 2008

Publication series

Name
PublisherIEEE Computer Society Press
Number08332

Keywords

  • EWI-14188
  • SCS-Cybersecurity
  • METIS-252119
  • IR-65126

Cite this

Hartel, P. H., Ruys, T. C., & Geilen, M. C. W. (2008). Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow. In A. Cimatti, & R. Jones (Eds.), 8th Int. Conf. on Formal Methods in Computer Aided Design (FMCAD) (pp. 161-170). [10.1109/FMCAD.2008.ECP.25] Piscataway: IEEE Computer Society. https://doi.org/10.1109/FMCAD.2008.ECP.25
Hartel, Pieter H. ; Ruys, T.C. ; Geilen, M.C.W. / Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow. 8th Int. Conf. on Formal Methods in Computer Aided Design (FMCAD). editor / A. Cimatti ; R. Jones. Piscataway : IEEE Computer Society, 2008. pp. 161-170
@inproceedings{0998853365154bf6babbc6b5b9314e38,
title = "Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow",
abstract = "Synchronous Data flow (SDF) graphs have a simple and elegant semantics (essentially linear algebra) which makes SDF graphs eminently suitable as a vehicle for studying scheduling optimisations. We extend related work on using SPIN to experiment with scheduling optimisations aimed at minimising buffer requirements.We show that for a benchmark of commonly used case studies the performance of our SPIN based scheduler is comparable to that of state of the art research tools. The key to success is using the semantics of SDF to prove when using (even unsound and/or incomplete) optimisations are justified. The main benefit of our approach lies in gaining deep insight in the optimisations at relatively low cost.",
keywords = "EWI-14188, SCS-Cybersecurity, METIS-252119, IR-65126",
author = "Hartel, {Pieter H.} and T.C. Ruys and M.C.W. Geilen",
year = "2008",
month = "11",
doi = "10.1109/FMCAD.2008.ECP.25",
language = "Undefined",
isbn = "978-1-4244-2735-2",
publisher = "IEEE Computer Society",
number = "08332",
pages = "161--170",
editor = "A. Cimatti and R. Jones",
booktitle = "8th Int. Conf. on Formal Methods in Computer Aided Design (FMCAD)",
address = "United States",

}

Hartel, PH, Ruys, TC & Geilen, MCW 2008, Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow. in A Cimatti & R Jones (eds), 8th Int. Conf. on Formal Methods in Computer Aided Design (FMCAD)., 10.1109/FMCAD.2008.ECP.25, IEEE Computer Society, Piscataway, pp. 161-170. https://doi.org/10.1109/FMCAD.2008.ECP.25

Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow. / Hartel, Pieter H.; Ruys, T.C.; Geilen, M.C.W.

8th Int. Conf. on Formal Methods in Computer Aided Design (FMCAD). ed. / A. Cimatti; R. Jones. Piscataway : IEEE Computer Society, 2008. p. 161-170 10.1109/FMCAD.2008.ECP.25.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow

AU - Hartel, Pieter H.

AU - Ruys, T.C.

AU - Geilen, M.C.W.

PY - 2008/11

Y1 - 2008/11

N2 - Synchronous Data flow (SDF) graphs have a simple and elegant semantics (essentially linear algebra) which makes SDF graphs eminently suitable as a vehicle for studying scheduling optimisations. We extend related work on using SPIN to experiment with scheduling optimisations aimed at minimising buffer requirements.We show that for a benchmark of commonly used case studies the performance of our SPIN based scheduler is comparable to that of state of the art research tools. The key to success is using the semantics of SDF to prove when using (even unsound and/or incomplete) optimisations are justified. The main benefit of our approach lies in gaining deep insight in the optimisations at relatively low cost.

AB - Synchronous Data flow (SDF) graphs have a simple and elegant semantics (essentially linear algebra) which makes SDF graphs eminently suitable as a vehicle for studying scheduling optimisations. We extend related work on using SPIN to experiment with scheduling optimisations aimed at minimising buffer requirements.We show that for a benchmark of commonly used case studies the performance of our SPIN based scheduler is comparable to that of state of the art research tools. The key to success is using the semantics of SDF to prove when using (even unsound and/or incomplete) optimisations are justified. The main benefit of our approach lies in gaining deep insight in the optimisations at relatively low cost.

KW - EWI-14188

KW - SCS-Cybersecurity

KW - METIS-252119

KW - IR-65126

U2 - 10.1109/FMCAD.2008.ECP.25

DO - 10.1109/FMCAD.2008.ECP.25

M3 - Conference contribution

SN - 978-1-4244-2735-2

SP - 161

EP - 170

BT - 8th Int. Conf. on Formal Methods in Computer Aided Design (FMCAD)

A2 - Cimatti, A.

A2 - Jones, R.

PB - IEEE Computer Society

CY - Piscataway

ER -

Hartel PH, Ruys TC, Geilen MCW. Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow. In Cimatti A, Jones R, editors, 8th Int. Conf. on Formal Methods in Computer Aided Design (FMCAD). Piscataway: IEEE Computer Society. 2008. p. 161-170. 10.1109/FMCAD.2008.ECP.25 https://doi.org/10.1109/FMCAD.2008.ECP.25