Caches: Calculate the Number of Index Bits

Index bits are used to determine which “line” of a cache you are looking into, therefore you must have enough bits to identify all of the “lines” in the cache.  There are a few different ways to organize data blocks into these “lines”.  Here’s how to calculate the number of index bits needed for the following organization methods:

• Direct-Mapped – Each line has 1 data block.  Therefore, to determine the number of lines, simply divide the total size of the data in cache by size of an individual block.  Once you have that, determine the number of bits required to identify each line -> 2^n lines requires n bits to identify all addresses.
• Fully-Associative – There is one long line of m blocks, where m is the number of entries in the cache.  Because there is only one line, you don’t need an index bit.
• Set-Associative – In each “line” of the cache, there are n blocks for an n-way associative cache.  First determine the number of blocks per line then divide the total size of data in the cache by the size of the data in each line - For example, if you are given an 8-way associative cache with block size of 4 bytes and 1kb of total data, you’d calculate the number of index bits needed by doing the following:
• Data per line = 8 * 4 bytes = 32 bytes
• Number of lines = 1kb / 32 bytes = 2<>10/25 = 2^5
• Therefore, you need 5 bits in order to identify all of the lines.