2009 | OriginalPaper | Chapter
Throughput Constraint for Synchronous Data Flow Graphs
Authors : Alessio Bonfietti, Michele Lombardi, Michela Milano, Luca Benini
Published in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Stream (data-flow) computing is considered an effective para-digm for parallel programming of high-end multi-core architectures for embedded applications (networking, multimedia, wireless communication). Our work addresses a key step in stream programming for embedded multicores, namely, the efficient mapping of a synchronous data-flow graph (SDFG) onto a multi-core platform subject to a minimum throughput requirement. This problem has been extensively studied in the past, and its complexity has lead researches to develop incomplete algorithms which cannot exclude false negatives. We developed a CP-based complete algorithm based on a new throughput-bounding constraint. The algorithm has been tested on a number of non-trivial SDFG mapping problems with promising results.