Hierarchical task scheduling for accelerators
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.
1. A system for scheduling tasks among a plurality of accelerator circuits, the system comprising:
a hierarchical task scheduler comprising:
a coarse scheduling circuit module configured to:
receive task-set metadata comprising a task graph having vertices representing respective tasks and directed edges, each from a respective source vertex of the vertices to a respective destination vertex of the vertices, joining respective pairs of the vertices, each of the directed edges having a weight representing a measure of data transfer from an upstream task represented by the respective source vertex to a downstream task represented by the respective destination vertex;
based on the task graph, schedule tasks from the task-set metadata among the plurality of accelerator circuits to minimize a makespan; and
dispatch the scheduled tasks to the plurality of accelerator circuits; and
two or more fine scheduling circuit modules, wherein each fine scheduling circuit module is communicatively coupled with the coarse scheduling circuit module and with a corresponding accelerator circuit from among the plurality of accelerator circuits, the corresponding accelerator circuit having a limited amount of local memory storage for computation and data transfers;
wherein the each fine scheduling circuit module comprises:
an interface sub-module configured to receive, from the coarse scheduling circuit module, the tasks scheduled for the corresponding accelerator circuit; and
an accelerator-specific scheduler (AS) sub-module configured to:
partition, for a given task of the received scheduled tasks, the 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
schedule the computation sub-tasks to execute synchronously and in parallel with the data-transfer sub-tasks on the corresponding accelerator circuit, each of the computation sub-tasks executing in a respective first time slot and having input or output data transferred by a respective one of the data-transfer sub-tasks in a second time slot adjacent to the first time slot;
wherein the AS sub-module enables the received scheduled tasks to be executed at the corresponding accelerator circuit with the limited amount of the local memory storage being less than or equal to two tiles of the local memory storage.
2. The system of claim 1 , wherein the interface sub-module comprises a first-in first-out queue (FIFO) configured to queue the received scheduled tasks.
3. The system of claim 1 , wherein:
the each fine scheduling circuit module further comprises a respective memory controller; and
the AS sub-module is configured to schedule the data-transfer sub-tasks to be executed by the respective memory controller.
4. The system of claim 3 , wherein the respective memory controller is communicatively coupled with accelerator-side static random-access memory (SRAM) through a direct memory access (DMA) channel, and is communicatively coupled with main memory through a bus shared among the two or more fine scheduling circuit modules.
5. The system of claim 1 , wherein the first sub-tasks comprise instructions to configure accelerator-specific memory-mapped addresses and DMA-specific memory-mapped addresses.
6. The system of claim 1 , wherein the accelerator circuits comprise respective neural network kernels, each of the neural network kernels configured as a convolution kernel, a batch normalization kernel, or a fully-connected layer kernel.
7. The system of claim 1 , wherein the accelerator circuits comprise convolution kernels of multiple types.
8. The system of claim 1 , wherein the coarse scheduling circuit module and at least one of the fine scheduling circuit modules comprise distinct respective processor cores configured to execute respective scheduling instructions.
9. The system of claim 1 , wherein at least one of the fine scheduling circuit modules is implemented as a hard-wired circuit.
10. The system of claim 1 , wherein the coarse scheduling circuit module and at least one of the fine scheduling circuit modules are implemented on a common chip.
11. A chipset comprising:
the system of claim 1 ; and
the plurality of accelerator circuits.
12. The system of claim 11 , wherein the accelerator circuits comprise two or more of: a neuromorphic array, a field-programmable gate array (FPGA), a general-purpose graphics processor unit (GPGPU), or an application specific integrated circuit (ASIC).
13. A high-performance computing (HPC) apparatus comprising:
the system of claim 1 ;
a host processor configured to provide the task-set metadata to the coarse scheduling circuit module; and
the plurality of accelerator circuits.
14. A chipset comprising:
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, the accelerator having only a given amount of local memory storage for computation and data transfers, and a sub-task scheduler;
wherein the task scheduler is configured to receive task-set metadata comprising a task graph having vertices representing respective tasks and directed edges, each from a respective source vertex of the vertices to a respective destination vertex of the vertices, joining respective pairs of the vertices, each of the directed edges having a weight representing a measure of data transfer from an upstream task represented by the respective source vertex to a downstream task represented by the respective destination vertex;
wherein, based on the task graph, the task scheduler is further configured to schedule tasks from the task-set metadata among a plurality of accelerators, including the accelerator, to minimize a makespan;
wherein the first circuitry is configured to dispatch a first task, among the scheduled tasks, to the second circuitry based on output from the task scheduler;
wherein the sub-task scheduler is configured to schedule a plurality of sub-tasks of the first task for execution at the accelerator, the sub-tasks 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;
wherein the computation sub-tasks are scheduled to execute synchronously and in parallel with the data-transfer sub-tasks at the accelerator, each of the computation sub-tasks executing in a respective first time slot and having input or output data transferred by a respective one of the data-transfer sub-tasks in a second time slot adjacent to the first time slot; and
wherein 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.
15. The chipset of claim 14 , wherein the processor core is a second processor core; the first circuitry comprises a first processor core and hard-wired circuitry implementing the task scheduler; and the first processor core is coupled to the hard-wired circuitry and configured to control the task scheduler.
16. The chipset of claim 14 , wherein the second circuitry comprises hard-wired circuitry implementing the sub-task scheduler; and the processor core is coupled to the hard-wired circuitry and configured to control the sub-task scheduler.
17. The chipset of claim 14 , wherein the processor core is configured to implement the sub-task scheduler by executing program instructions.
18. The chipset of claim 14 , wherein the processor core is a first processor core, the accelerator is a first accelerator, the sub-task scheduler is a first sub-task scheduler, and further comprising:
third circuitry, coupled to the first circuitry, implementing a second accelerator and a second processor core, wherein the second processor core is configured to implement a second sub-task scheduler;
wherein the first circuitry is configured to dispatch a second task to the third circuitry based on the output from the task scheduler; and
wherein the second sub-task scheduler is configured to schedule a plurality of sub-tasks of the second task at the second accelerator.
19. The chipset of claim 18 , further comprising:
eight additional circuitries, each coupled to the first circuitry, each implementing a respective additional accelerator and a respective additional processor core configured to implement a respective additional sub-task scheduler;
wherein the first circuitry is configured to dispatch respective tasks to the additional circuitries based on the output from the task scheduler; and
wherein each of the additional sub-task schedulers is configured to schedule a plurality of sub-tasks of the respective task at the respective additional accelerator.
20. The chipset of claim 14 , wherein the accelerator implements a neural network kernel, a convolution function, a matrix arithmetic function, a matrix analysis function, a data compression function, an encryption function, a domain transform, a bit blit function, a regular expression search function, a wireless coding function, or a beamforming function.
21. The chipset of claim 14 , wherein the processor core is a RISC-V processor core.
22. A smartphone comprising the chipset of claim 14 , wherein the smartphone supports a 5G cellular network standard or a 6G cellular network standard.
23. A multimedia streaming apparatus comprising the chipset of claim 14 , wherein the accelerator is configured to support high-efficiency video coding (HEVC).
24. A media streaming apparatus comprising the chipset of claim 14 , wherein the accelerator is configured to support MP3 coding.
25. A telephony apparatus comprising the chipset of claim 14 , wherein the accelerator is configured to support a voice coding standard.
26. A computer-implemented method comprising:
for the chipset of claim 16 :
producing a first computer-readable description of the first circuitry implementing the task scheduler; and
producing a second computer-readable description of the second circuitry; and
storing the first and second computer-readable descriptions in one or more computer-readable storage media, the first and second computer-readable descriptions being usable for fabricating one or more masks or reticles for manufacturing one or more integrated circuits implementing the first circuitry and the second circuitry.
27. The computer-implemented method of claim 26 further comprising:
fabricating the one or more masks or reticles using the stored first computer-readable description and the stored second computer-readable description.
28. The computer-implemented method of claim 26 further comprising:
manufacturing the one or more integrated circuits using the stored first computer-readable description and the stored second computer-readable description.