Affordable Access

Scheduling optimisations for SPIN to minimise buffer requirements in synchronous data flow.

IEEE Computer Society
Publication Date
  • Linguistics
  • Mathematics


Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow Scheduling Optimisations for SPIN to Minimise Buffer Requirements in Synchronous Data Flow Pieter H. Hartel and Theo C. Ruys University of Twente, The Netherlands email: {P.H.Hartel,T.C.Ruys} Marc C. W. Geilen Eindhoven University of Technology, The Netherlands email: 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 schedul- ing 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. I. INTRODUCTION Synchronous Data Flow (SDF) is a paradigm for describing Digital Signal Processing (DSP) applications [13]. SDF has a long history dating back to the early 70s. Mainly due to the ever increasing interest in embedded systems, SDF is currently an active area of research. A typical application processes an infinite stream of data samples, which enter the SDF graph at the source node(s), and which exit the graph at the sink node(s). The SDF formalism abstracts away from the actual calculations taking place at the nodes, the contents of the tokens, and the time taken to transfer tokens or to perform calculations. An SDF graph is a directed, connected graph. Each node in the graph represents a processing step, and the edges transport tokens between nodes. The nodes may fire independently of each other, and concurrently. The term synchronous means that when a node f

There are no comments yet on this publication. Be the first to share your thoughts.