Midterm Flashcards
How do you objectively campare the complexity of two circuits
number of gates. max propogation delay, number of transistors
JSR - 6502
jump to sub routine, push the address of the next op on to the stack
TSX - 6502
transfer stack pointer to x.
minumum # of basic logic gates for a half adder
2
minimmum # of basic logic gates for a full adder
5
Universal set
express any boolean function using only the gates in S
Name the universal sets
AND,OR,NOT NAND NOR AND, NOT
SCRAM lacked circuitry for what commands?
JMZ, ADD, SUB
the ones complement of signed integers has two zeros +0 and -0
true: 0000, 1111
Ones compliment
obtained by inverting all bits in the binary number. negative if first digit is 1
6502 BNE command
branches if zero flag is clear.
6502 BCC
branches if carry flag clear
6502 BCS
branches if carry flag set
6502 BEQ
branches if zero flag set
6502 BMI
branch if negative flag set
6502 BPL
Branches if negativ eflag clear
6502 BVC
branch if overflow flag clear
6502 BVS
branch if overflow flag set
twos compliment of 5 bit range
-2^4 to 2^4 -1
The encoding for all 6502 instructions is between 2 and 4 bytre long
false, sta $ffff is 5 bytes, ASL and TXA are 1
of SCRAM machine instructions
16 - there are 16 pins
6502 CLC
clear carry flag
6502 CLD
clear decimal mode flag
6502 CLI
clear interrupt disable flag
6502 CLV
clear overflow flag
6502 SEC
set carry flag
6502 SED
set decimal mode flag
6502 SEI
set interrupt disable flag
6502 ASL
arithmetic shift left
6502 LSR
logical shift right
6502 ROL
rotate left
6502 ROR
rotate right
CPX, CPY, CMP 6502
compare x, compare y, compare accumulator
\The compare instructions subtract (without carry) an immediate value or the contents of a memory location from the addressed register, but do not save the result in the register. The only indications of the results are the states of the three status flags: Negative (N), Zero (Z), and Carry (C). The combination of these three flags indicate whether the register contents are less than, equal to (the same as), or greater than the operand “data” (the immediate value or contents of the addressed memory location. The table below summarizes the result indicators for the compare instructions.
ADC/SBC 6502
Add/sub with carry
6502 PHA. PHP, PLA, PLP
Push accumulator on stack Push processor status on stack pull accumulator from stack pull processor status from stack
LDA, LDX, LDY
Load accumulator, load x, load y
add $a, $b, $c
a = b + c
addu $a, $b, $c
add unsigned
addi
adds constant
lw $t, C($s)
load word from MEM[$s + c] and following 3 bytes
lb $t, C($s)
loads byte from MEM[$s + c]
sw $t, C($s)
stores word into MEM[$s + c] and next 3 bits
sb $t, C($s)
stores the least-significant 8 bits of a register into MEM[$s +c]
and $d, $s, $t
bitwise $d = $s & $t
andi $t, $s, C
pads leftmost 16 bits with -s
beq $s,$t,C
jumps to c if equal
bne $s,$t,C
jumps if not equal
j C
jump to C
jr $s
go to address $s
jal
calls subrotine, jumps and links by copying program counter to $ra
MIPS add to stack
sub $sp, 4 sw $ra, ($sp)
MIPS subtract from stack
lw $ra, 0($sp) add $sp, 4 jr $ra
twos complement range
-2^(N-1) to 2^(N-1) - 1
twos complement
invert digits and add 1
NAND - and gate
NAND - OR gate
NAND - NOT Gate
NOR - AND gate
NOR - or gate
NOT From NOR gate
xor
RS latch
shift register
DNF
disjunctive normal form - zeros
a’b’ + ab
CNF
half adder
full adder
D type RS Latch
edge triggered, master slave flip flop
Bits of memeory in SCRAM
16 8 bit memory slots = 128bits
Size of addresses for SCRAM
4 bit
OP Code size in SCRAM
4 bits
total SCRAM instruction size
op code + addr = 8 bit
sign and magnitude
first bit says +/-
5 steps to pipelining MPS
- Fetch Instruction - read from memory
- Instruction Decoding - read source registers
- Execution- execute
- Memory Access - read/write
- Write Back- store
JMZ
jump in 6502 if AC is 0
issue with JMZ
no connection from IR to PC
no way to tell if AC was 0
Edge-triggered D-type flip-flop
6502 interrupt
IRQ does the following:
The CPU has a input labelled IRQ
When the pin is pulled low/ has 0 applied to it - a signal is sent to the CPU.
The CPU halts the current program and runs the Interrupt Service Routine.
This specifically works by:
finishing the current instruction
pushing the PC to the stack (addr of the next instruction)
Interrupt disable flag is set
a 16 bit address is read from $FFFE-$FFFF and put into PC
That is where the ISR lives and needs to be supplied.
The interrupt service routine must retrieve a copy of the saved status register from where it was pushed onto the stack and check the status of the B flag in order to distinguish between an IRQ and a BRK.
Distincy boolean functions of n arguments
2^(2^n)
D-Type Master-Slave Edge-triggered flip flop description
D-Type Master-Slave Edge-triggered flip flop:
Data is captured on rising edge and output changes state on falling edge
of the clock. First D-latch is master, second D-latch is slave and gets inverted
Clock input.When clock signal changes from 0 to 1, output of slave latch takes
value of output of master latch, since by the time the slave is open, the master
already has taken the input, and can’t receive any more.
CNF
ANDS of Ors
DNF
OR of ANDS
AB + CD DNF OR CNF
DNF
(A+B)(C+D)
Conjunctive Normal Form
RS LATCH circuit with nands
RS LATCH NOR Truth table
RS LATCH with NORS circuit
RS Latch Nand truth table
RS LATCH NAND - Invalid state
S=0 R=0
LATCHED STATE NAND RS LATCH
R,S both = 1
Avoid invalid state on RS latch
this not gate makes the inputs always compliments of eachother
D Latch
Transparent latch
When enabled - whatever D is - Q is.
When disabled it stores the last value
Edge Trigger
D flip flop
D type latch with an enable that is connected to a clock and an edge trigger
How a D-type master slave edge triggered flip flop works
Data is captured on rising edge and output changes state on falling edge
of the clock. First D-latch is master, second D-latch is slave and gets inverted
Clock input.When clock signal changes from 0 to 1, output of slave latch takes
value of output of master latch, since by the time the slave is open, the master
already has taken the input, and can’t receive any more.
CAFE in binary
CAFE in decimal
CAFE in base 8
Binary: 1100 1010 1111 1110
Decimal: 5 1966
Octal: 14 5376
abs can be done without branches
true
describe pipeline proces`
1) fetch instruction IF = instruction fetch; assembler has turned pseudo instruction into actual cpu instruction
2) instruction decoding ID, understanding what instruction it is, what resources it needs, read some of the registers if needed
- - only load and store access memory
3) execution, EX drop to ALU, etc
4) if instruction needs to access memory, memory access stage MEM
5) write back, take what instruction computed and store it in the right register WB
structural hazard
structural hazard: run out of hardware, e.g. can’t do two additions at the same time. not a problem with mips. hardware
data hazards
occur when the pipeline changes the order of read/write accesses to operands so that the order differs from the order seen by sequentially executing instructions on the unpipelined machine.
Saving registers on interrupts.
The interrupts essentially jump to to the ISR (interrupt service routine). This ISR can do anything - and the main program will have no idea. So, it is responsible for saving the registers so that the program can continue.
Example situation - the keyboard is connected to IRQ and causes an interrupt whenever it is clicked to avoid polling. Say that the keyboard needs to use registers to store info about what keys are pressed. In this case - we do not want registers to be trashed and it is the calee’s responsibility to handle this - so we preserve the registers.
In fact, the interrupts cannot save to the stack to the best of my knowledge because the interrupt could be called due to a corrupted stack pointer. Therefore, the memory is preserved in statically allocated chunk of global memory.
two examples of data hazards.
Example:
(1) - add $t0, $t1, $t2
(2) - add $t7, $t0, $t8
Instruction (2) needs value from (1). WB is when the result is
available but at this point (2) is already at MEM, which is an issue
because that means it used the old value at $t0.
Can be avoided by forwarding:
Result of $t0 is already available at EX stage. We can add a path
for output of EX back into EX, which allows updated $t0 to be available
for (2).
Example:
(1) - lw $t0, 16($t7)
(2) - add $t1, $t0, $t9
Both instructions depend on $t0. (1) result is only available at MEM
stage after (1) loaded from memory, so (2) can’t execute. Can’t do anything
about it, so you’re forced to stall and do nothhing in EX for one cycle
What architechture is MIPS
RICS - reduced instruction set computing
CISC
Complex Instruction Set Computing
6502 Specs
- 8 bit accumulator. 3
- 8 bit registers.
- X,Y,P.
- 16 bit addresses.
- Memory: 64kb
Absolute Adressing 6502
An instruction has explicit address in memory
Prefeced with $.
Absolute with X/Y Adressing
Access what is in the specified memory location + contents of X/Y
$ffff, x or ,y
Zero PAge Adressing 6502
memory in first 256 bytes of memory where msb is 0. Does one lestt memory fetch during execution.
relative adressing 6502
*+4, gives you an offset
indirect adressing 6502
JMP ($40,x) load byte indirectly from memory.
Indexed Indirect Addressing (only works with X)
Ultimately gives an array of pointers indexed by X.
If X = 1, and LDA ($11, X) is called, then 1 is added to 11 (which gives
12) and we look at the addresses 12 and 13 together. If address 12
contained FE and address 13 contained CA, then we would then look at
the contents of memory address CAFE.
Indirect Indexed Addressing (only works with Y)
With Y = 1, assume LDA ($10, Y) is called. We then look at the addresses
10 an 11 together. If address 10 contained 00 and address 11 contained C0,
then we would then look at the contents of memory address C000 + Y, which
is C001.
6502 endedness
6502 is littleendian which means right most bytes is the op code. Instruction is left most. Adress is stored in reverse order.
MIPS specs
32 registers. 32 bits each. 4gb of memory.
3 addre
$zero
always zero register
$at
asembler temporary
$v*
function results
$a*
function arguments
$t*
temporaries
$s*
saved temporaries
$sp
stack pointer
$ra
return address
Write through
update cache and ram. Bring into cache and RAM concurrently
Write Buffer
Queue of pending writes so you dont need to wait for RAM to finish, just add to buffer. Best for few writes among many reads.
Write Back
Only update cache. When you load other things after there are more misses -write it back once you miss. Requires a dirty bit, write back on eviction from cache
Write allocate
read block from memory then write. Painful if want to initialize all to 0, tons of reads tat we dont need to do. If there are lots of writes but almost n oreads.
No write allocate
just write to memory, not going to read at all. JUST write to RAM. Wait for read - only fill cache when there is a reade.
SCRAM memory width
8 bits
SCRAM adress size. Instruction size
4 bits each
PC SCRAM
program counter. 4 bit register that holds current address
Accumulator SCRAM
8 bit register
CLU SCRAM
centeral logic unit, has all pins. controls flow.
MAR SCRAM
memory address register, Feeds into memory block
MBR Scram
memory address buffer- takes data from memory
SCRAM IR
holds op code and addr. Instruction Register.
6502 Endidness
Little Endian
Accumulator size 6502
8 bit
3 Registers 6502
A register (arithmatic)
X register - index register only inc/dec
Y register - same as X
P register - status register, holds all flags.
ALL 8 Bits
6502 memory size
64kb, 6 bit addr space 2^16 bytes.
6502 Compares
CMP, CMX, CMY setzero and carry flags
6502 branch instructions
if statements to jump
BCC, BCS, BEQ, BNE
6502 increament/decrements instructions
incx, incy.
6502 shift/rotates
ASL,LSR
ROR,ROL
6502 Jump Instructions
JMP - go to addr in memory
JSR - jump to subroutine
RTS - return from subroutine
Stack instructions 6502
PHP,PHA,TSX,TSX, PHA,PHP
6502 Absolute Addressing
Supplying instruction w/numberical addr:
LDA $FE
6502 absolute x/y addressing
XY offsets access memory +x or y
STA $0200,X
6502 Immediate Addressing
uses the value not the value at the address
and #$1f
6502 zero page addressign
adresses that are only 8 bits 00-FF faster access
6502 indexed indirect addressing
works only with x register
does address + x then loads two adjacent addresses
6502 indirect indexed addressing
gets two adresses adjacent. adds Y to that address.
MIPS internal improvements
higher clock speeds, pipelining
MIPS architechture bit
32
MIPS memory size
4GB
MIPS # registers/size of each
32 registers, 32-bits each
jump MIPS
j
How to do ifs with MIPS
slt - set if less than
slt $t0, $t1, $t2 t2=1 or 0
branch seperate.
MIPS at
asssembler temporary
MIPS v0,v1
output/return values
MIPS a0-a3
inputs/parameters
MIPS t0-t7
temporaries
MIPS s0-s7
saved registers
MIPS sp
stack pointer
MIPS ra
return address
dynamic branch prediction simple
either taken or not taken gueses. Flaw: first last guess in loop will be wrong
dynamic branch prediction complex
taken, not taken
taken maybe, not taken maybe
if taken or taken maybe it will be taken again
memory heirarchy
register
internal cache
2 level cahce
tetriery cahce
physical memory
disk
block/line cache
min amount of info/memory in the cache or that can be brought into the cache
hit rate
fraction of memory accessess found in cche
miss rate
1 - hit rate
hit time
access time fro cache
miss penalty
time to get from RAM
direct mapping
one slot fo each tag
set associative
>1 slot for each tag
Random evicion policies
good bottom line for comparison (not hardware)
FIFO
first in first out. throw out whats been there the longest. can implement in hardware.
LRU eviction policiess
least recently used. takes care of problem that FIFO could forget loop conter. Throws out what you have used the least often.
size of slot
log2(#sets)
size of offset
log2(block size)
tag
32 - slot - offset
x86 size of registers/number
8 32 bit registers
ESP
stck pointer
EBP
base pointer
size of addresses x86
32
[ebx] vs ebx
[ebx] address held in ebx so moving into [ebx] moves into the address held at ebx
x86 push
pushes stack by decrementing ESP by 4. Places operand into 32 bit location at ESP.
x86 Pop
removess 4 byte data from top of hardware stack. Moves 4 bytes into sp then into specified register. Increaments esp by 4.
6502 instruction size
1-3 bits
6502 address size
16
