This chapter combines and applies many analytical techniques we have studied thus far (Renewal-Reward, general transform analysis, and M/G/1 response time analysis) toward analyzing the problem of power management of a single server. The goal is to understand when a server should be turned off to save on power (sometimes called “power napping”) and when it should be left on.

In Section 27.1 we provide background on powering a server and state the specific power optimization problem that we address. To solve this problem, we first need to develop two more analysis topics.

The first topic is busy period analysis for the M/G/1. We have touched on busy periods in the exercise sections of prior chapters, but in Section 27.2, we go into much more depth in describing busy periods, including different types of busy periods and the Laplace transform of the busy period.

The second topic is the analysis of an M/G/1 with setup time, where the first job starting a busy period incurs an extra delay, known as the setup time. Setup times have also been discussed in earlier exercises; however, in Section 27.3 we consider their effect on the M/G/1.

Finally, in Section 27.4, we combine the analyses in Sections 27.2 and 27.3 to solve our power optimization problem.

The Power Optimization Problem

Consider the operation of a single-server system, specifically an M/G/1/FCFS queue. Thus far, we have only been concerned about the response time of the system.We now discuss the power usage.

This chapter and all the remaining chapters focus on scheduling for the case of an M/G/1 queue. We always assume ρ < 1 and that G is continuous with finite mean and finite variance. Every scheduling policywe consider iswork-conserving (i.e., whenever there is a job to be worked on, some job will receive service).

Definition 29.1 A non-preemptive service order is one that does not preempt a job once it starts service (i.e., each job is run to completion).

This chapter focuses on non-preemptive scheduling policies that do not make use of knowing a job's size.

FCFS, LCFS, and RANDOM

The following three non-preemptive policies do not assume knowledge of job size:

FCFS: When the server frees up, it always chooses the job at the head of the queue to be served and runs that job to completion.

LCFS (non-preemptive): When the server frees up, it always chooses the last job to arrive and runs that job to completion.

RANDOM: When the server frees up, it chooses a random job to run next.

Question: When would one use LCFS?

Answer: Consider the situation where arriving jobs get pushed on a stack, and therefore it is easiest to access the job that arrived last (e.g., the task at the top of the pile on my desk!).

Question: Which of these three non-preemptive policies do you think has the lowest mean response time?

Answer: It seems like FCFS should have the best mean response time because jobs are serviced most closely to the time they arrive, whereas LCFS may make a job wait a very long time. However, surprisingly, it turns out that all three policies have exactly the same mean response time. In fact, an even stronger statement can be made.

This chapter is a very brief introduction to the wonderful world of transforms. One can think of the transform of a random variable as an onion. This onion is an expression that contains inside it all the moments of the random variable. Getting the moments out of the onion is not an easy task, however, and may involve some tears as the onion is peeled, where the “peeling process” involves differentiating the transform. The first moment is stored in the outermost layer of the onion and thus does not require too much peeling to reach. The second moment is stored a little deeper, the third moment even deeper (more tears), etc. Although getting the moments is painful, it is entirely straightforward how to do it – just keep peeling the layers.

Transforms are a hugely powerful analysis technique. For example, until now we have only learned how to derive the mean response time, E[T], for the M/G/1. However, by the end of the next chapter, we will be able to derive the transform of T, which will allow us to obtain any desired moment of T.

The subject of transforms is very broad. In this chapter we only cover a small subset, namely those theorems that aremost applicable in analyzing the performance of queues. We use transforms heavily in analyzing scheduling algorithms in Part VII.

This chapter discusses applications of DTMCs in the real world. Section 10.1 describes Google's PageRank algorithm, and Section 10.2 analyzes the Aloha Ethernet protocol. Both problems are presented from the perspective of open-ended research problems, so that they serve as a lesson in modeling. Both are also good examples of ergodicity issues that come up in real-world problems. Finally, in Section 10.3, we consider DTMCs that arise frequently in practice but for which it is difficult to “guess a solution” for the limiting probabilities. We illustrate how generating functions can be used to find the solution for such chains.

Google's PageRank Algorithm

Google's DTMC Algorithm

Most of you probably cannot remember a search engine before google.com. When Google came on the scene, it quickly wiped out all prior search engines. The feature that makes Google so good is not the web pages that it finds, but the order in which it ranks them.

Consider a search on some term; for example, “koala bears.” Thousands of web pages include the phrase “koala bears,” ranging from the San Diego zoo koala bear home page, to anecdotes on the mating preferences of Australian lesbian koala bears, to a koala bear chair. The value of a good search engine is to rank these pages so that the page we need will most likely fall within the “top 10,” thus enabling us to quickly find our information. Of course, how can a search engine know exactly which of the thousand pages will be most relevant to us?

In this chapter, we show how to implement the simplified DLX. The implementation consists of two parts: a finite state machine, called the control, and a circuit containing registers and functional modules, called the datapath. The separation of the design into a controller and a datapath greatly simplifies the task of designing the simplified DLX.

The datapath contains all the modules needed to execute instructions. These modules include registers, a shifter, and an arithmetic logic unit. The control is the brain that uses the datapath to execute the instructions.

DATAPATH

In this section, we outline an implementation of the datapath of a simplified DLX, as depicted in Figure 22.1. We outline the implementation by specifying the inputs, outputs, and functionality of every module in the datapath. The implementation of every module is done by using the memory modules and the combinational circuits that we have implemented throughout this book. Note that Figure 22.1 is not complete: (i) inputs and outputs of the control FSM are not presented and (ii) some of the input–output ports, and their corresponding wires, are not presented. In fact, only wires that are 32-bit wide are presented in Figure 22.1.

The Outside World: The Memory Controller

We begin with the outside world, that is, the (external) memory. Recall that both the executed program and the data are stored in the memory.

The memory controller is a circuit that is positioned between theDLX and the main memory.

Consider the following problem. We need a combinational circuit that controls many devices numbered 0, 1, …, 2k − 1. At every moment, the circuit instructs exactly one device to work while the others must be inactive. The input to the circuit is a k-bit string that represents the number i of the device to be active. Now, the circuit has 2k outputs, one for each device, and only the ith output should equal 1; the other outputs must equal zero. How do we design such a circuit? The circuit described previously is known as a decoder. The circuit that implements the inverse Boolean function is called an encoder.

In this chapter, we specify and design decoders and encoders. We also prove that the combinational circuit are correct, namely, they satisfy the specification. Moreover, we prove that these designs are asymptotically optimal.

BUSES

We begin this section by describing what buses are. Consider a circuit that contains an adder and a register (a memory device). The output of the adder should be stored by the register. Suppose that the adder outputs 8 bits. This means that there are eight different wires that emanate from the output of the adder to the input of the register. These eight wires are distinct and must have distinct names. Instead of naming the wires a, b, c, …, we often use names such as a[0], a[1], …, a[7].

This chapter introduces two major notions: sets and functions. We are all familiar with real functions, for example, f (x) = 2x + 1 and g(x) = sin(x). Here the approach is somewhat different. The first difference is that we do not limit the discussion to the set of real numbers; instead, we consider arbitrary sets and are mostly interested in sets that contain only a finite number of elements. The second difference is that we do not define a “rule” for assigning a value for each x; instead, a function is simply a list of pairs (x, y), where y denotes the value of the function when the argument equals x. The definition of functions relies on the definitions of sets and relations over sets. That is why we need to define various operations over sets such as union, intersection, complement, and Cartesian product.

The focus of this book is Boolean functions. Boolean functions are a special family of functions. Their arguments and values are finite sequences of 0 and 1 (also called bits). In this chapter, we show how to represent a Boolean function by a truth table and multiplication tables. Other representations presented later in the book are Boolean formulas and combinational circuits.

SETS

A set is a collection of objects. When we deal with sets, we usually have a universal set that contains all the possible objects. In this section, we denote the universal set by U.

A long-standing source of confusion is the order of bits in binary strings. This issue is very important when strings of bits are serially communicated or stored in memories. Consider the following two scenarios.

In the first setting, Alice wishes to send to Bob a binary string a[n − 1 : 0]. The channel that Alice and Bob use for communication is a serial channel. This means that Alice can only send one bit at a time. Now Alice has two natural choices:

• She can send a[n − 1] first and a[0] last; namely, she can send the bits in descending index order. This order is often referred to as most significant bit first or just MSB first.

• She can send a[0] first and a[n − 1] last; namely, she can send the bits in ascending index order. This order is often referred to as least significant bit first or just LSB first.

In the second setting, computer words are stored in memory. A memory is a vector of storage places. We denote this vector by M[0], M[1],. … Suppose that each storage place is capable of storing a byte (i.e., 8 bits). The typical word size in modern computers is 32 bits (and even 64 bits). This means that a word is stored in four memory slots. The question is, how do we store a word a[31 :0]in four memory slots?

In this chapter, we study the rate of growth of positive sequences. We introduce a formal definition that enables us to say that one sequence does not grow faster than another sequence. Suppose we have two sequences and. We could say that xi does not grow faster than yi if xi ≤ yi for every i. However, such a restricted definition is rather limited, as suggested by the following examples:

1. The sequence xi is constant: xi = 1000 for every i, while the sequence yi is defined by yi = i. Clearly we would like to say that yi grows faster than xi even though y100 < x100.

2. The sequences satisfy xi = yi + 5 or xi = 2 · yi for every i. In this case, we would like to say that the two sequences grow at the same rate even though xi > yi.

Thus we are looking for a definition that is insensitive to the values of finite prefixes of the sequence. In addition, we are looking for a definition that is insensitive to addition or multiplication by constants. This definition is called the asymptotic behavior of a sequence.

ORDER OF GROWTH RATES

Consider the Fibonacci sequence. The exact value of g(n), or an analytic equation for g(n), is interesting but sometimes all we need to know is how fast does g(n)grow?