Hierarchical task scheduling for accelerators
Inventors
MINISKAR, Narasinga Rao • Liu, Frank Y. • Young, Aaron R. • Vetter, Jeffrey S. • Chakraborty, Dwaipayan
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12430166-B2
Publication Date
2025-09-30
Expiration Date
Abstract
Apparatus and methods are disclosed for scheduling tasks in a heterogeneous computing environment. Coarse scheduling of a received task-set is performed centrally, with tasks dispatched to respective processing resources including one or more accelerators. At each accelerator, sub-tasks of a received task are identified, scheduled, and executed. Data-transfer and computation sub-tasks can be pipelined. The accelerator operates using small tiles of local data, which are transferred to or from a large shared reservoir of main memory. Sub-task scheduling can be customized to each accelerator; coarse task scheduling can work on larger tasks; both can be efficient. Simulations demonstrate large improvements in makespan and/or circuit area. Disclosed technologies are scalable and can be implemented in varying combinations of hard-wired or software modules. These technologies are widely applicable to high-performance computing, image classification, media processing, wireless coding, encryption, and other fields.
Core Innovation
The invention describes a hierarchical task scheduler for scheduling tasks among a plurality of accelerator circuits. The coarse scheduling circuit module receives task-set metadata comprising a task graph with vertices representing tasks and directed edges with weights representing a measure of data transfer from an upstream task to a downstream task, and schedules tasks among the plurality of accelerator circuits to minimize a makespan and dispatches the scheduled tasks to the plurality of accelerator circuits.
Each accelerator circuit has limited local memory storage for computation and data transfers, and each corresponding fine scheduling circuit module performs accelerator-specific fine scheduling. The fine scheduling circuit module receives, from the coarse scheduling circuit module, the tasks scheduled for the corresponding accelerator circuit, and an accelerator-specific scheduler sub-module partitions a given task into two or more streams of first sub-tasks, including a first stream with computation sub-tasks that each require one tile of the local memory storage and a second stream with data-transfer sub-tasks.
The accelerator-specific scheduler schedules the computation sub-tasks to execute synchronously and in parallel with the data-transfer sub-tasks. Each computation sub-task executes in a respective first time slot, and input or output data for the computation sub-task is transferred by a respective data-transfer sub-task in a second time slot adjacent to the first time slot. This scheduling enables execution of the received scheduled tasks at the accelerator with the limited amount of local memory storage being less than or equal to two tiles of the local memory storage.
Claims Coverage
Two independent claims are identified. Across the independent claims, the core inventive features include weighted task-graph coarse scheduling to minimize makespan and accelerator-specific fine scheduling that partitions each task into computation and data-transfer streams with synchronous and parallel execution across adjacent time slots under a local-memory tile constraint.
Weighted task graph coarse scheduling to minimize makespan
The system comprises a coarse scheduling circuit module configured to receive task-set metadata comprising a task graph with vertices representing tasks and directed edges each having a weight representing a measure of data transfer from an upstream task to a downstream task, and to schedule tasks among a plurality of accelerator circuits to minimize a makespan and dispatch the scheduled tasks to the plurality of accelerator circuits.
Partitioning tasks into computation and data-transfer streams with adjacent time slots
Each fine scheduling circuit module receives the tasks scheduled for the corresponding accelerator circuit and an accelerator-specific scheduler sub-module partitions a given task into two or more streams of first sub-tasks, including a first stream comprising computation sub-tasks each requiring one tile of the local memory storage and a second stream comprising data-transfer sub-tasks; and schedules the computation sub-tasks to execute synchronously and in parallel with the data-transfer sub-tasks such that each computation sub-task executes in a respective first time slot and its input or output data is transferred by a respective data-transfer sub-task in a second time slot adjacent to the first time slot.
Executing with limited local memory storage bounded by two tiles
The accelerator-specific scheduler enables the received scheduled tasks to be executed at the corresponding accelerator circuit with the limited amount of local memory storage being less than or equal to two tiles of the local memory storage.
Chipset task scheduler and coupled accelerator with sub-task scheduling
The chipset comprises first circuitry configured to implement a task scheduler and second circuitry distinct from and coupled to the first circuitry incorporating a processor core and implementing an accelerator with only a given amount of local memory storage and a sub-task scheduler; wherein the task scheduler receives task-set metadata comprising a task graph with vertices representing tasks and directed edges with weights representing a measure of data transfer and schedules tasks among a plurality of accelerators including the accelerator to minimize a makespan, and first circuitry dispatches a first task among the scheduled tasks to the second circuitry based on output from the task scheduler.
Sub-task scheduler organizes sub-tasks into computation and data-transfer streams with adjacent time slots
The sub-task scheduler is configured to schedule a plurality of sub-tasks of the first task for execution at the accelerator, organized as two or more streams including a first stream comprising computation sub-tasks each requiring one tile of the local memory storage and a second stream comprising data-transfer sub-tasks; and to schedule the computation sub-tasks to execute synchronously and in parallel with the data-transfer sub-tasks at the accelerator such that each computation sub-task executes in a respective first time slot and has input or output data transferred by a respective data-transfer sub-task in a second time slot adjacent to the first time slot.
Sub-task scheduling under local-memory tile constraint
The sub-task scheduler enables the first task to be executed at the accelerator with the given amount of the local memory storage being less than or equal to two tiles of the local memory storage.
Across the independent claims, the claims center on weighted task-graph coarse scheduling to minimize makespan, followed by accelerator-specific or sub-task scheduling that partitions each task into computation and data-transfer streams for synchronous and parallel execution across adjacent time slots while enabling execution using limited local memory storage bounded to no more than two tiles.
Stated Advantages
Minimizing a makespan.
Documented Applications
A hierarchical scheduling architecture for heterogeneous accelerator systems in example workloads including Inception-v3, ResNet-50, U-Net, and VGG-16 is described, with substantial makespan improvements and scaling behavior.
Image recognition application.
HEVC/MP3/voice coding examples.
HPC system contexts and simulation results using a GEMS cycle-level simulator.
EDA tools and fabrication/manufacturing contexts, including masks or reticles and fabrication.
Interested in licensing this patent?