System-Level Power Management And An Overview:Petri Net-Based Approaches

Petri Net-Based Approaches

The DPM approaches based on Markov decision processes offer significant improvements over heuristic power management policies in terms of the theoretical framework and ability to apply strong mathematical optimization techniques [25–31]. However, previous works based on Markov decision processes only describe modeling and policy optimization techniques for a simple power-managed system. Such a system contains one SP that provides services (e.g., computing and file access), one SQ that buffers the service requests for the SP, and one SR that generates the requests for SP. It is relatively easy to construct the stochastic models of the individual components because their behavior is rather simple. However a signif- icant effort is required to construct the joint model of SP and SQ mostly because of the required synchro- nization between state transitions of SP and SQ. Furthermore, the size of the Markov process model of the overall system rises rapidly as the number of SPs and SRs is increased.

Generalized stochastic Petri Nets (GSPNs) target more complex power-managed systems as shown in Figure 15.8. The example depicts a typical multiserver (distributed computing) system. Note that this model only captures those system behaviors that are related to the power management. The system contains multiple SPs with their own local SQs (LSQ). There is a SR that generates the tasks (requests) that need to be serviced. The request dispatcher (RD) makes decisions about which SP should service which request. Different SPs may have different power/performance parameters. In real applications, the RD and LSQs can be part of the operating system, while SPs can be multiple processors in a multiprocessor computing system or number of networked computers of a distributed computing system.

The complexity of the modeling problem for the above system is high not only because of the increased number of components, but also because of the complex system behaviors that are present. For example, one needs to consider the synchronization of LSQs and SPs, the synchronization of the SR and LSQs, the dispatch behavior of the RD, and so on. In this situation when complex behaviors must be captured by the system model, the modeling techniques in Ref. [11] become inefficient because they only offer stochastic models for individual components and require that global system behaviors be captured manually. Obviously, we need new DPM modeling techniques for large systems with complex behaviors.

For a detailed introduction to Petri nets, refer to Ref. [33].

A Petri net (PN) model is graphically represented by a directed bipartite graph in which the two types of nodes (places and transitions) are drawn as circles, and either bars or boxes, respectively (cf. Figure 15.9). The edges of the graph are classified (with respect to transitions) as

• Input edges: arrow-headed edges from places to transitions

• Output edges: arrow-headed edges from transitions to places

Multiple (input/output) edges between places and transitions are permitted and annotated with a number specifying their multiplicities.

Places can contain tokens, which are drawn as black dots within places. The state of a PN is called marking, and is defined by the number of tokens in each place. As in classical automata theory, in PN there is a notion of initial state (initial marking). Places are used to describe possible local system states (named conditions or situations). Transitions are used to describe events that may modify the system state. Edges specify the relation between local states and events in two ways: they indicate the local state in which the event can occur, and the local state transformations induced by the event.

The dynamic behavior of the PN is governed by the firing rule. A transition can fire (an event takes place) if all the transition input places (i.e., those places connected to the transition with an arc whose direction is from the place to the transition), contain at least one token. In this case the transition is said to be enabled. The firing of an enabled transition removes one token from all of its input places, and generates one token in each of its output places (i.e., those places connected to the transition with an arc whose direction is from the transition to the place). The firing of a transition is an atomic operation. Tokens are removed from input places, and deposited into output places with one indivisible action. Typically, the firing of a transition describes the result of either a logical condition becoming true in the system, or the completion of an activity. The latter interpretation is the reason for associating timing with transitions, as many authors did in their proposals for the definition of temporal concepts in PNs. Hence, time can be naturally associated with transitions. In the semantics of PNs, this type of transitions with associated temporal specifications is called a timed transition. These transitions are represented graphically by boxes or thick bars and are denoted with names that start with T. In contrast, immediate transitions fire as soon as they become enabled (with zero delay), thus acquiring a sort of precedence over timed transitions, and leading to the choice of giving priority to immediate transitions in the definition of GSPNs. In this chapter, immediate transitions are depicted as thin bars.

It should be noted that the PN state transformation is local, in the sense that it involves only the places connected to a transition by input and output arcs (this will be visible in the forthcoming examples; the PN model of a switch is so simple that local and global states coincide). This is one of the key features of PNs, which allows compact description of distributed systems.

Example

A simple example of a PN model is given in Figure 15.9, where two places PON and POFF , and two transitions TON-OFF and TOFF-ON are connected with four arcs. Both places define conditions (i.e., the “ON condition” or the “OFF condition”). The state depicted in Figure 15.9 is such that place POFF contains one token; thus the “OFF condition” is true; instead, since place PON is empty, the “ON condition” is false. In this simple example, transition TOFF-ON is enabled, and it fires, removing one token from POFF and depositing one token in PON. The new state is such that the “ON condition” is true and the “OFF condition” is false. In the new state, transition TON-OFF is enabled, and it fires restoring the state shown in Figure 15.9. The simple PN model in Figure 15.9 may be interpreted as the PN description of the behavior of a switch.

In a stochastic petri net (SPN) model, each timed transition is associated not only with a single transition time but a collection of randomly generated transition times from an exponential distribution. As in case of timed transitions, for the description of SPNs, one can assume that each timed transition possesses a timer. When the transition becomes enabled for the first time after firing, the timer is set to a value that is sampled from the exponential pdf associated with the transition. During all time periods in which the transition is enabled, the timer is decremented. Transitions fire when their timer readout goes down to zero. With this interpretation, each timed transition can be used to model the execution of an activity in a distributed environment; all activities execute in parallel (unless otherwise specified by the PN structure) until they complete. At completion, activities induce a local change of the system state, which is specified with the interconnection of the transition to input and output places. In GSPNs, the expo- nentially timed and immediate transitions coexist in the same model. In the context of GSPNs, places can be divided into two different classes based on the type of the transitions for which they are inputs, i.e., vanishing places and tangible places. The place is a vanishing place if it is the only input place of an immediate transition; otherwise the place is called a tangible place.

Let us see how one can use this modeling tool to develop a DPM policy by capturing the exact behavior of a complex EMC system. To capture the energy consumption of the EMC in the GSPN model, the following two definitions are necessary:

1. A GSPN with cost is a GSPN model with the addition of two types of cost: impulse cost associate with marking transitions and rate cost associated with places. Impulse cost occurs when the GSPN makes a transition from one marking to another. Rate cost is the cost per unit time when the GSPN stays in a certain marking.

2. A controllable GSPN with cost is a GSPN where all or part of the probabilities of timed transitions can be controlled by outside commands.

Example

Consider that a SP in the processor has two power states: {ON, OFF}. In the ON state, the SP provides service with an average service time of 5 ms. The average time to switch from the ON state to OFF state is 0.66 ms, and the average time to switch from the OFF state to ON state is 6 ms. The power consumption of the SP is 2.3 W when it is in the ON state and 0.1 W when it is in the OFF state. The energy needed to switch from the ON state to OFF state is 2 mJ, and the energy needed to switch from the OFF state to ON state is 30 mJ. Assume that the maximum length of the SQ is 3. Figure 15.10 shows the GSPN model of the single-processor system. The input gate Gcapacity sets the SQ capacity constraint. The place PON-OFF denotes the SP status when it is switching from the ON state to OFF state while the place POFF-ON denotes the SP status when it is switching from the OFF state to ON state. The place Pidle(ON)/Pidle(OFF) denotes the SP status when it is idle and the power state is ON/OFF. The place Pwork(ON) denotes the SP status when it is working and the power state is ON. The SP will have exactly one such status at any time. From the topology of the GSPN, one realizes that the sum of tokens in places PON-OFF , Pidle(ON), Pwork(ON), Pidle(OFF), and POFF-ON is 1 at any time.

The number of tokens in PSQ denotes the number of waiting requests in the SQ. The initial marking of Pidle(ON) is 1 while the initial marking of the other places is 0, which indicates that the initial state of the SP is idle and the initial state of SQ is empty. The places Pdecision(ON) and Pdecision(OFF) are vanishing places. They indicate the very short period of time when the SP is taking command from PM and is in the ON or OFF state. The place Pchanging is also a vanishing place. It is an auxiliary place, which indicates that the state of the system is changing so that it is time for the SP to receive the power management command if it is currently idle. TON-OFF and TOFF-ON are timed activities. They indicate the time needed to switch from the ON state to OFF state and the time needed to switch from the OFF state to ON state. Tprocessing is also a timed transition, which indicates the time needed to process one request. Tinput denotes the time needed to generate the next request. It actually belongs to the GSPN model of the request generation system. Tdecision(ON) and Tdecision(OFF) are immediate transitions. They represent the process of randomized action issued by the PM. The two cases in Tdecision(ON) or Tdecision(OFF) are mutually exclusive. The case probability equals the action probability, which is marking- and policy- dependent. If the policy is unknown, the GSPN is a controllable GSPN. When the SP is idle and ON (a token is in place Pidle(ON)) and SQ is not empty, the immediate transition Tstart is completed which indicates that the SP enters the busy state. When the SP is OFF (a token is in place Pidle(OFF)) and the state of SQ is changing (a token is in place Pchanging), the immediate transition Tre-decision is completed which indicates that the SP returns to the action taking stage. If the SP is not OFF and the state of SQ is changing, the immediate transition Tvanish is completed which indicates that the change is ignored.

In the complex system the request generation system (RGS) can be very complicated and cumbersome. RGS can generate various types of requests. The generation time of different types of request may be different. Some types of requests can be serviced by several different SPs; whereas some other types of requests can be serviced by only a certain SP. There may exist correlations among the generation of different types of requests. If the SQ is full, the RGS will stop generating request. It will resume request generation when there is vacancy in the SQ.

Example

Assume that there are three types of requests: the first is type A which can only be serviced by SP A, the second is type B which can only be service by SP B, and the third is type AB which can be serviced

by both SP A and SP B. The correlations among these requests are given by a probabilistic matrix, For example, from the matrix one will know that the probability that a type AB request was issued after a type A request is 0.6. Figure 15.11 shows the GSPN model of this RSG. In this figure, the case probability of activities Tswitch(A), Tswitch(B), and Tswitch(AB) takes value from a probabilistic matrix. The input gate Gcap_A represents the condition that the SQ in SP A is not full. The input gate Gcap_B represents the condition that the SQ in SP B is not full. The input gate Gcap_AB represents the condition that the SQ in SP A or the SQ in SP B is not full. Notice that the input places of these input gates belong to the GSPN model of each SP. These input gates enable or disable the request generation. For example, if the condition given by Gcap_A is false, which means that SQ of SP A is full, then the time activity Tgen(A) is disabled, which means that request generation procedure of type A request pauses. Tgen(A) will be enabled when the condition given by Gcap_A becomes true, which means that the request generation procedure resumes when there is a vacancy in the SQ.

To model a complex system composed of several SPs, similar to the one shown in Figure 15.8 with an RGS and interactions among the components, a hierarchical approach can be used. First, each SP is modeled using a single requester–single server model. Next, the requests generated by the RGS are sent to the SP #i with probability pi through a dispatcher. If the request can only be serviced by SP #i, then pi is 1. If the request cannot be serviced by SP #i then pi is 0. In all other cases the probability pi is controlled by the dispatcher. The optimal dispatch policy can be obtained by solving a Markov decision process. The GSPN model of such complex system contains the following components:

1. The GSPN models of RGS and SPs.

2. A set of input gates {Gcap_i}. The input place of a Gcap_i is the PSQ of all SPs, which can provide service for request type i. The activity of Gcap_i is Tgen(i). A gate Gcap_i indicates the condition that there are free positions in SQ to buffer the request.

3. Arcs from transition Tgen(i) in RGS to place PSQ in any SP that can provide service for request i.

Example

Consider a complex system which contains two SPs and one RGS as described in a previous example.

Figure 15.12 shows the GSPN model of this system.

After generating the controllable GSPN model, one can reduce it to a SPN, which is the same as a GSPN except that SPN does not have instantaneous activities [32]. From the SPN, we can find its reachability graph, and thereby, generate the corresponding continuous time Markov decision process. The state si of the CTMDP corresponds to the marking Mi in the reachability set. The rate cost of si is the sum of the rate costs of places in Mi. The transition cost of the CTMDP from state si to sj is the impulse costs of the completed activities when the GSPN is switching from marking Mi to Mj . The reader may refer to Ref. [32] for the procedure of reducing a GSPN to a SPN. The optimal policy in CTMDP is obtained by solving a set of linear programming. A GSPN can be converted to a CTMDP, hence it can be evaluated efficiently. However, the exponential distribution is not always an appropriate way to represent the transition time. If the transition time has a general distribution, the Markovian property will be destroyed. This problem can be circumvented by using the stage method [31], which approximates the general distributions using the series or parallel combinations of exponential stages.