How does a TLB lookup compare all keys simultaneously?

Question

I am reading OS Concepts dinosaur book which says, "Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously."

I checked How does a TLB and data cache work? but it does not say anything about the implementation that allows this parallel checking of the keys.

I read something about a parallel hash table here: http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/lectures/lecture27.pdf

Is this the basic idea? The insertion of a key outputs a frame number and this could either be a hit or miss?

Answer 1

Computer hardware is fundamentally parallel. Even a modern single CPU core is pipelined, meaning that at the same instant in time, one physical part of the CPU is initiating a fetch of an instruction, another is decoding a slightly earlier fetched instruction, another is calculating the new result of a slightly earlier decoded instruction, and another is writing back the results of a slightly earlier calculating instruction.

One of the reasons a layer 1 cache in a CPU is so small, and so much more expensive per bit of storage, is that the tag cache portion of the address is broadcast to multiple cache lines, and each of them has some independent hardware logic to compare this tag value against its own tag value in parallel, each independently calculating "that tag matches what I have" or "it doesn't match me".