[SOLVED] CS Java RISC-V assembly python ! CS3410-sp21 Assignments P1: ALU

! 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, youll design a RISC-V ALU. RISC-V is an instrucon set architecture (ISA) that defines the funcons a computer can carry out through assembly instrucons. An ALU, or arithmec and logic unit, performs many of the core computaons dictated by those instrucons. So in short, youll be building a key component of a CPU. Throughout this project and the next, youll move from small, special-purpose circuits to the full, complex CPU in all its glory! (Well, not all. Well be ignoring more advanced RISC-V features like traps/excepons and coprocessor instrucons.)
The program you will use to create your ALU is Logisim, a free hardware-design and circuit-simulaon tool. Logisim comes with libraries containing basic gates, memory chips, mulplexers 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 informaon available on the web and in textbooks. You may consult any RISC-V documentaon available to you in order to learn about the instrucon set, what each instrucon does, how an ALU works, etc. However, we expect your design to be enrely your own, and your submission should cite any significant sources of informaon 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 weve 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 Logisims test vector funcon to test your circuits. In order for it to work correctly, you must ensure that the Logisim circuits containing your soluons 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 implementaon of your circuit.
A README with your name, NetID, crical 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: Add32C[32]C = A + B + Cin; V = overflow A[32], B[32], CinOutputs:The output C is computed by adding A , B , and Cin . A , B , and C are signed two’s complement numbers. Ifoverflow 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 AddersThere 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], VCircuit 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 V1111 and1110 or001x shi! le! logical1100 xor1101 nor0110 shi! right logical0111 shi! rightarithme”c1010 ne1011 eq1000 le1001 gt010x subtract 000x addC[32], VC = A& B C = A| BC = B << Sa C = A^ BC = ~(A | B)C = B >>> Sa
C = B >> Sa
C = (A != B) ? 0000001 : 0000000
C = (A == B) ? 0000001 : 0000000
C = (A 0) ? 0000001 : 0000000
C = (A > 0) ? 0000001 : 0000000
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 operaon. 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 arithmec 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 operaons. Also note that le and gt compare A to 0, not B.
Dont 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 addion and subtracon. Similarly, your ALU should use only a single 32-bit le! shi!er component to implement all of the shi! operaons. 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 implementaon clear, but do not duplicate components in an effort to do so.
Dont 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 operaons. Foremost, some of the inputs to this large mux would be unused or duplicated which is poor design. Addionally, larger muxes add much more complexity and gates, further increasing the crical 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 specificaons
It is important that your implementaon of the three circuits described above adhere to the specificaon in this document. Adhering to specificaon 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-sensive!) and behave exactly as specified.
Also recall that when the specificaon 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 Documentaon
We want to know what youre thinking, even if your circuit has mistakes. Thats where design documentaon 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 connecons between them. Explain any funconality 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/annotaons as necessary. Your diagrams shouldnt be much more complex than the ones shown in class.
Explanaons of your control logic. What exactly does this mux do? What effect does changing this bit have? Show us the process. Include a brief descripon 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 dont have to follow it.
README
In addion to a design document, you are required to submit a short README. The README includes the following:
Your name and NetID
An esmate of the crical path length of the complete ALU
An esmate of the number of gates required to implement the ALU (including gates needed for subcomponents)
Crical Path
In synchronous logic (logic that is driven by a clock signal), the crical path is the slowest logic path in the circuit. We have assumed that the operaon 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 parcular path is called the crical path. The amount of me for the input signals to propagate through the crical 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 crical path in terms of the number of gates in the path. To determine the crical path you should use the following simplifying assumpons:
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 todays 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 assumpons:
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 arent 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 its made of) Test Vectors
Extensively tesng your circuit is important to ensure correctness. Logisim, luckily, allows the use of test vectors for automated tesng of circuits.
While you obviously cant 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 dont require it. You should strive to choose inputs strategically and include enough of them to test the en!re funconality of your ALU. Some of your tuples might be wri$en by hand to test corner cases (e.g. adding combinaons of zero, +1, -1, max_int, min_int, etc.). Some might be generated systemacally (e.g. tesng every possible shi! amount, and every possible Op ), and others might be generated randomly (to catch cases you didnt 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 Shier, 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 starng 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-operaons. 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 operaons 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 potenally needed values of the output C using the pieces you have already built and then to select the appropriate one using a mulplexer.
Decoding logic: Your circuit will compute several values in parallel, but it will ulmately 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 ulmately that it will be selected for output. In short, try to find the cases where you really dont 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 opmized 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 relavely simple funconality will not work in your favor during grading.
Logisim combina!onal analysis: Take advantage of Logisims combinaonal analysis window (found under Project > Analyze Circuit), which can automacally generate near-opmal 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 Quesons
Logisim
Q: How does component xxx work in Logisim?
We have had many quesons asking about how to use a parcular 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 enre reference from the le! pane.
Alternavely, 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 creaon.
Q: How to build a one-bit adder?
Logisim has a very nice feature for eding a truth table and generang the corresponding logic circuit. You could refer to the following pages Edit truth table and Generate Circuit for an explanaon.
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 Combinaonal Analysis window 4. Edit the truth table and Generate the circuit
Q: How does this mul!plexer thing work?
It takes mulple inputs and selects one of them based on the control signal. For instance, suppose I have 4 inputs into the mulplexer 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 mulplexer. In this parcular case, the mapping would be: 00 => 1, 01 => 2, 10 => 3, 11 => 4.
Shi! and overflow
Q: Should our adder perform unsigned or twos complement addi!on? What is the difference?
What is the difference, indeed?
Q: How to do right shi with le shier?
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-transformaon 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.
Tesng
Q: How do we test our circuits?
The Cornell version of Logisim adds a special Test Vector feature to Logisim for automated tesng of circuits. The documentaon for this is accessed from within Logisim: select Help->Users 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 ALUs operaons are clearly defined arithmec operaons. The results can easily be computed by hand. Even be$er, implementaons of these arithmec operaons are available in every major programming language. Q: We can just use Logisims logging feature to generate a test vector, right?
Lets 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 youre 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 wont 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