Periodic schedules for Cyclo-Static Dataflow

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Bodin, Bruno, Munier-Kordon, Alix, de Dinechin, Benoit Dupont
Format: Conference Proceeding
Language:English
Subjects:
Equations
Mathematical model
Optimization
Processor scheduling
Schedules
Throughput
Vectors
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2325-1271
DOI:10.1109/ESTIMedia.2013.6704509