Periodic schedules for Cyclo-Static Dataflow

B. Bodin, A. Munier-Kordon, B. D. de Dinechin

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

Abstract

Cyclo-Static Dataflow Graphs (CSDFGs in short) is a static model commonly used to describe communications between processes. It is increasingly considered for modeling applications executed by many-core architectures; their static analysis becomes thus essential for developing efficient compile-time optimization. This paper aims to develop efficient algorithms to approximately solve two main difficult problems: the determination of the maximum throughput of a CSDFG and the optimization of the buffer sizes with a minimum required throughput. They are both based on a new characterization of feasible periodic schedules. A polynomial-time algorithm is deduced to evaluate the maximum throughput of a periodic schedule, providing a lower bound of the maximum throughput of the CSDFG. A new model for the optimization of the buffer sizes with a minimum required throughput based on integer linear programming is also developed, leading to a new algorithm to solve it approximately. Our algorithms are successfully compared with other academic solutions through representative benchmarks.
Original languageEnglish
Title of host publicationEmbedded Systems for Real-time Multimedia (ESTIMedia), 2013 IEEE 11th Symposium on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages105-114
Number of pages10
DOIs
Publication statusPublished - 1 Oct 2013

Keywords

  • buffer storage
  • data flow graphs
  • integer programming
  • linear programming
  • multimedia communication
  • CSDFG
  • buffer sizes
  • compile-time optimization
  • cyclo-static dataflow graph
  • integer linear programming
  • many-core architecture
  • maximum throughput
  • periodic schedule
  • polynomial-time algorithm
  • static analysis
  • Equations
  • Mathematical model
  • Optimization
  • Processor scheduling
  • Schedules
  • Throughput
  • Vectors

Fingerprint

Dive into the research topics of 'Periodic schedules for Cyclo-Static Dataflow'. Together they form a unique fingerprint.

Cite this