This document has been updated (as of March 13, 2000) to inline points made in the Updates and FAQ. It makes no new information beyond that already included in that document. These changes are merely provided for your convenience. All updated items are italicized and marked with the "new" icon.

I. Introduction

• What the best choices are,
• How to reconcile sometimes conflicting goals, and
• How to keep the complexity of your design under control.

II. The problem

While speed is not a problem, the same is not true of energy consumption. Battery technology is not improving at a rapid rate, and in fact, there are fundamental limitations to how much more efficient batteries can be. Unfortunately, computers have numerous components that consume significant amounts of energy---for example, the processor power dissipation is proportional to its clock frequency, and hard disks have mechanical parts that use up a lot of energy to start spinning from an idle state, and only a little bit less while continuing to spin.

Hands21.com is building a product for the expanding class of handheld computer users who want to do more than just manage their calendar and maintain addresses. A market survey indicates that users are interested in surfing the Web, communicating using audio and video, and using speech-based interfaces on their handhelds. Hands21.com has decided to meet this challenge by designing a complete computer system---hardware and software---for this market.

As chief operating system designer for Hands21.com, you need to make sure that the system isn't a battery-eater. So, together with the hardware designers, you come up with the following hardware specifications for the components in the product based on components that aren't energy hogs but which still provide reasonable performance to run interesting applications.

Each disk operation takes essentially 10ms. The time given for reads and writes is an average value that takes into account seek, rotational latency, and transmission times (these are parameters that we haven't yet discussed in class). However, the amount of data being transferred is relatively unimportant (unless you are reading many megabytes of data).

The processor in the handheld can be clocked as fast as 200 MHz, but also has modes where it can run at 100 MHz and 33 MHz. The peak power consumption is 400 mW when running at 200 MHz. Recall from freshman physics that power is the rate at which energy is consumed, which implies that the processor power dissipation is proportional to the processor clock speed. If you decide to adjust processor speeds, that's OK, but you have to understand and justify the need to do so. Assume that the processing for compression and decompression are pipelined well-enough so that there are no idle cycles.

You analyze the typical applications your customers want to run on the handheld, and discover that most of them are processor or memory-bound, and consume large amounts of memory (all that memory-intensive video). The file system itself isn't stressed all that much, which is good because your disk's power consumption seems substantial. Unfortunately, you also realize that paging activity is likely to activate the disk because it is the default backing store in most traditional operating systems. You therefore need to pay attention to the paging subsystem to ensure that the system as a whole is energy-efficient.

Thus, your job is to design a virtual memory (VM) subsystem for Hands21.com to make sure that paging to and from program memory does not take up too much energy. You mention this in passing to Alyssa P. Hacker, who thinks for a minute and wonders if data compression algorithms can help here. She suggests that because the disk is the energy hog, try and avoid using it as much as possible. When a page needs to be sent to backing store, rather than simply write it to disk, compress it and put it at another place in memory. Of course, you end up not being able to use all the memory for programs, but the potential gain is in extending precious battery life.

Excited, you analyze the target applications and find that those pages seem to compress quite well, 1 : 4 on average. But compression is variable; not all compressed pages are the same size. This means that on average, you gain a factor of 4 by compressing (e.g., 10 Mbytes of data can be stored compressed in 2.5 Mbytes of RAM.) Some pages may not compress at all and others may compress by a factor of ten. The amount of extra memory you need to store tables etc. for compression and decompression is relatively small with the algorithm you're using.

You run some experiments to understand the working set behavior of your target applications with the standard LRU replacement algorithm. You find that as a function of the amount of RAM used, the miss rate m is given, for the LRU replacement policy, by the following table:

That is, if the amount of RAM in the computer is X, the miss rate is f(X), where f(X) is the second column of the table.  As you can easily verify, the miss rate halves for every additional 8 MBytes in the 24MBytes-120MBytes range for your programs. Note, this means that this table applies to the compressed store as well. Think of it this way: with compression, you can make it look like you have more RAM than you actually do. You are absolutely limited to 32 MBytes of RAM in the system --- the goal of the project is to design a virtual memory system.

You also measure how much computation is needed to compress and decompress an 8 KByte page of data. You find that it takes on average 4 instructions per byte to do this, and does not involve any paging or file system activity.  The processor executes one instruction every clock cycle.

To summarize the main issues:

• Paging to disk consumes a lot of energy.
• Compressing pages to another place in memory appears to be a way in which to reduce energy consumption.
• In your design, assume that 16 MBytes of RAM are used for compressed store, and 16 MBytes of RAM are used for uncompressed store. Try and estimate how much you gain in terms of energy savings over a scheme that does not use compression. Assume that the miss rate for 16 MBytes of RAM is 4%.
• An analysis of the programs reveals that memory pages compress by 1 : 4 on average, but that the size of a compressed page is variable.
• The page size is 8 KBytes.
• Power is the rate at which energy is consumed or dissipated: 1 Watt second = 1 Joule.

• Clearly describe the data structures for keeping track of pages in the in-memory compressed store and on disk.
• What specific steps are involved in paging in and out to the compressed store? For example, how do you locate a page in the compressed store?
• Briefly outline the procedure by which you can decide how to partition RAM. You DO NOT need to actually calculate the value. (Replaces "What fraction of RAM should you use for programs and how much for the in-memory compressed store? Clearly describe what the factors deciding this are and how you arrive at the conclusion.")
• If you are ambitious, you can try to calculate an optimal partitioning of RAM between compressed and uncompressed regions. To do this, you will need to fit an exponential-decay function to the values in the miss rate table. You can assume that the miss rate table can be extrapolated for memory amounts less than 16 MBytes. Note that the miss rate table also applies to the compressed store.
• Estimate how much energy it takes to load a page from disk and load from the compressed store respectively.
• Do you ever need to use the disk? If not, explain how your design avoids it; if so, describe when it does. Discuss possible ways of further reducing the amount of energy consumed when this happens, remembering that frequent spinning up and down may be a losing proposition.
• Do you gain in terms of energy consumption by running the processor at one of the slower rates while compressing/decompressing pages?
• Does your design achieve the goal of improving energy efficiency? Can you substantiate this by presenting a (rough) analysis of how much you gain with your solution (either in terms of a percentage improvement or absolute value)? Does your design lead to worse performance in terms of execution time for applications?
• Speculate on how technology trends will affect the performance of your system design. Consider in particular what happens when the processor get faster (for the same amount of memory), and when memory sizes get bigger.

You do not need to address the following issues in your design:

• Page replacement policy; assume that LRU is sufficient.
• The design of other parts of the operating system, e.g., the file system, display subsystem, the CPU scheduler, network, etc.
• Hardware issues related to the processor, caches, memory, etc.

III. Your report

III.1. Suggestions on Writing Style

Your paper should be as long as is necessary to explain the problem, your solution, the alternatives you considered, and the reasons for your choices.  It should be no longer than that.  We estimate that a good paper will be 8 to 10 pages in length.

A good paper begins with an abstract.  The abstract is a very short summary of the entire paper.  It is not an outline of the organization of the paper! It states the problem to be addressed (in one sentence).  It states the essential points of your solution, without any detailed justification.  And it announces any conclusions you have drawn. Good abstracts can fit in 100-150 words, at most.

The body of your paper should expand the points made in the abstract. Here you should:

1. Explain the problem and the externally imposed constraints.

    You should explain to your intended audience the background of the problem in terms that the audience can understand.

2. Explain and elaborate your solution.

    Be sure to explain the approach or architecture conceptually before delving into details, components, and mechanics. (Remember, you aren't writing a mystery novel!) Present any analysis clearly and concisely.

3. Show how your solution satisfies the constraints and solves the problem (or how it fails to do so);

    Explain how the properties of your solution that result from choices you have made in your design are reasonable or desirable in the context of the problem statement.  Include analysis of the estimated (or measured, if it applies) performance characteristics of your solution.

4. Describe the alternative approaches that you considered and rejected, and why you rejected them.

    Your paper will be more convincing if you say not just why your idea is good, but why it is better than the alternatives.  (For example, if another approach would meet all of the objectives perfectly, but the cost would be 100 times higher, then you should mention that as a reason for choosing your less general but cheaper approach.)

5. Document your sources, giving a list of all references (including personal communications). The style of your citations (references) and bibliography should be similar to the styles in the technical papers you're reading in this class. In particular, a bibliography at the end and no citations in the text of your paper is insufficient; we'd like to see what specific pieces of information you learned from where as we read your paper.

Write for an audience consisting of colleagues who took 6.033 five years ago. That is, they understand the underlying system and network concepts and have a fair amount of experience applying them in various situations, but they have not thought carefully about the particular problem you are dealing with. Assume that your paper will also be used to convince the Hands21 staff that you have a viable design. Finally, give enough detail that they can turn the project over to their Information Technology programmers for implementation with some confidence that you won't surprised by the result.

III.2. How do we evaluate your report?

When evaluating your report, your instructor will look at both content and writing.

Some content considerations:

• Does your solution actually address the stated problem?
• Do you explain your decisions and the trade-offs?
• How complex is your solution? Simple is better, yet sometimes simple won't do the job. But unnecessary complexity is bad.
• Does your solution fit well with the rest of the system? If your solution requires modifying every piece of hardware, software, and data in sight, it won't be credible, unless you can come up with a very good story why everything needs to be changed.
• How extensible is your design? Are there opportunities for later addition of desirable features that you decided to omit?
• Is your analysis clear?

• Is the report easy to comprehend?
• Is it well organized and coherent?
• Does it use diagrams where appropriate? (A frequent problem when people use word processors is that they try to express everything in words, either because the word processor doesn't make it easy to include diagrams, or they haven't ever learned how to use the drawing features. Pictures can communicate some ideas far better.)
• Does it use the concepts, models, and terminology introduced in 6.033? If not, does it have a good reason for using a different universe of discourse?
• Does it address the intended audience?
• Is there a good abstract and bibliography?

Phase Two writing considerations

If you are enrolled in the 6.033 writing practicum, you don't need to do anything special; your practicum instructor will explain how the report will get you credit for the Phase II writing requirement. If you are not enrolled in the practicum, and you want us to forward your design project report to the writing program as your phase II writing project, please say so on the cover page, and make sure that your report is at least 8 pages long. Note also that the writing program has a rule that they will accept only reports that earn a B or better from the class in which they originate. Finally, be aware that the second design project will probably be a team project, and thus much more difficult to tailor to the needs of the writing program than this one.

IV. Collaboration

V. Schedule