Associative Cache

Theory
Design of Associative Cache:
Cache memory is a small (in size) and very fast (zero wait state) memory which
sits between the CPU and main memory. The notion of cache memory actually
rely on the correlation properties observed in sequences of address references
generated by CPU while executing a programm(principle of locality).When a
memory request is generated, the request is first presented to the cache
memory, and if the cache cannot respond, the request is then presented to
main memory.
 Hit: a cache access finds data resident in the cache memory
 Miss: a cache access does not find data resident, so it forces to access
the main memory.
Cache treats main memory as a set of blocks.As the cache size is much smaller
than main memory so the number of cache lines are very less than the number
of main memory blocks. So a procedure is needed for mapping main memory
blocks into cache lines.cache mapping scheme affects cost and performance.
There are three methods in block placement-
 Direct Mapped Cache
 Fully Associative Mapped Cache
 Set Associative Mapped Cache
Associative Cache
Any main memory block can mapped into any cache line. main memory address
is divided into two groups which are tags and word bits. Words are low-order
bits and identifies the location of a word within a block and tags are high-order
bits which identifies the block.

Block diagram of a associated cache :

Objective
Objective of Associative Cache design:
1. Understanding behaviour of associative cache from working module
2. Designing a associative cache for given parameters
Examining behaviour of given associatived cache
 number of tag bits: 2
 modulus value arising from given tag bits: 22=4
 number of bits in block component: 0
Loading data in the cache (refer to procedure tab for pin numbers)
 global initialisation: (S=1, R/W'A=0, R/W'D=0)
 in cache line 0, load as follows:
o data= "11" (D1=1, D0=1)
o tag= "10" (T1=1, T0=0)
o valid bit= "1" (valid=1)
 in cache line 1, load as follows:
o data= "10" (D1=1, D0=0)
o tag= "01" (T1=0, T0=1)
o valid bit= "1" (valid=1)
 in cache line 2, load as follows:
o data= "01" (D1=0, D0=1)
o tag= "00" (T1=0, T0=0)
o valid bit= "0" (valid=0)
Examining hit behaviour
 load data in address latch as:
o tag= "10" (A1=1, A0=0)
 initiate cache mapping:
o S=0, R/W'A=1, R/W'D=1
 check output:
o F0=1, F1=1, hit/miss=1
Examining miss behaviour due to mismatch of tag:
 load data in address latch as:
o tag= "11" (A1=1, A0=1)
 initiate cache mapping:
o S=0, R/W'A=1, R/W'D=1, Den= 0
 check output:
o F0=0, F1=0, hit/miss=0
Examining miss behaviour due to valid bit not set:
 load data in address latch as:
o tag= "00" (A1=1, A0=1)
 initiate cache mapping:
o S=0, R/W'A=1, R/W'D=1
 check output:
o F0=0, F1=0, hit/miss=0
Recommended learning activities for the experiment: Leaning activities are
designed in two stages, a basic stage and an advanced stage. Accomplishment
of each stage can be self-evaluated through the given set of quiz questions
consisting of multiple type and subjective type questions. In the basic stage, it
is recommended to perform the experiment firstly, on the given encapsulated
working module, secondly, on the module designed by the student, having
gone through the theory, objective and procuder. By performing the experiment
on the working module, students can only observe the input-output behavior.
Where as, performing experiments on the designed module, students can do
circuit analysis, error analysis in addition with the input-output behavior. It is
recommended to perform the experiments following the given guideline to
check behavior and test plans along with their own circuit analysis. Then
students are recommended to move on to the advanced stage. The advanced
stage includes the accomplishment of the given assignments which will provide
deeper understanding of the topic with innovative circuit design experience. At
any time, students can mature their knowledge base by further reading the
references provided for the experiment.
 color configuration of wire for 5 valued logic supported by the simulator:
 if value is UNKNOWN, wire color= maroon
 if value is TRUE, wire color= blue
 if value is FALSE, wire color= black
 if value is HI IMPEDENCE, wire color= green
 if value is INVALID, wire color= orange
Test Plan :
1. give some valid input initially in the cache then give such address so that
hit occurs then alter the address content or the tag or valid bit to get a
miss.
 2. Use Display units for checking output. Try to use minimum number of
components to build. The pin configuration of the canned components
are shown when mouse hovered over a component.
Assignment Statements :
You are required to build the following associative cache:
1. cache with one word, 4 bit memory address, 2 bit data without
repacement policy.
2. cache with 8 bit memory address, 8 bit data without repacement policy.
3. cache with each set containing multiple words without repacement policy.
Procedure
Design of Associative Cache :
Procedure to perform the experiment for associative cache on the existing
component 'Associative Cache' component in the 'other components' drawer in
the simulator.This simulator supports 5-valued logic.
1. Click on the 'Associative Cache' component(in the 'other components'
drawer in the pallet) and then click on the position of the editor window
where you want to add the component(no drag and drop, simple click will
serve the purpose), likewise add 15 Bit switches and 3 Bit Displays(from
Display and Input drawer of the pallet,if it is not seen scroll down in the
drawer)
2. 'Associative Cache' component in the 'other components' drawer in the
simulator supports both writing in the cache and the cache mapping. No
replacement policy has been implemented. Initially the cache is empty,
user has to give inputs. the component contains 4 sets, each set has 5
bits, the left most bit is the valid bit, next 2 bits are tags, next bits are
data bits, also it contains a one dimensional array of memory with 2 bit
to store the memory address, user has to give this address input also.the
cache reads all the data bits at a time so block offset is not required.
3. The pin configuration of the component can be seen whenever the mouse
is hovered on any canned component of the palette or press the 'show
pinconfig' button. Pin numbering starts from 1 and from the bottom left
corner(indicating with the circle) and increases anticlockwise.
4. For a 'Associative Cache' component pin configuration is:
o pin-32= S(selects whether user wants to perform cache write or
cache mapping)
 o pin-31= R/W'A(selects whether user wants to input the address or
cache mapping)
o pin-30=A1, pin-29=A0 (these 2 pins are used to give address
input). A1 is the most significant bit and A0 is the least significant
bit. As we are reading the whole word at a time, the whole address
will be in tag. So, A1 and A0 will be compared with the tag. A1 and
A0 will select the corrsponding set.
o pin-28= R/W'D(selects whether user wants to input in the set of
cache or cache mapping)
o pin-27= M1, pin-26=M0 (M1 is the most significant bit and M0 is
the least significant bit). thiese two bits are used for cache write
purpose, it selects the particular set of which user wants to give
inputs to the valid bit, tag bits and data bits.
o pin-21= valid bit
o pin-20= T1, pin-19=T0 (T1 is the most significant bit and T0 is
the least significant bit). These are tag bits.
o pin-18= D1, pin-17=D0 (D1 is the most significant bit and D0 is
the least significant bit). These are data bits.
o pin-14= Hit/Miss bit(if it gives 1 then hit otherwise miss)
o pin-15= F1, pin-16=F0 (F1 is the most significant bit and F0 is the
least significant bit). These are output data bits and will be given
only when there is a hit.
5. Essential pin configurations for writing in the cache: S=1, R/W'A=0,
R/W'D=0
6. Essential pin configurations for cache mapping: S=0, R/W'A=1, R/W'D=1
7. To connect any two components select the Connection menu of Palette,
and then click on the Source terminal and click on the target terminal.
According to the circuit diagram connect all the components. After the
connection is over click the selection tool in the pallete.
8. See the output, Bit switches are used to give input so that you can toggle
its value with a double click and see the outputs with different inputs.
Components :
To build a associative Cache with 4 bit memory address and 2 bit data address
without any replacement policy, we need :
1. Decoder with enable and decoder without enable
 2. Multiplexer with enable and multiplexer without enable
3. Single bit memory elements
4. XOR gates, NOR gates, AND gates
5. Bit switches to give inputs
6. Display units to check the outputs.
7. Wires to connect.
Experiment
Design of Associative Cache :
General guideline to use the simulator for performing the experiment:
 Start the simulator as directed. For more detail please refer to the manual
for using the simulator
 The simulator supports 5-valued logic
 To add the logic components to the editor or canvas (where you build the
circuit) select any component and click on the position of the canvas
where you want to add the component
 The pin configuration is shown when you select the component and press
the 'show pinconfig' button in the left toolbar or whenever the mouse is
hovered on any canned component of palette
 To connect any two components select the connection tool of palette, and
then click on the source terminal and then click on the the target
terminal
 To move any component select the component using the selection tool
and drag the component to the desired position
 To give a toggle input to the circuit, use 'Bit Switch' which will toggle its
value with a double click
 Use 'Bit Display' component to see any single bit value. 'Digital Display'
will show the output in digital format
 undo/redo, delete, zoom in/zoom out, and other functionalities have
been given in the top toolbar for ease of circuit building
 Use start/stop clock pulse to start or stop the clock input of the circuit.
Clock period can be set from the given 'set clock' button in the left
toolbar
 Use 'plot graph' button to see input-output wave forms
 Users can save their circuits with .logic extension and reuse them
  After building the circuit press the simulate button in the top toolbar to
get the output
 If the circuit contains a clock pulse input, then the 'start clock' button will
start the simulation of the whole circuit. Then there is no need to again
press the 'simulate' button
Software for conducting the experiment, as appropriate for your platform, may
be downloaded via SOFTWARE