15-251: Processor Lab

The processor lab

This page serves to cover some of the more basic concepts in the processor lab, as well as a repository for frequently asked questions. Please also remember that we have a discussion board (cyrus.academic.cs.15-251.discuss), or if you're too shy you can email us directly :).

Note that new additions will be indicated in blue.

Important Notes :

Homework 8 will be due at the beginning of lecture on Tuesday, March 22nd. You will be handing in a hardcopy of the assignment (i.e., in paper form). You are allowed to hand it in on Monday during recitation, if you finish early.
You are allowed to handwrite this assignment.
Note that this homework is not due on the Tuesday after Spring Break, but the one afterwards (the 22nd of March).
UPDATE: The behavior of any jump instruction is officially undefined if the previous instruction is non-arithmetic. That is, the "jump always" instruction is permitted not to jump if the previous instruction wasn't an arithmetic instruction and all the EFLAGS are set to 0.

Schedule:

Pace yourself!! By Wednesday, March 16th you should definitely be working on registers (and hopefully will be further along).
Note that we do NOT expect you to be working over Spring Break - this assignment is designed to be completed even if you don't do any work over the break.

Frequently Asked Questions:

Q: Can I just implement the processor with both extra credit and regular instructions (instead of doing seperate ones for each)?
- Yes. However, note that if your extra credit is screwed up, then you may impact the regular processor instructions. Be certain that the processor you come up with at the end definitely implements the basic instructions correctly.

Adders and Addition:

Part of this lab asks you to write a mechanism for doing addition. To start, think back to grade school; how did you add two numbers? (add two digits, possibly having a carry, and repeat until you've reached the end of the number).
- It turns out that you can do the same thing with binary numbers (in fact, you saw this in homework 6). As a test, try adding 1001 to 0011 (you should get 1100).
So now you know how to add two binary numbers. How can we do this with circuits? First, try solving a simpler problem - create a 1-bit adder. Namely, your circuit should take two bits b₁ and b₂ and output two values - one on wire, output the sum and on the other ouput the carry. Note the following examples:
- b₁=1 and b₂=0 should output 0 on the carry wire, and 1 on the sum wire.
- b₁=1 and b₂=1 should output 1 on the carry wire, and 0 on the sum wire.
Cool, we now have a 1-bit adder :). We now need to find a way to create a four-bit adder. Perhaps we can use a combination of 1-bit adders to allow us to do this.
- First attack an easier problem: try sketching out a 2-bit adder. Remember we now might have a carry from the first bit addition that affects the second.
- You can use the same ideas from the 2-bit adder to create a 4-bit one. Note that this addition is a linear operation - you need the carry from the previous bit addition to computer the new sum/carry digit.

Two's complement:

In order to complete this lab, you will require a basic understanding of how machines store negative numbers.

There is a nice, painless introduction to the Two's Complement representation of numbers here.
Back when people were trying to figure out how to store negative numbers in a computer, they came up with a list of desirable properties.
- One of the most important was that addition should extend naturally onto the negative numbers - one should just be able to use the natural adder developed above to add negative numbers.
- Another nice property would be that one should easily be able to tell whether a number was negative or not.

So smart people went to small meeting rooms with decaffeinated coffee and developed the Two's Complement system. This representation turns out to have both of the above properties, and almost every computer nowadays uses this method to represent integers.

Consider an n-bit number. Like in normal binary, the first digit is 2⁰, the second is 2¹, etc. The leftmost bit, however, represents -2ⁿ rather than 2ⁿ.

As a concrete example, look at the following representations for numbers in an 8-bit system.

Number	Two's Complement Representation	Notes
-128	1000 0000	-128 = -128
-74	1011 0110	-128 + 32 + 16 + 4 + 2
-1	1111 1111	-128 + 64+ 32 + 16 + 8 + 4 + 2 + 1
0	0000 0000	0
1	0000 0001	1
127	0111 1111	64+ 32 + 16 + 8 + 4 + 2 + 1

Why is this a good system? As mentioned above, it turns out that addition works nicely and intuitively :). Moreover, this implies that we can use the same circuit for both addition and subtraction - just negate a number and add the two together.