Computer Organization and Architecture

Module III:Memory Systems & Cache Organization

Name:Prof.Reshma Kohad

Memory Hierarchy

• Concept and need for memory hierarchy

​

• Why Memory Hierarchy is Required in the System?
• Memory Hierarchy helps in optimizing the memory available in the computer.
• There are multiple levels present in the memory, each one having a different size, different cost, etc.
• Some types of memory like cache, and main memory are faster as compared to other types of memory but they are having a little less size and are also costly whereas some memory has a little higher storage value, but they are a little slower.
• Accessing of data is not similar in all types of memory, some have faster access whereas some have slower access.

​

• Types of Memory Hierarchy

​

• This Memory Hierarchy Design is divided into 2 main types:

​

• External Memory or Secondary Memory: Comprising of Magnetic Disk, Optical Disk, and Magnetic Tape i.e. peripheral storage devices which are accessible by the processor via an I/O Module.

​

• Internal Memory or Primary Memory: Comprising of Main Memory, Cache Memory & CPU registers. This is directly accessible by the processor.

�

​

​

​

​

​

​

​

​

• Memory Hierarchy Design
• 1. Registers
• Registers are small, high-speed memory units located in the CPU. They are used to store the most frequently used data and instructions. Registers have the fastest access time and the smallest storage capacity, typically ranging from 16 to 64 bits.

​

2. Cache Memory

• Cache memory is a small, fast memory unit located close to the CPU.
• It stores frequently used data and instructions that have been recently accessed from the main memory. 
• Cache memory is designed to minimize the time it takes to access data by providing the CPU with quick access to frequently used data.

​

3. Main Memory

• Main memory, also known as RAM (Random Access Memory), is the primary memory of a computer system.
• It has a larger storage capacity than cache memory, but it is slower.
•  Main memory is used to store data and instructions that are currently in use by the CPU.

​

​

Types of Main Memory�

• Static RAM: Static RAM stores the binary information in flip flops and information remains valid until power is supplied. 
• Static RAM has a faster access time and is used in implementing cache memory.

​

• Dynamic RAM: It stores the binary information as a charge on the capacitor. It requires refreshing circuitry to maintain the charge on the capacitors after a few milliseconds.
• It contains more memory cells per unit area as compared to SRAM.

​

• 4. Secondary Storage
• Secondary storage, such as hard disk drives (HDD) and solid-state drives (SSD) , is a non-volatile memory unit that has a larger storage capacity than main memory.
• It is used to store data and instructions that are not currently in use by the CPU.
• Secondary storage has the slowest access time and is typically the least expensive type of memory in the memory hierarchy.

​

​

5. Magnetic Disk

• Magnetic Disks are simply circular plates that are fabricated with either a metal or a plastic or a magnetized material.
• The Magnetic disks work at a high speed inside the computer and these are frequently used.

​

6. Magnetic Tape

• Magnetic Tape is simply a magnetic recording device that is covered with a plastic film.
•  Magnetic Tape is generally used for the backup of data. In the case of a magnetic tape, the access time for a computer is a little slower and therefore, it requires some amount of time for accessing the strip.

​

Characteristics of Memory Hierarchy�

• Capacity: It is the global volume of information the memory can store. As we move from top to bottom in the Hierarchy, the capacity increases.

​

• Access Time: It is the time interval between the read/write request and the availability of the data. As we move from top to bottom in the Hierarchy, the access time increases.

​

• Performance: The Memory Hierarch design ensures that frequently accessed data is stored in faster memory to improve system performance.

​

• Cost Per Bit: As we move from bottom to top in the Hierarchy, the cost per bit increases i.e. Internal Memory is costlier than External Memory.

​

Advantages of Memory Hierarchy�

• Performance: Frequently used data is stored in faster memory (like cache), reducing access time and improving overall system performance.

​

• Cost Efficiency: By combining small, fast memory (like registers and cache) with larger, slower memory (like RAM and HDD), the system achieves a balance between cost and performance. It saves the consumer's price and time.

​

• Optimized Resource Utilization: Combines the benefits of small, fast memory and large, cost-effective storage to maximize system performance.

​

• Efficient Data Management: Frequently accessed data is kept closer to the CPU, while less frequently used data is stored in larger, slower memory, ensuring efficient data handling.

​

Disadvantages of Memory Hierarchy�

• Complex Design: Managing and coordinating data across different levels of the hierarchy adds complexity to the system's design and operation.
• Cost: Faster memory components like registers and cache are expensive, limiting their size and increasing the overall cost of the system.
• Latency: Accessing data stored in slower memory (like secondary or tertiary storage) increases the latency and reduces system performance.
• Maintenance Overhead: Managing and maintaining different types of memory adds overhead in terms of hardware and software.

​

Levels of memory

• Types of Computer Memory
• In general, computer memory is divided into three types:
• Primary memory
• Secondary memory
• Cache memory

​

1. Primary Memory

• It is also known as the main memory of the computer system. It is used to store data and programs, or instructions during computer operations.
• It uses semiconductor technology and hence is commonly called semiconductor memory. Primary memory is of two types:

​

​

​

RAM (Random Access Memory):�

• It is a volatile memory. Volatile memory stores information based on the power supply.
• If the power supply fails/ interrupted/stopped, all the data and information on this memory will be lost.
•  RAM is used for booting up or starting the computer. It temporarily stores programs/data which has to be executed by the processor.

RAM is of two types:

​

• S RAM (Static RAM):S RAM uses transistors and the circuits of this memory are capable of retaining their state as long as the power is applied. This memory consists of the number of flip flops with each flip flop storing 1 bit. It has less access time and hence, it is faster.

​

• D RAM (Dynamic RAM):D RAM uses capacitors and transistors and stores the data as a charge on the capacitors. They contain thousands of memory cells. It needs refreshing of charge on capacitor after a few milliseconds. This memory is slower than S RAM.

​

ROM (Read Only Memory)

​

• It is a non-volatile memory. Non-volatile memory stores information even when there is a power supply failed/ interrupted/stopped. 
• ROM is used to store information that is used to operate the system. As its name refers to read-only memory, we can only read the programs and data that are stored on it.
• It contains some electronic fuses that can be programmed for a piece of specific information.
• The information is stored in the ROM in binary format. It is also known as permanent memory. ROM is of four types:

​

​

​

Types of Rom

• MROM(Masked ROM): Hard-wired devices with a pre-programmed collection of data or instructions were the first ROMs.
• Masked ROMs are a type of low-cost ROM that works in this way.

​

• PROM (Programmable Read Only Memory): This read-only memory is modifiable once by the user.
• The user purchases a blank PROM and uses a PROM program to put the required contents into the PROM. Its content can't be erased once written.

​

• EPROM (Erasable Programmable Read Only Memory):EPROM is an extension to PROM where you can erase the content of ROM by exposing it to Ultraviolet rays for nearly 40 minutes.

​

• EEPROM (Electrically Erasable Programmable Read Only Memory): Here the written contents can be erased electrically. You can delete and reprogram EEPROM up to 10,000 times. Erasing and programming take very little time, i.e., nearly  4 -10 ms(milliseconds). Any area in an EEPROM can be wiped and programmed selectively.

​

 Secondary Memory�

• It is also known as auxiliary memory and backup memory.
• It is a non-volatile memory and used to store a large amount of data or information.
• The data or information stored in secondary memory is permanent, and it is slower than primary memory.
• A CPU cannot access secondary memory directly.
• The data/information from the auxiliary memory is first transferred to the main memory, and then the CPU can access it.

Characteristics of Secondary Memory

• It is a slow memory but reusable.
• It is a reliable and non-volatile memory.
• It is cheaper than primary memory.
• The storage capacity of secondary memory is large.
• A computer system can run without secondary memory.
• In secondary memory, data is stored permanently even when the power is off

​

Types of Secondary Memory

• 1. Magnetic Tapes: Magnetic tape is a long, narrow strip of plastic film with a thin, magnetic coating on it that is used for magnetic recording.
• Bits are recorded on tape as magnetic patches called RECORDS that run along many tracks. Typically, 7 or 9 bits are recorded concurrently.
• Each track has one read/write head, which allows data to be recorded and read as a sequence of characters.
• It can be stopped, started moving forward or backwards or rewound.

​

2. Magnetic Disks: A magnetic disk is a circular metal or a plastic plate and these plates are coated with magnetic material.

• The disc is used on both sides. Bits are stored in magnetized surfaces in locations called tracks that run in concentric rings. Sectors are typically used to break tracks into pieces.

​

• Hard discs are discs that are permanently attached and cannot be removed by a single user.

​

​

• 3. Optical Disks: It's a laser-based storage medium that can be written to and read.
• It is reasonably priced and has a long lifespan. The optical disc can be taken out of the computer by occasional users.

Types of Optical Disks�

• CD - ROM
• It's called a compact disk. Only read from memory.
• Information is written to the disc by using a controlled laser beam to burn pits on the disc surface.
• It has a highly reflecting surface, which is usually aluminium.
• The diameter of the disc is 5.25 inches.
• 16000 tracks per inch is the track density.
• The capacity of a CD-ROM is 600 MB, with each sector storing 2048 bytes of data.
• The data transfer rate is about 4800KB/sec. & the new access time is around 80 milliseconds.

​

WORM-(WRITE ONCE READ MANY)�

• A user can only write data once.
• The information is written on the disc using a laser beam.
• It is possible to read the written data as many times as desired.
• They keep lasting records of information but access time is high.
• It is possible to rewrite updated or new data to another part of the disc.
• Data that has already been written cannot be changed.
• Usual size - 5.25 inch or 3.5 inch diameter.
• The usual capacity of a 5.25-inch disk is 650 MB,5.2GB etc.

​

DVDs

• The term "DVD" stands for "Digital Versatile/Video Disc," and there are two sorts of DVDs:
• DVDR (writable)
• DVDRW (Re-Writable)
• DVD-ROMS (Digital Versatile Discs): These are read-only memory (ROM) discs that can be used in a variety of ways.
• When compared to CD-ROMs, they can store a lot more data. It has a thick polycarbonate plastic layer that serves as a foundation for the other layers.
• It's an optical memory that can read and write data.
• DVD-R: DVD-R is a writable optical disc that can be used just once. It's a DVD that can be recorded. It's a lot like WORM. DVD-ROMs have capacities ranging from 4.7 to 17 GB. The capacity of 3.5 inch disk is 1.3 GB.

​

3. Cache Memory�

• Cache Memory is a type of high-speed semiconductor memory that can help the CPU run faster.
• Between the CPU and the main memory, it serves as a buffer.
• It is used to store the data and programs that the CPU uses the most frequently.

​

​

​

​

​

​

​

​

​

Advantages of Cache Memory

• It is faster than the main memory.
• When compared to the main memory, it takes less time to access it.
• It keeps the programs that can be run in a short amount of time.
• It stores data for temporary use.

Disadvantages of Cache Memory

• Because of the semiconductors used, it is very expensive.
• The size of the cache (amount of data it can store) is usually small.

​

Levels of memory

• The Computer memory hierarchy looks like a pyramid structure which is used to describe the differences among memory types. It separates the computer storage based on hierarchy.
• Level 0: CPU registers
• Level 1: Cache memory
• Level 2: Main memory or primary memory
• Level 3: Magnetic disks or secondary memory
• Level 4: Optical disks or magnetic types or tertiary Memory

​

Levels of memory

​

​

​

​

​

​

• In Memory Hierarchy the cost of memory, capacity is inversely proportional to speed. Here the devices are arranged in a manner Fast to slow, that is form register to Tertiary memory.
• Let us discuss each level in detail:

​

• Level-0 − Registers
• The registers are present inside the CPU. As they are present inside the CPU, they have least access time. Registers are most expensive and smallest in size generally in kilobytes. They are implemented by using Flip-Flops.

​

• Level-1 − Cache
• Cache memory is used to store the segments of a program that are frequently accessed by the processor. It is expensive and smaller in size generally in Megabytes and is implemented by using static RAM.

​

• Level-3 − Secondary storage
• Secondary storage devices like Magnetic Disk are present at level 3. They are used as backup storage. They are cheaper than main memory and larger in size generally in a few TB.

​

• Level-4 − Tertiary storage
• Tertiary storage devices like magnetic tape are present at level 4. They are used to store removable files and are the cheapest and largest in size (1-20 TB).

​

Let us see the memory levels in terms of size, access time, bandwidth.

​

​

Latency (Memory Latency)�

• Definition:�
• Latency is the time delay between a request for data and the moment the data becomes available.
• Memory latency measures the delay between a data request and its availability, usually in nanoseconds or CPU cycles, with lower values indicating better performance

​

• Explanation:�When the CPU requests data from memory, it takes some time before the memory sends the data. This delay is called latency.

​

Example:

• CPU requests data from RAM
• RAM takes 50 nanoseconds to respond
• That 50 ns is the memory latency

​

Simple Analogy:�Ordering food in a restaurant 🍽️

• Time between ordering and receiving food = Latency

​

Throughput

• Definition:�Throughput is the amount of data that can be processed or transferred in a given time.

​

• Explanation:�It measures how many memory operations the system can complete per second.

​

• Example:�If a memory system can complete 1000 memory operations per second, its throughput is 1000 operations/sec.
• For eg: Number of customers served per hour in a restaurant.

​

​

• Throughput is the total amount of work done in a given time. 
• CPU execution time is the total time a CPU spends computing on a given task. It also excludes time for I/O or running other programs. This is also referred to as simply CPU time. Performance is determined by execution time as performance is inversely proportional to execution time.

​

• Performance = (1 / Execution time)
• (Performance of A / Performance of B)
• = (Execution Time of B / Execution Time of A)
• (Performance of A / Performance of B)
• = (Execution Time of B / Execution Time of A)
• = 125 / 100 = 1.25

Bandwidth

• Definition:�Bandwidth is the maximum amount of data that can be transferred between memory and CPU per second.

​

• Explanation:�It indicates the data transfer capacity of memory.

​

• Example:�If RAM can transfer 25 GB of data per second, its bandwidth is 25 GB/s.

​

• Formula:
• Bandwidth=Data Transfer Rate× Bus width
• For eg: Wider highway = more cars can travel simultaneously.

Memory Technologies: Overview of main memory technologies.

• Classification of Memory
• Memory is classified into primary and secondary types based on speed, accessibility, and volatility.
• Primary Memory: Directly accessible by the CPU; fast but limited in capacity.
• Secondary Memory: Used for long-term storage; slower but larger in capacity.

​

​

RAM (Random Access Memory)�

• RAM is the computer’s main memory used for temporary storage of active programs and data.
• RAM is a volatile memory, which means, it is present as long as the Computer is in the ON state, as soon as the computer turns OFF, the memory is erased.
• It is referred to as the primary memory of the computer, as it directly supports the CPU during operation.
• RAM is relatively expensive because it allows for fast, direct access to data.
• As the fastest type of memory, RAM serves as internal memory within the computer, enabling quick data retrieval.
• The overall speed of the computer is greatly influenced by the amount of RAM. With less RAM, the computer takes longer to load and may slow down significantly.

​

​

​

​

​

Types of RAM�

1)SRAM (Static Random Access memory)

• SRAM is used for Cache memory, it can hold the data as long as the power availability is there.
• It is refreshed simultaneously to store the present information. It is made with CMOS technology.
• It contains 4 to 6 transistors and it also uses clocks.
• It does not require a periodic refresh cycle due to the presence of transistors.
• Although SRAM is faster, it requires more power and is more expensive. Since SRAM requires more power, more heat is lost here as well.
• The function of SRAM is that it provides a direct interface with the Central Processing Unit at higher speeds.

2. DRAM (Dynamic Random Access memory)�

• DRAM is used for the Main memory, it has a different construction than SRAM, it uses one transistor and one capacitor (also known as a conductor), which is needed to get recharged in milliseconds due to the presence of the capacitor.
• Dynamic RAM was the first sold memory integrated circuit. DRAM is the second most compact technology in production (the First is Flash Memory).
• DRAM has one transistor and one capacitor in 1 memory bit. Although DRAM is slower, it can store more bits per chip, for instance, for the same amount of memory stored in SRAM, DRAM requires one less chip.
• DRAM requires less power and hence, less heat is produced. 
• DRAM is used as the Main Memory inside the computer.
• DRAM is known to be a fast memory but not as fast as SRAM.
• DRAM is cheaper as compared to SRAM.
• DRAM has a higher density (number of memory cells per unit area)
• The power consumption by DRAM is more

​

Types of DRAM�

• SDRAM: Synchronous DRAM, increases performance through its pins, which sync up with the data connection between the main memory and the microprocessor.

​

• DDR SDRAM: (Double Data Rate) It has features of SDRAM also but with double speed.

​

• ECC DRAM: (Error Correcting Code) This RAM can find corrupted data easily and sometimes can fix it.

​

• RDRAM: It stands for Rambus DRAM. It used to be popular in the late 1990s and early 2000s. It was developed by a company named Rambus Inc. At that time it competed with SDRAM. Its latency was higher at the beginning but it was more stable than SDRAM, consoles like Nintendo 64 and Sony Play Station 2 used that.

​

• DDR2, DDR3, AND DDR4: These are successor versions of DDR SDRAM with upgrades in performance

Read Only Memory (ROM)�

• RAM (Random Access Memory), which loses its data when the power is turned off, ROM is designed to store essential information permanently.
• ROM stands for Read-Only Memory.
• It is a non-volatile memory was used to operate the system.
• As its name refers to read-only memory, we can only read the stored programs and data.
• Information stored in ROM is permanent.
• Information and programs are stored on ROM in binary format (0s and 1s).
• It is used in the start-up process of the computer.

​

�Types of ROM �

• MROM(Masked ROM): Hard-wired devices with a pre-programmed collection of data or instructions were the first ROMs. Masked ROMs are a type of low-cost ROM that works in this way.
• PROM (Programmable Read Only Memory): This read-only memory is modifiable once by the user. The user purchases a blank PROM and uses a PROM program to put the required contents into the PROM. Its content can't be erased once written.
• EPROM (Erasable Programmable Read Only Memory):EPROM is an extension to PROM where you can erase the content of ROM by exposing it to Ultraviolet rays for nearly 40 minutes.
• EEPROM (Electrically Erasable Programmable Read Only Memory): Here the written contents can be erased electrically. You can delete and reprogram EEPROM up to 10,000 times. Erasing and programming take very little time, i.e., nearly  4 -10 ms(milliseconds). Any area in an EEPROM can be wiped and programmed selectively.

​

Cache Memory: Purpose of cache memory

• Cache memory is a small, high-speed storage area in a computer.
• It stores copies of the data from frequently used main memory locations. There are various independent caches in a CPU, which store instructions and data.
• The most important use of cache memory is that it is used to reduce the average time to access data from the main memory.
• The concept of cache works because there exists locality of reference (the same items or nearby items are more likely to be accessed next) in processes.
• Cache memory is much faster than the main memory (RAM).
• When the CPU needs data, it first checks the cache. If the data is there, the CPU can access it quickly. If not, it must fetch the data from the slower main memory.

�Characteristics of Cache Memory�

• Extremely fast memory type that acts as a buffer between RAM and the CPU.
• Holds frequently requested data and instructions, ensuring that they are immediately available to the CPU when needed.
• Costlier than main memory or disk memory but more economical than CPU registers.
• Used to speed up processing and synchronize with the high-speed CPU.

​

Cache memory Types�Instruction and data caches, Unified cache

• CPU cache stores both frequently accessed data and instructions.
• When the CPU needs to access data or instructions, it first checks the cache.
• If the required data or instructions are found in the cache (cache hit), it can be quickly retrieved.
• If not found (cache miss), the CPU retrieves the data or instructions from main memory and stores them in the cache for future use.
• If the data is not there, then the CPU access the system main memory & then puts a copy of the new data in the cache before processing it.
• Next time,if the CPU needs to access the same data again,it will just retrive the data from the cache instead of going through the whole loading process again.

​

Instruction Cache (I-Cache)

• 🔹 Definition
• Instruction Cache stores only program instructions (machine code) that the CPU needs to execute.
• 🔹 Working
• CPU fetches instructions from memory
• Frequently used instructions are stored in I-cache
• Reduces time required for instruction fetch
• 🔹 Features
• Read-only (mostly, no modification needed)
• Used during instruction fetch stage
• Faster execution of programs
• 🔹 Advantages
• Faster instruction access� Improves CPU pipeline performance� Reduces memory access latency

​

Data Cache (D-Cache)

• Definition
• Data Cache stores data values (variables, arrays, etc.) used by programs.
• 🔹 Working
• CPU reads/writes data frequently
• Frequently accessed data is stored in D-cache
• Supports both read and write operations
• 🔹 Features
• Read and write operations
• Used during execution stage
• Handles memory updates
• 🔹 Advantages
• Faster data access� Improves program execution speed
• Reduces load/store delays

​

​

Unified Cache

• Definition
• Unified Cache stores both instructions and data in a single cache memory.
• 🔹 Working
• One cache is shared for instructions and data
• Dynamically allocates space based on need
• 🔹 Features
• Flexible memory usage
• Simpler design
• Used in L2 or L3 cache levels
• Advantages
• ✔ Better cache utilization�✔ Efficient use of memory space�✔ Simpler hardware design

​

​

Cache Performance�

• When the processor needs to read or write a location in the main memory, it first checks for a corresponding entry in the cache.
• If the processor finds that the memory location is in the cache, a Cache Hit has occurred and data is read from the cache.
• If the processor does not find the memory location in the cache, a cache miss has occurred. For a cache miss, the cache allocates a new entry and copies in data from the main memory, then the request is fulfilled from the contents of the cache.
• The performance of cache memory is frequently measured in terms of a quantity called Hit ratio.

​

• Hit Ratio(H) = hit / (hit + miss) = no. of hits/total accesses
• Miss Ratio = miss / (hit + miss) = no. of miss/total accesses = 1 - hit ratio(H)

​

Write Through: 

• In write-through, data is simultaneously updated to cache and memory. This process is simpler and more reliable.
• This is used when there are no frequent writes to the cache(The number of write operations is less). �
• It helps in data recovery (In case of a power outage or system failure).
• A data write will experience latency (delay) as we have to write to two locations (both Memory and Cache).
• It Solves the inconsistency problem. But it questions the advantage of having a cache in write operation (As the whole point of using a cache was to avoid multiple access to the main memory). 

Write Back: 

• The data is updated only in the cache and updated into the memory at a later time.
• Data is updated in the memory only when the cache line is ready to be replaced (cache line replacement is done using Belady's Anomaly, Least Recently Used Algorithm, FIFO, LIFO, and others depending on the application). �Write Back is also known as Write Deferred. ��Dirty Bit: Each Block in the cache needs a bit to indicate if the data present in the cache was modified(Dirty) or not modified(Clean).
• If it is clean there is no need to write it into the memory. It is designed to reduce write operation to a memory.
• If Cache fails or if the System fails or power outages the modified data will be lost. Because it's nearly impossible to restore data from cache if lost. ��If write occurs to a location that is not present in the Cache(Write Miss), we use two options, Write Allocation and Write Around. 

Types of cache misses

• 1. Compulsory Misses
• Description: Compulsory misses occur when a memory block is accessed for the first time, meaning it’s not yet in the cache. Since the data has never been loaded before, the cache will miss the access and need to fetch the data from the main memory.
• Other Names: Cold-start misses, compulsory line fills.
• Impact: These misses are inevitable and cannot be avoided, especially for new data accesses. However, they can be minimized by increasing cache efficiency or using better prefetching techniques.

​

2. Capacity Misses�

• Description: Capacity misses happen when the cache does not have enough space to store all the data needed by the processor. When the cache becomes full, older or unused data may be evicted, resulting in misses when the data is accessed again.
• Impact: These misses are more likely to occur when dealing with large datasets or applications that require more data than the cache can hold.

​

3. Conflict Misses�

• Description: Conflict misses occur in direct-mapped and set-associative caches due to the limited number of locations available for storing data. If multiple memory blocks map to the same cache location, one block will evict another, causing a miss when the evicted block is accessed again.
• Impact: Conflict misses are more common in direct-mapped caches, where each memory block is mapped to a specific location.

​

4. Coherence Misses�

• Description: Coherence misses, also known as invalidation misses, occur in systems with multiple processors or cores. These misses arise when a processor's cache holds stale data that has been modified by another processor or an external device (e.g., I/O devices).
• Cause: These misses typically occur when data is invalidated or modified in one cache, and the change must be reflected in other caches.
• Impact: Coherence misses can introduce delays due to the need for data synchronization across processors or devices.

​

Cache Mapping and Operations

• Cache mapping techniques
• Cache mapping refers to the method used to store data from main memory into the cache. It determines how data from memory is mapped to specific locations in the cache.
• There are three different types of mapping used for the purpose of cache memory which is as follows:
• Direct Mapping
• Fully Associative Mapping
• Set-Associative Mapping

​

�1. Direct Mapping�

• Direct mapping is a simple and commonly used cache mapping technique where each block of main memory is mapped to exactly one location in the cache called cache line.
• If two memory blocks map to the same cache line, one will overwrite the other, leading to potential cache misses. Direct mapping's performance is directly proportional to the Hit ratio.

​

• Memory block is assigned to cache line using the formula below:

​

• i = j modulo m = j % m
• where,
• i = cache line number
• j = main memory block number
• m = number of lines in the cache

​

​

• The Cache Memory consists of cache lines. These cache lines has same size as memory blocks. The address in cache memory consists of:
• Block Offset: This is the same block offset we use in Main Memory.
• Index: It represent cache line number. This part of the memory address determines which cache line (or slot) the data will be placed in.
• Tag: The Tag is the remaining part of the address that uniquely identifies which block is currently occupying the cache line.

​

​

​

​

​

​

​

• The index field in main memory maps directly to the index in cache memory, which determines the cache line where the block will be stored.
• The block offset in both main memory and cache memory indicates the exact word within the block. In the cache, the tag identifies which memory block is currently stored in the cache line.
• This mapping ensures that each memory block is mapped to exactly one cache line, and the data is accessed using the tag and index while the block offset specifies the exact word in the block.

�2. Fully Associative Mapping�

• Fully associative mapping is a type of cache mapping where any block of main memory can be stored in any cache line.
• Unlike direct-mapped cache, where each memory block is restricted to a specific cache line based on its index, fully associative mapping gives the cache the flexibility to place a memory block in any available cache line.
• This improves the hit ratio but requires a more complex system for searching and managing cache lines.
• The address structure of Cache Memory is different in fully associative mapping from direct mapping.
• In fully associative mapping, the cache does not have an index field. It only have a tag which is same as Index Field in memory address.
• Any block of memory can be placed in any cache line. This flexibility means that there’s no fixed position for memory blocks in the cache.

​

• To determine whether a block is present in the cache, the tag is compared with the tags stored in all cache lines.
• If a match is found, it is a cache hit, and the data is retrieved from that cache line. If no match is found, it's a cache miss, and the required data is fetched from main memory.

​

​

​

​

​

​

�3. Set-Associative Mapping�

• Set-associative mapping is a compromise between direct-mapped and fully-associative mapping in cache systems. It combines the flexibility of fully associative mapping with the efficiency of direct mapping. In this scheme, multiple cache lines (typically 2, 4, or more) are grouped into sets.

​

• v = m / k
• where,
• m = number of cache lines in the cache memory
• k = number of cache lines we want in each set
• v = number of sets

​

• Like direct mapping, now each memory block can be placed into any cache line within a specific set.

​

• i = j modulo v = j % v
• where,
• j = main memory block number
• v = number of sets
• i = cache line set number

​

• The Cache address structure is as follows:

​

​

​

• This reduces the conflict misses that occur in direct mapping while still limiting the search space compared to fully-associative mapping.
• For example, consider a 2-way set associative cache, which means 2 cache lines make a set in this cache structure. There are 8 memory blocks and 4 cache lines, thus the number of sets will be 4/2 = 2 sets. Using direct mapping strategy first, block 0 will be in set 0, block 1 in set 1, block 2 in set 2 and so on. Then, the tag is used to search through all cache lines in that set to find the correct block (Associative Mapping).

​

• Data Array: The data array holds the actual contents of the cached memory blocks (cache lines).
• Its path drives the selection of the data from the potential sets.
• Tag Array: The tag array stores the address tags that identify which memory block is currently stored in a particular cache line.
• The path through the tag array determines if a cache hit or miss has occurred by comparing the requested address tag with the stored tags.

​

multi-level caches

• Cache is a type of random access memory (RAM) used by the CPU to reduce the average time required to access data from memory.
• Multilevel caches are one of the techniques used to improve cache performance by reducing the miss penalty.
• The miss penalty refers to the additional time needed to retrieve data from the main memory when a cache miss occurs.

​

• Effective Access Time = Hit rate * Cache access time + Miss rate * Lower level access time
• Here,
• Hit Rate: The probability or percentage of finding data in the cache.
• Miss Rate: The probability or percentage of not finding data in the cache. (Miss Rate = 1 - Hit Rate)
• Cache Access Time: The time required to access data directly from the cache.
• Lower-Level Memory Access Time: The time required to access data from lower-level memory, such as main memory or secondary storage.

​

• Here the Cache performance is optimized further by introducing multilevel Caches. As shown in the below figure, we are considering 2 level Cache Design.
• It is clear that here the Miss Penalty is reduced considerably than that in the previous case thereby improving the Performance of Cache Memory. 

​

• where �H1 is the Hit rate in the L1 caches. �H2 is the Hit rate in the L2 cache. �C1 is the Time to access information in the L1 caches. �C2 is the Miss penalty to transfer information from the L2 cache to an L1 cache. �M is the Miss penalty to transfer information from the main memory to the L2 cache. 
• Assume: 6 L1 hits , 3 L1 misses that hit in L2 ,1 full miss (goes to main memory)
• Access times:
• L1 hits → 6 × 1 ns = 6 ns
• L2 hits → 3 × (1 ns + 5 ns) = 3 × 6 ns = 18 ns
• Main memory → 1 × (1 ns + 5 ns + 100 ns) = 106 ns
• Total time = 6 ns + 18 ns + 106 ns = 130 ns

​

Least Recently Used (LRU)�

• Least Recently Used (LRU)
• LRU replaces the block that hasn’t been accessed for the longest time, based on the principle that recently used data is likely to be used again soon. It is widely used in systems where temporal locality is common.
• Example:�Cache size = 3, Reference string: 1, 2, 3, 1, 4, 5, 2
• Load 1, 2, 3 → Cache = [1, 2, 3]
• Access 1 → Hit, recently used, no replacement → Cache = [1, 2, 3]
• Next 4 → Replace 2 (least recently used) → Cache = [1, 4, 3]
• Next 5 → Replace 3 → Cache = [1, 4, 5]
• Next 2 → Replace 1 → Cache = [2, 4, 5]

​

�Levels of Memory�

• Level 1 or Register: It is a type of memory in which data is stored and accepted that are immediately stored in the CPU. The most commonly used register is Accumulator, Program counter, Address Register, etc.
• Level 2 or Cache memory: It is the fastest memory that has faster access time where data is temporarily stored for faster access.
• Level 3 or Main Memory: It is the memory on which the computer works currently. It is small in size and once power is off data no longer stays in this memory.
• Level 4 or Secondary Memory: It is external memory that is not as fast as the main memory but data stays permanently in this memory.

​