IP Library › Granted Patent US 12,360,804
Granted Patent B2
US 12,360,804 · App. 18/091,441 · Granted Jul 15, 2025

Data dependency-aware scheduling

Inventor: Harris Gasparakis (Santa Clara, CA)
Assignee: Advanced Micro Devices, Inc.
G06F9/4881G06F9/522
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,360,804
App. No.
18/091,441
Filed
Dec 30, 2022
Granted
Jul 15, 2025
Kind
B2
Examiner
DOMAN, SHAWN
Art Unit
2183
USPC
712/220
Abstract

A processing system flexibly schedules workgroups across kernels based on data dependencies between workgroups to enhance processing efficiency. The workgroups are partitioned into subsets based on the data dependencies and workgroups of a first subset that produces data are scheduled to execute immediately before workgroups of a second subset that consumes the data generated by the first subset. Thus, the processing system does not execute one kernel at a time, but instead schedules workgroups across kernels based on data dependencies across kernels. By limiting the sizes of the subsets to the amount of data that can be stored at local caches, the processing system increases the probability that data to be consumed by workgroups of a subset will be resident in a local cache and will not require a memory access.

Claims (52)

1. A method, comprising:

scheduling, at a command processor, a first subset of one or more workgroups of a first kernel to execute at a parallel processor and generate data that is stored at a cache local to the parallel processor immediately prior to a second subset of one or more workgroups of a second kernel based on data dependencies between the first subset and the second subset, wherein the second subset of one or more workgroups of the second kernel executes at the parallel processor prior to the first kernel completing execution and consumes data stored at the cache that was generated by the first subset of one or more workgroups of the first kernel.

2. The method of claim 1 , further comprising:

partitioning, at a runtime, a plurality of workgroups into the first subset of one or more workgroups and the second subset of one or more workgroups based on the data dependencies.

3. The method of claim 2 , wherein partitioning is further based on a size and locality of the cache to a set of one or more compute units executing the one or more workgroups of the second subset.

4. The method of claim 2 , further comprising:

specifying, by the runtime, a mapping between the first subset of one or more workgroups of the first kernel and the second subset of one or more workgroups of the second kernel.

5. The method of claim 1 , wherein a mapping between the first subset of one or more workgroups of the first kernel and the second subset of one or more workgroups of the second kernel is declared in a companion function for each of the first kernel and the second kernel.

6. The method of claim 1 , wherein a number of workgroups in the first subset differs from a number of workgroups in the second subset.

7. The method of claim 1 , further comprising:

inserting a barrier into a kernel packet to delay execution of the second subset of one or more workgroups until the first subset of one or more workgroups has completed execution.

8. The method of claim 7 , further comprising:

initializing a counter by a number of workgroups of the first subset of one or more workgroups that must complete execution prior to the second subset of one or more workgroups executing; and

decrementing the counter in response to a workgroup reaching the barrier.

9. The method of claim 1 , further comprising:

generating a command describing pairings of two or more kernels based on the data dependencies; and

scheduling the one or more workgroups of the first subset and the one or more workgroups of the second subset to execute at a processor based on the command.

10. The method of claim 9 , further comprising:

placing the command and an identifier of a kernel launch for the one or more workgroups of the first subset and the one or more workgroups of the second subset in a ring buffer; and

scheduling workgroups at a command processor based on the command and the identifier.

11. A parallel processor, comprising:

a cache; and

a command processor configured to:

schedule a first subset of one or more workgroups of a first kernel to execute at aa the parallel processor and produce data that is stored at the cache; and

schedule a second subset of one or more workgroups of a second kernel to execute at the parallel processor immediately after execution of the first subset and prior to the first kernel completing execution, based on data dependencies between the first subset and the second subset, wherein the second subset of one or more workgroups consumes data stored at the cache that was generated by the first subset of one or more workgroups.

12. The command processor of claim 11 , wherein a number of workgroups in the first subset differs from a number of workgroups in the second subset.

13. The command processor of claim 11 , further configured to:

schedule the second subset based on a barrier inserted into a kernel packet to delay execution of the second subset of one or more workgroups until the first subset of one or more workgroups has completed execution.

14. The command processor of claim 13 , further configured to:

initialize a counter by a number of workgroups of the second subset of one or more workgroups that must complete execution prior to the first subset of one or more workgroups executing; and

decrement the counter in response to a workgroup reaching the barrier.

15. The command processor of claim 11 , further configured to:

generate a command describing pairings of two or more kernels based on the data dependencies; and

schedule the one or more workgroups of the first subset and the one or more workgroups of the second subset to execute at a processor based on the command.

16. The command processor of claim 15 , further configured to:

place the command and an identifier of a kernel launch for the one or more workgroups of the first subset and the one or more workgroups of the second subset in a ring buffer; and

schedule workgroups at a command processor based on the command and the identifier.

17. A processing system, comprising:

a parallel processor comprising:

a command processor configured to schedule a first subset of one or more workgroups of a first kernel to execute and produce data that is stored at a cache immediately prior to a second subset of one or more workgroups of a second kernel, wherein the second subset of one or more workgroups consumes data stored at the cache that was generated by the first subset of one or more workgroups and executes and prior to the first kernel completing execution.

18. The processing system of claim 17 , wherein a number of workgroups in the first subset of one or more workgroups differs from a number of workgroups in the second subset of one or more workgroups.

19. The processing system of claim 17 , further comprising:

a runtime configured to insert a barrier into a kernel packet to delay execution of the second subset of one or more workgroups until the first subset of one or more workgroups has completed execution.

20. The processing system of claim 19 , wherein the runtime is further configured to: initialize a counter by a number of workgroups of the first subset of one or more workgroups that must complete execution prior to the second subset of one or more workgroups executing; and

decrement the counter in response to a workgroup reaching the barrier.

21. The processing system of claim 17 , further comprising:

a runtime configured to generate a command describing pairings of two or more kernels based on data dependencies among workgroups of the two or more kernels, wherein

the command processor is further configured to schedule the first subset of one or more workgroups and the second subset of one or more workgroups to execute at a processor based on the command.

22. The processing system of claim 21 , further comprising:

a ring buffer, wherein

the runtime is further configured to place the command and an identifier of a kernel launch for the first subset of one or more workgroups and the second subset of one or more workgroups in the ring buffer; and

the command processor is further configured to schedule workgroups based on the command and the identifier.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 9, 2023
From: GASPARAKIS, HARRIS
To: ADVANCED MICRO DEVICES, INC.
Reel/Frame 063586/0257 →
Continuity (1)
Related Publication 20240220314A1 · Jul 4, 2024
References Cited (24)
US 20120320070A1 · Arvo · 2012 [cited by examiner]
US 20160180486A1 · Rao et al. · 2016 [cited by applicant]
US 20160267622A1 · Brothers · 2016 [cited by examiner]
US 20160321777A1 · Jin et al. · 2016 [cited by applicant]
US 20180349145A1 · Tye · 2018 [cited by examiner]
US 20210182072A1 · Ashkar · 2021 [cited by examiner]
US 20210326750A1 · Shah et al. · 2021 [cited by applicant]
US 20210334933A1 · Strauss · 2021 [cited by examiner]
US 20220058053A1 · Andrei et al. · 2022 [cited by applicant]
US 20220350683A1 · Surendran · 2022 [cited by examiner]
CN 115185860 · 2022 [cited by applicant]
A. Abdolrashidi et al., “Wireframe: Supporting Data-dependent Parallelism through Dependency Graph Execution in GPUs,” 2017 Micro, pp. 600-611, [online], [retrieved on Jun. 11, 2024]. Retrieved from the Internet <URL: h… [cited by examiner]
Chen et al. “Improving GPGPU Performance via Cache Locality Aware Thread Block Scheduling,” in IEEE Comp. Arch. Letters, vol. 16, No. 2, pp. 127-131, 2017, [online], [retrieved on Jun. 11, 2024]. From the Internet <URL:… [cited by examiner]
International Search Report and Written Opinion issued in Application No. PCT/US2023/086048, mailed May 9, 2024, 11 pages. [cited by applicant]
Binas, Jonathan and Yoshua Bengio, “Low-memory convolutional neural networks through incremental depth-first processing,” 2018, 9 pages. [cited by applicant]
Qiao et al., “From Loop Fusion to Kernel Fusion: A Domain-Specific Approach to Locality Optimization,” 2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2019, pp. 242-253, doi: 10.1109/CGO… [cited by applicant]
Jia et al. “Enabling Efficient Fast Convolution Algorithms on GPUs via MegaKernels.” IEEE Transactions on Computers 69 (2020): 986-997. DOI:10.1109/TC.2020.2973144. 12 pages. [cited by applicant]
Alwani, Manoj et al. “Fused-layer CNN accelerators.” 2016 49th Annual IEEE/ACM international Symposium on Microarchitecture (MICRO) (2016): 12 pages. [cited by applicant]
Ashari, Arash, et al. “On Optimizing Machine Learning Workloads via Kernel Fusion.” Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Jan. 2015. https://doi.org/10.1145/26… [cited by applicant]
Müller, Thomas, et al. “Real-Time Neural Radiance Caching for Path Tracing.” ACM Transactions on Graphics, vol. 40, No. 4, Jul. 2021, pp. 1-16. https://doi.org/10.48550/arXiv.2106.12372. 16 Pages. [cited by applicant]
Müller, T. et al., “tiny-cuda-nn/src/fully_fused_mlp.cu” tiny-cuda-nn (Version 1.7) [Computer software], GitHub, 2021, <https://github.com/NVlabs/tiny-cuda-nn/blob/39df2387a684e4fe0cfa33542aebf5eab237716b/src/fully_fuse… [cited by applicant]
Harris, Mark and Kyrylo Perelygin, “Cooperative Groups: Flexible CUDA Thread Programming,” NVIDIA Developer, Technical Blog, 2017, <https://developer.nvidia.com/blog/cooperative-groups/>, Accessed Mar. 16, 2023, 7 pages. [cited by applicant]
Klenk, Benjamin, et al. “An in-network architecture for accelerating shared-memory multiprocessor collectives.” 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). IEEE, 2020. [cited by applicant]
U.S. Appl. No. 18/091,443, filed Dec. 30, 2022, listing Suchita Pati et al. as inventors, entitled “Dynamic Control of Work Scheduling”. [cited by applicant]