CS 252编程辅导、讲解C/C++编程、c++程序设计辅导
- 首页 >> Matlab编程 CS 252: Computer Organization
Sim #3
Single-Cycle CPU
milestone 1 - see class website for due date
milestone 2 - see class website for due date
1 Purpose
In this project, you will implement a single-cycle CPU. One of the keys of this
project is understanding how the control bits are used to direct the rest of the
processor - so most of your code will be finding (and then using) the various
control bits.
Unfortunately, in order to test that you are doing this correctly (without
having the TAs spend hours looking at your code), I had to break the CPU
down into a fairly large number of relatively small pieces. You will implement
a number of functions - most will be fairly small - and my testcases will join all
of the little pieces together into a larger system.
You’ll be happy to learn that in this project, I have removed the restrictions!
Now, if you want to add, multiply, or whatever, you are allowed to do
it. We can allow this now because now you know what it takes - something
as simple as the + operator in C actually represents a non-trivial component in
hardware.
We’ll be writing this project entirely in C.
1.1 Two Milestones
In this project, you will be submitting your code twice (that is, there will be
two folders in GradeScope).
Milestone 1 only requires that you implement the extract instructionFields()
and fill CPUControl() functions. And, in your CPU Control function, you
are only required to implement the “ordinary” instructions (see below).
For milestone 2, implement the complete spec.
NOTE: Most of the testcases are for milestone 2, but I’ve provided a couple for
milestone 1. The milestone 1 testcases include stub functions for the functions
you are not required to implement (to make it easier to write milestone 1). But
they won’t compile anymore once you define your own, real versions.
1.2 “Extra” Instructions and Their Testcases
There are a certain set of instructions which all students must implement - basically,
these are the set which can be easily implemented by the basic processor
design that we’ve provided for you.
1
However, you will also be expected to expand on this design a bit. We
have provided a set of “extra” instructions, which can also be implemented
with (relatively) small changes to the processor. You must choose three of these
instructions, and update your design to support them (details below).
When you download the testcases for your program, you should download the
“ordinary” testcases (they are all numbered), and then download the “extra”
testcases for the instructions that you have chosen. Test them all using the
grading script.
1.3 Required Filenames to Turn in
Both milestones require that you turn in a C file; name it sim3.c. (If you’re an
overachiever and complete the entire project in the first week, then turn in the
file into both folders.)
In addition, in milestone 2 only, turn in a README file - it must be a
text file. Name it README or README.txt. The first paragraph of this file should
simply list the “extra” instructions you have chosen to implement1
.
The rest of the README file should describe how you changed the processor
to support them.
We’ll use this README file to (manually) configure the grading script for
you - so please, follow the instructions. I don’t want to have to search through
100 different student directories for hard-to-read README files!
1.4 More Complex Testcases
Because the testcases have a lot of C code that they share, I now have some
“common code” which is shared across all of them. This is contained in a header
file sim3 test commonCode.h and the matching source file sim3 test commonCode.c.
Each testcase will include the header, and link with the shared code.
While you are allowed to include the test-common-code header if you want,
I don’t think that you will need it. Feel free to poke around the code, however.
1.5 Random Numbers
Please note that testcase 08 uses C’s rand() function to generate inputs. The
.out file that I have provided works when running on Lectura, but it may or
may not work on your machine. If you are failing testcase 08, try running it on
Lectura instead.
2 “Ordinary” Instructions
Your CPU must support all of the following instructions:
1
If you didn’t have time to implement this, then say so.
2
• add, addu, sub, subu, addi, addiu
(Treat the ’u’ instructions exactly the same as their more ordinary counterparts.
Just use C addition and subtraction, using signed integers. Ignore
overflow.)
• and, or, xor2
• slt, slti
• lw, sw
• beq, j
The testcases will handle the syscall instruction on your behalf - you don’t
have to write any code to make it work.
Your implementation for these instructions must match the book
- and the slides we’ve been going over in lecture. You must use the same
control wires, with the same meanings.3 Your “extra” control wires (if any)
must all be zero for these instructions.
2.1 “Extra” Instructions
Choose three instructions from the following list (no more than one from each
group below!), and implement them as well in your CPU:
• andi, ori, xori, nor
• lui
• sra, srl, sll
• srav, srlv, sllv
• bne
• lb, sb
• mul
• mult, div4
• mfhi, mflo
2The book’s version of the CPU cannot do XOR - but in Sim 3, we added ALU op 4. We’ll
keep that up in this project - you must implement XOR as ALU operation 4. We’ll pretend
that it is “standard.”
3The only exception - as I’ve said in class - is that we don’t use a separate “ALU Control”
in our processor. Instead, you will set the ALU operation directly, in your control logic.
4
If you implement this, you must also implement mfhi or mflo so that we can test your
results.
3
Your implementation for these instructions must match the MIPS architecture;
you can look each of these up, in Appendix A, to find out exactly how they
work. You must use the opcode that MIPS requires, and do exactly
what the MIPS architecture says these instructions do.
However, none of these can be implemented with the standard CPU design
that we’ve discussed. Each one needs some sort of small change. Some can
be implemented by adding a new ALU operation, or by adding a new input to
an existing MUX; others will require that you add a new MUX, or new logic
somewhere in the processor.
2.2 New Control Bits
To support your extra features, you must set new control bits in the CPU design.
One option is to simply add new values to a field; for instance, you could add
an ALU operation 5 (the standard processor only supports 0-45
), which did
something new. Likewise, you might add a new input to the ALUsrc MUX
(which feeds into ALU input 2).
Alternatively, you might add entirely new control lines. For instance, you
might add a new control wire which means “invert the Zero output from the
ALU.” To support these, the CPUControl struct (see below) includes 3 different
“extra” fields. You get to decide what these mean - in theory you could
have 96 new control wires! Or, you may ignore them, if you don’t need them.
I have just one limitation: you must not simply copy the instruction, opcode,
or funct fields into the extra fields. Instead, you must decode the opcode/funct,
and set control wires. It’s just that you get to decide what the
new control wires mean.6
2.3 “Don’t Cares”
In some instructions, there are control bits which don’t matter. For instance, in
any instruction which sets regWrite=0, the control bits regDst and memToReg
don’t matter, since they can’t possibly affect what happens this clock cycle.
In real hardware, these are called “don’t cares,” and thus we can set these
to whatever value - basically, we choose arbitrary values for them - whatever
makes the hardware implementation cheaper.
But in our code, we will be dumping these values in the testcase, and comparing
them against a standard output - so we need a standard value for each
one. So our rule is: if you don’t care about a control wire, always set it
to zero.
2.4 Invalid Instructions
In real hardware, if your code includes an instruction with a bad opcode, the
program will crash. That is, the CPU has special circuits which force an “excep-
5See the footnote above, about XOR and ALU op 4.
6For the same reason, global variables are forbidden!
4
tion” if an invalid opcode is found; this forces the software into the Operating
System - and normally results in the OS killing your program.
To simplify things, you won’t implement any of this, except for one part: if
the opcode is invalid (or if the opcode indicates “R-format” but the funct field
is invalid), then you will return 0 from fill CPUControl(). (If it is recognized,
then you will return 1, after filling in all of the control bits.)
2.5 Not-Required Instructions
Some students like to implement some additional instructions that I don’t require.
This is fine, but they must be standard MIPS instructions, using
the normal opcodes. For instance, you could implement jal - but if so, it must
use opcode 0x3.
Our testcases will check to see if your Control component returns 0 from
fill CPUControl() as required. But since we don’t know which students may
have supported additional (normal) MIPS instructions, we will only test opcodes
that are not valid in standard MIPS.
Remember, only instructions from the approved list above count towards
your grade. (Sorry, but those are the only ones for which we have testcases.)
3 Typedefs, Structures, and Utility Functions
I have provided sim3.h, which defines several types for you and the prototypes
for each of the functions which you must implement.
You must not change this header. If you do, your code won’t compile
when I test it.
3.1 WORD
WORD is a typedef that will be 32 bits in size. I use it for parameters and return
values which need to be exactly 32 bits, and I encourage you to use it for your
variables (when they are 32 bits as well). Bit fields (from single bits, all the way
up to huge ones) are represented by simple int variables.
So yes, there are some ints in the data structures that represent a single bit
(such as bNegate). There are others (such as funct) that represent 5 or 6 bits,
and some (such as imm16) that even represent 16 bits!
3.2 WORD signExtend16to32(int)
This utility function is already provided by me; you don’t have to write it. It
takes a 16-bit input, sign extends it to a full word, and then returns the value.
3.3 struct InstructionFields
This struct is initialized by the extract instructionFields() function, which
you will write.
5
This struct represents all of the fields in the instruction. When you fill this
struct, set all of the fields, with no intelligence at all. So, for instance,
you should always set the address field - even if this is not a J instruction; the
address field just represents the 26 wires, which can be then connected to other
places.
3.4 struct CPUControl
This struct is initialized by the fill CPUControl() function, which you will
write. (This function will make up most of your code for this project.)
This struct represents all of the control bits. Your code will read the function
fields (out of an InstructionFields struct), decode the opcode an funct fields,
and set all of the control bits that are required.
We will describe fill CPUControl() in detail later in this spec. For now,
remember two rules:
• You must fill in all of the fields in this struct, in fill CPUControl().
• You must never modify any of these fields later in your program.
3.5 struct ALUResult
This tiny struct has two fields: result (32 bits, stored in a WORD variable) and
zero (1 bit, although we store it in an int). It simply represents the output
from the ALU; you will fill in both fields in execute ALU().
Always set the zero output (to either 0 or 1), no matter what ALU operation
you perform.
3.6 struct MemResult
This tiny struct only has a single field - readVal. But I placed it inside a struct
so that execute MEM() will work roughly like execute ALU().
7
4 The Fields of CPUControl
The CPUControl struct has many fields. You need to set all of them in fill CPUControl().
4.1 The Real Control Bits
CPUControl has fields for every one of the control bits that we’ve discussed in
class and in the book - except for the ALUop that goes from the main Conrol
7Maybe I’m being silly, but I like symmetry!
6
using to the ALU Control. (In this struct, we’ll simply set the proper ALU
operation directly, in the field named ALU.op8
.)
See above for the discussion of “ordinary” and “extra” instructions (those
that can be implemented by the processor design shown in the book, and those
that need additional control bits). For the “ordinary” instructions, you must
implement the control bits exactly as described in the book and slides.
For the “extra” instructions, you must either define new control bits (which are
zero for the “ordinary” instructions, but which you turn on for certain “extra”
instructions), or define new values (such as adding new ALU operations, or
adding more inputs to a MUX).
As noted above, there are some situations where a bit may be a “don’t care”
- meaning it can have no effect on the operation of the CPU for this clock cycle
(because other bits make it pointless). Always set “don’t cares” to zero.
4.2 Extra Words
Finally, CPUControl has three extra WORDs provided for you. These fields must
all be zero for all “ordinary” instructions. However, if you want, you can use
these to store up to 96 additional control bits, to make the “extra” instructions
work.
It is not required that you use these fields. Some designs may support the
“extra” fields simply by adding new legal values to existing fields (such as the
ALU operation). But I’ve provided these for you just in case you find them
handy.
5 The Functions
You must implement all of the following functions. I strongly recommend
that you implement these one at a time, and test them individually.
The first several testcases are designed to test these one at a time - sometimes
in isolation, and sometimes in concert with other pieces. After the intro testcases,
we will then test complete instructions, all as one pack - and then small
programs.
8
In C, the operator -> is used to access the fields inside a struct, when you have a pointer
to the struct. The . (‘dot’) operator is the same thing, but when you have the struct itself,
not a pointer to it.
In this project, we pass a pointer to the CPUControl struct to your function,
fill CPUControl(). So to access most fields, you will use ->, like this:
pointer->field = value;
However, the are a couple of fields which are grouped together into an ALU struct, inside
CPUControl. You must use -> to get from the pointer to the ALU struct, and then . to get the
field inside the ALU struct, like this:
pointer->ALU.op = 2;
7
As you are writing your solution, start by “stubbing out” all of the required
functions. That is, cut-n-paste the declarations from sim3.h into your file, and
give them (empty) bodies. That way, the code will compile - and you can start
testing - long before the rest of your code is written.
5.1 WORD getInstruction(WORD curPC, WORD *instructionMemory)
You must read the proper word out of instruction memory, given the current
Program Counter. Return the value. Remember that the Program Counter
gives the address of the current instruction in bytes but that this is an array
of words.
5.2 void extract instructionFields(WORD, InstructionFields
*fieldsOut)
This function is passed an instruction as input; it must read all of the fields
out of the instruction, and store them into the fields in the InstructionFields
struct.
No other function in your code may modify any field in this struct!
5.3 int fill CPUControl(InstructionFields*, CPUControl*)
The first parameter is an in parameter: it is the InstructionFields struct
that you fille. The second is a CPUControl* struct. Read the opcode and funct
from the Fields struct, and then set all of the correct controls in the Control
struct.
This function returns 1 if the instruction is recognized, and 0 if the opcode
or funct is invalid.
No other function in your code may modify any field in this struct!
5.4 WORD getALUinput*(...)
There are two of these functions, one for each of the ALU inputs. These function
have several input parameters:
• The CPUControl for this instruction
• The InstructionFields for this instruction
• The value of the two registers read from the register file (based on the
rs,rt fields you set in InstructionFields)
• The value of registers 33 and 34.
(The basic set of registers only has 32 registers - but our simulator has 34,
so that you can implement the lo,hi registers for multiply, if you want.)
8
• The old PC value - that is, the PC of the currently executing instruction.
(This parameter only exists to support certain extra instructions, which
some students might implement.)
Note that you might not need all of these inputs for your implementation -
but we’ve designed this project with flexibility. If (for instance) you wanted to
add a MUX in front of ALU input 1 (like we already have one in front of ALU
input 2), you should be able to do that with the parameters we’ve provided.
5.5 void execute ALU(CPUControl*, WORD,WORD, ALUResult*)
This function implements the ALU. Remember, we’ve removed the limitations
- so I fully expect you to use the C addition and subtraction operators
(or anything else that might be handy). However, you must choose what you
do only by reading the various control fields in the CPUControl struct. (You
will notice that you don’t have access to the instruction itself in this function!)
The second and third parameters are the ALU inputs 1 and 2 (see the functions
above).
The fourth parameter is an out parameter: set all of its fields, every time
that this function is called!
5.6 void execute MEM(CPUControl*,ALUResult*, WORD,WORD, WORD*,
MEMResult*)
This function implements the data memory unit. The first parameter is the
CPU control; check for the memory control bits inside it to see what you need
to do (if anything). Most of the time, you will do nothing - but even in that
case, you must set the output bits (to zero).
The second parameter is the ALUResult struct, which you set in a previous
call to execute ALU(). You must not change anything inside this struct, but
you can read the fields.
The third and fourth parameters are the two registers that were read for
this instruction - based on the rs,rt values you set in the InstructionFields
struct.
The fifth parameter is an array of WORDs, representing the data memory.
(Remember: all memory addresses are given in bytes, but the array is an array
of words.)
The final parameter is an out parameter: it is the “Read data” field, coming
out of the memory unit. If you read a value from memory, then this field must
have that value. If not (if you write, or if you do nothing), then you must set
this to zero.
5.7 WORD getNextPC(...)
This function implements the logic which decides what the next PC will be. The
first parameter is the InstructionFields for this instruction, and the second
9
is the CPUControl. The third is the aluZero output from the ALU. The next
two are the two registers read for this instruction; the fifth is the previous PC.
Return the new PC.
5.8 void execute updateRegs(...)
This represents the final stage of the processor: writing to a register (if required).
The first parameter is the fields of the instruction, followed by the control bits;
the third and fourth are the results from the ALU and Memory, respectively.
The last parameter is a pointer to the current set of registers, which you
may have to write to.
6 Data and Instruction Memory Sizes; Number
of Registers
I will ensure (in my testcases) that any address we use (any PC or data address)
will be small enough to fit into the memory that I provide you. So you don’t
have to check for any address is that is “too large.” (I will also not ever use
unaligned memory addresses.)
When I pass you registers (getALUInput*(), execute updateRegs()), I
will always pass you an array of 34 registers. This is to represent the 32 ordinary
registers, plus the lo,hi registers which are used for multiplication and division.
You are not expected to implement multiplication and division, but I wanted
to make it possible for the students who were interested.
6.1 Register Zero
I’m not sure, in the official MIPS specification, what happens when you try to
write to register $zero. (I’m sure that it doesn’t actually change anything - but
I don’t know if there are any errors or other side-effects that are required.)
So, in our testcases, we will never try to write to it - meaning that you
don’t need to write any special code to handle it. Moreover, you may assume,
any time I pass you the array of registers, that element [0] of the array contains
0.
7 A Note About Grading
Your code will be tested automatically. Therefore, your code must:
• Use exactly the filenames that we specify (remember that names are case
sensitive).
• Not use any other files (unless allowed by the project spec) - since our
grading script won’t know to use them.
10
• Follow the spec precisely (don’t change any names, or edit the files I give
you, unless the spec says to do so).
• (In projects that require output) match the required output exactly! Any
extra spaces, blank lines misspelled words, etc. will cause the testcase to
fail.
To make it easy to check, I have provided the grading script. I strongly
recommend that you download the grading script and all of the testcases, and
use them to test your code from the beginning. You want to detect any problems
early on!
7.1 Testcases
You can find the files for this project on the class website, and also on D2L.
For assembly language programs, the testcases will be named test *.s .
For C programs, the testcases will be named test *.c . For Java programs,
the testcases will be named Test *.java . (You will only have testcases for the
languages that you have to actually write for each project, of course.)
Each testcase has a matching output file, which ends in .out; our grading
script needs to have both files available in order to test your code.
For many projects, we will have “secret testcases,” which are additional
testcases that we do not publish until after the solutions have been posted.
These may cover corner cases not covered by the basic testcase, or may simply
provide additional testing. You are encouraged to write testcases of your
own, in order to better test your code.
7.2 Automatic Testing
We have provided a testing script (in the same directory), named grade sim3.
Place this script, all of the testcase files (including their .out files if assembly
language), and your program files in the same directory. (I recommend that
you do this on Lectura, or a similar department machine. It might also work
on your Mac, but no promises!)
7.3 Writing Your Own Testcases
The grading script will grade your code based on the testcases it finds in the
current directory. Start with the testcases I provide - however, I encourage you
to write your own as well. If you write your own, simply name your testcases
using the same pattern as mine, and the grading script will pick them up.
While you normally cannot share code with friends and classmates, testcases
are the exception. We encourage you to share you testcases - ideally
by posting them on Piazza. Sometimes, I may even pick your testcase up to be
part of the official set, when I do the grading!
11
8 Turning in Your Solution
You must turn in your code to GradeScope. Turn in only your program; do not
turn in any testcases.
12
Sim #3
Single-Cycle CPU
milestone 1 - see class website for due date
milestone 2 - see class website for due date
1 Purpose
In this project, you will implement a single-cycle CPU. One of the keys of this
project is understanding how the control bits are used to direct the rest of the
processor - so most of your code will be finding (and then using) the various
control bits.
Unfortunately, in order to test that you are doing this correctly (without
having the TAs spend hours looking at your code), I had to break the CPU
down into a fairly large number of relatively small pieces. You will implement
a number of functions - most will be fairly small - and my testcases will join all
of the little pieces together into a larger system.
You’ll be happy to learn that in this project, I have removed the restrictions!
Now, if you want to add, multiply, or whatever, you are allowed to do
it. We can allow this now because now you know what it takes - something
as simple as the + operator in C actually represents a non-trivial component in
hardware.
We’ll be writing this project entirely in C.
1.1 Two Milestones
In this project, you will be submitting your code twice (that is, there will be
two folders in GradeScope).
Milestone 1 only requires that you implement the extract instructionFields()
and fill CPUControl() functions. And, in your CPU Control function, you
are only required to implement the “ordinary” instructions (see below).
For milestone 2, implement the complete spec.
NOTE: Most of the testcases are for milestone 2, but I’ve provided a couple for
milestone 1. The milestone 1 testcases include stub functions for the functions
you are not required to implement (to make it easier to write milestone 1). But
they won’t compile anymore once you define your own, real versions.
1.2 “Extra” Instructions and Their Testcases
There are a certain set of instructions which all students must implement - basically,
these are the set which can be easily implemented by the basic processor
design that we’ve provided for you.
1
However, you will also be expected to expand on this design a bit. We
have provided a set of “extra” instructions, which can also be implemented
with (relatively) small changes to the processor. You must choose three of these
instructions, and update your design to support them (details below).
When you download the testcases for your program, you should download the
“ordinary” testcases (they are all numbered), and then download the “extra”
testcases for the instructions that you have chosen. Test them all using the
grading script.
1.3 Required Filenames to Turn in
Both milestones require that you turn in a C file; name it sim3.c. (If you’re an
overachiever and complete the entire project in the first week, then turn in the
file into both folders.)
In addition, in milestone 2 only, turn in a README file - it must be a
text file. Name it README or README.txt. The first paragraph of this file should
simply list the “extra” instructions you have chosen to implement1
.
The rest of the README file should describe how you changed the processor
to support them.
We’ll use this README file to (manually) configure the grading script for
you - so please, follow the instructions. I don’t want to have to search through
100 different student directories for hard-to-read README files!
1.4 More Complex Testcases
Because the testcases have a lot of C code that they share, I now have some
“common code” which is shared across all of them. This is contained in a header
file sim3 test commonCode.h and the matching source file sim3 test commonCode.c.
Each testcase will include the header, and link with the shared code.
While you are allowed to include the test-common-code header if you want,
I don’t think that you will need it. Feel free to poke around the code, however.
1.5 Random Numbers
Please note that testcase 08 uses C’s rand() function to generate inputs. The
.out file that I have provided works when running on Lectura, but it may or
may not work on your machine. If you are failing testcase 08, try running it on
Lectura instead.
2 “Ordinary” Instructions
Your CPU must support all of the following instructions:
1
If you didn’t have time to implement this, then say so.
2
• add, addu, sub, subu, addi, addiu
(Treat the ’u’ instructions exactly the same as their more ordinary counterparts.
Just use C addition and subtraction, using signed integers. Ignore
overflow.)
• and, or, xor2
• slt, slti
• lw, sw
• beq, j
The testcases will handle the syscall instruction on your behalf - you don’t
have to write any code to make it work.
Your implementation for these instructions must match the book
- and the slides we’ve been going over in lecture. You must use the same
control wires, with the same meanings.3 Your “extra” control wires (if any)
must all be zero for these instructions.
2.1 “Extra” Instructions
Choose three instructions from the following list (no more than one from each
group below!), and implement them as well in your CPU:
• andi, ori, xori, nor
• lui
• sra, srl, sll
• srav, srlv, sllv
• bne
• lb, sb
• mul
• mult, div4
• mfhi, mflo
2The book’s version of the CPU cannot do XOR - but in Sim 3, we added ALU op 4. We’ll
keep that up in this project - you must implement XOR as ALU operation 4. We’ll pretend
that it is “standard.”
3The only exception - as I’ve said in class - is that we don’t use a separate “ALU Control”
in our processor. Instead, you will set the ALU operation directly, in your control logic.
4
If you implement this, you must also implement mfhi or mflo so that we can test your
results.
3
Your implementation for these instructions must match the MIPS architecture;
you can look each of these up, in Appendix A, to find out exactly how they
work. You must use the opcode that MIPS requires, and do exactly
what the MIPS architecture says these instructions do.
However, none of these can be implemented with the standard CPU design
that we’ve discussed. Each one needs some sort of small change. Some can
be implemented by adding a new ALU operation, or by adding a new input to
an existing MUX; others will require that you add a new MUX, or new logic
somewhere in the processor.
2.2 New Control Bits
To support your extra features, you must set new control bits in the CPU design.
One option is to simply add new values to a field; for instance, you could add
an ALU operation 5 (the standard processor only supports 0-45
), which did
something new. Likewise, you might add a new input to the ALUsrc MUX
(which feeds into ALU input 2).
Alternatively, you might add entirely new control lines. For instance, you
might add a new control wire which means “invert the Zero output from the
ALU.” To support these, the CPUControl struct (see below) includes 3 different
“extra” fields. You get to decide what these mean - in theory you could
have 96 new control wires! Or, you may ignore them, if you don’t need them.
I have just one limitation: you must not simply copy the instruction, opcode,
or funct fields into the extra fields. Instead, you must decode the opcode/funct,
and set control wires. It’s just that you get to decide what the
new control wires mean.6
2.3 “Don’t Cares”
In some instructions, there are control bits which don’t matter. For instance, in
any instruction which sets regWrite=0, the control bits regDst and memToReg
don’t matter, since they can’t possibly affect what happens this clock cycle.
In real hardware, these are called “don’t cares,” and thus we can set these
to whatever value - basically, we choose arbitrary values for them - whatever
makes the hardware implementation cheaper.
But in our code, we will be dumping these values in the testcase, and comparing
them against a standard output - so we need a standard value for each
one. So our rule is: if you don’t care about a control wire, always set it
to zero.
2.4 Invalid Instructions
In real hardware, if your code includes an instruction with a bad opcode, the
program will crash. That is, the CPU has special circuits which force an “excep-
5See the footnote above, about XOR and ALU op 4.
6For the same reason, global variables are forbidden!
4
tion” if an invalid opcode is found; this forces the software into the Operating
System - and normally results in the OS killing your program.
To simplify things, you won’t implement any of this, except for one part: if
the opcode is invalid (or if the opcode indicates “R-format” but the funct field
is invalid), then you will return 0 from fill CPUControl(). (If it is recognized,
then you will return 1, after filling in all of the control bits.)
2.5 Not-Required Instructions
Some students like to implement some additional instructions that I don’t require.
This is fine, but they must be standard MIPS instructions, using
the normal opcodes. For instance, you could implement jal - but if so, it must
use opcode 0x3.
Our testcases will check to see if your Control component returns 0 from
fill CPUControl() as required. But since we don’t know which students may
have supported additional (normal) MIPS instructions, we will only test opcodes
that are not valid in standard MIPS.
Remember, only instructions from the approved list above count towards
your grade. (Sorry, but those are the only ones for which we have testcases.)
3 Typedefs, Structures, and Utility Functions
I have provided sim3.h, which defines several types for you and the prototypes
for each of the functions which you must implement.
You must not change this header. If you do, your code won’t compile
when I test it.
3.1 WORD
WORD is a typedef that will be 32 bits in size. I use it for parameters and return
values which need to be exactly 32 bits, and I encourage you to use it for your
variables (when they are 32 bits as well). Bit fields (from single bits, all the way
up to huge ones) are represented by simple int variables.
So yes, there are some ints in the data structures that represent a single bit
(such as bNegate). There are others (such as funct) that represent 5 or 6 bits,
and some (such as imm16) that even represent 16 bits!
3.2 WORD signExtend16to32(int)
This utility function is already provided by me; you don’t have to write it. It
takes a 16-bit input, sign extends it to a full word, and then returns the value.
3.3 struct InstructionFields
This struct is initialized by the extract instructionFields() function, which
you will write.
5
This struct represents all of the fields in the instruction. When you fill this
struct, set all of the fields, with no intelligence at all. So, for instance,
you should always set the address field - even if this is not a J instruction; the
address field just represents the 26 wires, which can be then connected to other
places.
3.4 struct CPUControl
This struct is initialized by the fill CPUControl() function, which you will
write. (This function will make up most of your code for this project.)
This struct represents all of the control bits. Your code will read the function
fields (out of an InstructionFields struct), decode the opcode an funct fields,
and set all of the control bits that are required.
We will describe fill CPUControl() in detail later in this spec. For now,
remember two rules:
• You must fill in all of the fields in this struct, in fill CPUControl().
• You must never modify any of these fields later in your program.
3.5 struct ALUResult
This tiny struct has two fields: result (32 bits, stored in a WORD variable) and
zero (1 bit, although we store it in an int). It simply represents the output
from the ALU; you will fill in both fields in execute ALU().
Always set the zero output (to either 0 or 1), no matter what ALU operation
you perform.
3.6 struct MemResult
This tiny struct only has a single field - readVal. But I placed it inside a struct
so that execute MEM() will work roughly like execute ALU().
7
4 The Fields of CPUControl
The CPUControl struct has many fields. You need to set all of them in fill CPUControl().
4.1 The Real Control Bits
CPUControl has fields for every one of the control bits that we’ve discussed in
class and in the book - except for the ALUop that goes from the main Conrol
7Maybe I’m being silly, but I like symmetry!
6
using to the ALU Control. (In this struct, we’ll simply set the proper ALU
operation directly, in the field named ALU.op8
.)
See above for the discussion of “ordinary” and “extra” instructions (those
that can be implemented by the processor design shown in the book, and those
that need additional control bits). For the “ordinary” instructions, you must
implement the control bits exactly as described in the book and slides.
For the “extra” instructions, you must either define new control bits (which are
zero for the “ordinary” instructions, but which you turn on for certain “extra”
instructions), or define new values (such as adding new ALU operations, or
adding more inputs to a MUX).
As noted above, there are some situations where a bit may be a “don’t care”
- meaning it can have no effect on the operation of the CPU for this clock cycle
(because other bits make it pointless). Always set “don’t cares” to zero.
4.2 Extra Words
Finally, CPUControl has three extra WORDs provided for you. These fields must
all be zero for all “ordinary” instructions. However, if you want, you can use
these to store up to 96 additional control bits, to make the “extra” instructions
work.
It is not required that you use these fields. Some designs may support the
“extra” fields simply by adding new legal values to existing fields (such as the
ALU operation). But I’ve provided these for you just in case you find them
handy.
5 The Functions
You must implement all of the following functions. I strongly recommend
that you implement these one at a time, and test them individually.
The first several testcases are designed to test these one at a time - sometimes
in isolation, and sometimes in concert with other pieces. After the intro testcases,
we will then test complete instructions, all as one pack - and then small
programs.
8
In C, the operator -> is used to access the fields inside a struct, when you have a pointer
to the struct. The . (‘dot’) operator is the same thing, but when you have the struct itself,
not a pointer to it.
In this project, we pass a pointer to the CPUControl struct to your function,
fill CPUControl(). So to access most fields, you will use ->, like this:
pointer->field = value;
However, the are a couple of fields which are grouped together into an ALU struct, inside
CPUControl. You must use -> to get from the pointer to the ALU struct, and then . to get the
field inside the ALU struct, like this:
pointer->ALU.op = 2;
7
As you are writing your solution, start by “stubbing out” all of the required
functions. That is, cut-n-paste the declarations from sim3.h into your file, and
give them (empty) bodies. That way, the code will compile - and you can start
testing - long before the rest of your code is written.
5.1 WORD getInstruction(WORD curPC, WORD *instructionMemory)
You must read the proper word out of instruction memory, given the current
Program Counter. Return the value. Remember that the Program Counter
gives the address of the current instruction in bytes but that this is an array
of words.
5.2 void extract instructionFields(WORD, InstructionFields
*fieldsOut)
This function is passed an instruction as input; it must read all of the fields
out of the instruction, and store them into the fields in the InstructionFields
struct.
No other function in your code may modify any field in this struct!
5.3 int fill CPUControl(InstructionFields*, CPUControl*)
The first parameter is an in parameter: it is the InstructionFields struct
that you fille. The second is a CPUControl* struct. Read the opcode and funct
from the Fields struct, and then set all of the correct controls in the Control
struct.
This function returns 1 if the instruction is recognized, and 0 if the opcode
or funct is invalid.
No other function in your code may modify any field in this struct!
5.4 WORD getALUinput*(...)
There are two of these functions, one for each of the ALU inputs. These function
have several input parameters:
• The CPUControl for this instruction
• The InstructionFields for this instruction
• The value of the two registers read from the register file (based on the
rs,rt fields you set in InstructionFields)
• The value of registers 33 and 34.
(The basic set of registers only has 32 registers - but our simulator has 34,
so that you can implement the lo,hi registers for multiply, if you want.)
8
• The old PC value - that is, the PC of the currently executing instruction.
(This parameter only exists to support certain extra instructions, which
some students might implement.)
Note that you might not need all of these inputs for your implementation -
but we’ve designed this project with flexibility. If (for instance) you wanted to
add a MUX in front of ALU input 1 (like we already have one in front of ALU
input 2), you should be able to do that with the parameters we’ve provided.
5.5 void execute ALU(CPUControl*, WORD,WORD, ALUResult*)
This function implements the ALU. Remember, we’ve removed the limitations
- so I fully expect you to use the C addition and subtraction operators
(or anything else that might be handy). However, you must choose what you
do only by reading the various control fields in the CPUControl struct. (You
will notice that you don’t have access to the instruction itself in this function!)
The second and third parameters are the ALU inputs 1 and 2 (see the functions
above).
The fourth parameter is an out parameter: set all of its fields, every time
that this function is called!
5.6 void execute MEM(CPUControl*,ALUResult*, WORD,WORD, WORD*,
MEMResult*)
This function implements the data memory unit. The first parameter is the
CPU control; check for the memory control bits inside it to see what you need
to do (if anything). Most of the time, you will do nothing - but even in that
case, you must set the output bits (to zero).
The second parameter is the ALUResult struct, which you set in a previous
call to execute ALU(). You must not change anything inside this struct, but
you can read the fields.
The third and fourth parameters are the two registers that were read for
this instruction - based on the rs,rt values you set in the InstructionFields
struct.
The fifth parameter is an array of WORDs, representing the data memory.
(Remember: all memory addresses are given in bytes, but the array is an array
of words.)
The final parameter is an out parameter: it is the “Read data” field, coming
out of the memory unit. If you read a value from memory, then this field must
have that value. If not (if you write, or if you do nothing), then you must set
this to zero.
5.7 WORD getNextPC(...)
This function implements the logic which decides what the next PC will be. The
first parameter is the InstructionFields for this instruction, and the second
9
is the CPUControl. The third is the aluZero output from the ALU. The next
two are the two registers read for this instruction; the fifth is the previous PC.
Return the new PC.
5.8 void execute updateRegs(...)
This represents the final stage of the processor: writing to a register (if required).
The first parameter is the fields of the instruction, followed by the control bits;
the third and fourth are the results from the ALU and Memory, respectively.
The last parameter is a pointer to the current set of registers, which you
may have to write to.
6 Data and Instruction Memory Sizes; Number
of Registers
I will ensure (in my testcases) that any address we use (any PC or data address)
will be small enough to fit into the memory that I provide you. So you don’t
have to check for any address is that is “too large.” (I will also not ever use
unaligned memory addresses.)
When I pass you registers (getALUInput*(), execute updateRegs()), I
will always pass you an array of 34 registers. This is to represent the 32 ordinary
registers, plus the lo,hi registers which are used for multiplication and division.
You are not expected to implement multiplication and division, but I wanted
to make it possible for the students who were interested.
6.1 Register Zero
I’m not sure, in the official MIPS specification, what happens when you try to
write to register $zero. (I’m sure that it doesn’t actually change anything - but
I don’t know if there are any errors or other side-effects that are required.)
So, in our testcases, we will never try to write to it - meaning that you
don’t need to write any special code to handle it. Moreover, you may assume,
any time I pass you the array of registers, that element [0] of the array contains
0.
7 A Note About Grading
Your code will be tested automatically. Therefore, your code must:
• Use exactly the filenames that we specify (remember that names are case
sensitive).
• Not use any other files (unless allowed by the project spec) - since our
grading script won’t know to use them.
10
• Follow the spec precisely (don’t change any names, or edit the files I give
you, unless the spec says to do so).
• (In projects that require output) match the required output exactly! Any
extra spaces, blank lines misspelled words, etc. will cause the testcase to
fail.
To make it easy to check, I have provided the grading script. I strongly
recommend that you download the grading script and all of the testcases, and
use them to test your code from the beginning. You want to detect any problems
early on!
7.1 Testcases
You can find the files for this project on the class website, and also on D2L.
For assembly language programs, the testcases will be named test *.s .
For C programs, the testcases will be named test *.c . For Java programs,
the testcases will be named Test *.java . (You will only have testcases for the
languages that you have to actually write for each project, of course.)
Each testcase has a matching output file, which ends in .out; our grading
script needs to have both files available in order to test your code.
For many projects, we will have “secret testcases,” which are additional
testcases that we do not publish until after the solutions have been posted.
These may cover corner cases not covered by the basic testcase, or may simply
provide additional testing. You are encouraged to write testcases of your
own, in order to better test your code.
7.2 Automatic Testing
We have provided a testing script (in the same directory), named grade sim3.
Place this script, all of the testcase files (including their .out files if assembly
language), and your program files in the same directory. (I recommend that
you do this on Lectura, or a similar department machine. It might also work
on your Mac, but no promises!)
7.3 Writing Your Own Testcases
The grading script will grade your code based on the testcases it finds in the
current directory. Start with the testcases I provide - however, I encourage you
to write your own as well. If you write your own, simply name your testcases
using the same pattern as mine, and the grading script will pick them up.
While you normally cannot share code with friends and classmates, testcases
are the exception. We encourage you to share you testcases - ideally
by posting them on Piazza. Sometimes, I may even pick your testcase up to be
part of the official set, when I do the grading!
11
8 Turning in Your Solution
You must turn in your code to GradeScope. Turn in only your program; do not
turn in any testcases.
12