Abstract
Modern Multiprocessor Systems-on-Chip (MPSoCs) increasingly rely on fine-grained task parallelism to meet performance demands. However, the resulting communication overhead often becomes a bottleneck. This paper presents Fine-Grained Communication-Aware Task Scheduling (FCATS), a novel approach that integrates communication pipelining—overlapping data transfers with computation—directly into the scheduling process. By utilizing retiming theory to manage both acyclic and cyclic task graphs, FCATS achieves significant performance improvements, reaching up to 46% over traditional scheduling methods.
Introduction
The shift toward fine-grained task decomposition in MPSoCs aims to maximize core utilization but introduces a "granularity trap." As tasks become smaller, the frequency and relative cost of inter-task communication increase, often negating the benefits of parallelism. Traditional scheduling approaches typically separate task placement from communication optimization, failing to exploit the potential for latency hiding. FCATS addresses this by treating communication as a primary scheduling constraint, specifically focusing on the inter-dependency between task timing and data transfer pipelines.
The FCATS Framework
FCATS is designed to handle complex task topologies, including those with cyclic dependencies (loops). The framework models applications as Communication-aware Task Graphs, where nodes represent computation and edges represent data dependencies.
To balance scheduling quality with computational overhead, the authors propose two variants:
- S-FCATS (Search-based): A high-precision approach combining Genetic Algorithms (GA) for pipeline allocation with Integer Linear Programming (ILP) for optimal scheduling.
- H-FCATS (Heuristic-based): A scalable version utilizing list-scheduling heuristics (uprank and downrank) to provide near-optimal solutions for large-scale applications, such as H.264 decoders.
Communication Pipelining and Retiming
The core innovation of FCATS is the automated application of communication pipelining. By using Retiming Theory, the scheduler can "retime" tasks to allow a processor to begin receiving data for a future iteration while still processing the current one.
This pipelining is particularly effective when task durations are balanced with communication times. The framework also incorporates deadlock prevention mechanisms for cyclic graphs, ensuring that the number of pipeline stages does not exceed the available delay cycles in a loop.
Experimental Results
The FCATS approach was validated using synthetic graphs (TGFF), standard benchmarks (Robot Control, Sparse Matrix Solver), and a real-world H.264 baseline decoder. Key findings include:
- Performance: S-FCATS outperformed standard ILP-based scheduling by up to 26%.
- Heuristic Gains: H-FCATS showed a 46.5% improvement over traditional heuristics for robot control tasks.
- Real-World Application: For the H.264 decoder, H-FCATS reduced communication costs by 37% and improved overall performance by 13.9% compared to state-of-the-art GA-based schedulers.
Conclusion
FCATS demonstrates that integrating communication awareness into the scheduling logic is essential for optimizing fine-grained MPSoC applications. By leveraging retiming and pipelining, the approach effectively hides communication latency. Future work will focus on integrating task mapping directly into the FCATS flow to provide a comprehensive end-to-end optimization tool.
Summary updated