Source: http://www.freepatentsonline.com/9003215.html
Timestamp: 2017-12-13 18:57:47
Document Index: 672096195

Matched Legal Cases: ['application No. 200980112179', 'application No. 2010139638', 'application No. 2011', 'application No. 200980112179', 'application No. 2009801121791', 'Application No. 98105020']

Power-aware thread scheduling and dynamic use of processors - Microsoft Technology Licensing, LLC
Power-aware thread scheduling and dynamic use of processors
United States Patent 9003215
Techniques and apparatuses for providing power-aware thread scheduling and dynamic use of processors are disclosed. In some aspects, a multi-core system is monitored to determine core activity. The core activity may be compared to a power policy that balances a power savings plan with a performance plan. One or more of the cores may be parked in response to the comparison to reduce power consumption by the multi-core system. In additional aspects, the power-aware scheduling may be performed during a predetermined interval to dynamically park or unpark cores. Further aspects include adjusting the power state of unparked cores in response to the comparison of the core activity and power policy.
Marshall, Allen (Woodinville, WA, US)
Ritz, Andrew J. (Sammamish, WA, US)
Deng, Yimin (Sammamish, WA, US)
Judge, Nicholas S. (Bellevue, WA, US)
13/214545
713/320, 713/324, 718/105
G06F1/32; G06F9/50
713/320, 713/323, 713/324, 718/105
Download PDF 9003215 PDF help
7992151 Methods and apparatuses for core allocations 2011-08-02 Warrier et al. 718/104
7966506 Saving power in a computer system 2011-06-21 Bodas et al. 713/323
7962770 Dynamic processor reconfiguration for low power without reducing performance based on workload execution characteristics 2011-06-14 Capps et al. 713/300
7900069 Dynamic power reduction 2011-03-01 Allarey 713/320
20090249094 POWER-AWARE THREAD SCHEDULING AND DYNAMIC USE OF PROCESSORS 2009-10-01 Marshall et al.
7318164 Conserving energy in a data processing system by selectively powering down processors 2008-01-08 Rawson, III
7315952 Power state coordination between devices sharing power-managed resources 2008-01-01 Wilcox et al.
20070234088 Identifying a target processor idle state 2007-10-04 Marshall et al.
20070220289 Scaling idle detection metric for power management on computing device 2007-09-20 Holle et al.
7174467 Message based power management in a multi-processor system 2007-02-06 Helms et al.
7137117 Dynamically variable idle time thread scheduling 2006-11-14 Ginsberg
20060212677 Multicore processor having active and inactive execution cores 2006-09-21 Fossum
7111182 Thread scheduling mechanisms for processor resource power management 2006-09-19 Gary
20060149975 Operating point management in multi-core architectures 2006-07-06 Rotem et al.
20060123251 Performance state-based thread management 2006-06-08 Nakajima et al.
20060090161 Performance-based workload scheduling in multi-core architectures 2006-04-27 Bodas et al.
20060004988 Single bit control of threads in a multithreaded multicore processor 2006-01-05 Jordan
20050273635 Power state coordination between devices sharing power-managed resources 2005-12-08 Wilcox et al.
6901522 System and method for reducing power consumption in multiprocessor system 2005-05-31 Buch
20050050373 Distribution of processing activity in a multiple core microprocessor 2005-03-03 Orenstien et al.
JP9185589 July, 1997
JP2000112585A 2000-04-21 SYSTEM LSI AND POWER MANAGEMENT METHOD
JP2006302059A 2006-11-02 COMPOSIT TYPE COMPUTING DEVICE AND ITS MANAGEMENT METHOD
JP200937335 February, 2009
RU2171490C2 2001-07-27 MULTIPROCESSOR COMPUTER SYSTEM HAVING COHERENT CASH WITH REDUCED POWER CONSUMPTION
TW200809469A 2008-02-16 Predict computing platform memory power utilization
JPH09185589A 1997-07-15
JP2009037335A 2009-02-19
Chinese Office Action mailed Jan. 18, 2013 for Chinese patent application No. 200980112179.7, a counterpart foreign application of US patent No. 8,010,822, 10 pages.
Russian Office Action mailed Dec. 11, 2012 for Russian patent application No. 2010139638, a counterpart foreign application of US patent No. 8,010,822, 4 pages.
Japanese Office Action mailed Mar. 28, 2012 for Japanese patent application No. 2011-501858, a counterpart foreign application of US patent No. 8,010,822, 3 pages.
Chinese Office Action mailed Apr. 27, 2012 for Chinese patent application No. 200980112179.7, a counterpart foreign application of US patent No. 8,010,822, 12 pages.
Isci et al., “An Analysis of Efficient Multi-Core Global Power Management Policies: Maximizing Performance for a Given Power Budget”, 39th Annual IEEE/ACM Intl Symposium on Microarchitecture, 2006, 12 pgs.
Kumar et al., “Processor Power Reduction via Single-ISA Heterogeneous Multi-Core Architectures”, Computer Architecture Letters, Apr. 2003, 4 pgs.
Pallipadi et al., “Processor Power Management features and Process Scheduler: Do we need to tie them together?”, Intel Open Source Technology Center, 2007, pp. 1-8.
Chinese Office Action mailed Apr. 15, 2013 for Chinese patent application No. 2009801121791, a counterpart foreign application of US patent No. 8,010,822, 7 pages.
PCT Search Report for PCT Application No. PCT/US2009/034209, mailed Sep. 1, 2009 (10 pages).
“Search Report Issued in Taiwan Patent Application No. 98105020”, Dated: Feb. 6, 2014, Filed Date: Feb. 17, 2009, 1 Page.
The present application is a continuation of U.S. patent application Ser. No. 12/057,716 (currently referenced as U.S. Patent Publication No. 2009/0249094), filed on Mar. 28, 2008, which is hereby incorporated by reference in its entirety.
1. A method for balancing performance and power savings of a computing device having multiple cores, comprising: determining which cores of the multiple cores are actively processing work; determining a power policy to initiate a performance and power savings plan for the multiple cores, wherein determining the power policy comprises calculating which cores are designated as parked or unparked based at least in part on an available processor set and on a distribution of the multiple cores over multiple core blocks; and parking at least one of the cores actively processing work based at least in part on the power policy indicating that the one of the cores actively processing work is designated as a parked core.
2. The method of claim 1, wherein the determining the power policy occurs dynamically as an iterative process.
4. The method of claim 3, wherein the scaling the at least one of the multiple cores includes adjusting at least one of a core utility or a power state (p-state) of a core to increase power savings.
5. The method of claim 1, wherein the parking at least one of the multiple cores includes: determining if an unparked core block of the multiple core blocks includes a parked core; and if the unparked core block is determined to have the parked core, parking at least one unparked core in the unparked core block before parking a different unparked core in a different core block of the multiple core blocks.
6. The method of claim 1, further comprising modifying the power policy using at least one of: core and system heuristics; processor dependency relationship; and core policy parameters for core parking.
8. The method of claim 1, wherein determining the power policy comprises providing at least a portion of the performance and power savings plan for the cores by combining a core parking mask and a thread processor affinity mask.
9. One or more computer storage memories comprising computer-executable instructions that, when executed by a computer, perform acts comprising: monitoring core activity in a multi-core system; retrieving a power policy for the multi-core system, the power policy balancing power savings and processing performance of individual cores in the multi-core system; unparking at least one core of multiple cores based at least partly on the core activity and the power policy; reassigning at least one thread of a plurality of threads to the at least one unparked core; and causing the at least one thread to be executed on the at least one unparked core in addition to causing one or more additional threads of the plurality of threads to be executed on one or more previously unparked cores of the multiple cores.
10. One or more computer storage memories as in claim 9, wherein the acts further comprise adjusting the power state of one or more previously unparked cores of the previously unparked cores.
11. One or more computer storage memories as in claim 9, wherein the unparking the least one core based at least partly on the core activity is dynamically initiated at a predetermined frequency.
12. One or more computer storage memories as in claim 9, wherein the acts further comprise monitoring the core activity in the multi-core system for a predetermined time period.
13. One or more computer storage memories as in claim 9, wherein the unparking the at least one core comprises unparking a core of the multiple cores in a core block that includes at least one other unparked core, wherein the core block has a level of power dissipation when any of the cores in the core block are unparked.
14. One or more computer storage memories as in claim 9, wherein the acts further comprise parking at least one other core of the multiple cores in response to the core activity based on the power policy.
15. A multiple logical processor system, comprising: a plurality of processors, wherein the plurality of processors include at least one core block having multiple cores; and a controller coupled to the plurality of processors, the controller to: implement a performance schedule; implement a power savings policy; balance the performance schedule and the power savings policy by parking one or more cores of the multiple cores; and reassign two or more threads from the parked one or more cores to two or more unparked cores of the multiple cores.
17. The system of claim 15, wherein the controller adjusts a p-state of at least one unparked core.
18. The system of claim 15, wherein the power savings policy restricts a number of cores to be used and expresses the number of cores to be used as a percentage of maximum core utilization.
19. The system of claim 15, wherein the power savings policy includes a core parking mask, the core parking mask and one or more program module schedules to determine a resulting set of processors on which to schedule work.
20. The system of claim 15, wherein the balancing the performance schedule and the power savings policy further comprises creating a core parking prioritization for an unparked core in a core block having at least one parked core.
Computer system management of power consumption is important to extend the operational ability of a battery and to reduce overall power consumption, which can be both fiscally and environmentally beneficial. Even for non-mobile computers, reducing power requirements is beneficial to save important global resources and prolong operation when relying on a battery backup system, such as during a utility power interruption.
Although most components of a computing system use power during system operation, the processor uses a disproportionate share of the system power. Many computer systems, including consumer based systems, include multiple processors and/or processors with multiple cores. Multiple processors enable the computers to execute increasing levels of work in parallel however additional processors may also increase power consumption. Most modern processors feature very low power idle power states, which may be applied per-core on a multi-core system, and which may be controlled by an operating system. In addition, processor frequency may be scaled on a per-core or per core group basis to reduce power usage by the system.
This summary is provided to introduce simplified concepts of providing power-aware thread scheduling and dynamic use of processors, which is further described below in the Detailed Description. This summary is not intended to identify essential features of the claimed subject matter, nor is it intended for use in determining the scope of the claimed subject matter.
Processors may enable low power idle power states, including an idle state that consumes no power (zero watts). An operating system may direct one or more processors (or simply “cores”) to an idle power state (i.e., processor sleep state) when there is no useful work to perform. Maximizing time spent in these low power states may increase system energy efficiency and/or extend battery performance. In addition to these processor idle power states, processors may also provide controls for scaling the processor's frequency, either alone or in conjunction with a simultaneous reduction in processor core voltage. These controls can be collectively referred to as processor power management (PPM) features.
Therefore, the PPM may reduce power demands by directing unused processors to a low power state or a sleep state (“parked” state) when the processors do not have adequate workload to justify higher power states. Parked cores may be placed in a processor idle power state (ACPI C-state) using a minimal amount of power or no power at all. The active work to be done on the system will be time multi-plexed on the unparked processors.
FIG. 1 is an illustrative system 100 that may be used to implement at least one embodiment of power-aware thread scheduling and dynamic use of processors. The system 100 includes a computing device 102. For example, the computing device may be a mobile computer 102(1), a desktop computer 102(2), and/or a server 102(N), among other possible computing devices. In a very basic configuration, computing device 102 typically includes one or more processors (“processors”) 104. For example, the processors 104 may be at least one of multiple independent processors configured in parallel or in series and a multi-core processing unit, either singly or in various combinations. A multi-core processor may have two or more processors (“cores”) included on the same chip or integrated circuit. The terms “processor,” “core,” and “logical processor” may be used interchangeable throughout this disclosure unless specifically stated otherwise with reference to a particular element.
The computing device 102 may have additional features or functionality. For example, the computing device 102 may also include additional data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Such additional storage is illustrated in FIG. 1 by a removable storage 118 and a non-removable storage 120. The computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. The system memory 106, the removable storage 118, and the non-removable storage 120 are all examples of the computer storage media. Thus, the computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by the computing device 102. Any such computer storage media may be part of the computer device 102.
The computing device 100 may also include a communication connection 126 that allows the device to communicate with other computing devices, such as over a network. The communication connection 126 is one example of communication media. The communication media may typically be embodied by computer readable instructions, data structures, or program modules. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. The computer readable media can be any available media that can be accessed by the computing device 102. By way of example, and not limitation, the computer readable media may comprise the “computer storage media” and the “communications media.”
As shown in FIG. 2, a core parking mask is created in the system memory at 202. For example, the kernel power manager 114 may create the core parking mask at 202, which resides in the operating system 108. An illustrative core parking mask (“bit mask” or simply “mask”) 204 may provide a cell representing a corresponding core. As shown in FIG. 2, the illustrative system includes eight cores, however more or fewer cores may be used. The bit mask 204 includes a bit value in each cell, where “1” represents a parked core and “0” represents an unparked core. A parked core is a core that is placed into a low power sleep state. In some embodiments, a parked core has no power consumption, thus uses zero watts. In some embodiments, cores have dependencies such as shared hardware circuitry. If both cores can be put into a low power state, dependencies can also be implicitly placed into a low power state. Thus a core parking mask can be selected which will maximize power savings compared to another mask. For example, turning off all cores in a single processor socket might save more power than turning off half the cores in two processor sockets. The bit mask 204 includes four parked cores, numbered (right to left, zero to seven): 3, 5, 6, and 7. It follows that cores 0, 1, 2, and 4 are unparked cores.
In accordance with one or more embodiments, the bit mask 204 may be inverted at 206 to create the inverted bit mask 208. For example, the kernel power manager 114 may create the inverted bit mask 208. The inverted bit mask includes an inverted bit value for each cell (i.e., core). Accordingly, cores designated with a “1” may be preferred to process data while cores designated with a “0” may not be preferred to process application threads.
In some embodiments, at 214 the program module affinity masks 212 are combined, one at a time, with the inverted bit mask 208 using an “AND” operator 216 to determine the set of eligible processors for an available processor set 218. At 220, the first affinity mask 212(1) is used to create a first available processor set 218(1). The process 200 may include an iterative process of operations 210, 214, and 220 for each program module (i.e., for each combination of the inverted bit mask 208 and the affinity mask 212). Thus, the second affinity mask 212(2) is used to create a second available processor set 218(2) during a second iteration of the operations 210, 214, and 220, and so forth.
As discussed above, the bit values for each core (e.g., core 0, . . . , core 7) are used to determine the available processor set 218 for scheduling threads. The “AND” operator 216 returns a core bit value of “1” where both of the operands (i.e., combined bit values for a core) include a “1” representing a thread affinitized to a specific core. For example, when the first affinity mask 212(1) is combined with the inverted bit mask 208, cores 0 and 1 both are active cores and will return a core bit value of “1” while the remaining cores 2-7 include a core bit value of “0,” as illustratively shown in the first available processor set 218(1).
The second affinity mask 212(2) includes a core value of “1” at core 3, while the inverted bit mask 208 indicates core 3 is parked. The kernel scheduler 116 may choose to override the inverted bit mask to accommodate the second affinity mask 212(2), which is represented in the second available processor set 218(2) where core 3 includes a core value of “1,” therefore shifting work to a core designated as parked in the inverted bit mask 208 (which may be subsequently unparked). In some embodiments, the thread may be scheduled using any number of heuristics. An optimal core in the thread's affinity may be used while ignoring the inverted bit mask 208. If the optimal core is parked, a fallback may include selecting a processor in the same NUMA (non-uniform memory access) node as the preferred core. The scheduler treats the core parking inverted mask as a hint of preferred locations to run the thread, but it will choose amongst the hard limitation (the hard affinity) of what it believes to be the most performant option.
Where all cores are designated as available, such as in the affinity mask 212(P), the bit value may be ignored because the program module is indicated that it allows the threads to be executed by any core. The affinity mask 212(P) may include scheduled cores at any of the cores indicated by the inverted bit mask 208, such as cores 0, 1, 2, and 4, as represented by the available processor set 218(P) by core values showing “1/0” (either “1” or “0”, while at least one core must have a core value of “1” to enable scheduling the work of the affinity mask 212(P)). In some embodiments, the available processor set 218(P) may select cores that are unparked and idle when determining an allocation of work to available cores. Ideally, work shifting may allocate work to cores 0, 1, 2, and 3, thus leaving core 4 unused and possibly parked in a subsequent action. Other considerations, as discussed below, may determine which cores are allocated work in response to the affinity mask 212(P) to create a preferred location. For example, a preferred location may be based on factors such as optional memory access performance.
In accordance with one or more embodiments, FIG. 2 illustrates an example core usage 222 for a time slice. For example, a combination of the cores that are active from the available processor set 218 may result in the core usage 222 during a given time check interval, such as without limitations 100 milliseconds. The core 4 in the core usage 222 may or may not indicated as used depending on whether work is scheduled to core 4 in the available processor set 218(P), as discussed above. From the perspective of the kernel power manager 114, the core usage 222 will ideally include a core value of “0” for core 4, thus minimizing the number of unparked cores and resulting in a reduction of power consumption. Regardless of the core usage 222, a new core parking mask may be created for the next time slice, which may use information from the core usage 222 to determine the new core parking mask. In some instances, core 3 may not be required because core 2 may have enough processing utilization to satisfy the second affinity mask 212(2) and is still an unparked core.
Each core includes a core utilization (“core utility”) 310 that represents the workload of that core, expressed as the percentage of a core's run time out of the total time, independent of the core's performance state. For example, the core 0 302 may have a core utility of 80% indicating that the core is doing 20% less work than the workload maximum capacity of core “0.” Accordingly, a core utility of 100% represents a core working a maximum capacity while a core having a 0% core utility represents an unused core. In some embodiments, the kernel power manager 114 may monitor the core utility 310.
Each core includes an output utilization value (“output utility”) 314 that represents the workload of the core in relation to the total workload capacity. For example, the output utility 314 may have a scale of 0-10,000 where 0 represents no utilization and 10,000 represents maximum utilization. The output utility 314 may be calculated by multiplying the core utility 310 and the p-state 312. For example, the core 0 302 includes a core utility of 80% and a p-state of 80%, therefore the output utility is 6,400. In some embodiments, the output utility 314 is used by the kernel power manager 114 to determine core parking decisions and/or determine p-state 312 settings, such as with reference to the power policy.
In some embodiments, the system 300 may include a core block 316, such as a first core block 316(1) and a second core block 316(2), however more or fewer core blocks may be implemented in the system 300. The core block 316 may represent a platform having multiple cores with a single circuit, such as a dual-core or multi-core processor. Each core block 316 may include unique power consumption characteristics. For example, a core may include active level power consumption, core leakage, or other power dissipations which occur when either of the cores in the block is unparked. For example, if both cores in the first core block 316(1) are unparked and have the output utility of 10,000, the combined power consumption may be 2x watts. If the core 0 302 in the first core block 316(1) is subsequently parked (e.g., output utilization is 0) and the core 1 304 remains unchanged, the combined power consumption may be greater than x watts because of factors associated with the core block 316 such as power leakage, active power consumption, and/or other factors. When the core 1 is subsequently parked, the resultant power consumption may be 0 watts. Therefore, it may be advantageous to park cores such that entire core blocks become parked before other cores are subsequently parked, thus maximizing power savings.
In an example utilization scenario, the kernel power manager 114 may calculate the output of system 300 to determine a total system utility of 12,600 (i.e., 6,400+3,200+3,000=12,600) of a maximum total system utility of 30,000 (i.e., 3 unparked cores×10,000=30,000). The utilization numbers referenced above are intended to be explanatory in nature of calculations that may be performed using the total system utility, and thus are not limiting to the disclosure.
When a second core is parked, the maximum total system utility of the revised system will drop to 20,000 (2 cores×10,000). The kernel power manager 114 may park any of the cores which were active in the previous state (as shown in FIG. 3A). As discussed above, it may be advantageous to park core 2 306 to completely park the second core block 316(2), resulting in a parked core block 320. Accordingly, the parked core block 320 may increase power saving as compared to parking the core 0 302 or the core 1 304 instead of the core 2 306.
In accordance with one or more embodiments, a “TimeCheck” periodic evaluation routine may begin at 502. For example, a deferred procedure call (DPC) may begin at 502. In some embodiments, a state machine is entered on each core via the DPC running at a fixed periodic rate configured by a power policy parameter “TimeCheck” for a time value, such as 100 ms, 50 ms, or another time value. At 504, the kernel power manager 114 may gather metrics for the cores. For example, the DPC is queued to each currently active core to snap metrics for the active cores. The metrics may include core utilization, thread priority distribution, an average wait time for ready threads for each core, and/or success and failure metrics for idle state residency, among other possible metrics.
At 706(2), the kernel power manager 114 may implement an increase and/or decrease policy. For example, a first policy option may only park a set number of cores at a time, such as one core at a time. A second policy option may park or unpark cores to achieve ideal core utilization, thus parking and/or unparking multiple cores at a time. A third policy may go to one extreme or the other (either park as many as possible or unpark as many as possible).
At 714, the core package (block) relationships may be considered, such as dependencies described in FIGS. 3A and 3B regarding the efficiencies of a core block, and more specifically parking a core block before parking another core in a new core block. Finally, at 716, memory locality may be used by the kernel power manager 114 when implementing core parking considerations. For example, two or more cores may have package relationships such as the cores sharing a physical processor package having a shared memory bank (e.g., NUMA (non-uniform memory access) node). The shared memory bank may enable the cores to have reduced memory access time as compared to cores that do not share the shared memory bank
The above-described techniques, systems, and apparatuses pertain to providing power-aware thread scheduling and dynamic use of processors. Although the techniques, systems, and apparatuses have been described in language specific to structural features and/or methodological acts, it is to be understood that the appended claims are not necessarily limited to the specific features or acts described. Rather, the specific features and acts are disclosed as exemplary forms of implementing such techniques and apparatuses.
<- Previous Patent (Circuit, system and ...) | Next Patent (Power regulation of ...) ->