# US 10,310,861 B2 · Mechanism for scheduling threads on a multiprocessor > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,310,861 B2 - Document ID: US10310861B2 - Status: Granted - Kind: B2 - Application number: 15/477,017 - Filed: 2017-04-01 - Published: 2018-10-04 - Granted: 2019-06-04 - Earliest claimed: 2017-04-01 - Assignees: Intel Corporation - Applicants: Intel Corporation - Inventors: Balaji Vembu; Abhishek R. Appu; Joydeep Ray; Altug Koker - Web page: https://patentgrep.com/patent/US10310861B2 ## CPC - G06F 9/46: Multiprogramming arrangements - G06F 9/3851: {from multiple instruction streams, e.g. multistreaming} - G06F 9/3888: {controlled by a single instruction for multiple threads [SIMT] in parallel} - G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system} - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals} - G06F 9/522: {Barrier synchronisation} - G06F 9/545: {where tasks reside in different layers, e.g. user- and kernel-space} - G06F 12/0842: for multiprocessing or multitasking - G06F 12/0866: for peripheral storage systems, e.g. disk cache - G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811) - G06F 15/16: Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs {(coordinating program control therefor G06F9/52; in regulating and control system G05B)} - G06F 15/76: Architectures of general purpose stored program computers (with program plugboard G06F15/08; multicomputers G06F15/16) - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06T 1/60: Memory management - G06F 2209/5018: Thread allocation - G06T 2200/28: involving image processing hardware - Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE ## Abstract An apparatus to facilitate thread scheduling is disclosed. The apparatus includes logic to store barrier usage data based on a magnitude of barrier messages in an application kernel and a scheduler to schedule execution of threads across a plurality of multiprocessors based on the barrier usage data. ## Claims ### Claim 1 An apparatus comprising: a processor to analyze an application kernel to determine a magnitude of barrier messages in the application kernel and generate barrier usage data having a value corresponding to the magnitude of barrier messages in the application kernel; a memory to store the barrier usage data; and a graphics processor, including: a plurality of multiprocessors; and a scheduler to retrieve the barrier usage data from the memory and to schedule execution of each thread of a plurality of threads to a respective microprocessor of the plurality of multiprocessors according to a scheduling policy, the scheduling policy being based at least in part on the barrier usage data, wherein the scheduler is to prioritize scheduling threads of a thread group to a same microprocessor of the plurality of multiprocessors upon a determination that the barrier usage data indicates a high magnitude of barrier messages in the thread group. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the memory is to store the barrier usage data as thread meta-data for the application kernel. ### Claim 3 (depends on 1) The apparatus of claim 1, wherein the scheduling policy is based both on the barrier usage data and on load balancing of the plurality of threads across the plurality of multiprocessors. ### Claim 4 (depends on 3) The apparatus of claim 3, wherein the scheduler is to perform the load balancing by performing a first cost function for each thread of the plurality of threads, the first cost function to determine a maximum number of threads scheduled for each of the plurality of multiprocessors. ### Claim 5 (depends on 4) The apparatus of claim 4, wherein the scheduler is to perform a second cost function for each thread of the plurality of threads, the second cost function being based at least in part on the barrier usage data. ### Claim 6 (depends on 5) The apparatus of claim 5, wherein the scheduler is to schedule the execution of each thread of the plurality of threads by minimizing a sum of values including the first cost function and the second cost function. ### Claim 7 (depends on 1) The apparatus of claim 1, wherein the scheduler is to schedule the threads of the thread group for execution at two or more of the plurality of multiprocessors upon a determination that the barrier usage data indicates a low magnitude of barrier messages. ### Claim 8 A method comprising: analyzing an application kernel during compiling to determine a magnitude of barrier messages in the application kernel; generating barrier usage data during the compiling having a value corresponding to the magnitude of barrier messages in the application kernel; receiving a plurality of threads for scheduling; and scheduling execution of each thread of the plurality of threads to a respective microprocessor of a plurality of multiprocessors according to a scheduling policy, the scheduling policy being based at least in part on the barrier usage data, wherein scheduling includes prioritizing the scheduling of threads of a thread group for execution to a same microprocessor of the plurality of multiprocessors upon a determination that the barrier usage data indicates a high magnitude of barrier messages in the thread group. ### Claim 9 (depends on 8) The method of claim 8, further comprising storing the barrier usage data in a computer memory. ### Claim 10 (depends on 9) The method of claim 9, wherein storing the barrier usage data includes storing the barrier usage data as thread meta-data for the application kernel. ### Claim 11 (depends on 8) The method of claim 8, wherein the scheduling policy is based both on the barrier usage data and on load balancing of the plurality of threads across the plurality of multiprocessors. ### Claim 12 (depends on 11) The method of claim 11, further comprising: performing the load balancing by performing a first cost function for each thread of the plurality of threads, the first cost function to determine a maximum number of threads scheduled for each of the plurality of multiprocessors; and performing a second cost function for each thread of the plurality of threads, the second cost function being based at least in part on the barrier usage data. ### Claim 13 (depends on 12) The method of claim 12, further comprising scheduling the execution of each thread of the plurality of threads by minimizing a sum of values including the first cost function and the second cost function. ### Claim 14 A non-transitory computer readable medium having instructions, which when executed by one or more processors, cause the processors to perform operations comprising: analyzing an application kernel during compiling to determine a magnitude of barrier messages in the application kernel; generating barrier usage data during the compiling having a value corresponding to the magnitude of barrier messages in the application kernel; receiving a plurality of threads for scheduling; and scheduling execution of each thread of the plurality of threads to a respective microprocessor of a plurality of multiprocessors according to a scheduling policy, the scheduling policy being based at least in part on the barrier usage data, wherein scheduling includes prioritizing the scheduling of threads of a thread group for execution to a same microprocessor of the plurality of multiprocessors upon a determination that the barrier usage data indicates a high magnitude of barrier messages in the thread group. ### Claim 15 (depends on 14) The computer readable medium of claim 14, wherein the scheduling policy is based both on the barrier usage data and on load balancing of the plurality of threads across the plurality of multiprocessors. ### Claim 16 (depends on 15) The computer readable medium of claim 15, having instructions, which when executed by the one or more processors, further cause the processors to perform operations comprising: performing the load balancing by performing a first cost function for each thread of the plurality of threads, the first cost function to determine a maximum number of threads scheduled for each of the plurality of multiprocessors; and performing a second cost function for each thread of the plurality of threads, the second cost function being based at least in part on the barrier usage data. ### Claim 17 (depends on 16) The computer readable medium of claim 16, having instructions, which when executed by the one or more processors, further cause the processors to perform operations comprising: scheduling the execution of each thread of the plurality of threads by minimizing a sum of values including the first cost function and the second cost function.