Booth Algorithm
Flowchart
Multiplicand in BR
Multiplier in QR
AC, Qn+1, SC = 0, 0, n
while SC > 0:
Switch(Qn, Qn+1)
if 10 AC += -BR + 1
if 00 or 11 pass
if 01 AC += BR
ashr(AC & QR)
end
Hardware
BR Reg Sequence Counter
Complement and Parallel adder
Qn Qn+1
AC Reg -> QR Register ->
Async Data Transfer
Digital system operate on clock pulses
Sync if common clock with CPU reg else async
Async requires time of data transfer, methods for this are
Strobe, Handshake
Strobe: 2 types, SID and DIS (strobe connection reversed)
Data Bus
Source Unit Strobe Destination Unit
Sends data in data bus and when done send signal through strobe,
repeat for every data tranfer
Disadvantage: source or destination doesn't know when transfer complete
Handshake
Basically 2 strobes
Use 2 diagrams for 2 types
BCD Adder:
2 4 bit nums a,b
if 4,3 bits = 1,1 or carry or 4,2 bits = 1,1 BCDcarry = True
If carry = true add 6 to result
DMA
Transfer data without CPU involve, CPU idle
Transfer in burst mode or cycle steal mode
Burst mode: all data word transfer continuous
Cycle steal mode: one data word at a time then return to CPU
DMA Controller: 3 types
Address Reg: specify desire loc in memory
Word Count Reg: No of words to transfer
Control Reg: mode of transfer
Use Diagram for logic
DMA Transfer
1. Device sends DMA req
2. DMA asks CPU with BR
3. CPU grants BR with BG if BG = 0 RD & WR are input lines from CPU to DMA else
output from DMA to RAM
4. Put address reg val into address bus, allow device
5. When allowed put data word into data bus
6. For each word DMA increase address reg val and word count val
7. If word count reach 0 DMA remove bus request and inform CPU of transfer or
interrupt
DMA used for fast transfer and update display interactively
Pipelining
Peform serial tasks in parallel
In conventional machine time = n * tn (time taken for each task)
In pipeline machine time = (k + n - 1) * tp (clock cycle time)
Arithmetic Pipelining
Compare exponent
Align mantissa
Compute mantissas
Normalize result
Instruction Pipelining
Fetch instruction from memory
Decode instruction
Calc effective address
Fetch operands from memory
Execute instruction (Check for interrupt)
Store result
Features of RISC (Reduced Instruction Set Computing)
Simple, Uniform instructions
Load/Store Arch, Many Regs
Pipeline, Few Addressing Mode
Orthogonal Instruction set, Efficient compiler
Simple Hardware, Emphasize software solution
Diff btw Isolated IO and Memory Mapped IO
separate, same address bus
limited no, any instruction
I/O device called port, memory location
Efficient, Inefficient
Large, small
Complex, common internal logic
Slow, fast
Diff btw RISC and CISC
Less, more instructions
Fixed, variable length
Simple complex pipeline
Load/Store, Direct Operation
Less, more clock cycles required
More, less instruction to perform
Characteristics of Multiprocessor
Connect many CPUs with IOP aka Multiple Instruction Multiple Data Strema (MIMD)
systems
Advantage: Parallel operations and parallel tasks
Classification
Shared or Tightly Coupled: Single shared memory
Distributed or Loosely Coupled: Private local memory
Inter communication services:
1. Time Shared common bus: one processor at a time, multiple buses required for
speed
2. Multiport memory: divide into several buses connected to all CPUs, modules have
internal logic to determine access, expensive
3. Crossbar switch: Switch determines path of signal, expensive and complex
4. Multistage Switching Network: 2 in 2 out interchange, we can create binary tree
5. Omega Network: Many in many out interchange
6. Hypercube system: 2^n processors connected in imaginary hypercube
Virtual Memory
Hardware mapping mechanism + Software memory management
Need to prevent thrashing. Combines RAM w/ disk temp space
Page file: Area that stores RAM image
AS: VA, MS: PA
MMU: translate VA to PA
Explain Cache memory and Mapping techniques
a) Locality of reference: Cache = SRAM faster than DRAM
1. Temporal: when first needed info it stores in cache
2. Spacial: Also stores adjacent address data
b) Write in Cache:
1. Write through: Cache, main memory updated
2. Write back: cache updated, if cache miss then main memory updated
Direct Mapping
15 bits, 6 tag 9 index
if 2 hits then data present in cache else miss
disadvantage: reduce hit ratio
Associative mapping
Store address and data
Set associative mapping
Improved direct mapping 1 word of cache can store many words of memory in same
location, complex
Memory Hierarchy:
Registers: fast and close, limited
Cache(SRAM): made of transistors, fast, expensive
Main memory(DRAM): made of capacitors, leak, info fades, cheap, more memory
Magnetic disk: HDD (explain many disks stuff)
Magnetic tape: Plastic w/ magnetic medium
Async DRAM: conventional, async, slow
Sync DRAM: sync, pipeline, fast
