In this blog post, we’ll compare a smartphone’s “Favorites” feature to a computer’s cache to explore the principle of keeping frequently used data close at hand, as well as the structure and operation of a cache.
When using a smartphone, placing frequently used apps—such as KakaoTalk or the phone app—in an easily accessible location reduces the time it takes to find them, making them more convenient to use. On an iPhone, for example, you can place four frequently used apps at the bottom of the screen for easy access at any time. This principle of placing frequently used items in an easily accessible location is also applied in computer memory, and one such mechanism is the cache.
In computer science, a cache refers to a temporary storage area where data or values are pre-stored. It can take relatively long for a program to retrieve data from main memory. Therefore, storing frequently used data in the cache can reduce the time it takes to retrieve the necessary data. In actual computer systems, caches are often organized into multiple levels; if the requested data is in the cache, a “cache hit” occurs, and if it is not, a “cache miss” occurs. When a cache miss occurs, the data is retrieved from the next memory level or main memory.
A cache consists of multiple sets, and each set contains multiple lines. Each line typically includes a valid bit, a tag, and a cache line or data block where the data is stored. The valid bit indicates whether the line contains valid data; a value of 1 means valid data is present, while a value of 0 means no valid data is present. The tag is used to identify which memory address the data corresponds to, and the data block actually holds the data stored in the cache.
When accessing the cache using an address, the address can be divided into a tag, a set index, and a block offset. The specific configuration depends on the cache’s design, but for the purposes of this discussion, let’s assume the cache has two sets, each containing two lines. You can think of it as a 2×2 table. Let’s say the first two bits of the address represent the tag, the next bit represents the set index, and the last bit represents the block offset. If the block size is two data units, the block offset indicates the position of the desired data within that block. For example, if the block offset is 1, it points to the second data position in that block.
Suppose you want to retrieve data from a specific address ranging from 0 to 15. Since computers represent numbers in binary, the address is first converted to a binary number and then divided into a tag, a set index, and a block offset to locate the data in the cache.
First, the system searches for the line in set 0 with a tag of 00. However, since all valid bits are initially set to 0, that line is not valid. Therefore, the system accesses memory to retrieve the data at address 0. It then sets the valid bit for that line to 1 and the tag to 00, and stores the data belonging to that memory block in the data block.
Next, when accessing address 1, it looks for the line in set 0 with a tag of 00. This is the line added immediately before, and since the block offset is 1, it retrieves the second piece of data from that line’s data block. Since there is no need to access memory again to retrieve the data, time is saved—this is a key benefit of using a cache.
Similarly, since address 7 corresponds to set 1 and has a tag of 01, the block containing the data for addresses 6 and 7 is added to that line. Since address 8 corresponds to set 0 and has a tag of 10, the block containing the data for addresses 8 and 9 is added to that line. In this way, as a result of referencing data from memory, the cache stores data blocks corresponding to each address.
Just as using a cache reduces the time spent on unnecessary memory accesses and improves efficiency, in our daily lives, we can use our time more wisely by keeping frequently used items in easily accessible places.
