Systems and methods for energy proportional scheduling

• US 10,540,107 B2
• Filed: 01/04/2016
• Issued: 01/21/2020
• Est. Priority Date: 01/02/2015
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Reservoir Labs, Inc (Qualcomm, Inc.)
• Inventors: Baskaran, Muthu M., Henretty, Thomas, Johnson, Ann, Konstantinidis, Athanasios, Langston, M. H., McMahon, Janice O., Meister, Benoit J., Mountcastle, Paul D., Naqvi, Aale, Pradelle, Benoit, Ramananandro, Tahina, Tavarageri, Sanket, Lethin, Richard A.
• Primary Examiner(s): Vo, Ted T.
• Application Number:
  US14/987,202
• Publication Number:
  US 20160196121A1
• Time in Patent Office: 1,478 Days
• Field of Search: 717151-161
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0671 In-line storage system
• CPC Class Codes: G06F 8/4432 Reducing the energy consumption
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code
• CPC Class Codes: G06F 8/453 Data distribution
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A compilation system using an energy model based on a set of generic and practical hardware and software parameters is presented. The model can represent the major trends in energy consumption spanning potential hardware configurations using only parameters available at compilation time. Experimental verification indicates that the model is nimble yet sufficiently precise, allowing efficient selection of one or more parameters of a target computing system so as to minimize power/energy consumption of a program while achieving other performance related goals. A voltage and/or frequency optimization and selection is presented which can determine an efficient dynamic hardware configuration schedule at compilation time. In various embodiments, the configuration schedule is chosen based on its predicted effect on energy consumption. A concurrency throttling technique based on the energy model can exploit the power-gating features exposed by the target computing system to increase the energy efficiency of programs.

Claims

1. A method for optimizing energy consumption of a data processor while executing a program, the method comprising performing by a compilation processor the steps of:

(a) generating within the program a first power-coherent region;

(b) computing using an energy model a plurality of estimated energy consumption values for the first power-coherent region, each value corresponding to a respective power setting;

(c) identifying an energy-minimizing power setting corresponding to a minimum of the plurality of the estimated energy consumption values; and

(d) inserting in the first power-coherent region a power setting operation setting at least one parameter of the data processor according to the energy-minimizing power setting,

wherein generating the first power-coherent region comprises performing by the compilation processor the steps of;

partitioning program instructions into a plurality of groups, each group having a specified number of instructions and a statically determined type, the type being either computation intensive or memory intensive; and

statically determining a type of a first group and merging another group into the first group if the type of the first group after the merging would not change and, otherwise designating the other group as a second group.

2. The method of claim 1, wherein each of the steps (a) through (d) is performed by the compilation processor via static analysis of the program and without executing any portion of the program.

3. The method of claim 1, wherein at least one of the steps (a) and (b) is based on a polyhedral model of the program.

4. The method of claim 1, wherein the type of the first group comprises one of compute intense and memory intense.

5. The method of claim 1, further comprising designating a group having a number of instructions at most equal to a specified threshold as a default power-coherent region.

6. The method of claim 1, wherein the energy model comprises at least one of:

an operating frequency of the data processor, an operating voltage of the data processor, a number of processing units in the data processor, a number of computations in the first power-coherent region, an amount of memory accessed by the first power-coherent region from a first memory level, power consumed by a unit of the data processor during one computation at a specified frequency, power consumed by a unit of the data processor for accessing one byte of data from a specified level of memory at the specified frequency, performance of a unit of the data processor at the specified frequency, and available bandwidth of the data processor at the specified level and using a specified number of processing units.

7. The method of claim 1, wherein computing an estimated energy consumption value corresponding to a frequency setting comprises computing at least one of:

energy consumed by a plurality of computational operations in the program using;

a total number of computational operations in the first power-coherent region and average energy consumed by a single computational operation at the frequency setting; and

energy consumed by a plurality of memory access operations in the first power-coherent region using;

a total number of memory accesses within the first power-coherent region at least one memory level, available memory access bandwidth at the at least one memory level at the frequency setting, average power consumption by a single memory access operation at the frequency setting, and a number of processing units in the data processor.

8. The method of claim 7, wherein the available memory access bandwidth at the at least one memory level at the frequency setting comprises one of:

a memory access bandwidth computed as function of;

(i) a memory access bandwidth required by one processing unit at the at least one memory level at the frequency setting, and (ii) the number of processing units in the data processor; and

a maximum memory access bandwidth available at the at least one memory level at the frequency setting.

9. The method of claim 7, further comprising:

computing a number of memory accesses required by a data structure within the first power-coherent region;

computing a stride between consecutive memory accesses by the data structure;

if the stride does not exceed a bulk-transfer size associated with a first memory level, associating the number of memory accesses required by the data structure with the first memory level; and

otherwise associating the number of memory accesses required by the data structure with a second memory level.

10. The method of claim 1, wherein the power setting operation setting at least one parameter of the data processor:

is inserted at a beginning of the first power-coherent region; and

adjusts at least one of a frequency of the data processor and an operating voltage of the data processor.

11. The method of claim 10, further comprising:

inserting at an end of the first power-coherent region another power setting operation that at least one of;

(i) adjusts a frequency of the data processor to a default frequency, and (ii) adjusts an operating voltage of the data processor to a default operating voltage.

12. The method of claim 11, further comprising:

identifying a second power-coherent region within execution proximity of the first power-coherent region;

comparing;

(i) the power setting operation inserted at the beginning in the first power-coherent region, (ii) the power setting operation inserted at the end in the first power-coherent region, and (iii) a power setting operation inserted in the second power-coherent region; and

based on the comparison, removing at least one of;

(i) the power setting operation inserted at the end in the first power-coherent region, and (ii) the power setting operation inserted in the second power-coherent region.

13. A method for optimizing energy consumption of a data processor comprising a plurality of N^T processing units, the method comprising performing by a compilation processor the steps of:

computing for a particular operation frequency, a required single-unit resource capacity for a specified resource, for executing a specified program using one unit of the plurality of N^T processing units;

computing using the single-unit resource capacity a maximum number of processing units N_max, such that using more than N_max processing units would exceed an available resource capacity of the specified resource, at the particular operation frequency; and

inserting into the program by the compilation processor a command execution of which causes at least one and up to (N^T-N_max) processing units to enter a sleep mode when a number of processing units operating concurrently exceeds N_max.

14. The method of claim 13, wherein:

the resource comprises data-processor memory bandwidth; and

the resource parameter comprises a memory level.

15. The method of claim 13, wherein the resource comprises data-processor input-output (I/O) bandwidth.

16. A method for optimizing energy consumption of a data processor comprising a plurality of processing units, the method comprising performing by a compilation processor the steps of:

computing for a particular operation frequency and a particular memory level, a required single-unit memory bandwidth for executing a specified program using one unit of the plurality of processing units;

computing using the single-unit memory bandwidth a maximum number of processing units N_max, such that using more than N_max processing units would exceed an available memory bandwidth at the particular operation frequency and the particular memory level;

for each value of a number of processing units N in a range from 1 up to N_max, estimating using an energy model an energy consumption for executing the specified program using N processing units;

determining an optimized number of processing units N_opt for which;

a difference between the estimated energy consumption using N_opt processing units and using N_maxprocessing units is greater than a specified percentage of the estimated energy consumption using N_max processing units; and

a difference between performance using N_opt processing units and using N_max processing units is less than a specified percentage of the performance using N_maxprocessing units; and

inserting into the program by the compilation processor a command execution of which causes at least one processing unit to enter a sleep mode when a number of processing units operating concurrently exceeds the optimized number of processing units N_opt.

17. The method of claim 16, wherein computing the required single-unit memory bandwidth comprises:

computing a stride distance between two consecutive memory accesses associated with the particular memory level from a selected portion of the specified program; and

comparing the stride distance with a size of single access at the particular memory level.

18. The method of claim 16, wherein the energy model comprises:

the number of processing units; and

at least one of;

an operating frequency of the data processor, an operating voltage of the data processor, a number of computations in a program, an amount of memory at a specified level accessed by the program;

power consumed by a unit of the data processor during one computation at a specified frequency, power consumed by a unit of the data processor for accessing one byte of data from a specified level of memory at the specified frequency, and performance of a unit of the data processor at the specified frequency.

19. The method of claim 16, further comprising setting by the compilation processor a degree of maximum parallelization to the optimized number of processing units N_opt.