Monotonic Optimization of Dataflow Buffer Sizes.

Area of Science:

• Computer Science
• Signal Processing
• Optimization Theory

Background:

• High data-rate video processing applications face a critical trade-off between system throughput and buffer sizes (storage distribution).
• Functional correctness in these applications is directly tied to throughput, while minimizing storage distribution is crucial for resource efficiency.
• Cyclo-static dataflow graphs are commonly used to model computation kernels in these video processing systems.

Purpose of the Study:

• To address the challenge of minimizing the total weighted size of the storage distribution for cyclo-static dataflow graphs.
• To develop an algorithm that satisfies throughput constraints while optimizing buffer sizes.
• To improve upon existing state-of-the-art storage optimization approaches for video processing applications.

Main Methods:

• The study combines monotonic optimization techniques with causal dependency analysis from existing storage optimization methods.
• A novel algorithm is developed that iteratively refines solutions, providing a bound on suboptimality at each step.
• The algorithm's scalability is enhanced compared to previous state-of-the-art approaches.

Main Results:

• The proposed algorithm demonstrates significantly improved scalability over existing methods.
• It can provide a feasible solution and a suboptimality bound at any point during its execution.
• Experiments on various models, including a healthcare video processing application, show performance increases of several orders of magnitude.

Conclusions:

• The developed algorithm offers an effective and scalable solution for minimizing storage distribution in cyclo-static dataflow graphs under throughput constraints.
• This approach is particularly relevant for high data-rate video processing applications, including those in the healthcare domain.
• The method provides a practical way to balance performance requirements with resource usage optimization.