Publication

Buffer optimization based on critical path analysis of a dataflow program design

Abstract

The trade-off between throughput and memory constraints is a common design problem in embedded systems, and especially for streaming applications, where the memory in question usually occurs in the form of buffers for streams of data. This paper presents a methodology, based on the post-processing of dataflow execution traces, that enables designers to make principled choices in the design space for arbitrary streaming applications in a scalable manner. It significantly extends the class of applications over traditional compile-time-only techniques, and effectively enables designers to find a close-to-minimum solution for this NP-complete problem. A heuristic algorithm exploring different buffer size configurations lets designers choose appropriate alternatives and enables them to rapidly navigate the design space. Methodology and experimental results are demonstrated in an at-size scenario using a real-world MPEG-4 SP decoder.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts (35)
Streaming media
Streaming media is multimedia that is delivered and consumed in a continuous manner from a source, with little or no intermediate storage in network elements. Streaming refers to the delivery method of content, rather than the content itself. Distinguishing delivery method from the media applies specifically to telecommunications networks, as most of the traditional media delivery systems are either inherently streaming (e.g. radio, television) or inherently non-streaming (e.g. books, videotapes, audio CDs).
NP-completeness
In computational complexity theory, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.
Dataflow programming
In computer programming, dataflow programming is a programming paradigm that models a program as a directed graph of the data flowing between operations, thus implementing dataflow principles and architecture. Dataflow programming languages share some features of functional languages, and were generally developed in order to bring some functional concepts to a language more suitable for numeric processing. Some authors use the term datastream instead of dataflow to avoid confusion with dataflow computing or dataflow architecture, based on an indeterministic machine paradigm.
Show more
Related publications (38)

Design Space Exploration for Partitioning Dataflow Program on CPU-GPU Heterogeneous System

Marco Mattavelli, Simone Casale Brunet, Aurélien François Gilbert Bloch

Dataflow programming is a methodology that enables the development of high-level, parametric programs that are independent of the underlying platform. This approach is particularly useful for heterogeneous platforms, as it eliminates the need to rewrite ap ...
SPRINGER2023

From C/C plus plus Code to High-Performance Dataflow Circuits

Paolo Ienne, Andrea Guerrieri, Lana Josipovic

High-level synthesis (HLS) tools typically generate statically scheduled datapaths. Static scheduling implies that the resulting circuits have a hard time exploiting parallelism in code with potential memory dependences, with control dependences, or where ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Adaptive Streaming in Interactive Multiview Video Systems

Pascal Frossard, Laura Toni, Xue Zhang, Yao Zhao

Multiview applications endow final users with the possibility to freely navigate within 3D scenes with minimum-delay. A real feeling of scene navigation is enabled by transmitting multiple high-quality camera views, which can be used to synthesize addition ...
2019
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.