Edinburgh Research Explorer

Periodic schedules for Cyclo-Static Dataflow

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

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

Related Edinburgh Organisations

Original languageEnglish
Title of host publicationEmbedded Systems for Real-time Multimedia (ESTIMedia), 2013 IEEE 11th Symposium on
PublisherIEEE
Pages105-114
Number of pages10
DOIs
StatePublished - 1 Oct 2013

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.

Research areas

  • 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

ID: 24370877