M.I.T. DEPARTMENT OF EECS

6.033 - Computer System Engineering (Spring 2005)

February 15, 2005


Please find additional clarifications and details in the DP1 FAQ.

Design Project 1 - BED Bus

I. Assignment

There are two deliverables for 6.033 Design Project #1:

  1. Two copies of a design proposal not exceeding 800 words, due on Tuesday, March 1, 2005, and:
  2. Two copies of a design report not exceeding 5,000 words, due on Thursday, March 17, 2005.

The organization of this document is as follows. Section II gives an overview of the problem, which Section III elaborates on. Section IV lists the requirements of your design. Section V mentions some issues to motivate the analysis of your design. Section VI describes the format of your written report. Section VII states the collaboration policy, and Section VIII summarizes the deliverables once again.

We strongly recommend that you get started early. A good design is likely to take more than just a few days to put together.

II. The Problem

In 6.004, you designed a microprocessor, the brain of a modern computer. But just as your brain would be useless without its nervous system, the Beta would be useless without a way to connect to external devices. Processors need to communicate with the outside world -- through video displays, network cards, and keyboards. It's these devices and others that turn a processor into a useful computer system.

In this project, you will design a bus: a way to attach lots of external devices to the Beta at the same time. We call these devices "Beta External Devices," or BEDs. They can be keyboards, hard drives, iPods, video cards, DDR pads, digital cameras, Ethernet cards, mice -- you name it.

Your design will need to specify how the bus works at four levels:

It's very important that your design be simple and correct. Your design does not have to do everything. But you need to be able to identify and discuss its weaknesses and limitations. Explain why you chose the trade-offs you did, and what the consequences of your choices are.

As a high-level way of beginning to approach this problem, you may want to review the material related to naming and name resolution taught in Lectures #3 and #4, as well as chapter 2 of the class notes. Many of the issues in this design project are related to how different hardware and software components name each other. You may also find it useful to review the discussion of the bus abstraction in section B of chapter 3 of the class notes.

III. Problem Walkthrough

This section walks you through the parts of the problem and starts you off with a solution to each section. In your report, specify what you have designed for each of the four major sections. Explain what your design can and cannot do. You are not required to use our partial solution, but if you solution is different, you should explain how and why.

Your design will need to specify how the bus works at four levels described above: physical connection, identification, initialization, and application interface.

(A) Physical Connection

First, see 6.004's Lab 7 for a refresher on the Beta's inputs and outputs. You may also find it helpful to review the 6.004 bus lecture.

How will BEDs connect to the Beta? One idea is to use the Beta's "Memory Data Address," "Memory Read Data" and "Memory Write Data" pins. In 6.004, those pins were connected to a data memory that the Beta could read and write from. The Beta puts an address on the 32 "Memory Data Address" pins, and sets either "Memory Write Enable" (MR) (to store the 32 "Memory Write Data" bits in the address), or "Memory Output Enable" (MOE) (to read 32 bits on the "Memory Read Data" pins).

But there is no rule that says these pins may only be connected to a memory. You should use these pins as the physical bus, in addition to connecting them to memory. Here is a hardware design to get you started:

The following signals are part of the bus, and any BED can connect to them: Memory Data Address (32 lines), Memory Read Data (32 lines), Memory Write Data (32 lines), Clock, Interrupt Request (IRQ), Memory Write Enable (WR), Memory Output Enable (MOE), Power (VDD), and Ground.

You will need to specify the following software issues

You should be able to answer this design project without adding any additional hardware (however, if you can argue convincingly that additional hardware would be useful, you may do it.) You are not required to add additional bus lines or specify any of the electrical properties of the connection between the BEDs, the bus, and the processor.

Note: Chapter 3, on pages 3-16 to 3-18, describes a multi-master bus based on the communication path abstraction. In contrast, this design project suggests designing a single-master bus (the Beta is the master) based on the memory abstraction. Starting in the middle of page 3-19, the notes go on to explain how to do memory-mapped I/O on top of the communication path abstraction. That discussion is relevant to this design project, even though the earlier material is not directly relevant. For a single-master bus, the underlying bus design in chapter 3 could have been based on the memory abstraction to begin with.

(B) Identifying Each BED

The Beta needs to be able to figure out how many BEDs are connected to it, and it needs to be able to talk to each BED independently. If you have BEDs look for their own "names" on the Memory Data Address lines, then each BED will be named by its own, unique, 32-bit ID.

How are these 32-bit IDs assigned? Here is one possibility:

Addresses less than 2^31 are reserved for the data memory (up to 2 gigabytes). That leaves all of the addresses between 2^31 and 2^32 (another 2.1 billion addresses) for BED IDs. Each BED gets shipped from the factory with a distinct, unique 32-bit ID whose most significant bit is always 1. Each BED listens for its own ID on the Memory Data Address lines, and if the ID matches, the BED responds to the Beta's read or write request.

There are two problems with this proposal:

  1. There are more than 500 million computers in the world. If every computer has 5-10 BEDs (hard drives, sound cards, keyboards, mice, video cards, network cards), we have already run out of the 2.1 billion possible IDs. Simply doubling the ID space doesn't solve the problem, either.
  2. Although there do exist some examples of mass-produced hardware devices that have unique IDs (such as Ethernet), requiring manufacturers to agree on the format for a unique ID typically requires many years of difficult committee work. For the purposes of this project, you should assume that manufacturers were unable to come to a consensus on the format of unique IDs, so you should not assume that such IDs are available.
You also shouldn't make the users have to assign an ID to each BED themselves. We want this system to be easy to use ("plug-and-play", to use marketing jargon). So your design will probably need to assign IDs to BEDs dynamically, when they are plugged in.

(C) Detecting and Initializing New BEDs

How will the Beta know when a new BED is attached to the bus? How will the Beta assign that BED a "name" for addressing on the bus?

To start you off, we suggest you specify that all BEDs come from the factory with a fixed "initialization" address. When the Beta detects that a new BED has been added to the bus, it sees if the BED is still using the "initialization" address. If so, it communicates with the BED and instructs it to change to a new, unique, address.

Some of What's Missing:

(D) How Does Software Interact With BEDs?

Software programs running on the Beta will want to use BEDs connected to the bus. E.g.:

Applications have been written to use the API proposed in the Unix Paper [MIT Certificates Required], where BEDs are identified by filesystem entries in the "/dev" directory (as described in Section 3.3 of the Unix paper).

Filesystem entries are only present if such a BED is actually connected to the bus. For instance, if only one hard drive is connected, then only one device with the name /dev/hdXX (where XX is some integer) will exist in the filesystem.

Applications communicate with BEDs using the API described in Section 3.6 of the Unix paper.

Your job is to describe how you would implement the API. Here is an outline of one possible implementation to get you started:

Every BED comes with an identifier, describing what "type" of device it is (sound card, hard drive, etc.). Each type of device has a corresponding "device driver" -- a part of the operating system kernel that knows how to talk to the device.

When the BED is first initialized, it communicates with the operating system kernel and says what type of device it is. The kernel uses this to select the proper device driver, which is then responsible for setting up the entry in /dev, and for handling application calls functions such as open(), read(), write(), and close().

Some of What's Missing:

IV. Requirements

Here are the requirements of your design.

(A) Physical Connection

  1. Your design must specify how BEDs connect to the Beta. Are you proposing any hardware changes to the basic design described above? How are the wires on the bus used to transfer data to and from the BEDs and data memory?
  2. Your design must specify the capabilities a BED must have. Does every BED need a processor? Do BEDs need nonvolatile storage?
  3. Your design must specify how the Beta talks to its data memory. Does your design limit the maximum amount of data memory the Beta can address?
  4. Your bus must allow the Beta to realize when a new device is inserted and must allow the Beta to assign a unique identifier (name) to that device.
  5. Your design must specify how the Beta sends data to BEDs, and how BEDs send data to the Beta. Do devices on the bus have addresses that are different from memory addresses? If so, how are memory references resolved to bus addresses?
  6. Your bus must allow BEDs to send data asynchronously to the Beta by raising interrupts. It must allow multiple BEDs to raise interrupts at once. (For example, a user hits a key on the keyboard at the same instant that the Ethernet card receives a packet from the network.)
  7. Your bus must allow at least 16 devices to be connected at once.
  8. Assuming a Beta clockspeed of 10 MHz, your bus must support data transfers between the Beta and a BED of at least 30 megabytes per second.

(B) Identifying Each BED

  1. Your design must allow at least 100 billion BEDs to be manufactured.
  2. Your design must not require manufacturers to install a unique ID in BEDs as they leave the factory.
  3. Your design must not require the user to manually assign IDs to BEDs.

(C) Detecting and Initializing New BEDs

  1. Your bus must be able to identify and initialize a new BED that was connected while the Beta was turned off. You should use pseudocode or show a diagram illustrating how initialization works.
  2. Your design must explain whether the Beta reassigns or maintains bus addresses when (a) the Beta is rebooted, (b) BEDs are removed and re-inserted, and (c) BEDs are removed and plugged into another computer. If they are maintained, you should describe how this is done.

(D) How Does Software Interact With BEDs?

  1. Your bus must provide some means of identifying the proper device driver to load for a particular BED. If identifiers are used to identify "types" of devices, who assigns these identifiers? Is there a limit?
  2. Your design must specify how filesystem device names (e.g., "/dev/hd0") are mapped to bus addresses. How are paths of this sort resolved to a particular device driver?
  3. Your design must specify what happens when an application calls open(), read(), write(), or close(). (You do not need to specify what happens when other Unix file system calls, such as ioctl() and lseek() are called.) Specifically, you should specify how each of these API calls is processed by the OS. How does the OS determine which BED each of these calls corresponds to? How does the OS issue these calls to the BED? How are the results of these calls delivered from the BED to the OS? In additional to a detailed English description of what happens on each of these calls, your report should include at least one picture explaining how the Beta transfers data from memory to a particular type of BED (e.g., an Ethernet card), and some pseudocode for open and write for that device.
  4. Your bus must allow the Beta to be rebooted without shuffling the order of hard drives and sound cards. For example, /dev/hd2 can't become /dev/hd0 after a reboot.
  5. Your bus must allow BEDs to be removed without shuffling the order of devices. For example, if three hard drives are connected to the Beta, and then the user removes the hard drive corresponding to /dev/hd1, /dev/hd2 still needs to map to the same hard drive as before.
Your report should present a design that satisfies these requirements. You don't need to describe each requirement individually; rather, we are looking for a coherent design from which it is obvious that the requirements have been met.

V. Issues to Consider

This section lists some issues to consider in analyzing your design. You should use these questions to motivate your analysis, but don't just answer these questions in sequence. Rather, make sure that you do answer each question somewhere in your report.

It's okay, and sometimes desirable, to say, "no, my design doesn't do that" as long as you can identify what your design can and can't do, and explain why you made the trade-offs you did. Remember: a simple, correct design that meets the requirements laid out above is more important than a complex one that is hard to understand and does a flaky job. When in doubt, leave it out!

VI. Your written work

This section provides some suggestions on writing style and outlines the standard structure of a design report.

Suggestions on writing style

Who is the audience for this paper? Write for an audience consisting of colleagues who took 6.033 five years ago. These are readers who understand the underlying system and network concepts and have a fair amount of experience applying those principles, but they have not thought carefully about the particular problem you are dealing with. Assume that your paper will also be used to convince readers that you have a feasible design. Finally, give enough detail that your project can be turned over to an implementation team with some confidence that you will not be surprised by the result. One qualitative way that 6.033 reports are evaluated is by asking the question, "Do we want this person on our team? Can this designer provide us an accurate description of his/her design?"

The following are some tips on the organization of a design report. You can find other helpful suggestions on writing this kind of report in the 6.033 online lecture "How to Write Design Reports". You may also want to look at the Mayfield Handbook's explanation of IEEE documentation style. A good book on writing style is: "The Elements of Style," by William Strunk Jr. and E. B. White, Third Ed., MacMillan Publishing Co., New York, NY, 1979. (Also available from the MIT libraries.)

Report Outline

The following is a suggested outline for your report. You don't have to follow this organization, if you think your design would be better described some other way. The full report (including abstract) should be no longer than 5000 words long. Please choose a font size and line spacing that will be easy on our aging eyes and make it easy for us to write comments on your report (e.g., 11 pt font or larger; 1.5-spaced or greater.)
Title Page

Give your design report a title that reflects the subject and scope of your project. Include your name, recitation time and section, and the date on the title page.

Table of Contents
Abstract

A good paper begins with an abstract. The abstract is a 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 elaboration. It announces any conclusions you have drawn. Abstracts are normally about 200 words long. Write the abstract after you have written your report.

1. Introduction

Summarize the salient aspects of your design and summarize the rationale for the design you have chosen. You may assume that the reader has read the DP1 assignment; you do not need to restate the problem in detail.

2. Design Overview

Explain the approach or architecture conceptually before delving into details, components, and mechanics. (Remember, you are not writing a mystery novel!) Present any analysis clearly and concisely. Make sure that you include a figure of your design architecture.

3. Design Description

Explain and elaborate your solution. Show how your solution satisfies the constraints and solves the problem (or how it fails to do so). Explain how your design choices are reasonable or desirable in the context of the problem statement. Include analysis of the estimated performance characteristics of your solution. You will almost certainly need to use figures or pseudocode in this section. If you use pseudocode to illustrate your solution, be sure to describe what the pseudocode does in English as well in the text.

4. Feasibility and Analysis

Describe the alternative approaches that you considered and rejected, and why you rejected those approaches. Your paper will be more convincing if you explain why your design is appropriate and why your design 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 the exorbitant cost as a reason for choosing your less general but cheaper approach.) 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. If you prefer, you may integrate arguments about the feasability of your design into the design description rather than including this as a separate section.

References

Document your sources, giving a list of all references (including personal communications). The style of your citations (references) and bibliography should be in the format described in the Mayfield Handbook's explanation of the IEEE style.

How do we evaluate your report?

When evaluating your report, your recitation instructor will look at both content and writing and assign a letter grade. The writing program will separately grade the proposal for writing and assign a letter grade.

Some content considerations:

Some writing considerations:

CI-M Considerations

Your design report will be evaluated by the writing program staff as a part of the Communication Intensive in the Major requirement.

VII. Collaboration

This project is an individual effort. You are welcome to discuss the problem and ideas for solutions with your friends, but if you include any of their ideas in your solution you should explicitly give them credit. You must be the sole author of your report.

VIII. Tasks and Due Dates

Please use 1-inch margins.