# How is parallel tag checking achieved in associative Mapping?

I originally posted this question on stack overflow and then realised it was better suited to computer science .

In the book on computer organization and architecture by William stallings , in the cache memory chapter and associative mapping topic , the author says that the cache control logic simultaneously checks all the tag fields for a match when presented with an address . However , there is nothing said about how this actually happens , how the simultaneous checking takes place and I wanted to know about how this is implemented and what kind of circuitry is required to achieve this.

[I don't have this book]

Let's take a common example : A 4 ways, 16kB cache made of 4 ways of 4kB. And a cache line of 32 bytes.

Each way of the cache is made of a 4kB RAM containing data and another RAM which stores cache tags, its size is 4096/32 = 128 lines, each tag can probably fit in a 32 bits.

The tag RAM is indexed with the low address bits (here A[12:6]), and its content is compared with the high address bits A[31:7].

If you have 4 ways, you have 4 tag RAMs, the address bits are the same, but you have 4 comparators.

Cache is made of ordinary RAM blocks.

(In current advanced CPUs, to save power and complexity, the cache ways are often not compared at the same time, there is a preferred way, selected with some heuristics, wich is tested first, the other ways are tested only if the first one do not match)

• Even for way prediction, all the tags may be checked in parallel. This has some energy cost but provides earlier miss determination and can facilitate a faster misprediction correction on a hit. For non-skewed associativity the tags can be arranged for one wide read (SIMD-style) rather than multiple quasi-independent reads. (In addition, the data can be read in parallel with the tag read and compare and the correct [hitting] data selected.) – Paul A. Clayton Mar 26 '16 at 14:30
• @PaulA.Clayton : Thank you for these details. There is also the history bits (LRU/PLRU...) which are shared between ways, and can be implemented by reading and updating all tags at once. – TEMLIB Mar 26 '16 at 14:59
• @TEMLIB I still did not understand how the tag fields are checked simultaneously , can you please explain a bit more ? Thanks in advance – nino Mar 26 '16 at 16:44
• @nino : en.wikipedia.org/wiki/CPU_cache, upload.wikimedia.org/wikipedia/commons/7/7e/…. You have RAM blocks, with data read busses, which are connected to several equality comparators. Maybe you are too software-minded : In hardware, there is no need to serialize operations. – TEMLIB Mar 26 '16 at 18:35
• @TEMLIB Okay so are there as many tag comparators as there are lines ? And all comparators simultaneously receive the tag to be compared and in this way a match is determined ? Please correct if there is any mistake. Also , thanks for pointing me in the right direction , I was thinking software wise . Sorry for the late reply – nino Mar 29 '16 at 15:21

In the book Computer Architecture: Fundamentals and Principles of Computer Design by Dumas in 2.3.4 chapter (https://books.google.ru/books?id=TZ6VDQAAQBAJ&pg=PT89&hl=ru&source=gbs_selected_pages&cad=2#v=onepage&q&f=false) it is explained as associative type mapping is physically organized by storing tags in special type memory - content associative memory CAM, which locates not by address, but by content. You can read more on it in wiki, where there are mentions of specific semiconductor implementations: https://en.m.wikipedia.org/wiki/Content-addressable_memory

• CAM are like RAMs with comparators on every address. For caches, it's usualy named "fully associative", and it's practically limited to very small caches, for example to compare addresses in write buffers. – TEMLIB Sep 25 '19 at 21:02
• @temlib, sure, sram is like dram, just little different ;-) anyway thanks for the reply! – Alexei Martianov Sep 26 '19 at 12:22