LMC Flashcards
components of LMC
- mailboxes: 3 digits –> 100 is max
- counter: 2 buttons- 1 increments and other resets to 00
- calculator: 3 digits: 0-9, +, - buttons, flag for -ve results
- input/output trays: input by user, output sent to user
routine in LMC
- looks at counter for mailbox number
- increments counter by 1
- goes to mailbox + reads 3 digits
- completes action indicated by digits
- restarts…
how do instructions work
3 digits: first is opcode (instructions), last digits are operand (mailbox number)
opcode 1
add: go to specified mailbox, read 3 dig number at address, go to calculator and add number to that on calculator
opcode 2
subtract: go to specified mailbox, read 3 dig number at address, go to calculator and subtract number from that on calculator
opcode 3
store: go to calculator, read 3 dig value, go to specified mailbox and store value there (overriding currently stored value)
opcode 5
load: go to mailbox specified in instruction, read in the 3 dig number, and enter into calculator (overriding current value)
opcode 6
branch: set program counter to the 2 address specified in instruction, and start fetch of instruction
opcode 7
branch on zero: check calculator, if value = 0, set program counter to address specified in instruction and start fetch else continue with next instruction as normal
opcode 8
branch on positive: check calculator, if +ve (inc 0), set program counter to address specified in instruction and start fetch else continue with next instruction as normal
instruction 901
input: go to IN tray, read 3 dig number there, go to calculator and enter value there. only read one input slip, then remove it, any others are used for future visits
instruction 902
output: go to calculator, read 3 digit value there and leave slip with value on OUT tray
opcode 0
break
fetch
find the instruction to execute: reads program counter, goes to mailbox at that address in instruction, reads 3 dig value
execute e.g. store
target address remembered. 3 digits in calculator read, 3 digits written in mailbox at target address. program counter incremented
von neumann
- same memory for instructions and data
- memory is addressed linearly: there is a number for every mailbox
- memory addressed by location: contents is irrelevant
- instructions executed sequentially unless branch or reset
harvard
-separate memory for instructions and data:
-avoids potential for malware and bugs from self-modifying code
-simpler to read and analyse code
-quicker to execute as can access instructions and data simultaneously
modern processors have split cache so best of harvard and VN
five major components of a CPU
- memory (RAM)
- registers
- ALU
- control unit
- buses
memory (RAM)
mailboxes
registers
special memory locations that can be accessed very fast and are manipulated directly by the CU 1-128 bits: includes program counter (PC), instruction register (IR), accumulator
have a defined purpose and wired to perform that purpose
holds binary values temporarily for storage, manipulation, calculations
ALU
calculator
buses
bundles of tiny wires- electrical conductors i.e. lines carrying signals- that carry data between components: address, data, control, power
- -carries data between different points on CPU
- carries data between CPU and main memory/computer peripherals*
control unit
responsible for directing flow of data and instructions within the CPU- compromised of multiplexor and decoder
accumulator
register part of the ALU. holds data + interim and final results of calculations + data to be transferred between different memory locations + (I/O+memory)
registers int the CU
PC, IR, flags
PC
holds the address of the next instruction to be executed
IR
holds the instruction currently being executed
flags
1 bit memory to keep track of special conditions- grouped together in 1+ status registers
e.g. arithmetic carry, power failure, internal computer error, overflow
memory address register
holds address of the memory location to which data is to be written to
only written to
memory data register
holds value that is being stored to or retrieved from a memory location addressed by MAR
written to and from
types of bus
point to point- carries signal between specific source and specific destination
broadcast- carries signals to many different devices
bus interface bridges- allows communication between buses e.g. peripheral control interface bus, external bus, universal serial bus
translate cab.bc (subscript 3)
from units left then from radix right:
13^0 + 0 3^1 + 2* 3^2
+ 13^-1 + 23^-2
(a = 0, b = 1, c = 2)
group of
4 bits, 8 bits, 16 bits, 32 bits, 64 bits
4 = nibble 8 = byte 16 = half word 32 = word 64 = double word size of word = CPU dependent, some have 32/64 bit words
why hexadecimal
- more compact
- easier to read and write than binary
- easy to convert between binary and hex
converting dec to binary
repeatedly div by 2 until 0 or 2 is reached, the remainder is the binary digit (from radix point left) e.g. 13(10) to binary: 13 div 2 = 6 rem 1 6 div 2 = 3 rem 0 3 div 2 = 1 rem 1 1 div 2 = 0 rem 1 therefore answer is 1101
converting dec fraction to binary
repeatedly multiply fractional part by 2 until fractional part = 0, if result >= 1 then binary digit = 1. (from radix point right) e.g. 0.8125(10) to binary: 0.8125 * 2 = 1.625 (1) 0.625 * 2 = 1.25 (1) 0.25 *2 = 0.5 (0) 0.5 * 2 = 1 (1) therefore = 0.1101(2)
overflow error
when a computer attempts to handle a value too large for it. triggers the status register, but can cause errors.
binary multiplication
- just like long multiplication for decimal numbers
- efficiently achieved using left shifts and add operations
negative representation of numbers
sign and magnitude, ones complement, twos complement, adding a bias
sign and magnitude
left most bit is a flag bit, 1 = -ve, 0 = +ve
two representations for 0: 0000 0000, 1000 0000
binary arithmetic is messy
ones complement
flip all bits, left most bit is still a flag bit
two representations for 0: 0000 0000, 1111 1111
binary addition is a bit simpler
twos complement
flip all bits and add 1, left most bit is still a flag bit
one representation for 0 (1111 1111 = -1)
binary arithmetic is much simpler
adding a bias (negative binary representation)
add a bias of ((2^k-1) -1) then store in normal binary.
allows storage of numbers -((2^k-1) -1) –> (2^k-1)
higher order bit does not indicate sign
used for floating point storage
negative subtraction
twos complement the second number and add
overflow is ignored
floating point representation
sign bit + exponent + mantissa
exponent
a number between -126 and 127, stored with a bias + 127 so number stored is between 0 and 255
0 and 255 special meanings
0 exponent + 0 mantissa = 0
0 exponent + non 0 mantissa = subnormal numbers
255 exponent + 0 mantissa = +/- infinity
255 exponent + non 0 mantissa = not a number
mantissa
e.g. 1.01…. binary number scaled so that leading 1 preceding radix point, don’t store leading 1 (assume its there)
store only the 23 digits of the fractional part
e.g. translate 0 sign bit + 124 exponent + 1.25 mantissa
0 = +ve
124 - 127 = -3 exponent
1.25 mantissa
therefore overall = 1.25*2^-3 = 1.25/8 =0.15625
translate -12.375 to floating point representation
1100.011 (2)
for leading 1: 1.100011 * 2^3
mantissa: 100011000…
exponent: 3+127 = 130 (10) = 1000 0010
floating point issues.
rounding error- cannot represent all numbers e.g. 0.1
have to limit to certain number of binary digits
floating point operations result in…
FP number closest to the answer
underflow/overflow level
underflow level = 2^-126 (-126 = smallest number that can be represented by exponent)
overflow level = (2-2^-23) * 2^127 (23 = number of digits of mantissa)
ariane 5 issue and how to overcome
overflow error, could not convert 64 bit FP to 16 bit signed integer
overcome by check if number outside range before conversion: if too large then set at a max value
transistor
electrically controlled switch: two ports (drain and source) are connected depending on voltage of a 3rd port (gate)
nMOS transistor
when g = 0, switch is OFF d is not connected to s
g = 1, switch is ON, d is connected to s
(see image L5)
pMOS transistor
when g = 0, switch is ON, s is connected to d
g = 1, switch is OFF, s is not connected to d
(see image L5)
most common transistor
MOSFET: metal oxide semiconductor field effect transistor
element used is silicon
most common element used in MOSFET and why
silicon: semiconductor since conductivity changes over many orders of magnitude depending on small changes in levels of dopants
- poor conductor of electricity since all 4 outer electrons involved in bonding
dopants
impurities providing extra electrons or electron holes increasing conductivity
n-type silicon
overall negative charge, the dopant added is Arsenic, it has an extra electron not involved in bonding which can carry charge
p-type silicon
overall positive charge, the dopant added is boron- it is short an electron so leaves a positive electron hole which can move around the lattice
diode
at a junction between p-type and n-type silicon, current can only flow from p-type to n-type
what happens at a junction of n-type and p-type silicon
electrons in the n-type region and electron holes in the p-type region cancel each other out, creating a ‘depletion region’
there are no mobile charge carriers in this region
how is binary addition implemented
using gates implementing boolean algebra
AND algebraic expression
Y = A . B (dot in centre)
OR algebraic expression
Y = A + B
NOT algebraic expression
Y = A- (line above A)
p-type and n-type junction:
positive voltage applied to p and negative voltage applied to n
electron holes in p-type attracted towards n-type
electrons in n-type attracted towards p-type
depletion region squeezed out and current flows
p-type and n-type junction:
negative voltage applied to p and positive voltage applied to n
electron holes in p-type repelled by the n-type and electrons in the n-type repelled by the p-type
depletion region expands and creates a barrier to current flow
issue at p -type and n-type junction trends
trends break down at sufficient voltage
capacitor
two pieces of conductive metal separated by an insulator.
if a positive voltage is applied to one side, it accumulates charge Q, and the other side the opposite charge -Q (not Q)
takes time and energy to charge/discharge a capacitor
nMOS transistor, when gate g is at V(DD)
capacitor effect draws electrons to the surface, and they create a temporary channel of n-type silicon, so current can then flow from source to drain
how to indicate 1s and 0s
high voltage = 1
low voltage = 0
voltages typically between 0V–> 5V with 0V = 0, 5V = 1, need to be able to tolerate noise though
V(DD)
- the high voltage, historically 5V
- modern chips with smaller transistors have lower max voltages e.g.3.3V to save power and avoid overloading transistors
logic levels
defined to allow the mapping of continuous voltage to discrete 0 and 1 of the digital abstraction
noise margin high and low calculations
NM(H) = V(OH) - V(IH) NM(L) = V(IL) - V(OL)
the ideal inverter
the ideal inverter would output V(DD) for inputs up to V(DD)/2 and 0 above this
reasonable choice of logic levels
on graph of V(A) vs V(Y), reasonable choice of logic levels are where slope = -1
static discipline
design restriction that you only allow circuit elements that all satisfy the same logic levels: means you can successfully apply digital abstraction and combine elements without concern about logic levels or analogue values
disadv of static discipline
reduces freedom to include arbitrary elements (but makes design simpler)
moores law
transistor density doubles every two years
graphical ways of representing boolean algebra
- linear truth table
- rectangular/coordinate table
- venn diagram
how many boolean operations on k inputs
2^2^k
why is NAND used as a universal gate
easier to make
NAND vs NOR, pMOS-wise
in NAND, the two pMOS are parallel and in NOR, the two pMOS are in series so NOR results in delays because of low mobility of holes
pMOS vs nMOS speed of operations
nMOS is faster.
for pMOS to match this- size has to increase = more silicon = more expensive
what are digital design principles about
about managing complexity of huge numbers of interacting elements
list the digital design principles
- abstraction: hiding irrelevant details
- discipline: restricting design choices to make things easier to model, design+combine
- hierarchy: breaking into modules+submodules
- modularity: well-defined functions+interfaces for modules
- regularity: encouraging uniformity so can reuse+swap modules
circuit properties
- 1+ discrete valued input terminals
- 1+ discrete valued output terminals
- specification of relationship between input+output
- specification of delay between input received and output responding
circuit is made up of
elements- circuit with inputs, outputs and specs
node-wire joining elements whose voltage conveys a discrete valued variable
why combinational + sequential logic
-arbitrary circuits lead to short circuits and instability
combinational logic rules
- individual gates are combinational circuits
- every circuit element must be a combinational circuit
- every node is either an input to the circuit or connected to exactly one output of a circuit element
- the circuit has no cyclic paths, every path through the circuit visits any node at most once
boolean algebra
algebra of 1/0 variables used to specify function of a combinational circuit
used to analyse and simplify circuits required to give a specified truth table
literals
AND of several literals are called…
OR of several literals are called…
- variables or their complements
- product/implicant
- sum/implicant
minterm
product involving all the inputs to a function
maxterm
sum involving all the inputs to a function
sum of products
every boolean expression can be written as minterms ORed together
product of sums
every boolean expression can be written as maxterms ANDed together
truth table to SOP
OR together the products of the literals that result in 1s
truth table to POS
AND the 0 values of the function, negating any literals which = 1, so each literal = 0
axioms dual
achieved by interchanging 1,0 and AND/OR
axiom: binary field
axiom: NOT
B = 1 if B!=0; B=0 if B!= 1;
not 1 = 0; not 0 = 1
AND/NOT
0 . 0 = 0, 1 . 1 = 1
0 + 0 = 0, 1 + 1 = 1
0 + 1 = 1, 0 . 1 = 0
identity theorem
null theorem
B . 1 = B; B + 0 = B;
B + 1 = 1; B . 0 = 0;
idempotency theorem
involution theorem
complements theorem
B+B = B; B . B = B
not not B = B
B + not B = 1; B . not B = 0
prove B . 0 = 0
case B = 0:
0 . 0 = 0 (axiom)
case B = 1:
1 . 0 = 0 (axiom)
commutativity
associativity
distributivity
- swapping variables around
- moving brackets around
- distribution AND into an OR bracket or two OR brackets amongst each other
covering
combining
consensus
de morgans
B . (B + C) = B; B + (B . C ) =B;
(B . C) + (B . notC) = B; (B+C) . (B+ notC) = B
(B + C) . (notB + D) . (C + D) = (B + C) . (notB + D) (+ v.v. with + and . switched)
(already know de morgans)
why simplify boolean logic
represent the same thing with much less hardware
each cell in a karnaugh map represents…
a minterm
prime implicants
implicants that cant be combined with each other
7 segment display driver
4 inputs D(3:0), 7 outputs.
the inputs represent a decimal digit 0-9
each output is a segment.
create a circuit for each segment determining whether segment should be lit up based on 4 inputs
unspecified inputs (for numbers>9) can be represented as 1/0 depending on what reduces circuitry
difference between sequential and combinational circuit
combinational: output depends on input
sequential: output depends on state and input i.e. history of input
e.g. of combinational circuits
adders: adds contents of two registers
multiplexors: uses a binary digit to select an input
decoders: uses a binary digit to activate a single line
e.g. of sequential circuits
latches/flip-flops: basic memory element
decoder
N inputs, 2^N outputs. only one of the outputs is 1 at a time, the rest are 0. which output is activated depends on the input
larger decoders require
multi input AND gates requiring a lot of circuitry. instead can use deeper circuitry = less transistors but slower response time
multiplexor
has k selector inputs and 2^k data inputs. the selector represents a binary number, indexing the data to be outputted
how can 2:1 multiplexer be built
- using sum of products logic
- using tristate buffers: tristate enables are arranged so that at all times, exactly one tristate buffer is active
how can a 4:1 multiplexer be implemented
-out of smaller 2:1 multiplexers
why cant you use a single transistor instead of a tristate buffer
the output of a single transistor isn’t driven
inverting tristate: purpose of final pair of transistors
control transmission- aiding voltage drain
propogation delay
max delay before the output is stable
contamination delay
min time before output changes
delay is caused by
- resistance and capacitance in a circuit
- speed of light limitation
why may t(pd) and t(cd) be different
- different raising and falling delays
- circuit may have multiple inputs and outputs, some of which are faster than others
- circuits slow down when hot and speed up when cold
critical path
longest path in a circuit, determining the propogation delay
short path
shortest path in a circuit, determining the contamination delay
glitch
output temporarily moving to an incorrect value before stabilising
tristate delays
different characteristics for selector and data change with different delays for each
gate delays in a full adder
3 gate delays, unless the first set of gates are pre-computed, in which case 2 gate delays once the C(in) comes in
ripple adder
computation of the carry bit ripples through the chained adders
how many gate delays for a k-bit ripple adder
3 + 2(k-1) = 2k + 1
two functions used in a carry look ahead adder
G(A,B) = generate function = A AND B
P(A, B) = propagation function = A OR B
Cout in a carry look ahead adder
C(out) = G(A,B) + P(A,B) . Cin
keep breaking down Cin into G and P functions
e.g. Cout = G4 + P4 . C3
=G4 + P4 . (G3 + P3 . C2) …etc
gate delays for computing Cout in a carry look ahead and overall sum
3 gate delays: one for Pi, Gi, one for AND and one for OR
for overall sum, 4 gate delays
4-bit CLA propagates if..
if all subsequent bits propagate
4 bit CLA generates if…
if any bit generates and all subsequent bits propagate
CLA adding n-bit numbers in constant gate delay
require order n^2 gates and order n inputs: impractical for large n
more efficient CLA
chain 4 bit CLAs: carry ripples 4x faster
a block is said to generate a carry if
it produces a carry independent of the carry in
a block is said to propagate if
it produces a carry out whenever there is a carry in to the block
instead of letting carry ripple through the CLA…
precompute whether a carry would be generated or propagated by each CLA
4 bit CLA propagates if…
if all bits propagate, P = p4.p3.p2.p1
4 bit CLA generates if…
any bit generates, and all subsequent bits propagate: G= g4 + p4.g3 + p4.p3.g2 + p4.p3.p2.g1
each 4 bit block contains
a 4 bit ripple carry adder and some lookahead logic to compute the carry out given the carry in bit
gate delay for 16 bit 2-level CLA
1 gate delay for bit level Gs and Ps
2 gate delays for block level Gs and Ps
1 gate delay for sums
2 gate delays for carries
time order with 3 level CLA vs normal ripple adder
CLA O(logn) ripple adder O(n) (grows faster, more gates required = more gate delays)
16 bit adders chained to give a gate delay of…
for an n bit adder: 2(n/16) + 4
sequential circuits can be modelled as
finite state machines
synchronous sequential circuits are made of
combinational components interleaved with banks of flip flops containing state of the circuit
SR: NOR latch
bistable: two stable states for a given input
the S and R inputs are both usually 0. Pulse on S -> output = 1 (or remains 1). Pulse on R -> output = 0 (or remains 0).
output remains even when the pulse is over
SR: NAND latch
bistable: two stable states for a given input
the S and R inputs are both usually 1. Pulse on S -> output = 0, Pulse on R -> output = 1
output remains even when the pulse is over
D-latch
a latch separating what and when.
CLK: indicates when to change state
D: data input, indicates what the new input should be
when clock = 1, latch is transparent: data flows onto the output
when clock = 0, latch is opaque: output is constant
register
bank of flip flops driven by the same clock
enabled flip flop
flip flop with an additional input (an enable) controlling whether or not data is loaded into the register
can control input using multiplexor or control the clock = gated clock
gated clocks issues
can cause glitches and timing errors
number of transistors for a D-type flip flop
NOR/NAND = 4
NOT = 2
AND = NAND + NOT = 6
D-Flip flop = 46 . but by direct design = 20
improved D latch
fewer gates = fewer transistors
Q = CLK . D + notCLK . Qprev
issues with the improved D latch
- race conditions: behaviour depends on which of the two routes carries the signal fastest and the gate delays
- logically identical circuits may exhibit different behaviours depending on temperature and technicalities of gate construction
problems caused by loops or cyclic paths. how to overcome this?
- inserting registers into the cyclic paths: stores the state of the circuit and breaks the paths. synchronous with the clock, only update on an edge
- if clock is sufficiently slow so all inputs to all the registers have settled, race conditions can’t arise
synchronous sequential circuits consist of elements such that
- every circuit element is either a register or combinational circuit
- at least one element is a register
- all registers receive the same clock signal
- theres a register in every cyclic path
a synchronous sequential circuit has
- a discrete set of states {S0…Sk-1}
- clock input, whose rising edge indicates when a state change occurs
- functional specification detailing next state and all outputs for each possible current state and set of inputs
dynamic discipline
restricts us to using circuit components satisfying time constraints allowing us to combine components
t(setup)
t(hold)
t(ccq)
t(pcq)
t(setup): time before rising edge during which inputs must be stable
t(hold): time after rising edge during which inputs must be stable
t(ccq): time after rising edge until output starts to change
t(pcq): time after rising edge until output has stabilised
how fast a computer operates is dependent on
clock frequency
overclocking
setting the clock speed higher than the manufacturer recommends
sequencing overhead
t(pcq) + t(setup)
this is normally fixed, along with the clock speed.
clock speed ticks have to be at least…
min cycle time = t(pcq) + t(pd) + t(setup)
t(pd) time between last output stabilising and next input having stabilised
max clock freq = 1/ min cycle time in seconds
elements of combinational logic must work within
bounds on t(pd) in order for the circuit to be reliable.
this is because clock and sequencing overhead is fixed
t(hold) min delay requirement
t(ccq) + t(cd) > t(hold)
t(cd) > t(hold) - t(ccq)
t(cd) time between last output starting to change and next input starting to change
to allow direct connections of flip flops: often t(hold) < t(ccq) (no t(cd) if no CL element)
hold time violations
find short path: if t(hold) > t(ccq) + t(cd) then input to flip flop may change before D value has reliably set its value to previous value
fixing time hold violations
add buffers, so add another t(cd) until total(t(cd)) + t(ccq) > t(hold)
metastable states: input D to a flip flop
If D is either 1/0 while the clock rises = stable state
if D changes state while clock is rising (between tsetup and thold) = metastable state = driven to 1/0 eventually but takes longer for state to stabilise
synchronisers
two flip flops can synchronise the input with the clock- if input to a register is not synchronised with the clock the output may be indeterminate
output of second register will be synchronised if..
resolution time of first register (time taken for output to stabilise) is small enough compared to clock rate
pipelining
improves throughput at the expense of latency
inserting more registers into a circuit, decreasing clock cycle time/increasing clock frequency/increasing throughput
but not necessarily splits clock cycle time in half, as added sequence overhead and circuit can’t be divided exactly into two halves
latency
number of clock cycles/overall time
