DPTM: An Adaptive Scheduler Design Utilizing Timeslot Matching and Release Methods for Concurrent and Multi-task Interleaved Pipelining-oriented CGRA

Coarse-grained reconfigurable architectures (CGRAs) are increasingly employed as domain-specific accelerators due to their efficiency and flexibility. However, the existing CGRA architectures suffer from low hardware resource utilization and performance due to the limitations of the scheduling scheme. In this paper, an adaptive scheduler (denoted as DPTM) for concurrent and multi-task interleaved pipelining-oriented CGRA is introduced, which exploits timeslot matching and release methods to avoid the pipeline conflicts and improve the scheduling performance. The characteristics of task scheduling based on directed acyclic graph (DAG) are analyzed, and several performance-influencing factors are extracted to build a scheduling performance model for reducing the time cost of scheduling and guiding the design of scheduling schemes. Moreover, the scoreboard method of dynamic instruction schedulers is optimized to control the entry time of multiple tasks into the pipeline, and then a timeslot matching method is proposed to provide non-conflict pipelining for the multiple tasks. Further, a timeslot release method is presented to release the timeslots for unscheduled sub-tasks dynamically, which can adapt the parallel processing of multiple tasks and decrease the scheduling time. Then, an adaptive scheduling scheme combines the dynamic priority-based task assignment method, timeslot matching method, and timeslot release method to schedule massive tasks for CGRA. Finally, the overall architecture of DPTM is introduced and designed to validate the efficacy of the proposed scheduling scheme. Experimental results show that the proposed timeslot matching/release approach reduces 84% total scheduling time and decreases 40% average scheduling time at most compared to the non-timeslot-matching scheduling schemes, the proposed task assignment approach decreases 8% total scheduling time and lowers 3% average scheduling time compared to the existing approaches, and the proposed scheduler decreases 51% critical path delay, lowers 35% area overhead, and reduces 12% power consumption at most compared with the existing schedulers.