! CS3410-sp21 Assignments P1: ALU
Account Dashboard Courses Calendar Inbox History Help
Due Wednesday by 11:59pm
Roremoninlinde)r:eTxcheispitsyaonuirnadsisvigdnueadl pTreoajmectm. Demobneorts.shEovewrytohuinrgwyooruk tsoubamnyitomneusotrbloeoikmaptlethmeewntoerdkboyf yaonuyopneers(oinntahlley.class Updates to this assignment will be posted as Canvas announcements.
Overview
Spring 2021
Home Announcements
Ed Discussion Syllabus Assignments Modules
Quizzes
Zoom
Grades 4 Library Reserves
My Media
P1: ALU
Points 100
Available
a!er Feb 10 at 12am
Text
In this project, you’ll design a RISC-V ALU. RISC-V is an instruc”on set architecture (ISA) that defines the func”ons a computer can carry out through assembly instruc”ons. An ALU, or arithme”c and logic unit, performs many of the core computa”ons dictated by those instruc”ons. So in short, you’ll be building a key component of a CPU. Throughout this project and the next, you’ll move from small, special-purpose circuits to the full, complex CPU in all its glory! (Well, not all. We’ll be ignoring more advanced RISC-V features like traps/excep”ons and coprocessor instruc”ons.)
The program you will use to create your ALU is Logisim, a free hardware-design and circuit-simula”on tool. Logisim comes with libraries containing basic gates, memory chips, mul”plexers and decoders, and other simple components. In the next project, you will use many of these components to build your final CPU.
However, for this assignment you may ONLY use the following Logisim elements:
Anything in the Wiring folder except: constants, and anything smaller/less abstract than a gate including but not limited to the resistor, power, ground and transistor elements.
Anything in the Base folder (wires, text, etc.)
Anything in the Gates folder except: the even parity, odd parity, and controlled buffer elements
Anything in the Plexers folder
Important – Use this guideline for your circuit design to avoid losing points! Academic Integrity. As one of the most widely studied architectures, RISC-V has a wealth of informa”on available on the web and in textbooks. You may consult any RISC-V documenta”on available to you in order to learn about the instruc”on set, what each instruc”on does, how an ALU works, etc. However, we expect your design to be en”rely your own, and your submission should cite any significant sources of informa”on you used. If you are unsure if it is okay to borrow from some other source, just ask the TAs. If you are hesitant to ask the TAs or to cite the source, then it is probably not okay. Plagiarism in any form will not be tolerated. It is also your responsibility to make sure your sources match the material we describe here (warning: the top Google hit for “RISC reference” contains several inaccuracies).
What to Submit
All of the following should be subcircuits in a single Logisim circuit file. To get you started we’ve provided an ALU_template.circ file with all the appropriate inputs and outputs specified.
A single Logisim project file containing your ALU and all needed subcomponents. Please ensure that your circuit has no external dependencies!
We will use Logisim’s test vector func”on to test your circuits. In order for it to work correctly, you must ensure that the Logisim circuits containing your solu”ons are named precisely “Le!Shi!32”, “Add32”, and “ALU32”, and the inputs/outputs are named “A”, “B”, “Op”, “Sa”, “C”, and “V”.
A design document that details the implementa”on of your circuit.
A README with your name, NetID, cri”cal path, and gate count.
Three text files containing your test vectors, one for each of the Le! Shi!er, Adder, and ALU circuits.
Circuit 1: Le!Shi!32 Le!Shi!32:
Inputs:
C = (B << Sa) | carrybits B[32], Sa[5], Cin
Outputs:
The output C is computed by shi!ing B to the le! Sa bits, and filling the vacated bits on the right with carrybits , which is just Sa copies of Cin . The shi! amount Sa can be anything from 0 to 31, encoded as an unsigned integer. Note: Some inputs and outputs are busses (as noted by the bus width in brackets); the rest are 1-bit wide.
One way to implement such a shi!er is to perform the shi! as a series of stages: the first stage shi!s either 0 or 16 bits, the second stage either 0 or 8 bits, the third stage either 0 or 4 bits, and so on. By enabling different combina"ons of stages, the circuit can shi! any desired amount.
Hint: Shi!ing a value on a 32-bit bus by a constant amount, either le! or right, is simply a ma$er of adding, removing, and renaming the wires on the bus, and so requires no gates at all (this can be done with a spli$er).
Circuit 2: Add32
C[32]
C = A + B + Cin; V = overflow A[32], B[32], Cin
Outputs:
The output C is computed by adding A , B , and Cin . A , B , and C are signed two's complement numbers. If
overflow occurs, the output V should be asserted. In such cases, the output C should correspond to the value computed if all overflow errors are ignored.
Hint: Use subcomponents to make wiring easier by building a 1-bit adder, then a 2-bit adder, then a 4-bit adder, and so on up to 32-bits.
Signed vs. Unsigned Adders
There actually isn't a huge difference between signed and unsigned adders. In fact the only difference between the two is the way that overflow is calculated. Below is a 4-bit unsigned adder, like the one you did in Lab 1...
...and here is a 4-bit two's complement signed adder.
Note that the one-bit adder subcircuits in both the signed and unsigned 4-bit adders are iden"cal (the one-bit adders are all unsigned adders). Use this dis"nc"on when building your 32-bit signed adder.
Add32: Inputs:
C[32], V
Circuit 3: ALU32 ALU32:
Inputs:
(C, V) = fOp(A, B, Sa) A[32], B[32], Op[4], Sa[5]
Outputs:
The C and V outputs are computed according the value of the Op input based on the table of opera"ons below. For the add and subtract opera"ons, the V output should be set to 1 if and only if the C output could be incorrect due to a numerical overflow occurring during computa"on. The value C output in the presence of overflow should correspond to the value computed if all overflow errors are ignored.
Op name C V
1111 and
1110 or
001x shi! le! logical
1100 xor
1101 nor
0110 shi! right logical
0111 shi! right
arithme"c
1010 ne
1011 eq
1000 le
1001 gt
010x subtract 000x add
C[32], V
C = A& B C = A| B
C = B << Sa C = A^ B
C = ~(A | B)
C = B >>> Sa
C = B >> Sa
C = (A != B) ? 000…0001 : 000…0000
C = (A == B) ? 000…0001 : 000…0000
C = (A ¡Ü 0) ? 000…0001 : 000…0000
C = (A > 0) ? 000…0001 : 000…0000
C = A- B
C = A+ B
V= 0
V= 0
V= 0
V= 0
V= 0
V= 0
V= 0
V= 0
V= 0
V= 0
V= 0
V = overflow V = overflow
An x in the opcode indicates that the circuit should not depend on the value of that bit when determining the appropriate opera”on. For example, your circuit should add when the opcode is either 0000 or 0001 .
The expression (test) ? 1 : 0 has a value of 1 if test is true, and 0 otherwise. In both cases, the upper 31 bits of the output are zero. Note the difference between logical right shi! (which fills with zero bits), and arithme”c right shi! (which fills the new bits with copies of the sign bit of B ). The logical and ( & ), or ( | ), xor ( ^ ), nor, and complement
( ~ ) operators are all bit-wise opera”ons. Also note that le and gt compare A to 0, not B.
Don’t duplicate components
Your ALU should use your adder and le! shi!er as components. But, as in class, your ALU should only use a single 32- bit adder component to implement both addi”on and subtrac”on. Similarly, your ALU should use only a single 32-bit le! shi!er component to implement all of the shi! opera”ons. For instance, right shi!ing can be accomplished by transforming the inputs and outputs to your le! shi!er. You will be penalized if your final ALU circuit uses more than one adder or le! shi!er. Of course, always strive to make your implementa”on clear, but do not duplicate components in an effort to do so.
Don’t use unnecessarily large muxes
Your ALU will need to be able to select the appropriate output from your components. Do not use a large mux as a way to select between your opera”ons. Foremost, some of the inputs to this large mux would be unused or duplicated which is poor design. Addi”onally, larger muxes add much more complexity and gates, further increasing the cri”cal path. Likewise, do not use a large decoder in your design. Take some “me to break this logic into smaller, concise stages. You will be penalized if your final ALU circuit uses a large mux (16 to 1) or decoder (4 to 16).
On specifica”ons
It is important that your implementa”on of the three circuits described above adhere to the specifica”on in this document. Adhering to specifica”on is important in most all design processes, and it will also have a more immediate effect on your grade for this lab. Automated grading will expect that the three circuits above (and their inputs and outputs) are named exactly as specified (case-sensi”ve!) and behave exactly as specified.
Also recall that when the specifica”on denotes a pin as A[32] , the pin should be named ” A ” and be 32 bits wide. The pin should not be named ” A[32] “.
Design Documenta”on
We want to know what you’re thinking, even if your circuit has mistakes. That’s where design documenta”on comes in handy. Your final submission will include a design doc explaining the following:
Diagrams showing the components of your ALU (adder, shi!er etc.) and connec”ons between them. Explain any func”onality that we might find confusing.
Note that this, and all diagrams, can simply be Logisim screenshots if your circuit is neat and easy to read. Please use the Logisim text tool or an image editor to add labels/annota”ons as necessary. Your diagrams shouldn’t be much more complex than the ones shown in class.
Explana”ons of your control logic. What exactly does this mux do? What effect does changing this bit have? Show us the process. Include a brief descrip”on of what the values of any control signal mean, and a truth table showing the value that signal takes for each possible opcode.
Any design decisions or tradeoffs you made, if you feel they are relevant.
Note that the design doc does not have to be long or overly detailed, nor does it have to be in LaTeX. Only tell us what we need to know. Here is an example format (Latex source ). You don’t have to follow it.
README
In addi”on to a design document, you are required to submit a short README. The README includes the following:
Your name and NetID
An es”mate of the cri”cal path length of the complete ALU
An es”mate of the number of gates required to implement the ALU (including gates needed for subcomponents)
Cri”cal Path
In synchronous logic (logic that is driven by a clock signal), the cri”cal path is the slowest logic path in the circuit. We have assumed that the opera”on of the ALU completes in one clock cycle. In order to determine how long the clock cycle is, you need to figure out which path in your circuit is the longest path for the input signals to propagate through. This par”cular path is called the cri”cal path. The amount of “me for the input signals to propagate through the cri”cal path is the minimum length of one clock cycle. The reciprocal of the clock period gives the maximum frequency of the input clock signal. You may express your cri”cal path in terms of the number of gates in the path. To determine the cri”cal path you should use the following simplifying assump”ons:
Standard AND, OR, NOR, NAND, XOR, and XNOR gates have a gate delay of one unit
NOT gates are ignored
Mul”-input and mul”-bit gates both have the same gate delay as their standard variants
A mux has a gate delay of 2 regardless of size (you can derive this formula on your own by looking at how a mux is built out of basic gates!)
Gate Count
In microprocessor design, gate count refers to the number of transistor switches, or gates, that are needed to implement a design. Even with today’s process technology providing what was formerly considered impossible numbers of gates on a single chip, gate counts remain one of the most important overall factors in the end price of a chip. Designs with fewer gates will typically cost less, and for this reason, gate count remains a commonly used metric in the industry. To determine the gate count you should use the following assump”ons:
Standard AND, OR, NOR, NAND, XOR and NXOR gates count as one gate
NOT gates are ignored
Mul”-input gates count as a single gate
An n-bit gate counts as n gates (the mul”-bit gates Logisim provides aren’t actually real; they are just a convenient shorthand for using a gate for each bit)
A mux counts as (# of data bits)*(# of inputs + 1) gates (again, you can see this by looking at what it’s made of) Test Vectors
Extensively tes”ng your circuit is important to ensure correctness. Logisim, luckily, allows the use of test vectors for automated tes”ng of circuits.
While you obviously can’t test every possible input, it is feasible in Logisim to test up to several thousand input tuples. You can even write a program to do so (in Python, Java, Bash, etc.) if you would like to, although we don’t require it. You should strive to choose inputs strategically and include enough of them to test the en!re func”onality of your ALU. Some of your tuples might be wri$en by hand to test corner cases (e.g. adding combina”ons of zero, +1, -1, max_int, min_int, etc.). Some might be generated systema”cally (e.g. tes”ng every possible shi! amount, and every possible Op ), and others might be generated randomly (to catch cases you didn’t think of). Tes!ng is an important part of this project and you will be graded on both your random and edge cases.
For this project, you should create three ASCII text test vector files, one for each of the Le” Shi”er, Adder, and ALU circuits. A brief comment at the beginning of each file should indicate how the tests were chosen/generated and what they are tes!ng. In addi!on, please clearly group your random and edge cases together and comment where each type begins (e.g. “#Random cases start here”). You can create a comment by star”ng a line with a pound sign (#). The box below demonstrates the format of a Logisim test vector.
Notes & Hints
Ge#ng started: Design your circuits on paper before building them in Logisim. Design, then build and test the le! shi!er circuit first. Next, design, build, and test a le!/right shi!ing unit to be used in the ALU. Think of the le!/right shi!er as miniature ALUs: it will have its own opcode-like control input of your choice that selects between its different sub-opera”ons. Repeat the same steps for circuit 2: design, build, and test an adder/subtractor unit for use in your ALU. Then design a comparator unit that can perform the four comparison opera”ons by processing the output of the adder/subtractor or other subcomponents. Finally, design, build, and test the complete ALU for circuit 3. The overall idea is to compute several poten”ally needed values of the output C using the pieces you have already built and then to select the appropriate one using a mul”plexer.
Decoding logic: Your circuit will compute several values in parallel, but it will ul”mately select only one for output. Your decoding logic can o!en be simplified if you note that you only need the output of a sub-component to be correct (i.e. for it to receive the correct inputs) if you know ul”mately that it will be selected for output. In short, try to find the cases where you really don’t care about the inputs to, or outputs from, a sub-component.
Is op!mal always best? We want you to build a good working circuit. What does good mean? It could mean speed, readability, compactness, etc. However, even if you opt for highly op”mized circuits, you should make sure all of your designs are clear and easy to follow. They should be annotated (with text labels on the circuits) for any unusual or difficult parts of the circuit. Think and design before you implement it. Laying down a very complicated circuit for rela”vely simple func”onality will not work in your favor during grading.
Logisim combina!onal analysis: Take advantage of Logisim’s combina”onal analysis window (found under Project > Analyze Circuit), which can automa”cally generate near-op”mal circuits given a truth table. This only works for circuits with a few inputs, but is very well suited to control logic.
Ge#ng help: Ask the course staff for help. We are always available on Campuswire.
Frequently Asked Ques”ons
Logisim
Q: How does component xxx work in Logisim?
We have had many ques”ons asking about how to use a par”cular component in Logisim. In general, the help file in Logisim has explained things very well. You can access the help file from the ‘Help’ menu in Logisim. You could either search by keyword or browse the en”re reference from the le! pane.
Alterna”vely, you can take a look at our CS 3410 Logisim Component Guide. Q: How to create a sub-circuit in Logisim?
Please refer to Sub-circuit crea”on.
Q: How to build a one-bit adder?
Logisim has a very nice feature for edi”ng a truth table and genera”ng the corresponding logic circuit. You could refer to the following pages Edit truth table and Generate Circuit for an explana”on.
The following steps have worked well:
1. Place the desired input and output nodes on the canvas.
2. Save the changes to the canvas.
3. Right Click on the symbol that represents the current canvas in the explorer pane, and select ‘Analyze Circuit’ to
bring up the ‘Combina”onal Analysis’ window 4. Edit the truth table and Generate the circuit
Q: How does this mul!plexer thing work?
It takes mul”ple inputs and selects one of them based on the control signal. For instance, suppose I have 4 inputs into the mul”plexer in the following order: 1, 2, 3, 4. Since we have 4 inputs, our control needs 2 bits (base 2 log of the number of inputs) to determine the output of the mul”plexer. In this par”cular case, the mapping would be: 00 => 1, 01 => 2, 10 => 3, 11 => 4.
Shi! and overflow
Q: Should our adder perform unsigned or two’s complement addi!on? What is the difference?
What is the difference, indeed?
Q: How to do right shi” with le” shi”er?
Hint: You need to manipulate the input bits before passing them to the le! shi!er, e.g. transform the input bits to an intermediate format, pass the input through the le! shi!er, and then do a reverse-transforma”on to get your result. Q: My overflow bits are buried within my 16-bit adders! How am I supposed to XOR the carry-in and carry-out of the MSB?
You could either break down your 16-bit adder so that you have access to the carry-in and carry-out of the MSB, or you could detect overflows the alternate way: If the sign bit of the two inputs is the same but different from the output, you have an overflow.
Tes”ng
Q: How do we test our circuits?
The Cornell version of Logisim adds a special “Test Vector” feature to Logisim for automated tes”ng of circuits. The documenta”on for this is accessed from within Logisim: select Help->User’s Guide from the toolbar. On the le! pane of the help window that appears, look for and select the item labeled “Test Vectors”.
Q: How do we comment our test vector files?
# starts a comment.
Q: To write a test case for my test vector, I need to know what the correct result for a certain opera!on is. How could I ever do this?
All of the ALU’s opera”ons are clearly defined arithme”c opera”ons. The results can easily be computed by hand. Even be$er, implementa”ons of these arithme”c opera”ons are available in every major programming language. Q: We can just use Logisim’s logging feature to generate a test vector, right?
Let’s get this straight. To verify the correctness of your ALU, you are going to log the output of your ALU for a few inputs, and then you are going to verify that your ALU gives the same output when given those same inputs? This is basically asking “does your ALU produce the same outputs as your ALU?”
The first rule of tautology club is the first rule of tautology club.
#First line labels input and output pins, labeled with [bit width] if >1 #Each line after is an individual test with each column representing a pin #Numbers can be in decimal, binary, hexadecimal, or even octal if you want #Logisim determines the base of your input value as follows:
#if starts with 0x or 0o: hex or octal respectively
#if length of input value == width of input/output pin: binary
#else: decimal
#Choose whichever base(s) is/are most comfortable for you.
#They will all be interpreted in binary by Logisim and you can assume this #will always work. The purpose of this is that, for instance, binary might be #easier for you if you are making tests for OR whereas decimal might be easier #if you’re making tests for ADD. We assume that, unless you are Prof. Bracy, #your brain defaults to 7+6=13, not 0b111+0b110=0b1101, for instance.
#In this example, the columns are aligned neatly for readability.
#Your test vector does NOT have to be aligned like this. You can separate each #value with a single whitespace. We won’t be grading your test on its looks.
B[32]
34
325948595 00000000000000000000000000000001 0x00000005
0o17777777777 00011111001010100010110111110001
Sa[5] Cin 2 0 15 0 00100 1 0x01 0x0 0o1 0o0 0o10 0x0
C[32]
136
-900104192 00000000000000000000000000011111 0x0000000A
0o37777777776 707653888
#Decimal
#Negative Decimal #Binary
#Hexadecimal
#Octal
#Everything together!
P2