Fine-Grained Communication-Aware Task Scheduling Approach for Acyclic and Cyclic Applications on MPSoCs

Kai Huang, Xiaowen Jiang, Haitian Jiang, Xiaomeng Zhang, Min Yu, Rongjie Yan, Xiaolang YanIEEE Access 2019 · DOI

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.

System model illustrating task distribution and cyclic dependencies across CPU subsystems.

To balance scheduling quality with computational overhead, the authors propose two variants:

  1. S-FCATS (Search-based): A high-precision approach combining Genetic Algorithms (GA) for pipeline allocation with Integer Linear Programming (ILP) for optimal scheduling.
  2. 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.

Timing diagrams comparing standard execution sequences with communication-pipelined sequences, demonstrating saved transfer time.

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

BibTeX
@article{huang2019fine,
  author = {Kai Huang and Xiaowen Jiang and Haitian Jiang and Xiaomeng Zhang and Min Yu and Rongjie Yan and Xiaolang Yan},
  title = {{Fine-Grained Communication-Aware Task Scheduling Approach for Acyclic and Cyclic Applications on MPSoCs}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2911653},
}
Figure