4.5.3. Mapping Functions

Let us assume that we have an n bit address bus. Therefore, we have a main memory consisting of 2n addressable words. For the purpose of mapping, the main memory is considered to consist of M = 2n/K fixed length blocks of K words each. So, we have a main memory which consists of 2n words or bytes and a block consisting of K words or bytes each. And each so the number of blocks we have in main memory is given by 2n/K. The cache contains m blocks called lines. Each line contains K words same as the same as the block size plus a few tag bits and a valid bit.

In a computer system, the address bus is the pathway through which data is transferred between the CPU and memory. If the address bus is n bits long, it can address 2^n different memory locations. For mapping, we organize this memory into blocks of K words. If we consider that there are M blocks altogether, we determine that the total number of blocks in main memory can be calculated as 2^n divided by K. The cache memory, which is another smaller type of memory, contains m blocks (or lines), and each of these lines also has K words. In addition to these words, each line includes tag bits, which help identify which block of memory is stored in that line, and a valid bit, which tells whether the data in the line is currently valid or usable.

Consider the memory system to be like a library. The address bus is the librarian who can access a certain number of books based on the number assigned to them. If the library has a total of 2^n books, and they are organized in groups of K books (like shelves), the librarian must know which shelf (or block) to go to. Cache memory acts like a small reading area within the library where the most frequently read books (the lines) are kept handy. The tag bits are like labels on the reading area that specify which set of books are currently available for easy access, while the valid bit is like a sign saying whether a particular book can be borrowed or not.

Since, m is much less than M; that is, the number of lines in cache is much less than the number of blocks in the main memory, we need a mechanism for mapping main memory blocks to cache lines. Therefore, we have a mapping function. The simplest mapping function is called direct mapping. In this each main memory block may be mapped to a single unique cache line and the mapping function is given by i = j modulo m; where i is the cache line number, j is the main memory block number and m is the number of cache lines.

When designing a cache, there are usually fewer lines in the cache (m) than there are memory blocks (M) in the main memory. To efficiently use these cache lines, a mapping function is necessary to determine where each block of main memory can be stored in the cache. Direct mapping is a straightforward approach where each block from the main memory is assigned to a specific position in the cache. This is calculated using the modulo operation; for example, if you have a memory block (j), the corresponding cache line (i) is found by taking j and dividing it by the number of cache lines (m), and using the remainder of that division. This means each block has a predetermined place in the cache, making retrieval and updates simpler.

Think of the mapping process like assigning seats in a theater. If there are more people (main memory blocks) than seats (cache lines), the theater assigns each person to a specific seat based on their ticket number, using a simple formula (modulo). So someone with ticket number 10 might always sit in seat 2 if there are 8 seats (since 10 % 8 = 2). This ensures that every time someone goes to watch a performance, they know exactly where to go, just like memory knows where to find its corresponding cache line.

For the purposes of cache access, when we want to read the cache, each main memory address may be viewed as consisting of s+w bits. So, we have a main memory consisting of s+w bits. So, here this is s and this is w. Each main memory address may be viewed as consisting of s + w bits. In which the w LSBs, the least significant bits identify a unique word within or byte within a main memory block. The block size is equal to the line size and is 2w bytes. Because there are w LSBs, we have 2w addressable bytes within a block or line. The s MSBs equal to is the block id, the most significant s bits are the block id. So, it identifies one of 2s main memory blocks. Given the size of cache equals to m = 2r. So, we have let the number of lines in cache equals to m and this m it is equals to 2r; r determines the, determines a line number or the cache index number. So, r bits are used to determine the line number or cache index number. So, s−r bits or the MSBs s−r MSBs of the main memory address gives the size of the tag field.

To access data stored in cache, a main memory address is divided into three parts: the tag, the cache index, and the word offset. The total address consists of s + w bits, where s represents the bits needed to identify the block, and w represents the bits needed to identify the specific word within that block. The least significant bits (w) indicate which word within the block is being accessed. The most significant bits (s) identify which block of memory is being requested. Lastly, there are r bits that correspond to the number of lines in the cache, which tell us exactly where to look within the cache for that block. This structured breakdown ensures that memory accesses are efficient and organized.

Imagine an apartment building where each apartment represents a memory block. The entire address of an apartment can be thought of as a combination of the building number (tag), the floor number (index), and the specific apartment number (word offset). For example, if you wanted to visit apartment number 205 in Building 2, you would first identify the right building (the tag, which is Building 2), then you would check which floor it is on (the index, Floor 0), and finally, which apartment it is on that floor (the offset, Apartment 5). Similarly, cache memory organizes and accesses data with a clear method so that it knows exactly where to go for each piece of information.

--