Patent Description:
An electronic component consumes (dissipates) power to operate, which generates heat within the component. The heat causes a temperature to rise within the component. Cooling systems that carry away the heat help to manage the component temperature. Another way to manage the temperature is to govern the power used by the component. For example, a central processing unit (CPU) may be associated with a power budget that limits the power usage above which the CPU is not allowed to operate. An on-chip controller (OCC) throttles the CPU operating frequency to prevent exceeding the power budget limit.

<CIT> describes a method of power management of a system of connected components includes initializing a token allocation map across the connected components, wherein each component is assigned a power budget as determined by a number of allocated tokens in the token allocation map, monitoring utilization sensor inputs and command state vector inputs, determining, at first periodic time intervals, a current performance level, a current power consumption level and an assigned power budget for the system based on the utilization sensor inputs and the command state vector inputs, and determining, at second periodic time intervals, a token re-allocation map based on the current performance level, the current power consumption level and the assigned power budget for the system, according to a re-assigned power budget of at least one of the connected components, while enforcing a power consumption limit based on a total number of allocated tokens in the system. <CIT> describes apparatus and methods that provide for a central power control unit to grant a power allowance to each of a plurality of computer components and to allocate a shared power pool locally accessible to each of the plurality of computer components when one or more of the plurality of components needs to exceed its granted power allowance. <CIT> describes a method, circuit arrangement, and program product for dynamically reallocating power consumption at a component level of a processor. Power tokens representative of a power consumption metric are allocated to interconnected IP blocks of the processor, and as additional power is required by an IP block to perform assigned operations, the IP block may communicate a request for additional power tokens to one or more interconnected IP blocks. The interconnected IP blocks may grant power tokens for the request based on a priority, availability, and/or power consumption target. The requesting IP block may modify power consumption based on power tokens granted by interconnected IP blocks for the request. A power management block may adjust power token allocation of one or more IP blocks by communicating a command to one or more IP blocks and/or by adjusting a power token request.

According to aspects of the present invention, a method, computer program product and system are provided that perform the following operations (not necessarily in the following order): (i) receiving, by a token pool, a power allowance request from a first power consuming device, of a plurality of power consuming devices of an integrated circuit; (ii) in response to receiving the power allowance request, the token pool determining a second power consuming device, of the plurality of power consuming devices, has a power allowance surplus; (iii) in response to determining the second power consuming device has a power allowance surplus, receiving the power allowance surplus from the second power consuming device; (iv) transferring, via the token pool, the power allowance surplus to the first power consuming device; and (v) in response to transferring the power allowance surplus to the first power consuming device: (a) increasing a first power usage limit corresponding to the first power consuming device, based on the power allowance surplus, and (b) decreasing a second power usage limit corresponding to the second power consuming device, based on the power allowance surplus.

In some embodiments of the present invention, a power management system employs a ring topology (a distributed token passing mechanism) to distribute a fixed number of power tokens among frequency domains of an electronic module. Each power token represents a fraction of the total power the electronic module is permitted to dissipate. The fixed number of power tokens collectively represent the pre-determined maximum power consumption (dissipation) budgeted for the electronic module.

An electronic module may have several frequency domains. Each frequency domain operates at a clock frequency that is controllable and independent of other frequency domains of the electronic module. A higher operating frequency means the frequency domain can process workload at a higher rate, while consequently dissipating more power. In some embodiments, a CPU core (in a multiple core CPU) is an example of such a frequency domain. Power dissipated by the several frequency domains fluctuates according to respective workloads. The power management system offers power tokens from a rotating token pool, which polls or addresses, in round-robin fashion (using a ring topology), each frequency domain in turn. A frequency domain, in conjunction with interacting with the token pool, may accept additional tokens from the token pool if needed (and available), or donate unneeded tokens to the token pool. A frequency domain in need of more power tokens (in a "power deficit" state) when the token pool has no power tokens (or not enough power tokens) available will wait for tokens to be relinquished by other frequency domains to the token pool. Other frequency domains, at their respective turns interacting with the token pool, may respond by placing unneeded (surplus) power tokens onto the token pool. Once the token pool circles back around and again interacts with the power deficit domain, the power deficit domain can acquire the available power tokens from the token pool.

A frequency domain operates at a frequency in accordance with the number of power tokens held by the frequency domain. Overall, an electronic module (having multiple frequency domains) stays within an assigned power budget (represented by the total number of power tokens distributed among the multiple frequency domains), while performing its workload more efficiently.

This Detailed Description section is divided into the following sub-sections: (i) The Hardware and Software Environment; (ii) Example Embodiment; (iii) Further Comments and/or Embodiments; and (iv) Definitions.

An embodiment of a possible hardware and software environment for software and/or methods according to the present invention will now be described in detail with reference to the Figures. <FIG> is a functional block diagram illustrating various portions of networked computers system <NUM>, including: server system <NUM>; client computer <NUM>; communication network <NUM>; server computer <NUM>; communications unit <NUM>; processor set <NUM>; input/output (I/O) interface set <NUM>; memory <NUM>; persistent storage <NUM>; display <NUM>; external devices <NUM>; random access memory (RAM) <NUM>; cache memory <NUM>; and power management program <NUM>.

Server system <NUM> is, in many respects, representative of the various computer sub-system(s) in the present invention. Accordingly, several portions of server system <NUM> will now be discussed in the following paragraphs.

Server system <NUM> may be a laptop computer, tablet computer, netbook computer, personal computer (PC), a desktop computer, a personal digital assistant (PDA), a smart phone, or any programmable electronic device capable of communicating with the client sub-systems via communication network <NUM>. Power management program <NUM> is a collection of machine readable instructions and/or data that is used to create, manage, and control certain software functions that will be discussed in detail, below, in the Example Embodiment sub-section of this Detailed Description section.

Server system <NUM> is capable of communicating with other computer sub-systems via communication network <NUM>. Communication network <NUM> can be, for example, a local area network (LAN), a wide area network (WAN) such as the Internet, or a combination of the two, and can include wired, wireless, or fiber optic connections. In general, communication network <NUM> can be any combination of connections and protocols that will support communications between server and client sub-systems.

Server system <NUM> is shown as a block diagram with many double arrows. These double arrows (no separate reference numerals) represent a communications fabric, which provides communications between various components of server system <NUM>. This communications fabric can be implemented with any architecture designed for passing data and/or control information between processors (such as microprocessors, communications and network processors, etc.), system memory, peripheral devices, and any other hardware components within a system. For example, the communications fabric can be implemented, at least in part, with one or more buses.

Memory <NUM> and persistent storage <NUM> are computer-readable storage media. In general, memory <NUM> can include any suitable volatile or non-volatile computer-readable storage media. It is further noted that, now and/or in the near future: (i) external devices <NUM> may be able to supply, some or all, memory for server system <NUM>; and/or (ii) devices external to server system <NUM> may be able to provide memory for server system <NUM>.

Power management program <NUM> is stored in persistent storage <NUM> for access and/or execution by one or more of the respective computer processor set <NUM>, usually through one or more memories of memory <NUM>. Persistent storage <NUM>: (i) is at least more persistent than a signal in transit; (ii) stores the program (including its soft logic and/or data), on a tangible medium (such as magnetic or optical domains); and (iii) is substantially less persistent than permanent storage. Alternatively, data storage may be more persistent and/or permanent than the type of storage provided by persistent storage <NUM>.

Power management program <NUM> may include both machine readable and performable instructions and/or substantive data (that is, the type of data stored in a database). In this particular embodiment, persistent storage <NUM> includes a magnetic hard disk drive. To name some possible variations, persistent storage <NUM> may include a solid state hard drive, a semiconductor storage device, read-only memory (ROM), erasable programmable read-only memory (EPROM), flash memory, or any other computer-readable storage media that is capable of storing program instructions or digital information.

Other examples include optical and magnetic disks, thumb drives, and smart cards that are inserted into a drive for transfer onto another computer-readable storage medium that is also part of persistent storage <NUM>.

Communications unit <NUM>, in these examples, provides for communications with other data processing systems or devices external to server system <NUM>. In these examples, communications unit <NUM> includes one or more network interface cards. Communications unit <NUM> may provide communications through the use of either or both physical and wireless communications links. Any software modules discussed herein may be downloaded to a persistent storage device (such as persistent storage <NUM>) through a communications unit (such as communications unit <NUM>).

I/O interface set <NUM> allows for input and output of data with other devices that may be connected locally in data communication with server computer <NUM>. For example, I/O interface set <NUM> provides a connection to external devices <NUM>. External devices <NUM> will typically include devices such as a keyboard, keypad, a touch screen, and/or some other suitable input device. External devices <NUM> can also include portable computer-readable storage media such as, for example, thumb drives, portable optical or magnetic disks, and memory cards. Software and data used to practice embodiments of the present invention, for example, power management program <NUM>, can be stored on such portable computer-readable storage media. In these embodiments, the relevant software may (or may not) be loaded, in whole or in part, onto persistent storage <NUM> via I/O interface set <NUM>. I/O interface set <NUM> also connects in data communication with display <NUM>.

Display <NUM> provides a mechanism to display data to a user and may be, for example, a computer monitor or a smart phone display screen.

The programs described herein are identified based upon the application for which they are implemented in a specific embodiment of the invention. However, it should be appreciated that any particular program nomenclature, herein, is used merely for convenience, and, thus, the invention should not be limited to use solely in any specific application identified and/or implied by such nomenclature.

The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

<FIG> shows flowchart <NUM> depicting a method according to the present invention. <FIG> shows power management program <NUM> for performing at least some of the method operations of flowchart <NUM>. This method and associated software will now be discussed, over the course of the following paragraphs, with extensive reference to <FIG> (for the method operation blocks) and <FIG> (for the software blocks).

Processing begins at operation S252, where token pool <NUM>, of power management program <NUM>, traverses a plurality of frequency domains of an integrated circuit chip. In some embodiments, the integrated circuit chip is a central processing unit (CPU), and each frequency domain, for example first frequency domain <NUM> and second frequency domain <NUM>, is a core of the CPU. The frequency domains are organized in a ring topology. Token pool <NUM> traverses around the ring indefinitely, interacting in turn with each frequency domain. At each interaction between token pool <NUM> and a frequency domain, various events may take place including, but not limited to: (i) token pool <NUM> receives token(s) from the frequency domain; (ii) token pool <NUM> gives token(s) to the frequency domain; (iii) token pool <NUM> receives a "starvation" flag from the frequency domain, which signals that the frequency domain is in need for more tokens. At some interactions, neither tokens nor "starvation" flag are passed between token pool <NUM> and the frequency domain.

As token pool <NUM> traverses the ring, tokens tend to migrate away from frequency domains that have excess tokens, and to frequency domains that need more tokens. A token represents an increment of power or operating frequency that the frequency domain in possession of the token may use. The total number of tokens assigned to the CPU represents the total power the CPU may consume, thus keeping the CPU within a power budget so as not to exceed physical cooling capacity (and consequently temperature limits) of the CPU.

Constrained by the total number of tokens for the CPU, power management program <NUM> distributes the tokens among the frequency domains based on the relative workloads of the frequency domains. Heavily loaded frequency domains, therefore, tend to possess more tokens, and consequently may operate at higher frequencies (consume more power), so as to perform the workload more quickly. The converse holds true for lightly loaded frequency domains.

Processing proceeds at operation S255, where token pool <NUM>, of power management program <NUM>, interacts with first control module <NUM>, of first frequency domain <NUM> of power management program <NUM>. In connection with the interaction, token pool <NUM>, receives starvation flag <NUM> from first control module <NUM>. Starvation flag <NUM> is sometimes herein referred to as a "starvation token", a "power request", a "power allowance request", or similar terms. In some embodiments, starvation flag <NUM> includes information indicating a magnitude of power allowance requested by first control module <NUM>. Starvation flag <NUM> indicates that first control module <NUM>, due to current workload, requests permission to consume more power so as to process the current workload (or backlog thereof) more quickly. In some embodiments, control modules not running a heavy workload voluntarily donate excess tokens to the token pool, even in the absence of a starvation flag. The starvation flag is a new feature added to a conventional system that operates under "altruistic" (fair distribution based on workload requirements) principles. The starvation flag may indicate that the associated control unit urgently needs additional tokens to start performing an operation.

Token pool <NUM> interacts alternately with first control module <NUM> and second control module <NUM>. Some embodiments have many of frequency domains and many respectively corresponding control units. Regardless of how many frequency domains (and corresponding control units) are present in an embodiment, the frequency domains are organized into a ring topology. Token pool <NUM> interacts with the many control units in sequence around the ring topology, conducting interactions with the control units ad infinitum.

The embodiment depicted in <FIG> has two frequency domains (first frequency domain <NUM> and second frequency domain <NUM>) and two respectively corresponding power control modules (first control module <NUM> and second control module <NUM>). Token pool <NUM> interacts with first control module <NUM>, second control module <NUM>, and repeats this sequence ad infinitum, shifting relative power usage by the two control units according to current relative workloads being processed by the corresponding frequency domains (<NUM> and <NUM>). This approach maintains the total power usage of the two frequency domains within a predetermined limit such that: (i) cooling load does not exceed the capacity of the cooling system; (ii) device junction temperatures do not exceed design limits; (iii) device temperatures are not exceeded; and/or (iv) reliability requirements are not negatively impacted, etc..

Processing proceeds at operation S260, where token pool <NUM> interacts with second control module <NUM>, of second frequency domain <NUM>, of power management program <NUM>. In connection with the interaction, second control module <NUM>, having surplus power allowance available, and upon detecting starvation flag <NUM> present in token pool <NUM>, relinquishes to token pool <NUM>, surplus power allowance <NUM>. In some embodiments, surplus power allowance <NUM> has a power allowance magnitude up to the magnitude requested by starvation flag <NUM>.

By relinquishing surplus power allowance <NUM>, second frequency module <NUM> decreases the operating frequency of second frequency domain <NUM>. The amount of decrease in operating frequency is based on surplus power allowance <NUM>. The decrease in operating frequency means that second frequency domain <NUM> operates at a slower speed, consuming less power while performing assigned workload more slowly. This is a desirable consequence of relinquishing surplus power allowance <NUM> because the current workload assigned to second frequency domain is such that frequency domain <NUM> is idle for some time. Therefore, frequency domain <NUM> can still process workload in a timely fashion with less (or no) idle time.

Processing proceeds at operation S265, where token pool <NUM> again interacts with first control module <NUM>. In connection with the interaction, token pool <NUM> transfers surplus power allowance <NUM> to first control module <NUM>.

Processing proceeds at operation S270, where first frequency module <NUM>, of first frequency domain <NUM>, of power management program <NUM>, increases the operating frequency of first frequency domain <NUM>. The amount of increase in operating frequency is based on surplus power allowance <NUM>. The increase in operating frequency means that first frequency domain <NUM> operates at a faster speed, consumes more power, and performs assigned workload more quickly.

In some embodiments, first frequency domain <NUM> and second frequency domain <NUM> are physically integrated on a common device, such as (without limitation) a central processing unit (CPU) or other integrated circuit chip (not shown in the Figures). The increase in power used by first frequency domain <NUM> is offset by the decrease in power used by second frequency domain <NUM>. Consequently, the power collectively used by both frequency domains, and the cooling load of the common device, remains without significant change.

An electronic module may comprise a single integrated circuit chip, such as (but not limited to) a central processing unit (CPU), a set of integrated circuit chips mounted in a common package, a circuit card such as a computer motherboard, comprising many components, circuits in a smartphone, a single-board computer, a memory card, a storage controller, and any electronic device with an identifiable set of electronic devices operatively coupled and/or operating in concert. For simplicity herein, the terms "CPU" and "chip" should be understood as being synonymous and to encompass at least the above mentioned devices.

Some embodiments of the present invention may include one, or more, of the following features, characteristics, and/or advantages: (i) the total number of power tokens assigned to a chip is based, at least in part, on the power budget for the chip; (ii) passing the tokens (and corresponding power usage allowance) among frequency domains on the chip shifts the power requirements for respective frequency domains, while keeping the chip within the power budget limit; (iii) a distributed frequency control algorithm ensures the system power budget limits are honored; (iv) minimizes on chip control (OCC) throttling due to power budget constraints; (v) sustains workload-optimized-frequency (WOF) ranges for longer duration; and/or (vi) maximizes workload throughput across frequency domains.

In some embodiments of the present invention, a power management system comprises a token pool that performs a token passing strategy, in round-robin fashion with a plurality of distributed control units, to efficiently shift power allowances (power tokens) among frequency domains respectively corresponding to the control units. The power management system initializes with: (i) a fixed number of power tokens in the token pool, and (ii) a "starvation flag" associated with ("owned" by) each control unit with which the control unit can request fair policy in the case of longer starvation. This system minimizes meta-data needed for organization and control, and consequently can be scaled to a system of any size without increasing complexity.

In some embodiments, each control unit (CU) retains only the number of tokens of which the CU can make use. This number of "useful" tokens is determined based on CU utilization and instructions per second (IPS) values. The combination of utilization and IPS values determines whether granting a token to the CU would be useful. If the CU has excess tokens (tokens which the CU is not using), it may donate the excess tokens to the token pool, ensuring that no CU holds unnecessary tokens. If a CU is in a starvation state for more than a threshold length of time, then the CU may raise a starvation flag after which no CU holds onto more than an average number of tokens. The starvation flag is removed once the "starving" CU gets sufficient tokens (which is guaranteed since the control units switch to operating in a "fair" policy).

In some embodiments, a frequency domain may set a maximum operating frequency (thus power consumption) based on the number of tokens held by the corresponding control unit. The frequency domain need not always operate at the maximum operating frequency, but may operate: (i) at the maximum frequency; (ii) a lower frequency; or (iii) workload optimized frequency (turbo WOF) that may exceed the "maximum frequency". A control unit that gives up power tokens to the token pool lowers maximum operating frequency of the corresponding frequency domain, based on the number of token given up.

Embodiments disclosed herein with respect to frequency domains of an electronic device are not to be construed to exclude any other embodiments.

Some embodiments of the present invention identify the parameters (for example, instruction per second (IPS) and task utilization) that are necessary and sufficient for determining the number of power tokens required to meet the energy requirements of a given frequency domain. A power token represents an allowance to use an increment of power.

A control unit may authorize an associated frequency domain to use an amount of power up to that represented by the number of power tokens held by the control unit. Some embodiments assign a default (base) amount of power to a frequency domain. Power tokens held by the control unit permit the frequency domain to increase power usage above the base by an increment up to that represented by the number of power tokens the control unit holds. Some embodiments assign the control unit a default number of power tokens, and assign the frequency domain a default amount of power. If the frequency domain uses less than the default amount of power (meaning the frequency domain has a power surplus), the control unit may pass to the token pool some or all of the power tokens held by the control unit.

In some embodiments, a given frequency domain is in a state of power deficit when the frequency domain's power requirements exceed the power allowance. In this case, workload assigned to the given frequency domain cannot be processed in a timely manner. In response, when the token pool interacts with the given control unit (associated with the given frequency domain), the control unit passes a starvation flag to the token pool if, for example, the control unit faces frequency deficit for some threshold of time. Subsequently, when the token pool interacts with other control units as it travels around the ring, the other control units (i) detect the starvation flag, (ii) limit themselves to an upper limit of power tokens that they can consume, and (iii) relinquish excess (surplus) power tokens to the token pool. When the token pool again comes around to the given control unit, the control unit picks up the surplus power tokens and removes the request token from the token pool (assuming enough power tokens to satisfy the power deficit were acquired). The control unit then increases the power usage allowance for the given frequency domain. In response, the frequency domain operates at an increased frequency (and consequently consumes more power) to process the assigned workload more quickly. Thus the power deficit is partly or fully eliminated within the time the token pool takes to traverse once around the ring.

<FIG> is a schematic diagram of a ring topology, in accordance with some embodiments of the present invention, including: control unit <NUM>; control unit <NUM>; control unit <NUM>; and token pool <NUM>. Token pool <NUM> repeatedly (iteratively) cycles through the ring topology, interacting in turn with all control units during each cycle. Each control unit is associated with, manages, and/or governs a frequency domain (not shown in the Figures) with respect to power usages allowed for each of the frequency domains. Each control unit is associated with a respectively corresponding starvation flag and a token count (the number of tokens held by the control unit). The ring topology may comprise any number of control units and respectively corresponding frequency domains.

In some embodiments, the order in which token pool <NUM> interacts with the control units is dynamic, effectively altering the ordering of control units in the ring topology. In at least one embodiment, alteration of the ordering of control units is triggered by a high-priority need of a particular control unit for more tokens. In an example scenario, token pool <NUM> receives a signal indicating a high priority control unit has a need for more power tokens. In response, token pool <NUM> services the high priority mission as follows: (i) breaks out of the normal ring sequence; (ii) picks up surplus tokens from one or more donor control units; (iii) delivers the surplus tokens to the high priority control unit; and/or (iv) resumes normal processing at the place in the normal ring sequence where it broke out to service the high priority mission.

In another example embodiment, consider a control unit that is processing a high priority task and needs more tokens. If there is a donor, then it is guaranteed that once the token pool reaches the donor, the donor donates all excess tokens to the token pool. Once the token pool again comes around to the control unit with the high priority task, the token pool transfers the excess tokens to the control unit. In some embodiments, a high priority task is identified based on: (i) instructions per second (IPS) processed by the frequency domain; and (ii) utilization of the frequency domain. A control unit calculates a required number of tokens based locally on IPS and utilization parameters.

In some embodiments, some control units are given relative weights (based on importance). The token pool interacts with the control units in a frequency based on the weights. For example, consider a ring topology comprising five control units (C1, C2, C3, C4, and C5), where C1 is given a weight of "<NUM>" and C2 through C5 are each given a weight of "<NUM>". The token pool interacts with the control units in the following sequence: C1, C2, C3, C1, C4, C5, C1, C2. etc., interacting with C1 twice as frequently as with each of the others.

In some embodiments, a control unit manages more than one frequency domain with respect to power distribution and allocation among the frequency domains. In some embodiments, a single control unit manages a plurality of frequency domains, on an integrated circuit chip. In some embodiments, a single control unit manages a plurality of frequency domains, distributed among one or more integrated circuit chips.

In some embodiments, more than one control unit manages a single frequency domain. For example, a redundancy scheme sets three control units in charge of the frequency domain. The control units operate on a voting system that requires agreement between at least two control units for taking action (donating or accepting tokens to or from the token pool, for example). In this way, a single control unit failure does not impact operation of the power management system with respect to the frequency domain.

In some embodiments of the present invention, at each interaction with a control unit, token pool <NUM> may perform one or more of the following actions (without limitation): (i) pass token(s) to the control unit; (ii) receive token(s) from the control unit; (iii) receive a starvation flag from the control unit; (iv) return a power request token to the control unit; (v) exchange status information (unidirectionally, or bidirectionally) with the control unit; and/or (vi) take no action.

<FIG> is a schematic diagram showing a control unit accepting power tokens from the token pool in accordance with some embodiments of the present invention. In particular, token pool <NUM> initially has <NUM> power tokens and control unit <NUM> has none. Token pool <NUM> transfers ten of the <NUM> power tokens to control unit <NUM>. After the transfer, token pool <NUM> has <NUM> tokens and control unit <NUM> has <NUM>. Consequently, control unit <NUM> allows the corresponding frequency domain (not shown) to increase power consumption by an increment not exceeding the power represented by the ten tokens.

<FIG> is a schematic diagram showing a control unit donating power tokens a token pool, in accordance with some embodiments of the present invention. In particular, token pool <NUM> initially has <NUM> power tokens and control unit <NUM> has <NUM>. Control unit <NUM> donates <NUM> tokens (may, or may not, represent surplus power tokens) to token pool <NUM>. After the transfer, token pool <NUM> has <NUM> tokens (<NUM> + <NUM> = <NUM>), and control unit <NUM> has <NUM> tokens (<NUM> - <NUM> = <NUM>). Consequently, control unit <NUM> reduces the power usage limit of corresponding frequency domain (not shown) by an increment represented by the <NUM> tokens donated. Note that if a CU donates tokens to the token pool, the tokens may be surplus tokens (of which the CU does not need and/or cannot make use of), or tokens in excess of an average number of tokens donated due to presence of the starvation flag.

<FIG> is a schematic diagram showing placement of a power request token by a control unit onto the token pool in accordance with some embodiments of the present invention. In particular, control unit <NUM> has a power deficit, and places starvation flag <NUM>, asking for <NUM> power tokens, onto token pool <NUM>. Token pool <NUM> continues around the ring topology, interacting with the other control units one by one, in turn.

In some embodiments, token pool <NUM> interacts with the control units based on control unit activity. That is, token pool <NUM> assumes an idle state until a control unit issues an interrupt signal. In response, token pool <NUM> interacts with the signaling control unit. Once token pool <NUM> determines the reason why the control unit issued the signal (for example to donate excess power tokens to token pool <NUM>), token pool <NUM> takes appropriate action (for example to receive the excess power tokens and deliver the donated power tokens to a "needy" control unit. Once no more action is called for, token pool <NUM> re-enters the idle state.

In some embodiments, a starvation flag specifies a number of tokens requested by the associated control unit, called the "remaining to be filled" number (RTBF number). The token pool collects up to the RTBF number of power tokens, earmarks them for delivery to the requesting control unit, and delivers the power tokens to the requesting control unit in satisfaction of the starvation flag. The token pool then returns the starvation flag (or otherwise cancels the starvation flag) to the requesting control unit.

In some embodiments, the token pool is unable to collect the requested number of power tokens in the first trip around the ring. The token pool continues going around the ring, gathering and earmarking tokens as they are made available by the other control units, and transferring the earmarked power tokens to the requesting control unit. Upon transferring earmarked power tokens, the token pool decrements the RTBF number by the number of power tokens transferred to the requesting control unit. Once the RTBF number reaches zero, the request has been fulfilled, and the token pool transfers the power request token back to the requesting control unit.

In some embodiments, the token pool takes on board multiple power request tokens from multiple respectively corresponding requesting control units. As the token pool gathers surplus tokens, it may use any suitable method to earmark the gathered surplus tokens among the multiple requesting control units until all requests have been fulfilled. In some embodiments, surplus tokens are allotted preferentially to higher priority control units. In some embodiments, the surplus tokens are allotted in proportion to the numbers requested (and/or based on the respective RTBF numbers) by the multiple control units.

<FIG> is a schematic diagram showing relinquishment of power tokens, in response to starvation flag <NUM>, in accordance with some embodiments of the present invention. As discussed above with respect to <FIG>, control unit <NUM> placed starvation flag <NUM> onto token pool <NUM>. Token pool <NUM> subsequently moves around the ring topology, and interacts next with control unit <NUM>. Control unit <NUM> has <NUM> surplus power tokens, and in response to detecting starvation flag <NUM> present in token pool <NUM>, transfers the <NUM> surplus tokens to token pool <NUM>. Token pool <NUM> earmarks the <NUM> tokens for delivery to control unit <NUM> in fulfillment of starvation flag <NUM>.

In some embodiments, if the token pool is not able to acquire all the token(s) requested by a control unit in a power deficit state (a "needy" control unit) within a predetermined time interval, the control unit raises a starvation flag. In response, the power management system initiates a token leveling process, based on "fair" token distribution to mitigate the power deficit. In the mitigation process, a power request token, placed on the token pool by the needy control unit, signals to the other control units to relinquish a certain amount of tokens (whether surplus or not) to create "fair token distribution" across all control units. Once the needy control unit puts the request token into the token pool, other control units (contributing control units) relinquish excess tokens to the token pool. If some (or all) other control units have no excess tokens, they nevertheless give up some tokens. The token pool transfers the tokens given up by the contributing control units, to the needy control unit, thereby effectively shifting some power usage from the contributing control units to the needy control unit. This levels out, at least to some extent, the power usage among all the control units while remaining within total power budgeted for the control units collectively.

<FIG> is a schematic diagram showing fulfilment of starvation flag <NUM>, upon return of token pool <NUM> to control unit <NUM>. As discusses above with respect to <FIG>, control unit <NUM> relinquished <NUM> tokens in response to starvation flag <NUM>. Once token pool <NUM> back around to control unit <NUM>, token pool <NUM> transfers, to control unit <NUM>, starvation flag <NUM> and the <NUM> surplus tokens contributed by control unit <NUM>.

Control unit <NUM>, authorizes the associated frequency domain to increase operating frequency by an amount based on the <NUM> additional power tokens now in possession of control unit <NUM>. The frequency domain subsequently processes workload more quickly at the expense of consuming more power, yet the total power used by all the frequency domain participants of the ring topology, in aggregate, remains within the established power budget.

<FIG> is a schematic diagram showing operation of a system in accordance with some embodiments of the present invention. A token passing model can be adapted to various layers of computing stacks such as a hardware stack or a software stack. In a hardware stack, control units may be discrete modules or physical circuits on an integrated chip, for instance. At a hardware level, in some embodiments, each on chip control (OCC) represents the control units, where shared memory represents the token passing mechanism.

In contrast, a control unit implemented in a user space layer of a software stack, comprises threads in an open multi-processing application programming interface (MP-API) that passes tokens using shared memory based approaches. Still with respect to user space, some embodiments treat MP-API threads (for instance, MP-API thread <NUM>, MP-API thread <NUM>, and MP-API thread <NUM>. MP-API thread N) as control units, and pass the token pool on to neighboring threads, with the use of shared memory, as shown in <FIG>. Moreover, in software implementations, both the user space and kernel space applications can inherit token passing models.

Some embodiments use MP-API processes as control units, and pass tokens among different systems by using a message passing interface (MPI).

In some embodiments, a scheduling policy within the kernel layer of an operating system, represents the control units that use shared memory to pass tokens.

In some embodiments, MP-API processes comprise control units and the token pool is passed on by the use of a message passing interface.

Some embodiments falling outside of the scope of the present invention, but useful for understanding, involve devices other than control units of an integrated circuit chip. For example, the techniques described herein can be applied to servers in a rack of servers, wherein tokens distributed among the servers in the rack govern the power usage allowed for each server. A heavily loaded server can have more tokens (and therefore be allowed to dissipate more power) than less heavily loaded servers in the rack. By this method, the servers in the rack, in total, do not exceed a power budget limit for the rack as a whole, yet maximizing the workload performed by the servers therein.

The same techniques can be applied to an entire data center in a nested fashion, whereby (i) a first level of tokens govern power distribution among parts of an integrated circuit chip of a server in a rack in a data center; (ii) a second level of tokens govern power distribution among components (for example, integrated circuit chips, circuit modules, circuit cards and circuit boards, storage devices, power supply, network adapters, memory, storage, etc.) of the server; (iii) a third level of tokens govern power distribution among a plurality of servers in the rack; and/or (iv) a fourth level of tokens govern power distribution among a group of racks.

Some embodiments of the present invention use token passing in a ring topology to govern power distribution within other types of power consuming devices, such as for example, transportation systems, automobiles, communication systems, networking systems, manufacturing systems, power generation systems, marine craft, aircraft, spacecraft, etc..

<FIG> is a pseudo-code listing showing an approach for initializing the token pool in accordance with at least one embodiment of the present invention.

<FIG> is a pseudo-code listing showing an approach for computing millions of instructions per second (MIPS) in accordance with at least one embodiment of the present invention.

<FIG> is a pseudo-code listing showing an approach for requesting additional tokens in accordance with at least one embodiment of the present invention.

<FIG> is a pseudo-code listing showing an approach for a daemon thread corresponding to a frequency domain (FD) in accordance with at least one embodiment of the present invention.

Some embodiments of the present invention may recognize one, or more, of the following facts, potential problems, and/or potential areas for improvement with respect to the current state of the art: (i) some central processing units (CPUs) have a well-defined power budget above which they are not allowed to operate; (ii) an on-chip controller (OCC) throttles CPU frequency to prevent the CPU exceeding a limit imposed by the power budget; (iii) some CPU frequency governors do not account for the power budget, but instead change the core operating frequencies according to core utilization, without feedback as to whether the CPU benefits from the changed frequencies; (iv) a distributed approach may produce indefinite power starvation across frequency domains; (v) does not consider the problem of resource starvation; and/or (vi) may overutilize some resources while other resources are underutilized or idle.

At least one embodiment of the present invention may include one, or more, of the following features, characteristics, and/or advantages: (i) implements an efficient scheme for setting respective operating frequencies of various CPU cores, such that the overall system power budget is not exceeded; (ii) avoids centralized bottlenecks, by selectively distributing power among the cores; (iii) redirects power/energy to parts of the system that are in most need of the power without starving other parts of the system; (iv) allows a subset of CPU cores to operate at higher than rated frequencies while maintaining the system power budget under control; (v) uses a distributed token passing mechanism among frequency domains to determine achievable frequencies in accordance with operating conditions, and changes thereof; (vi) allots a number of tokens for a circuit chip (for example, a CPU chip) based on the power budget for the chip; (vii) shifts the tokens (hence power usage allowances) among frequency domains of the chip, while maintaining chip total power usage within the budgeted limit; (viii) implements a distributed frequency control algorithm to ensure the system power budget limits are honored; (ix) minimizes on-chip controller (OCC) throttling due to the power budget constraints; (x) sustains workload-optimized-frequency (WOF) ranges for a longer durations; (xi) avoids indefinite power starvation across frequency domains which is a known problem with a distributed approach; and/or (xii) requires a minimum of metadata to implement, hence is scalable to a system of any size without significant increase in message complexity.

A number of tokens assigned to a chip determines, at least in part, the granularity (in terms of power increment) for power distribution among parts of the chip. For example, consider a coarse granularity for a chip with a power budget of <NUM> watts, to which <NUM> tokens are assigned. Power distribution among various frequency domains of the chip can be modified in increments of <NUM> watt (<NUM> watts / <NUM> tokens = <NUM> watt/token). In a finer granularity embodiment, <NUM> tokens are assigned to the chip. Power distribution can then be modified in increments of <NUM> watts (<NUM> watts / <NUM> tokens = <NUM> watts/token).

In some embodiments, a number of tokens assigned to a chip determines, at least in part, the granularity (in terms of operating frequency increment) for governing power distribution among parts of the chip. For example, consider a coarse granularity for a chip with a nominal operating frequency of <NUM> GigaHertz (<NUM>, meaning <NUM>,<NUM>,<NUM>,<NUM> cycles per second) for which <NUM>,<NUM> tokens are assigned. Operating frequencies of various frequency domains of the chip can be modified in increments of <NUM> MegaHertz (<NUM>, meaning <NUM>,<NUM>,<NUM> cycles per second) (<NUM> / <NUM> tokens = <NUM>/token). In a finer granularity embodiment, <NUM> million (<NUM>,<NUM>,<NUM>) tokens are assigned to the chip. Operating frequencies of the various frequency domains can then be modified in increments of <NUM> (<NUM> / <NUM>,<NUM>,<NUM> tokens = <NUM> / token).

In some embodiments of the present invention, a ring topology (i) arranges distributed control units for efficiently carrying out the distributed power-shifting, and/or (ii) defines a token passing strategy in the form of a rotating token pool that "travels" around the ring. The system (comprising control units and the token pool) is initialized with a fixed number of tokens in the token pool. Each control unit has a special token (a starvation flag) for indicating power starvation.

Some embodiments identify parameters (for example, instructions per second (IPS), task utilization, duty cycle, etc.) that are necessary and sufficient to determine how many tokens from the pool are required to meet the energy requirements for each control unit.

In some embodiments of the present invention, a mechanism, whereby a control unit acquires tokens without indefinitely starving other control units of power, comprises the following procedure: (i) a control unit is in a state of "power starvation" when one (or more) of the control unit's energy requirements is not met, based on the available number of tokens - in response, the control unit drops a special "power request token" into the token pool; (ii) when the token pool traverses around the ring and interacts with other control units, the other control units detect the power request token, and respond by relinquishing excess tokens, beyond those which they can consume (based on current power usages), back into the pool; (iii) the token pool eventually returns to the control unit in the "power starvation" state, transfers the excess tokens to the control unit, thus curing, or at least mitigating, the "power starvation" within a single trip around the ring; and/or (iv) the control unit that is no longer in a power starvation state removes its special power request token from the token pool.

In some embodiments of the present invention, a strategy for achieving a global (with respect to a whole chip having multiple frequency domains, for example) energy constraint via local (at the frequency domain level, for example) decisions comprises: <NUM>) maintaining a power budget; and <NUM>) sustaining a higher than rated frequency, sometimes referred to as turbo frequency, or workload optimized frequency, as next described.

<NUM>) Maintaining a Power Budget: Depending on the power budget for a module (a CPU for example), some embodiments increase or decrease the number of tokens in the pool such that the sum of the power consumed by the individual control units does not exceed the power budget. The number of tokens held by each control unit limits the power consumed by the control unit. In other words, the maximum allowed power consumed by a control unit is a function of the number of tokens held by the control unit.

In some embodiments, the function is linear, meaning the power limit is directly proportional to the number of tokens. Some embodiments employ a non-linear functional relationship between tokens and power consumption limit, in order to disproportionally skew power usage toward more heavily loaded control units, to allow them to process workload much faster, or to skew power usage disproportionally toward less heavily loaded control units so that more work can be directed thereto.

<NUM>) Sustaining turbo (WaF) frequency: When one or more cores (of a CPU for instance, or a frequency domain of any module) are idle, an active core can sustain a higher than rated frequency, provided the number of tokens the active core holds exceeds a default minimum number of tokens.

In some embodiments, the operating algorithm is generic in nature such that it can be implemented across any system infrastructure stack. For instance, the algorithm can be easily scaled across a cluster of nodes, or the algorithm can be implemented on some system cores that can act as control units. The algorithm is scalable without having (or at least minimizing) the problem of power starvation among control units.

An operating algorithm in accordance with some embodiments of the present invention comprises the following components: <NUM>) initialization of the token pool; <NUM>) useful load calculation; <NUM>) token to frequency mapping; and/or <NUM>) power starvation flag (sometimes herein referred to as "starvation token"). These components are next described:.

<NUM>) Initialization of the token pool: Defines the total number of tokens available in the system. The combined value of the tokens is mapped to the power budget constraints in the system.

<NUM>) Useful load calculation: Each control units calculates the load from the system utilization and the millions of instructions per second (MIPS) value which can distinguish between "frequency variant" and "frequency invariant" workloads. This leads to better token allocation among the control units as the frequency invariant tasks do not need to be given tokens, which instead can be given to other tasks to sustain a higher frequency for a longer duration.

<NUM>) Token to Frequency Mapping: Each control unit, based on a computation of useful load that can be processed by a corresponding frequency domain, receives or releases token(s) respectively from or to the rotating token pool. The operating algorithm then maps the available token(s) to the frequency achievable by the control unit.

<NUM>) Power starvation flag: Each control unit, upon not getting the tokens required to meet their current utilization needs for a certain threshold, is considered to be in a state of power starvation. In response, such a control unit places a "starvation flag" into the rotating token pool (refer to <FIG>). The power starvation flag mandates each control unit to release extra tokens such that every control unit still has a "fair" number of tokens. This evens out frequency demands (thus power allowance distribution) among contending control units.

Some embodiments of the present invention may include one, or more, of the following features, characteristics, and/or advantages: (i) when implemented in kernel space (for example, an operating system kernel), allows a system to sustain higher turbo frequencies for longer durations as compared to conventional approaches; (ii) results in higher throughput and lower latencies; (iii) are based on global power constraints of the system; (iv) makes uses of a MIPS metric to calculate useful workload capacities; and/or (v) decreases energy consumption of the system as compared to conventional approaches.

Some embodiments of the present invention, assign a fixed number of power tokens to an integrated circuit chip. The fixed number of power tokens is based on a power budget allotted to the integrated circuit chip which the circuit chip must not exceed. A rotating token pool apportions the power tokens among a plurality of frequency domains of the integrated circuit chip based on respectively corresponding workload requirements (for example, instructions per second and task utilization) of the frequency domains. As relative workload requirements shift among the frequency domains, the rotating token pool shifts power tokens away from lightly loaded frequency domains and to more heavily loaded frequency domains. By this method, the apportionment of power tokens (meaning apportionment of power usage allowance) is skewed in favor of heavily loaded frequency domains. A heavily loaded frequency domain can operate in Workload Optimized Frequency (WOF) when it receives a corresponding number of tokens from the token pool. The workload can thus be processed more quickly while not exceeding the power budget allotted to the integrated circuit chip.

and/or: inclusive or; for example, A, B "and/or" C means that at least one of A or B or C is true and applicable.

Including / include / includes: unless otherwise explicitly noted, means "including but not necessarily limited to".

User / subscriber: includes, but is not necessarily limited to, the following: (i) a single individual human; (ii) an artificial intelligence entity with sufficient intelligence to act as a user or subscriber; and/or (iii) a group of related users or subscribers.

Data communication: any sort of data communication scheme now known or to be developed in the future, including wireless communication, wired communication and communication routes that have wireless and wired portions; data communication is not necessarily limited to: (i) direct data communication; (ii) indirect data communication; and/or (iii) data communication where the format, packetization status, medium, encryption status and/or protocol remains constant over the entire course of the data communication.

Receive / provide / send / input / output / report: unless otherwise explicitly specified, these words should not be taken to imply: (i) any particular degree of directness with respect to the relationship between their objects and subjects; and/or (ii) absence of intermediate components, actions and/or things interposed between their objects and subjects.

Module / Sub-Module: any set of hardware, firmware and/or software that operatively works to do some kind of function, without regard as to whether the module is: (i) in a single local proximity; (ii) distributed over a wide area; (iii) in a single proximity within a larger piece of software code; (iv) located within a single piece of software code; (v) located in a single storage device, memory or medium; (vi) mechanically connected; (vii) electrically connected; and/or (viii) connected in data communication.

Claim 1:
A computer-implemented method comprising:
receiving (S255), by a token pool (<NUM>), a power allowance request from a first power consuming device, of a plurality of power consuming devices, of an integrated circuit;
in response to receiving the power allowance request, the token pool determining whether a second power consuming device, of the plurality of power consuming devices, has a power allowance surplus;
in response to determining the second power consuming device has a power allowance surplus, receiving (S260) the power allowance surplus from the second power consuming device;
transferring (S265), via the token pool, the power allowance surplus to the first power consuming device; and
in response to transferring the power allowance surplus to the first power consuming device: (i) increasing (S270) a first power usage limit corresponding to the first power consuming device, based on the power allowance surplus, and (ii) decreasing a second power usage limit corresponding to the second power consuming device, based on the power allowance surplus.