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:

Two copies of a design proposal not exceeding 800 words, due on Tuesday, March 1, 2005, and:

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:

(A) Physical Connection. We specify the one possible wiring configuration between the BEDs and the Beta, but you will need to design the protocol that the Beta uses to exchange data with BEDs and its memory.
(B) Identification. How does the Beta know what BEDs are connected? How does the Beta speak to an individual BED?
(C) Initialization. What does the Beta do when BEDs are added or removed?
(D) Application Interface. How does the operating system (OS) allow software applications to interact with BEDs?

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.
Each BED connects to all of these lines, in parallel.
When the Beta is sending data to a BED, it sets WR and sets the Memory Data Address to be the "name" of the destination. It sets Memory Write Data to the bits being sent.
When the Beta requests data from a BED, it sets MOE and sets the Memory Data Address to be the "name" of the BED. The BED puts 32 bits of data onto the Memory Read Data lines.
You may wish to look at 6.004 Lab 6 to refresh your memory about how the Beta interacts with its memory.

You will need to specify the following software issues

What addressing scheme does the Beta use to differentiate requests to BEDs from references to data memory?
How does the Beta realize when new devices are inserted?
Consider an Ethernet interface BED that occasionally receives packets from the Internet. What should the BED do when it receives a packet? (Hint: Remember the IRQ pin on the Beta.) How does the BED send that packet to the Beta? Suppose the user hits a key on the keyboard at exactly the same instant this packet arrives. In general, what happens if several BEDs are trying to send data to the Beta at the same time?

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:

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.
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:

What if the system boots up and there is a new BED connected, fresh from the factory? How does it assign a name to it? Doing this assignment may require support from the "Physical Connection" section of your design.
If you reboot the Beta, do the BEDs keep the same bus names?
What happens if you unplug a BED and plug it right back in? What bus name is it assigned?
What happens if you unplug a BED from one computer and plug it into another computer?

(D) How Does Software Interact With BEDs?

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

The file system wants to read and write from hard drives.
An MP3 player wants to send audio to the sound card.
A Web browser wants to interact with the network card.
The display system wants to send data to the video card.

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:

Who assigns these "type" identifiers?
Given the "type" identifier, how does the kernel know the proper device driver to load for a new BED? You may assume that a good-sized collection of device drivers is preloaded at boot time, and the main problem is to identify and hook up with the correct one. It is alright to pop up error messages of the form "Sorry, no device driver is available for the BED you just plugged in."
What is the mapping between entries in /dev and bus addresses? What determines which hard drive is /dev/hd0, which is /dev/hd1, and which is /dev/hd2?
What happens to entries in /dev when the Beta is rebooted? How do we make sure that the hard drives and sound cards don't get shuffled around?

IV. Requirements

Here are the requirements of your design.

(A) Physical Connection

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?
Your design must specify the capabilities a BED must have. Does every BED need a processor? Do BEDs need nonvolatile storage?
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?
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.
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?
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.)
Your bus must allow at least 16 devices to be connected at once.
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

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

(C) Detecting and Initializing New BEDs

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.
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?

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?
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?
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.
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.
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!

Your design specifies a method for using the data memory. Does this method require existing applications written to use the API described in Section III to be modified or re-compiled? What about applications written for the original Beta (without your modifications to support BEDs?)
Assume the Beta's clockspeed is 10 MHz. What is the maximum speed, in bits per second, that a BED can send data to the Beta?
What is the maximum number of BEDs that can be connected to the bus at a time?
What happens when a device is unplugged? For example, imagine three applications are reading data from /dev/hd0, /dev/hd1, and /dev/hd2. The hard drive corresponding to /dev/hd1 gets unplugged. Do the other two applications continue working? Now the hard drive corresponding to /dev/hd2 is switched off and then switched on again. Does it stay as /dev/hd2, or does it get a different entry in /dev? (Please do not consider the electrical issues associated with wires making or breaking contact as they are inserted or removed. Assume that the hardware designers have resolved these issues and focus on software concerns.)
What happens if more than one BED is added to the Beta at once? For instance, suppose the user buys a brand-new keyboard, mouse, and joystick, and plugs them all into the Beta while it is turned off. How will your design behave in this situation?
What happens when there is contention for the state of the bus lines by multiple BEDs? In particular, what happens if one BED tries to set some line HIGH, and another BED tries to set the same line LOW? Or does this situation never occur in your design?
You are working as a music recording engineer for The Betales. You set up a Beta-based recording computer in the studio with eight sound card BEDs. Two sound cards are used for Haringo's drums, two are used for Alyssa's and Ben's guitars, and four sound cards are used for the vocals. It takes you many hours to run all of the cables and adjust the different software settings (volume, equalization, signal routing) for each sound card BED.
One day, the Beta crashes and needs to be rebooted. When it starts back up, will the system remember which sound card was which? Or will they be renamed unpredictably, costing you another several hours of work tracing the cables?
In 2004, you bought a 10 MHz Beta-based computer for $2,000 and souped it up with lots of fancy BEDs (Dolby Digital sound card, MiniDV camcorder, Ethernet card, nVidia graphics card, wireless keyboard, and an iPod).
By 2005, Wal-Mart is selling a 20 MHz Beta-based computer for $1,000, so you can't resist buying one as an upgrade. Will your old BEDs work on this new computer? Why or why not?
Along similar lines, suppose you want to use your BEDs (designed for a 10 MHz Beta) with an older computer you bought your freshman year. That computer's Beta only runs at 3 MHz. Will your BEDs work on that older computer? Will they work on the same bus as older BEDs that you also bought your freshman year and have been using with the 3 MHz computer? Why or why not?
What if the user wants to plug their digital camera BED directly into their photo printer BED, without actually using a Beta-based computer at all? Does your bus design support this? If so, explain how.
Your lab buys a fancy $50,000 printer BED. You want to share it between computers. Is there any way to put this printer on a bus that has more than one Beta-based computer? For instance, could you have the bus include the printer, your computer, and your coworkers' computers? If not, how else could you share the printer between computers?

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:

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 will not do the job. On the other hand, unnecessary complexity is bad.
Is your solution a good fit with the goals of the system?
Is your analysis clear?

Some writing considerations:

Is the report well-organized? Does it follow standard organizational conventions for technical reports? Is the grammar and language sound?
Does the report use diagrams where appropriate? Are the diagrams appropriately labeled and referenced in the text? You may wish to consider including a diagram to help explain any protocol or algorithm you propose.
Does the report 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 the report address the intended audience?
Is there a list of References?

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

Two copies of design proposal (800 words or less) Due: March 1, 2005.
The design proposal should be a concise summary of your design choices and of the overall system design. Also, if any of your design decisions are "unusual" (particularly creative, experimental, or risky, or specifically warned against in the assignment), it would be wise to describe them here. You will receive feedback from both your TA and the Writing Program in time to adjust your final report.

Two copies of detailed design report (5000 words or less) Due: March 17, 2005.

Please use 1-inch margins.