Overview

The extra credit problem centers around the design and analysis of an imaginary computer system.  The requirements for this computer system are given in the next section.  Students have two options for earning the extra credit:

1. Analyze my computer design:  I will give you a complete (but inefficient) solution to the design problem.  To earn this extra credit you will need to give a thoroughly detailed evaluation and analysis of the performance of my solution.  (The exact requirements are given below.)  This extra credit option is worth up to a two grade increment advancement on your final grade, depending on the quality of your work.
2. Design and analyze your own computer that is better than mine:  To earn this extra credit you will prepare a complete design that meets the requirements given in the next section.  In addition, you will perform the a thoroughly detailed evaluation and analysis of the performance of your solution compared to mine.  (This part is exactly the same as option #1, but you analyze both solutions instead.)  This extra credit option is worth up to a four grade increment advancement on your final grade, depending on the quality of your work.

All work should either be typed, or very neatly written.  There are three possible grades for the extra credit work:

• 'A' - Good and correct work (a few minor flaws OK), neat and organized, and the student understands it well.
• 'B' - Sufficient and mostly correct work (a few major flaws OK), and the student has an adequate understanding of the material.
• 'No credit' - Nominally correct work, not organized, not thorough, or the student has an inadequate understanding of the material.

Your goal in completing the extra credit should be to make sure you understand the material, and to convince me that you deserve a better grade. 

Computer System Design Requirements

The embedded system must read one hundred 16-bit words from an input sensor, sort the words (as unsigned data), and write the sorted words out to an output device.  It must then repeat this process over and over again.  As you design your system, keep in mind that a faster part will result in more profit to the company (and to you).  The goal is to process as much data each second as possible.

Constraints:  Your computer system will be placed on a chip with other components and is subject to the following constraints:

• CPU design:  You may use a single-cycle design, multicycle design, or pipelined design.  Assume the following clock periods:  For a single-cycle design, 6 ns.  For a multicycle design, 2 ns.  For a pipelined design, 1 ns.  These clock periods are fixed - they cannot be shortened.  If you have too many instructions in your instruction set design, these clock periods may be longer, see below.

  (Note that on a cache miss, each design type will have to wait extra clock cycles for memory data to become available.)

You may use up to 10 registers in your design (including PC, but not including pipeline stage registers).

You may assume that you have ALU(s) equivalent to the ALU we studied in class.  It can add, subtract, do any logic operation, compare values, detect overflow, detect carry out, and detect zero.  Assume that the ALU only operates on unsigned data.

• Main memory:  You have 4096 bits of main memory available. It may be addressed as bytes, words, or any other way you like.  Assume that any memory access (read or write) takes 10 ns and that memory accesses may not be overlapped.

  Since memory is limited, it is up to you to decide how to put all the data and instructions in memory.

• Cache:  You have 512 bits of cache memory to use any way you like.  You may use it for branch prediction and/or caching memory, but all data, tag, and status bits must be stored within that 512 bits.  Assume that accesses to the cache memory take 1 ns.  This means that on a cache hit, the data will be available in 1 ns. 

  The cache may be split into two caches if you like.  Also, the cache supports simultaneous reads and writes.

• Instruction set design:  Assume that you can have as many instructions as you want, and that you may have the instructions do any work that your CPU design supports.  There are practical limitations, however, and you will pay a time penalty if you have too many instructions in your instruction set. 

  As you design your instruction set, you must allocate a fixed number of bits in the encoded instructions for the opcode.  If you allocate n bits for the opcode, then you can have at most 2ⁿ instructions.  In addition, if you allocate n bits for opcodes, but you include more than n instructions in your design, your CPU clock period will increase according to the following formula:

  clock period penalty = (# of available instructions - 1) / n ns

  Round down.  Example: Assume you designed a pipelined processor.  If, when deciding on how to encode instructions you allocate 4 bits for the opcode, but your instruction set has 10 instructions, you will have to add 2 ns to the clock period.  This would make the clock period for this pipelined design 3 ns.

• Input / Output:  Assume there are two external hardware modules that you will interface with.  The input module, when activated, will supply a 16 bit value in 5 ns.  (You should repeatedly read from it to retrieve the 100 data words.)  The output module, when written to, will accept a 16 bit data value every 5 ns.

  You may decide to use memory-mapped I/O, or specialized instructions for reading and writing data.  If you use memory-mapped I/O, you will need a memory controller.  Assume the memory controller adds 1 ns of latency to all accesses to main memory and to the I/O.  If you use specialized instructions, you will need additional data paths in and out of the processor.  In this case, assume that your I/O instructions add 5 ns of latency (in addition to the I/O latency) for every I/O instruction.

• Software:  You will write a program that runs on your processor.  This program must take a fixed amount of time (approximately) to read the 100 words of data, sort them, and write them out.  Note that this eliminates several popular sorting algorithms that take varying amounts of time.

  Remember that memory and cache are limited, so keep your program small.

My solution

Extra credit option #2

CPU: Select one of the three allowed design types: Single-cycle, multi-cycle, or pipelined.

Provide a block diagram (similar to those in Chapter 5 and 6) that shows the major components of your CPU along with control lines and data paths.  (I recommend using different colors to make your diagram easy to read.)

You may assume that your CPU interfaces with cache memory directly, and that cache memory may be split into two caches.  (See the constraints above, this simplifies building the diagram.)

In addition, if you use specialized instructions for accessing the I/O units, draw the required datapaths in your processor design.

Provide a few short paragraphs explaining your design decision.

Main memory:  Specify the memory architecture for your system.  How will memory be addressed?  How will it be organized?  Are there alignment restrictions?  You must make sure that your memory design fits within the allotted number of bits.

First, list your memory design specifics in a short table.  Then write a few short paragraphs justifying your memory design.  In addition, you should draw and label a diagram that indicates where data and instructions will be stored in memory.

Cache:  Specify a cache architecture (in detail).  If you include a branch prediction unit, include it as well.  You must make sure that your cache design fits within the allotted number of bits.

First, list your cache design specifics in a short table.  Draw the cache(s).  Then write a few short paragraphs justifying your design. 

Instruction set design:  List all of the instructions available to the programmer.  Your instructions must be supported by your CPU design.  Give the following information for each instruction:

Assembly language opcode/arguments:  How will the programmer write this instruction?

Machine language encoding:  How is this instruction converted to a numeric code?  Show how many bits will be used to identify the opcode, arguments, registers, immediates, etc.

CPU operation:  How will your CPU design execute this instruction?  Give an indication of which control lines will be set and how data will flow through the processor.

CPU timing:  Indicate how much time the instruction will take to complete.  Also list any known hazards or stalls that may be encountered.  (Note that in my solution I do not provide this information - it is part of the analysis stage for extra credit #1 and #2.)

Input / Output:  Indicate how the program will access the I/O: Choose either memory-mapped I/O or specialized instructions.  Provide enough detail that it is clear how the I/O is accessed from within the program.

In addition, draw a block diagram that shows the CPU, cache, main memory, the I/O units, and a memory controller (if needed) all connected together with data buses.  Explain your design decisions in a few short paragraphs.

Software:  Given your design and your instruction set, write the program that will perform the data operation.  Your program must read 100 16-bit words from the input, sort them, and write them to the output.

Comment your code, and indicate the memory address of the first line of code, the last line of code, and any labeled lines of code.  Also, if you use memory for storing variables, list these memory addresses alongside the variable labels.  Your code should resemble a complete assembly language program.

It should be easy to verify your code by looking at it.  If necessary, change your opcodes so that they are easy to decipher visually.

Extra credit option #1

Justify each answer by showing your work and explaining the result!  No credit will be given if you just show numbers.

1. What is the clock period for this design?  Was there any penalty due to the number of instructions?  If so, what was it?

2. What is the latency for a cache hit?  What is the latency for a cache miss?  What is the latency for a read from the input device?  What is the latency for writing to the output device?  In this design, do you have to wait for output device writes to complete?

3. Compute how long will each instruction will take to complete for each possible combination of cache misses / hits.  (This can be done separately for each instruction.)

4. If the design is pipelined, what hazards are there, and how many cycles will you have to stall for each hazard?

5. Analyze in depth the total running time for reading, sorting, and writing 100 data values using the supplied software.  While it is impractical to fully simulate the cache, you should estimate its performance for each instruction / data access.  Your analysis should include a justification for the average time to complete each and every instruction in the program. 

   In addition, you should total up the time required for each major portion of the program, and give a grand total for how long the program will take to do one set of data.

   How many times a second will this design read, sort, and write one set of data?

   This is the bulk of this part of the extra credit.  Make sure to spend the time needed to get it right.  Show your work, and give written explanations for each step you take.

6. (For extra credit #1, but not for #2) List at least three possible improvements that could be made to my design, and estimate their impact.  You do not need to redesign the system, just speculate and justify your answers.

   Write three short paragraphs, one for each possible improvement.

Page updated Sunday November 30, 2008 at 15:21:04.