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

Pieter H. Hartel; Theo C. Ruys; Marc C.W. Geilen

doi:10.1109/FMCAD.2008.ECP.25

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

Pieter H. Hartel, Theo C. Ruys, Marc C.W. Geilen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

6 Citations (Scopus)

107 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 language	English
Title of host publication	2008 Formal Methods in Computer-Aided Design
Subtitle of host publication	Portland, Oregon, USA, 17-20 November 2008
Editors	A. Cimatti, R. Jones
Place of Publication	Piscataway, NJ
Publisher	IEEE
Pages	161-170
Number of pages	10
ISBN (Print)	978-1-4244-2735-2
DOIs	https://doi.org/10.1109/FMCAD.2008.ECP.25
Publication status	Published - Nov 2008
Event	8th International Conference on Formal Methods in Computer Aided Design 2008 - Portland, United States Duration: 17 Nov 2008 → 20 Nov 2008 Conference number: 8

Conference

Conference	8th International Conference on Formal Methods in Computer Aided Design 2008
Country/Territory	United States
City	Portland
Period	17/11/08 → 20/11/08

Keywords

SCS-Cybersecurity

Access to Document

10.1109/FMCAD.2008.ECP.25

Hartel2008schedulingAccepted author version, 164 KB

6 Citations
1 Report

Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow: (with appendix)
Hartel, P. H. & Ruys, T. C., 11 May 2008, Enschede: Centre for Telematics and Information Technology (CTIT). 10 p. (CTIT Technical Report Series; no. TR-CTIT-08-16)
Research output: Book/Report › Report › Professional

Open Access
File

Cite this

@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 = "SCS-Cybersecurity",

author = "Hartel, {Pieter H.} and Ruys, {Theo C.} and Geilen, {Marc C.W.}",

year = "2008",

month = nov,

doi = "10.1109/FMCAD.2008.ECP.25",

language = "English",

isbn = "978-1-4244-2735-2",

pages = "161--170",

editor = "A. Cimatti and R. Jones",

booktitle = "2008 Formal Methods in Computer-Aided Design",

publisher = "IEEE",

address = "United States",

note = "8th International Conference on Formal Methods in Computer Aided Design 2008 ; Conference date: 17-11-2008 Through 20-11-2008",

}

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), 2008 Formal Methods in Computer-Aided Design: Portland, Oregon, USA, 17-20 November 2008. IEEE, Piscataway, NJ, pp. 161-170, 8th International Conference on Formal Methods in Computer Aided Design 2008, Portland, Oregon, United States, 17/11/08. 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, Theo C.; Geilen, Marc C.W.
2008 Formal Methods in Computer-Aided Design: Portland, Oregon, USA, 17-20 November 2008. ed. / A. Cimatti; R. Jones. Piscataway, NJ: IEEE, 2008. p. 161-170.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Hartel, Pieter H.

AU - Ruys, Theo C.

AU - Geilen, Marc C.W.

N1 - Conference code: 8

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 - SCS-Cybersecurity

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 - 2008 Formal Methods in Computer-Aided Design

A2 - Cimatti, A.

A2 - Jones, R.

PB - IEEE

CY - Piscataway, NJ

T2 - 8th International Conference on Formal Methods in Computer Aided Design 2008

Y2 - 17 November 2008 through 20 November 2008

ER -

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

Abstract

Conference

Keywords

Access to Document

Fingerprint

Research output

Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow: (with appendix)

Cite this