程序代做 MCIT 593 - Introduction to Computer Systems

MCIT 593 – Introduction to Computer Systems
THE DATAPATH
Property of Penn Engineering

MCIT 593 – Introduction to Computer Systems
In This Module…
Take the elements that we have encountered so far
• Combinational Elements
• Gates,Adders,Muxes,Decoders
• Storage Elements
• Flip-Flops,Registers,Memories
Use them to build a circuit that can perform a sequence of arithmetic operations • In essence, we will build a very simple CPU in this module!
Property of Penn Engineering 2

MCIT 593 – Introduction to Computer Systems
A Basic Model of a Computer
Memory ALU Instructions
Recall…4 main pieces: Memory (for data and instructions), PC, and ALU
• we have actually made each of these 4 parts already!
• we need to correctly assemble them
ADD 0, -20, $0
ADD 0, 10, $1
SUB $0, $1, $0
MPY $0, $4, $5
ADD $0, $5, $0
DIV $0, 5, $0
Property of Penn Engineering 4

MCIT 593 – Introduction to Computer Systems
23 by 16-bit Memory: Two Read Ports, One Write (Register File)
AW3 1616 16 16 16 16
23 x 16-bit Memory
“Register File”
Recall, this memory can read 2 addresses and write to a 3rd on the positive edge of CLK
Address Space, k= 23 = 8, or 8 drawers Addressability, m=16 bits, or 2 bytes in each drawer
Property of Penn Engineering 5

MCIT 593 – Introduction to Computer Systems
Recall: 16-bit Adder/Subtractor (Simplified ALU)
Adder/Subtractor
Basic Arithmetic Logic Unit (ALU): performs two operations: + / – on 16 bit values
• Inputs: A, B, Add/Sub
• Outputs: S
• Data inputs: A & B, “Control” inputs: Add/Sub
Property of Penn Engineering 6

MCIT 593 – Introduction to Computer Systems
Simple Processor: Datapath
Putting Register File Together with ALU:
• Our first CPU!
23 x 16-bit Memory
“Register File”
• The pathway that the DATA flows through (the wires shown on our CPU)
• But, what controls the flow of data through this datapath?
Control Signals
Property of Penn Engineering 7

MCIT 593 – Introduction to Computer Systems
A Useful Analogy
The datapath corresponds to the tracks in a railway
• Pathways that allow you to move information around the CPU
The control signals control the switches that connect the tracks
• Signals that setup the pathways so data can flow through CPU
Property of Penn Engineering 8

MCIT 593 – Introduction to Computer Systems
OUR FIRST CPU
Property of Penn Engineering

MCIT 593 – Introduction to Computer Systems
Simple Processor: Datapath w/Control
2n x k-bit Memory
AR1 AR2 AW
23 x 16-bit Memory
“Register File”
WE 16 16 16
These are the “control” signals (The lines in red)
• The signals needed to control the flow of data along the datapath
Notice, we added a second “Memory”
This memory will hold values for the control signals
i.e.: AR1, AR2, AW, WE, +/-
Property of Penn Engineering 11

MCIT 593 – Introduction to Computer Systems
Simple Processor: Example: Add Two #s
0 001 010 011 1
2n x k-bit Memory
23 x 16-bit Memory
“Register File”
WE =1 16 16 16
Our register file has 23=8 DFF registers within it:
• Let’s say we wish to add the contents of Regfile’s: Reg1 to Reg2
• Then store the result in Reg3. (akin to a simple program: a=b+c ) How would we set the “control” lines?
+/- = 0 (to indicate an add)
AR1 =001,AR2 =010,AW =011,WE=1(tostoreresult)
The settings for the control lines, come out of the control memory:
k is then 11 bits wide (in this case) and equals: 0 001 010 011 1
Property of Penn Engineering 12

MCIT 593 – Introduction to Computer Systems
Simple Processor: Example: Add Two #s
0 001 010 011 1
2n x k-bit Memory
23 x 16-bit Memory
“Register File”
WE 16 16 16
To ADD contents of R1+R2, control memory must contain:
If “row0” of the control memory had these 11-bits in it Our ALU would perform an ADD of
R1+R2 and write the results to R3
Property of Penn Engineering 13

MCIT 593 – Introduction to Computer Systems
Finite State Machines
• The CPU we’ve designed is an example of a Finite State Machine
• In general a Finite State Machine consists of 3 basic parts:
1) An n-bit register which stores the state of the machine
• In our CPU, this would be the memory
2) A block of logic that computes the next state as a function of the current state and the inputs, if any
• In our CPU, this would be the adder/subtractor (input = control mem) 3) A block of logic which computes the output based on the current state
We don’t have this in our CPU yet, but we will!
Clock Inputs
these boxes are combinational logic devices
Property of Penn Engineering 14

MCIT 593 – Introduction to Computer Systems
Simple Processor: Summary / Limits
Register File
• Contains DATA our processor operates upon
Control Memory
• Holds control signals for our processor
• In essence – holds the “program” we want our CPU to execute
Limitation in our Simple Processor Model…
• If we had a program with more than 1 instruction: a=b+c… • How could we advance to the next row of control Memory?
• We need a device to tell us what ‘row’ of our program we are on
In the next section, we’ll try to fix this limitation…
• With the counter we built last lecture!
Property of Penn Engineering 15

MCIT 593 – Introduction to Computer Systems
CPU AND THE PROGRAM COUNTER
Property of Penn Engineering

MCIT 593 – Introduction to Computer Systems
Simple Processor w/Program Counter (PC)
WE 16 16 16
2n x k-bit Memory
23 x 16-bit Memory
“Register File”
We’ve added a new register (PC) to our CPU -Holds the row # of the control memory we are on
Let’s also attached an incrementer…to make a counter -Advances us 1 row of control memory at each clock pulse -PC=PC+1 (just means go to next line in control mem)
Property of Penn Engineering 18
Program Counter (points to current row in control memory)

MCIT 593 – Introduction to Computer Systems
Simple Processor w/PC – Summary / Limits
Register File
• Contains DATA our processor operates upon
Control Memory
• Holds control signals for our processor
• In essence – holds the “program” we want our CPU to execute
PC (Program Counter)
• Holds “state” of control memory
• Essentially tells us what row of control memory to lookup
Limitation in our Simple Processor w/PC Model…
• This system is great if our programs run one line after another
• But what if we don’t want to execute the program in order?
• Can we add hardware to enable IF/THEN capability?
• Want hardware that allows us to jump around in our program
Property of Penn Engineering 19

MCIT 593 – Introduction to Computer Systems
CPU AND NZP TESTER
(HOW CPUS PERFORM COMPARISONS)
Property of Penn Engineering

MCIT 593 – Introduction to Computer Systems
Enhanced Processor w/ PC &
2n x k-bit Memory
AR1 AR2 AW
23 x 16-bit Memory
“Register File”
Of “TEST” box Determines Next value of PC!
If output of TEST = 0 PC = PC + 1
If output of TEST = 1 PC = NextPC
NZP Control Signal “controls” the TEST box…next slide shows how
Property of Penn Engineering 22

MCIT 593 – Introduction to Computer Systems
What Does the TEST Circuit Do?
Ultimately…control the next value for the Program Counter
• Tests output of ALU, for a condition: NZP (ex: is ALUOUT > 0 ?)
• If condition is TRUE, PC=NextPC
• If condition is FALSE, PC=PC+1
(ex: jump to another line: 100) (go to next line: 000+001=001)
ßto reg File
NZP 3 Is ALUOut > 0 ? TEST
NextPC n 100 1
to control mem
n +1 n0010 PC n
Property of Penn Engineering 23

MCIT 593 – Introduction to Computer Systems
Why Do We Want a TEST Circuit?
Give CPU ability to make decisions at runtime
• Skip over instructions in control memory
• Loop / repeat instructions in control memory
• Examples:
if (a>b) {
// do something
// otherwise skip here
while (a>b) {
// repeat these lines
• Values of variables (a,b) may not be known until program is running
• Essentially, we want the ability to COMPARE two values
Property of Penn Engineering 24

MCIT 593 – Introduction to Computer Systems
How Do We Implement Unsigned Comparisons?
We use ALU / Tester circuit / MUX to perform comparison…example:
• Step 1: perform subtraction: a-b (ALU can do this)
• Step 2: judge output of ALU: (Tester does this)
• Ifa-b<0,thenaissmallerthanb • Ifa-b =0,thenaisequaltob • Ifa-b>0,thenaisgreaterthanb
• Basic question for Tester: did subtraction produce a…
• Negative, Zero, or Positive number (NZP) ?
• Step 3: Jump to a line of program based on result of comparison
• If a>b, then PC=PC+1 (MUX does this)
• If a<=b, then PC=some new value while (a>b) {
// repeat these lines
Property of Penn Engineering 25

MCIT 593 – Introduction to Computer Systems
Enhanced Processor w/ PC &
2n x k-bit Memory
AR1 AR2 AW
23 x 16-bit Memory
“Register File”
Perform subtraction here:
Set desired comparison:
Perform comparison here
Results of comparison govern next input to PC
Property of Penn Engineering 26

MCIT 593 – Introduction to Computer Systems
INSIDE THE NZP TESTER
Property of Penn Engineering

MCIT 593 – Introduction to Computer Systems
Let’s Define Behavior of Our “TEST” Circuit
Want a circuit that can determine if output of ALU is: +, – or 0
(OR MORE than 1 of those conditions: e.g.: >=0 )
Inputs/Outputs/Behavior:
# to test (from ALU) 16
Result of Test
0 = condition was false 1 = condition was true
Condition to test # for is # to test: – 3 is # to test: 0
is # to test: +
(Or some combination)
Property of Penn Engineering 29

MCIT 593 – Introduction to Computer Systems
Example of “TEST” Circuit in Operation
Let’s test a 16-bit # to see if it is POSITIVE
Let’s say ALU outputs: 0000000000000000
Example In/Out:
# to test:
0000000000000000
Condition to test # for 16 0 N
>0 1 PZ TEST 1
Result of Test
Output of 0 indicates, condition was false, The # to test was not positive
Property of Penn Engineering 30

MCIT 593 – Introduction to Computer Systems
Example of “TEST” Circuit in Operation
Let’s test a 16-bit # to see if it is ZERO Let’s say ALU outputs: 0000000000000000 Example In/Out:
# to test:
0000000000000000
Condition to test # for 16
Result of Test
Output of 1 indicates, condition was true, The # to test was indeed equal to 0
Property of Penn Engineering 31

MCIT 593 – Introduction to Computer Systems
Example of “TEST” Circuit in Operation
Let’s test a 16-bit # to see if it is POSITIVE (OR) ZERO Let’s say ALU outputs: 0000000000000000
Example In/Out:
# to test:
0000000000000000
Condition to test # for 16
Result of Test
Output of 1 indicates, condition was true, The # to test was POSITIVE (OR) ZERO
Property of Penn Engineering 32

MCIT 593 – Introduction to Computer Systems
Implementing the NZP TEST Component
• # to test ß (1) 16-bit input
• N, Z, P ß (3) 1-bit inputs Condition to test for from USER
• Result of Test ß 1-bit output 0 if Condition from user is FALSE, 1 if TRUE
Two internal parts to the TEST component
• 1) Determine if incoming # is Negative/Zero/Positive
• 2) Compare incoming condition from user to output of part 1)
Comes from ALU
to test for from USER
Result of Test
Property of Penn Engineering 33

MCIT 593 – Introduction to Computer Systems
Implementing the NZP TEST Component (Part 1)
• Two internal parts to the TEST component
• 1) Determine if incoming # is Negative/Zero/Positive
# to test:
(Part 1) Determine if # is: -/+/0
You get to implement this for HW!
Output of PART 1:
If # is negative, Ni=1 If # is zero, Zi=1
If # is positive, Pi=1
Only 1 line can be high at a time
Property of Penn Engineering 34

MCIT 593 – Introduction to Computer Systems
Implementing the NZP TEST Component (Part 2)
• Two internal parts to the TEST component
• 1) Determine if incoming # is Negative/Zero/Positive
• 2) Compare incoming condition from user to output of part 1)
totestfor fromUSER 0P
Is (# to test <= 0)? # to test: Ex: 10...01 16 (Part 1) Determine if # is: -/+/0 1 Ni 0 Zi 0 Pi 100 You get to implement this for HW! (Part 2) Compares USER Condition to output of Part 1 User asked if # was negative Or zero... Output indicates it was one of those two Result of Test Property of Penn Engineering 35 MCIT 593 - Introduction to Computer Systems PROGRAMMING A CPU WITH MACHINE LANGUAGE - THE SETUP Property of Penn Engineering MCIT 593 - Introduction to Computer Systems Enhanced Processor: Example: Multiply Two #s • What if we wanted to get a bit fancier... • How could we use our “processor” to multiply? • We need an algorithm that uses our hardware: • We have only an adder/subtractor & TEST circuit • Multiplication is just repeated addition... while (B > 0) {
C=C+A; } B=B–1;
This algorithm Implements: C=A*B
Caveat: A&B are unsigned (positive) integers
Property of Penn Engineering 38

MCIT 593 – Introduction to Computer Systems
Multiply Algorithm: Flow Chart/“State Diagram”
Our program has 4 possible states.
PC – will hold that state!
Go back to state 0
Program done, Stay in state 3 forever
State 0: B > 0 ?
True, next state =1
State 1: C = C + A
Goto state 2
State 2: B = B – 1
while (B > 0) { C = C + A;
// END PROG.
False, next state =3
State 3: Loop
Property of Penn Engineering 39

MCIT 593 – Introduction to Computer Systems
PROGRAMMING A CPU WITH MACHINE LANGUAGE – THE EXECUTION
Property of Penn Engineering

MCIT 593 – Introduction to Computer Systems
Enhanced Processor w/ PC &
2n x k-bit Memory
AR1 AR2 AW
23 x 16-bit Memory
“Register File”
Algorithm:
while (B > 0) { C = C + A;
We need to put data in the register file & instructions in control memory
Property of Penn Engineering 42

MCIT 593 – Introduction to Computer Systems
Multiply Algorithm: Register File Setup
23 x 16-bit Memory
“Register File”
Algorithm:
while (B > 0) { C = C + A;
Register File:
R0 = 0 (for comparison)
R1 = 1 (to subtract from B) R2 = A (initially 5 for ex.) R3 = B (initially 2 for ex.) R4 = C (initially 0)
Property of Penn Engineering 43

MCIT 593 – Introduction to Computer Systems
Multiply Algorithm: Register File Setup
0 Contents:
Algorithm:
while (B > 0) { C = C + A;
Register File:
R0 = 0 (for comparison)
R1 = 1 (to subtract from B) R2 = A (initially 5 for ex.) R3 = B (initially 2 for ex.) R4 = C (initially 0)
Property of Penn Engineering 44

MCIT 593 – Introduction to Computer Systems
Multiply Algorithm: Control Memory Contents
• Let’s implement the algorithm in control memory
Algorithm:
while (B > 0) { C = C + A;
ROW 0 ROW 1
ROW 2 ROW 3
Functionality:
TEST: is B > 0 C=C+A
and loop back to row0
Loop forever on row 3
Register File:
R0 = 0 (for comparison)
R1 = 1 (to subtract from B) R2 = A (initially 5 for ex.) R3 = B (initially 2 for ex.) R4 = C (initially 0)
NZP Test Tricks • NZP Condition: 000
• Forces output to 0 • NZP Condition: 111
• Forces output to 1
Property of Penn Engineering 45

MCIT 593 – Introduction to Computer Systems
Multiply Algorithm: Control Memory Contents
• The complete algorithm shown in binary
Algorithm:
while (B > 0) { C = C + A;
ROW 0 ROW 1
ROW 2 ROW 3
Functionality:
TEST:isB>0 C=C+A
and loop back to row0
Loop forever on row 3
Register File:
R0 = 0 (for comparison)
R1 = 1 (to subtract from B) R2 = A (initially 5 for ex.) R3 = B (initially 2 for ex.) R4 = C (initially 0)
NZP Test Tricks • NZP Condition: 000
• Forces output to 0 • NZP Condition: 111
• Forces output to 1
Property of Penn Engineering 47

MCIT 593 – Introduction to Computer Systems
Multiply Execution Trace
Clock Cycle
PC (State)
Example: A=5, B=2
Property of Penn Engineering 48
Register values before PC “executes”
X = “don’t care”

MCIT 593 – Introduction to Computer Systems
Multiply Execution Trace
(Only the Register Values)
Register values before PC “executes”
PC (State)
// C = C + A // B = B – 1 // loop
Property of Penn Engineering 49

MCIT 593 – Introduction to Computer Systems
THE VON NEUMANN MODEL
Property of Penn Engineering

MCIT 593 – Introduction to Computer Systems
Enhanced Processor w/ PC &
2n x k-bit Memory
AR1 AR2 AW
23 x 16-bit Memory
“Register File”
Property of Penn Engineering 52

MCIT 593 – Introduction to Computer Systems
Enhanced Processor w/ PC & Summary / Limits
Register File
• Contains DATA our processor operates upon
Control Memory
• Holds control signals for our processor
• In essence – holds the “program” we want our CPU to execute
PC (Program Counter)
• Holds “state” of control memory
• Essentially tells us what row of control memory to lookup
• Allows us to alter the value of the PC by testing what comes out of the ALU for a particular condition
Limitation in our Enhanced Processor /w PC & PU…
• This system is great if our programs only contain 8 pieces of data!
• But what if we have mo

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts