TL;DR
This paper presents novel software synthesis techniques to significantly boost the performance of dynamic dataflow programs, particularly for video decoding applications. By optimizing communication and computation within the Dataflow Process Network (DPN) model, the authors achieve real-time HD video decoding, demonstrating over 100% frame-rate improvement compared to prior methods.
What Problem Does This Paper Address?
Modern applications, especially in multimedia like video decoding, demand high performance on increasingly complex parallel architectures. Dynamic dataflow programming offers a flexible way to build these applications by representing them as graphs of computational units (actors) communicating via FIFO channels. However, achieving the strict real-time performance required by applications like high-definition video decoding has been a major challenge. This is largely due to inefficiencies in how these programs handle communication and scheduling on parallel hardware. Traditional compilers have decades of optimization for memory locality, but dataflow programming requires new approaches to fully leverage processor capabilities. This paper tackles this gap by proposing advanced synthesis techniques specifically tailored for dynamic dataflow programs.
Methods
The core of this work lies in enhancing the software synthesis process for dynamic dataflow programs, focusing on two key areas:
- Branch-Free Communications: Traditional FIFO channel implementations in software often involve complex index management and potential overhead. The authors propose a "branch-free" approach where direct access to FIFO channel contents is used during action processing. This is made possible by the atomic nature of action firing in the DPN model, allowing FIFO indexes to be updated only after the entire action completes. This eliminates intermediate copies and simplifies the execution flow.
- Copy-Free Communications: For multi-rate actions (common in video coding, where an actor processes multiple data tokens at once), the standard DPN model involves reading tokens into local variables, processing them, and then writing them back. The authors' "copy-free" technique merges these steps by allowing direct access to FIFO channels during processing. This avoids unnecessary data copying between FIFO buffers and local variables, reducing memory footprint and instruction count.
- Aligned Communications: To further optimize performance, especially on processors that benefit from aligned memory accesses, the authors introduce an "aligned" version of actions. This version is executed when tokens are linearly accessible in the FIFO buffer, allowing for more efficient, potentially vectorized, memory accesses.
- Multi-level Dynamic Scheduling: The paper also touches upon scheduling, differentiating between actor scheduling (determining which actor to run next) and action scheduling (determining when an actor's internal actions can fire). They leverage existing runtime actor mapping/scheduling strategies that exploit spatial and temporal locality by executing an actor until it can no longer fire, then yielding to the scheduler.
These techniques are implemented within open-source tools, specifically the Orcc toolchain, and demonstrated on video decoders.
Datasets
The paper evaluates its techniques using standardized video sequences, specifically the "foreman QCIF" sequence for lower resolutions and a "720P" sequence for high-definition testing. The applications themselves are based on standardized video codecs like MPEG-4 SP and HEVC. No new benchmarks or datasets were introduced; rather, the focus was on applying the synthesis techniques to existing, well-known video decoding applications.
Key Insights and Ideas
- Dataflow's Communication Bottleneck: The paper strongly emphasizes that communication, not just computation, is a major bottleneck in dynamic dataflow programs. Their techniques directly address this by optimizing how data moves between actors.
- Leveraging DPN's Atomic Firing: The "branch-free" and "copy-free" communication optimizations are cleverly enabled by the DPN model's guarantee that an action firing is an indivisible quantum of execution. This allows for optimizations that might be unsafe in more general programming models.
- The Power of Alignment: The "aligned communications" technique highlights how exploiting memory access patterns can yield significant performance gains, especially on modern parallel architectures that benefit from instruction-level and word-level parallelism.
- Real-time HD is Achievable: The results demonstrate that with the right synthesis techniques, dynamic dataflow programs can indeed achieve real-time performance for demanding applications like HD video decoding, even on relatively modest hardware.
Key Results
The paper reports significant performance improvements:
- Frame-rate Improvement: Over 100% improvement in frame-rate is reported for video decoders compared to previously proposed implementations. Specifically, Table 1 shows improvements of over 200% for QCIF resolutions.
- Real-time HD Decoding: Table 2 demonstrates that their implementation can achieve real-time HD (720P) decoding frame-rates on desktop multi-core platforms, even with just a few processor cores. For example, with 2 cores, they achieve 54 FPS for MPEG-4 SP and 22 FPS for HEVC.
- Embedded Performance: The techniques also show strong results on embedded platforms, with significant frame-rate increases reported in Table 1 for both MPEG-4 SP and AVC.
Limitations and Future Work
- Limitations: While the paper focuses on communication and computation, it acknowledges that scheduling is also a critical factor. The current scheduling strategies are described as "runtime actor mapping/scheduling strategies," implying that further optimization in this area might be possible. The "aligned communications" technique relies on the FIFO channel width being compatible with bus widths, which might not always be the case.
- Future Work: The authors suggest that their approach is validated by the presented results and lays the groundwork for further advancements in efficient dynamic dataflow program implementation. Future work could likely explore more sophisticated scheduling algorithms, further optimizations for different hardware architectures, and potentially extending these techniques to other complex multimedia applications.
Summary updated