CSA NOTES

Direct Mapping

Each block of main memory maps to 1 cache line

Address:

Least significant w bits -> unique word
Most significant s bits -> one memory block
MSB -> cache line field r + tag s-r

Address length

s+w bits
no. of addressable units -> 2^(s+w)
block/line size -> 2^s
no. of lines in cache = m = 2^r
size of cache -> 2^(r+w)
size of tag -> (s-r) bits

Associative Mapping

Main memory block can load into any line of cache

Address:

Memory address -> tag + word
tag (identify)-> block of memory, every line examined for match

Address length

s+w bits
no. of addressable units -> 2^(s+w)
block/line size -> 2^w words/bytes
no. of blocks in main memory -> 2^s
size of tag -> s

Set Associative Mapping

Address

Cache consists of a number of sets
Each set contains a number of lines
A given block maps to any line in a given set
2-way -> a given block be in one of 2 lines in only one set

Address length

s+w
no. of addressable units -> 2^(s+w)
block/line size -> 2^w words/bytes
no. of blocks in main memory -> 2^s
Number of sets = v = 2^d
no. of lines in cache = kv = k*2^d
size of tag s-d bits

Hazard

Resource Hazard

arise from resource conflicts when the hardware cannot support all possible combinations of instructions in simultaneous overlapped execution

FO FI connot coexitst

Data Hazard

arise when an instruction depends on the result of a previous instruction in a way that is exposed by the overlapping of instructions in the pipeline.

FIrst half of cycle = WO
Second half = FO

Read after write (RAW), or true dependency An instruction modifies a register or memory location Succeeding instruction reads data in memory or register location Hazard occurs if the read takes place before write operation is complete

Write after read (WAR), or antidependency An instruction reads a register or memory location Succeeding instruction writes to the location Hazard occurs if the write operation completes before the read operation takes place

Write after write (WAW), or output dependency Two instructions both write to the same location Hazard occurs if the write operations take place in the reverse order of the intended sequence

WAR, WAW -> superscalar, multistream