6.033: Computer System Engineering - Spring 2003

Expectations for Design Project 1

(Or, things you could have done to get a better grade)

8 April 2003

  1. The paper.

    1. There should be an abstract. The abstract should tell the reader your solution, rather than just repeating the problem statement.

    2. Before diving into details, the paper should provide a brief overview outlining your design and the major assumptions on which you based that design.

    3. The paper should define or explain buzzwords (e.g., "segmentation", "base and bounds") that might not be familiar to all members of the intended audience.

    4. The paper should clearly separate the discussion of your design from the discussion of the alternative designs that you considered.

    5. The paper should have at least one figure showing a typical memory layout, and at least one block diagram of the MMU internal design. If your design bypasses the MMU in kernel mode, the bypass mechanism should appear in the diagram.

    6. The paper should include pseudocode that carefully defines how the functions to add, delete, grow, and switch domains work. The pseudocode should be detailed enough to exhibit your assumptions and show how it enforces restrictions.

    7. The paper should also have text that explains the figures and pseudocode and it should be consistent with those figures and pseudocode.

  2. Basic design issues that every paper should address:
    1. Applicable to all designs:

      1. The paper should answer all of the specific questions raised in the design project specification.

      2. It should be crystal clear which aspects of your design are performed by hardware and which by software.

      3. The paper should be specific about how memory access works and what the address space looks like, both when the kernel is in control and when an application program is in control, and it should explicitly state whether or not the MMU is active when the processor is in kernel mode.

      4. The design must make provision for the kernel to address the entire memory. (Among other things, the kernel has to be able to load user programs into any part of memory.) If your design takes advantage of the limited size of programs by ignoring or reusing high-order memory address bits, that feature should not prevent kernel access to all of memory.

      5. If you added an MMU that translates addresses, then you should mention that the kernel must simulate that MMU translation when it needs to retrieve user arguments on supervisor calls.

      6. If your design specifies that the MMU is active in kernel mode, you need a good story on how on-switch avoids atomicity problems and how the instructions at the end of on-switch are able to obtain their operands.

      7. There should be at least a brief explanation of how the supervisor's "return to user" instruction works in the presence of the MMU. It is not obvious, because that instruction operates with the MMU in one state, but the next instruction is supposed to be retrieved with the MMU in a different state.

      8. If your design includes additional registers in the processor or registers in the MMU that some program explicitly loads or stores, the paper should specify the new processor instructions that perform the loads and stores, and indicate whether these instructions are legal in user mode.

      9. If the design of the hardware makes restrictive assumptions about the number or size of application programs, the paper should explain what advantage you gain from doing so.

      10. Comparisons with another design should not assume an incompetent version of the other design, but rather one that has had at least as much careful optimization as your design.

    2. Applicable to base-and-bound designs:

      1. The paper should clearly specify whether the value in the bounds register is the largest virtual address permitted or the largest physical address permitted, rather than making the reader figure it out by studying the block diagrams.

      2. If the bound is a physical address, the addition of the base address to the user address can create a value that overflows 16 bits, which in turn may wrap around and lead to an address that the comparator accepts but that is below the area allocated to this user. The MMU should include an explicit check for addition overflow and use it to trigger an out-of-bounds fault.

      3. The paper should discuss how your design deals with memory fragmentation, and why your method is reasonable. If you move application programs around, the design should specify which, if any, references to the program, both in kernel data structures and in the MMU hardware registers, need to be updated.

    3. Applicable to page map designs:

      1. The design should be specifically tailored to the environment and specifications of the Mote, rather than simply adopting a textbook page map design intended for large systems. Considering the small program size specified for Mote programs, your design should not require an associative cache or a translation look-aside buffer to achieve high performance--a register file can do the job faster, cheaper, and with less complexity.

      2. The design should specify how it keeps track of which physical blocks of memory are in use and which are available to be assigned.

      3. The design should specify what happens if a program tries to refer to a virtual address larger than any for which pages have been allocated.

      4. The paper should discuss the trade-offs involved in choosing the page size and why the page size you chose is suitable.

      5. If your overall design assumes a maximum program size, The design and pseudocode for grow_protection_domain should check for and reject requests to grow programs larger than that limit.

      6. The design for grow_protection_domain should account for the possibility that the original allocation request (or previous additional allocation requests) for memory did not evenly fill up the previously allocated pages.

      7. The design for grow_protection_domain should specify which MMU registers must be updated with new values, as well as which kernel data structures.

  3. Subtle issues that help identify exceptionally good papers:
    1. Applicable to all designs:

      1. If the application program issues a write to an address that is illegal or out of bounds, and the MMU responds by triggering a fault, the MMU should also have a gate, controlled by the fault line, that blocks the write request so that it does not reach the memory. Lacking this gate, the memory may still receive the data, the write request, and either the original bad address or some other bad address, and not realize that it shouldn't respond to this write request.

    2. Applicable to base-and-bounds designs:

      1. The design specification says that the memory is byte-addressed with no alignment restrictions, and that the processor loads and stores two bytes at a time. If an application issues a request to read or write the last byte it has been allocated, after the request goes through the MMU the memory system will allow it to also retrieve or store into the next byte of physical memory, which lies outside the allocation boundary. This problem should not be solved by changing the hardware application programming interface, because previously written application programs would have to be rewritten or recompiled. A better method is to simply leave one or two unallocated bytes between each program in physical memory.

      2. There is actually no need for the MMU to do address translation. If one instead specifies that the compiler should generate relocatable code (for example by using PC-relative addressing), then the MMU can be simplified to a lower-bound and upper-bound register pair, with no address translation. The hardware implementation reduces to those two registers plus two register comparators, which are disabled in kernel mode. And, if there is no address translation, questions about how the kernel addresses user arguments and how the return-to-user instruction works disappear.

    3. Applicable to page map designs:

      1. The design specification says that the memory is byte-addressed with no alignment restrictions, and that the processor loads and stores two bytes at a time. If an application issues a request to read or write the last byte of a page, after the request goes through the MMU the memory will allow it to also retrieve or store into the next byte of physical memory, but that byte of physical memory belongs to a different page. The design should point out that there is no good solution to this problem short of changing the specification of the programming interface.

  4. Another issue that every paper should address: Energy

    1. For all designs, there should be an analysis of the extra energy consumed because of the addition of your MMU. That analysis should be based primarily on increased running times and increased memory reference counts, and it should include estimates of the magnitude of each of those increases. If you think that those costs are insignificant, there should be some analysis that demonstrates the basis for that claim.

    2. For base-and-bound designs, the paper should specifically discuss the costs in energy and performance associated with copying programs from one place in memory to another to achieve compaction, as part of growing address spaces and of deallocating old and allocating new address spaces.

      Here is an example energy analysis for a base-and-bounds design: For the specified modem speeds, downloading a 2K program takes 400 ms and thus consumes 1800 ma-seconds of battery capacity. Compacting all 30K of memory to make room for a new program would require no more than 15,000 iterations of a 4-instruction loop, and on average probably only half that, say 30,000 instructions. Assuming that an 8 MHz computer runs 3 MIPS, 30,000 instructions would require 10 ms of CPU and RAM time and would absorb no more than 80 ma-seconds of battery capacity. Thus, doing one compaction for every download would increase energy usage by less than 5%--probably much less, if the program runs for a significant length of time. A similar analysis suggests that if programs run more than 200 ms between calls to grow_protection_domain, one compaction per call would increase energy use by less than 5%.


Comments and suggestions: Saltzer@mit.edu