# US 2016/0259667 A1 · Hardware and runtime coordinated load balancing for parallel applications > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2016/0259667 A1 - Document ID: US20160259667A1 - Status: Published application - Kind: A1 - Application number: 14/641,220 - Filed: 2015-03-06 - Published: 2016-09-08 - Earliest claimed: 2015-03-06 - Assignees: Advanced Micro Devices, Inc. - Applicants: Advanced Micro Devices, Inc. - Inventors: Peter Bailey; Indrani Paul; Manish Arora - Web page: https://patentgrep.com/patent/US20160259667A1 ## CPC - G06F 9/505: {considering the load} - G06F 1/3243: {Power saving in microcontroller unit} - G06F 1/329: by task scheduling - G06F 8/443: {Optimisation} - G06F 9/30065: {Loop control instructions; iterative instructions, e.g. LOOP, REPEAT} - G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution} - G06F 9/3842: {Speculative instruction execution} - G06F 9/4893: {taking into account power or heat criteria (power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206)} - G06F 9/5094: {where the allocation takes into account power or heat criteria (power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206)} - G06F 9/522: {Barrier synchronisation} - G06F 2209/5019: Workload prediction - 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) - 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 A method of balancing execution rates for a plurality of parallel program loops being executed concurrently by a processor may include estimating a completion time for each program loop of the plurality of program loops, determining a difference between the estimated completion time of a first program loop of the plurality of program loops and the estimated completion time of a second program loop of the plurality of program loops, and decreasing the difference by adjusting an execution rate of the first program loop. ## Claims ### Claim 1 A method, comprising: estimating a completion time for each program loop of a plurality of program loops executed concurrently by a processor; determining a difference between the estimated completion time of a first program loop of the plurality of program loops and the estimated completion time of a second program loop of the plurality of program loops; and decreasing the difference by adjusting an execution rate of the first program loop. ### Claim 2 (depends on 1) The method of claim 1, further comprising storing loop progress information for each of the plurality of program loops in one or more loop progress buffers, wherein the estimated completion time for each program loop of the plurality of program loops is determined based on the loop progress information. ### Claim 3 (depends on 2) The method of claim 2, wherein the plurality of program loops is defined in an executable program executed by the processor, and wherein the method further comprises: identifying a dependent instruction block in the executable program to be executed after completion of all of the program loops of the plurality of program loops; and in response to identifying the dependent instruction block and in response to a backwards branch in the program corresponding to the first program loop, storing a program counter value of the backwards branch in the one or more loop progress buffers. ### Claim 4 (depends on 2) The method of claim 2, wherein for each program loop of the plurality of program loops, the loop progress information comprises a number of instructions, a number of completed cycles, and a number of expected total cycles for the program loop. ### Claim 5 (depends on 2) The method of claim 2, wherein for each program loop of the plurality of program loops, the loop progress information comprises a power state of a processing core executing the program loop and an estimated power consumption for the program loop. ### Claim 6 (depends on 2) The method of claim 2, further comprising: for each program loop of the plurality of program loops, storing values in one or more loop termination buffers including a speculative iteration count, a non-speculative iteration count, a trip count, and a confidence bit, wherein estimating the completion time is based on the values stored in the one or more loop termination buffers. ### Claim 7 (depends on 1) The method of claim 1, wherein the processor comprises a plurality of processing cores, and wherein adjusting the execution rate of the first program loop comprises adjusting an amount of power supplied to a processing core executing the first program loop. ### Claim 8 (depends on 1) The method of claim 1, further comprising: comparing the difference with a sleep threshold; and transitioning a processing core assigned to execute the first program loop to a sleep state after completion of the first program loop if the difference is greater than the sleep threshold, wherein the first program loop has an earlier estimated completion time than the second program loop. ### Claim 9 (depends on 8) The method of claim 8, wherein the sleep threshold is longer than a duration for the first program loop to enter the sleep state plus a duration for the first program loop to exit the sleep state. ### Claim 10 (depends on 8) The method of claim 8, further comprising causing the processing core assigned to execute the first program loop to exit the sleep state prior to the estimated completion time of the second loop. ### Claim 11 An apparatus, comprising: one or more loop progress buffers configured to store loop progress information for each of a plurality of program loops executed concurrently by a set of processing cores; a runtime system coupled with one or more loop progress buffers and configured to: estimate a completion time for each of the plurality of program loops based on the loop progress information; determine a difference between the estimated completion time of a first program loop of the plurality of program loops and the estimated completion time of a second program loop of the plurality of program loops; and a power management unit coupled with the runtime system, wherein the power management unit is configured to decrease the difference by adjusting an execution rate of the first program loop. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein the set of processing cores comprises multiple processing cores each configured to execute one of the plurality of program loops. ### Claim 13 (depends on 12) The apparatus of claim 12, wherein the power management unit is further configured to adjust the execution rate of the first program loop by redistributing power between two or more of the multiple processing cores. ### Claim 14 (depends on 12) The apparatus of claim 12, wherein the power management unit is further configured to cause at least one of the multiple cores to enter a sleep state based on the difference between the estimated completion time of the first program loop and the estimated completion time of the second program loop. ### Claim 15 (depends on 11) The apparatus of claim 11, wherein for each program loop of the plurality of program loops, the loop progress information comprises a number of instructions, a number of completed cycles, and a number of expected total cycles, a power state of a processing core executing the program loop, and an estimated power consumption for the program loop. ### Claim 16 (depends on 11) The apparatus of claim 11, further comprising one or more loop termination buffers coupled with the runtime system, wherein the one or more loop termination buffers are configured to, for each of the plurality of program loops, store loop termination information comprising a speculative iteration count, a non-speculative iteration count, a trip count, and a confidence bit, wherein the runtime system is further configured to estimate the completion time based on the loop termination information. ### Claim 17 A non-transitory computer-readable medium storing instructions that when executed by a processor, cause the processor to perform a method comprising: estimating a completion time for each program loop of a plurality of program loops executed concurrently by the processor; determining a difference between the estimated completion time of a first program loop of the plurality of program loops and the estimated completion time of a second program loop of the plurality of program loops; and decreasing the difference by adjusting an execution rate of the first program loop. ### Claim 18 (depends on 17) The non-transitory computer-readable medium of claim 17, wherein the method further comprises storing loop progress information for each of the plurality of program loops in one or more loop progress buffers, wherein the estimated completion time for each program loop of the plurality of program loops is determined based on the loop progress information. ### Claim 19 (depends on 17) The non-transitory computer-readable medium of claim 17, wherein the processor comprises a plurality of processing cores, and wherein adjusting the execution rate of the first program loop comprises adjusting an amount of power supplied to a processing core executing the first program loop. ### Claim 20 (depends on 17) The non-transitory computer-readable medium of claim 17, wherein the method further comprises: comparing the difference with a sleep threshold; and transitioning a processing core assigned to execute the first program loop to a sleep state after completion of the first program loop if the difference is greater than the sleep threshold, wherein the first program loop has an earlier estimated completion time than the second program loop.