The content of this blog is my personal opinion only. Although I am an employee - currently of Nvidia, in the past of other companies such as Iagination Technologies, MIPS, Intellectual Ventures, Intel, AMD, Motorola, and Gould - I reveal this only so that the reader may account for any possible bias I may have towards my employer's products. The statements I make here in no way represent my employer's position, nor am I authorized to speak on behalf of my employer. In fact, this posting may not even represent my personal opinion, since occasionally I play devil's advocate.

See http://docs.google.com/View?id=dcxddbtr_23cg5thdfj for photo credits.

Thursday, August 05, 2010

Table indexing - CompArch

Table indexing - CompArch: "Table indexing
When I say that 'a table is indexed by a value V', I do not mean that all of the bits of V are used to form an address. Although that could be done, for something like a 64 bit address it could be a very large address.
Rather, I mean that the value V is used to determine what entry in the table is to be used. Some bits of V may be used as a number, to index the table. I call that RAM indexing. It may also use a hash of V.
Some or all of the bits of V may be matched against addresses already in the table. This is called CAM addressing.
RAM indexing and CAM indexing may be combined. E.g. RAM indexing may determine a set containing N tags, which are compared against the other bits of V to determine which entry within the set (often called which way of the set) should match.
For that matter, I also call it CAM indexing if bits of V are used to determine 1 of N bits, and that 1 of N code is compared to multiple entries in a table. See Decoded CAM versus Encoded CAM.
Thus, the term 'indexing' is general, not limited to the specific form of RAM indexing"

No comments: