Introduction to Memory and Memory Parameters

Computer memory is a fundamental component of any computer system, serving as the

storage space for data and instructions that the Central Processing Unit (CPU) needs to
access quickly. Its primary purpose is to hold information temporarily or permanently for
processing.
Key parameters defining memory performance and characteristics include:
* Capacity: The total amount of data that a memory unit can store, typically measured
in bits, bytes, kilobytes (KB), megabytes (MB), gigabytes (GB), or terabytes (TB).
* Speed (Access Time): The time it takes for the CPU to retrieve data from or store
data into a memory location. Lower access time indicates faster memory.
* Bandwidth: The rate at which data can be transferred between the memory and the
CPU or other components, often measured in bytes per second.
* Location: Refers to whether the memory is internal (e.g., registers, cache, main
memory) or external (e.g., hard drives, SSDs).

*A general diagram illustrating the classification of computer memory.

Classifications of Primary and Secondary

Memories
Computer memory is broadly classified into primary and secondary memory based on
their function, speed, volatility, and direct accessibility by the CPU.

Primary Memory (Main Memory)

Primary memory is essential for the immediate operation of a computer.
* Direct Access: It is directly accessible by the CPU, meaning the CPU can read from
and write to it without needing I/O operations.
* Volatility: Most primary memory (like RAM) is volatile, meaning it loses its stored data
when the power is turned off. ROM is an exception as it is non-volatile.
* Speed and Cost: It is significantly faster but more expensive per unit of storage
compared to secondary memory.
* Examples: RAM (Random Access Memory), ROM (Read-Only Memory), Cache
memory, and CPU registers.

*Classification of computer memory into primary and secondary types.

Secondary Memory (Auxiliary Memory)

Secondary memory provides long-term, non-volatile storage.
* Indirect Access: The CPU cannot directly access secondary memory. Data must first
be transferred to primary memory (RAM) before the CPU can process it.
* Non-Volatility: It is non-volatile, meaning it retains data even when the power is
turned off.
* Speed and Cost: It is slower and much cheaper per unit of storage than primary
memory.
* Examples: Hard Disk Drives (HDDs), Solid State Drives (SSDs), USB flash drives,
CDs, DVDs, and magnetic tapes.
*Comparison of primary and secondary memory characteristics.

Types of RAM and ROM

RAM and ROM are two fundamental types of primary memory, each serving distinct
purposes.

Random Access Memory (RAM)

RAM is a volatile, read/write memory used for temporarily storing data and programs
that the CPU is currently using.
* SRAM (Static RAM):
* Faster, more expensive, and consumes more power than DRAM.
* Uses latches (transistors) to store bits, so it does not need to be refreshed periodically.
* Typically used for cache memory (L1, L2, L3) due to its speed.
* DRAM (Dynamic RAM):
* Slower, cheaper, and consumes less power than SRAM.
* Uses capacitors and transistors to store bits. Capacitors gradually lose their charge,
so DRAM needs to be refreshed periodically to retain data.
* Commonly used as the main memory (system RAM) in computers.
*Classification of memory, highlighting RAM and ROM types.

Read Only Memory (ROM)

ROM is a non-volatile memory that permanently stores firmware and boot-up
instructions. Its contents are generally set during manufacturing and are not meant to be
modified by the user during normal operation.
* Mask ROM (MROM): Programmed during the manufacturing process. Its content
cannot be altered. It is the oldest type of ROM.
* Programmable ROM (PROM): Can be programmed once by the user or
manufacturer using a special device called a PROM programmer. After programming, it
cannot be erased.
* Erasable Programmable ROM (EPROM): Can be erased by exposing it to strong
ultraviolet (UV) light. Once erased, it can be reprogrammed multiple times.
* Electrically Erasable Programmable ROM (EEPROM): Can be erased and
reprogrammed electrically, byte by byte, without removing it from the circuit board. It
has a limited number of erase/write cycles.

Memory Hierarchy and Characteristics

The memory hierarchy is a structured arrangement of different types of memory in a
computer system, organized based on their access speed, capacity, and cost per bit.
The goal is to optimize the trade-off between speed and cost, making the most
frequently accessed data available quickly.
*The memory hierarchy pyramid, showing various levels of memory.
Levels of Memory Hierarchy (from fastest/smallest/most expensive to
slowest/largest/cheapest):
1. Registers: Smallest and fastest memory, directly within the CPU. Used to hold
data that the CPU is actively processing.
2. Cache Memory (L1, L2, L3): Small, very fast memory placed between the CPU
and main memory. Stores copies of frequently accessed data and instructions
from main memory.
3. Main Memory (RAM): The primary working memory of the computer. It's larger
than cache but slower.
4. Secondary Storage (Magnetic Disks, SSDs, Optical Disks): Non-volatile
storage devices with large capacities, used for long-term data storage. Slower
than main memory.
5. Tertiary Storage (Magnetic Tapes, Optical Jukeboxes): Used for archival
storage, typically very large capacity, but with the slowest access times.
Characteristics of Memory Hierarchy:
* Capacity: Increases as you move down the hierarchy (from registers to tertiary
storage).
* Access Time: Increases as you move down the hierarchy (faster at the top, slower at
the bottom).
* Cost per bit: Decreases as you move down the hierarchy (more expensive at the top,
cheaper at the bottom).
* Frequency of Access by CPU: Data in higher levels (closer to CPU) is accessed
more frequently than data in lower levels.

Virtual Memory: Segmentation and Paging

Virtual memory is a memory management technique that allows programs to execute
even if they are not entirely loaded into physical memory. It creates the illusion of a
much larger memory space than physically available by using disk space as an
extension of RAM. This technique relies on mapping virtual addresses used by
programs to physical addresses in RAM. The two primary techniques for implementing
virtual memory are paging and segmentation.

Paging
Paging is a memory management scheme that divides both physical memory and
logical (virtual) memory into fixed-size blocks.
* Frames: Physical memory is divided into fixed-size blocks called frames.
* Pages: Logical (virtual) memory is divided into fixed-size blocks of the same size as
frames, called pages.
* Page Table: The operating system maintains a page table for each process. This
table maps the virtual page numbers to their corresponding physical frame numbers.
When a program tries to access a virtual address, the Memory Management Unit
(MMU) uses the page table to translate it into a physical address.
* Benefits: Paging eliminates external fragmentation (unused gaps between allocated
memory blocks) and simplifies memory allocation by treating memory as a uniform array
of fixed-size units.

*Illustrating the concept of virtual memory and paging. (Source: [Link])*

Segmentation
Segmentation is a memory management scheme that divides logical memory into
variable-sized blocks called segments. These segments correspond to logical units of a
program, such as code, data, stack, or subroutines.
* Segments: Each segment has a name and a length. Programs are organized into
segments that are meaningful to the programmer.
* Segment Table: The operating system uses a segment table to map logical segment
addresses to physical addresses. Each entry in the segment table contains the base
address and length of a segment.
* Benefits: Segmentation provides a clear, logical view of memory to the programmer,
simplifies protection and sharing of code/data segments among processes, and can
help with dynamic linking.
* Drawbacks: Can lead to external fragmentation as segments are of variable sizes,
making it difficult to find contiguous free blocks.

*Virtual memory segmentation example with two jobs. (Source: [Link])*

Modern operating systems often combine both paging and segmentation, where
segments are further divided into pages (segmented paging).

Cache Memory: Concept, Hierarchy, and

Mapping Techniques
Cache memory is a small, high-speed memory that stores copies of data from
frequently used main memory locations. Its primary goal is to reduce the average time
required to access data from the main memory, thereby speeding up CPU operations.
Concept
When the CPU needs data, it first checks the cache. If the data is found in the cache (a
"cache hit"), it's retrieved much faster than from main memory. If not (a "cache miss"),
the CPU fetches the data from main memory, and a copy is also placed in the cache for
future use.

*Key elements of cache design. (Source: [Link])*

Cache Hierarchy (L1, L2, L3)

Modern CPUs employ a multi-level cache hierarchy to further optimize performance:
* L1 Cache (Level 1):
* Smallest (tens of KB) and fastest cache.
* Typically integrated directly into the CPU chip and dedicated to each core.
* Often split into an instruction cache (for program instructions) and a data cache (for
data operands).
* L2 Cache (Level 2):
* Larger (hundreds of KB to several MB) and slower than L1, but faster than main
memory.
* Can be exclusive to a core or shared between a few cores.
* L3 Cache (Level 3):
* Largest (several MB to tens of MB) and slowest of the cache levels.
* Typically shared among all CPU cores. It acts as a victim cache for data evicted from
L2.
Mapping Techniques
Cache mapping techniques determine how a block of main memory maps to a line in
the cache. The choice of mapping technique impacts cache performance (hit rate) and
complexity.
1. Direct Mapping:
– The simplest technique. Each block from main memory can only be placed
into one specific, pre-determined line in the cache.
– The cache line index is determined by a modulo operation on the main
memory block address: Cache Line Index = (Main Memory Block Address)
MOD (Number of Cache Lines).
– Advantage: Simple hardware implementation.
– Disadvantage: High conflict misses if frequently accessed blocks map to
the same cache line, even if other cache lines are empty.
2. Fully Associative Mapping:
– The most flexible technique. Any block from main memory can be placed
in any available line in the cache.
– Requires a comparator for every cache line to check if the desired block is
present. This is done by comparing the tag of the requested address with
all tags in the cache simultaneously.
– Advantage: Highest hit rate, lowest conflict misses.
– Disadvantage: Most complex and expensive to implement (requires
Content Addressable Memory - CAM), making it practical only for very
small caches (e.g., TLBs - Translation Lookaside Buffers).

*A conceptual diagram of fully associative mapping.

1. Set-Associative Mapping:
 – A compromise between direct and fully associative mapping. The cache is
divided into a number of "sets," and each set contains a fixed number of
cache lines (e.g., 2-way, 4-way, 8-way).
– A main memory block maps to a specific set (determined by a modulo
operation), but within that set, it can be placed in any available cache line.
– Formula: Set Index = (Main Memory Block Address) MOD (Number of
Sets).
– Advantage: Better hit rate than direct mapping and less complex than
fully associative mapping. It's the most common mapping technique in
modern CPUs.

*Illustrating cache memory mapping components.

Cache Coherency and Techniques to Resolve It

Cache Coherency Problem: In a multiprocessor system, each processor typically has
its own local cache. When multiple processors share data, and one processor modifies
its copy of a data block in its cache, other processors' caches and main memory will
hold an outdated (stale) copy of that data. This inconsistency is known as the cache
coherency problem.
Cache Coherency: The consistency of data across multiple caches in a multiprocessor
system. A system is cache coherent if all reads of a data item return the most recently
written value, regardless of which cache holds it.
*An example of a multiprocessor system showing shared memory and individual
caches.
Techniques to Resolve Cache Coherency:
1. Snooping Protocols:
– Most common approach for bus-based multiprocessor systems.
– Each cache controller "snoops" or monitors the shared bus for memory
access requests from other processors.
– When a processor performs a write operation to a shared memory block, it
broadcasts a signal on the bus.
– Write-Invalidate Protocol: When a write operation is detected for a
shared block, all other caches holding a copy of that block invalidate their
local copy. Subsequent reads by those processors will result in a cache
miss, forcing them to fetch the updated data from the writer's cache or
main memory. This is the most widely used approach (e.g., MESI
protocol).
– Write-Update Protocol: When a write operation is detected, all other
caches holding a copy of that block update their local copy with the new
value. This generates more bus traffic but can reduce latency for
subsequent reads.
2. Directory-Based Protocols:
– More suitable for larger-scale multiprocessor systems where a shared bus
becomes a bottleneck.
 – A central directory (or distributed directories) maintains the state of each
memory block and tracks which caches hold copies of that block.
– When a processor wants to modify a shared block, it consults the
directory. The directory then sends messages (e.g., invalidate requests)
directly to the relevant caches.
– Advantage: Reduces bus traffic compared to snooping for large systems.
– Disadvantage: More complex hardware to implement and manage the
directory.

Interleaved and Associative Memory

These are two distinct memory organization techniques used to enhance memory
performance or functionality.

Interleaved Memory
Interleaved memory is a technique to improve memory bandwidth by dividing the main
memory into multiple independent modules or banks. Successive memory addresses
are distributed across these different modules.
* Concept: Instead of placing consecutive memory words in a single memory bank,
they are distributed sequentially among multiple banks. For example, in a 4-way
interleaved memory, word 0 is in bank 0, word 1 in bank 1, word 2 in bank 2, word 3 in
bank 3, and word 4 back in bank 0.
* Benefit: This allows the memory system to access multiple words in parallel (from
different banks) during a single memory cycle. It significantly improves throughput for
sequential data access, as the CPU doesn't have to wait for one bank to complete an
operation before starting another.
* Application: Commonly used in systems requiring high memory bandwidth, like
graphics cards or high-performance computing.

*An example of interleaved memory organization

Associative Memory (Content-Addressable Memory -
CAM)
Unlike traditional memory which is accessed by providing an address, associative
memory is accessed based on its content.
* Concept: When you provide a data pattern (the "search key"), the associative
memory simultaneously compares this pattern with all stored data items. If a match is
found, it returns the address(es) where the matching data is stored.
* Parallel Search: Its unique characteristic is its ability to perform parallel searches
across all stored data, making it extremely fast for lookup operations.
* Application:
* Cache Tag Memory: Used in fully associative and set-associative caches to quickly
determine if a memory block is present in the cache.
* Translation Lookaside Buffers (TLBs): Used in virtual memory systems to speed up
the translation of virtual addresses to physical addresses.
* Network Routers: For rapid lookup of routing tables.
* Database Acceleration: For faster searching and pattern matching.
* Drawbacks: Much more expensive and complex to implement than conventional RAM
due to the extensive comparison logic required for each memory cell.
*Conceptual overview of interleaved and associative memory.

Self-Study: Case Study of Pentium Processor

Cache Memory Model (MESI Protocol)
The MESI (Modified, Exclusive, Shared, Invalid) protocol is a widely adopted cache
coherence protocol, famously used in Intel's Pentium processors and many other multi-
core architectures. It is a write-invalidate protocol, meaning when a processor writes to
a shared cache line, it invalidates other copies rather than updating them directly. MESI
ensures that all processors in a system see a consistent view of shared memory.
Each cache line in a MESI-compliant cache is tagged with one of four states:
1. Modified (M):
– Meaning: The cache line contains data that has been modified by the
local CPU. This copy is dirty (i.e., different from main memory) and is the
only copy of this data block in any cache in the system.
– Action on Read by others: If another CPU tries to read this memory
block (BusRd), the current CPU must write the modified data back to main
memory before changing its state to Shared.
– Action on Write by CPU: The CPU can write to this line without a bus
transaction.
2. Exclusive (E):
– Meaning: The cache line contains data that is identical to main memory
(it's clean), and this cache is the only copy of this data block in any cache
in the system.
– Action on Write by CPU: If the CPU writes to this line, its state changes
directly to Modified (M) without needing any bus transaction (since it's the
only copy). This is a fast operation.
– Action on Read by others: If another CPU reads this block (BusRd), the
state changes to Shared (S).
3. Shared (S):
– Meaning: The cache line contains data that is identical to main memory
(it's clean), and other caches may also hold a copy of this data block.
– Action on Write by CPU: If the CPU wants to write to this line, it must
first issue a "Bus Update" or "Bus Read Exclusive" (BusRdX/BusUpgr)
signal on the bus. This invalidates all other shared copies, and its local
copy then transitions to Modified (M).
– Action on Read by CPU: The CPU can read this line without any bus
transaction.
4. Invalid (I):
– Meaning: The cache line does not contain valid data. The data is either
not present in the cache or has been invalidated by another processor's
write operation.
– Action on Read/Write by CPU: Any read or write access to this line will
result in a cache miss. The data must be fetched from main memory or
another cache that holds a valid (Modified or Shared) copy.
*State transition diagram of the MESI protocol.
How MESI Ensures Coherency (Examples of State Transitions):
Let's consider two CPUs, CPU1 and CPU2, both initially with an Invalid (I) copy of a
memory block X.
1. CPU1 Reads X (I -> E):
– CPU1 needs X, finds it Invalid. Issues a BusRd request.
– Since no other cache has X (or it's clean in main memory), CPU1 loads X
into its cache and sets its state to Exclusive (E).
– Result: CPU1 has the only copy, it's clean.
2. CPU2 Reads X (E -> S for CPU1, I -> S for CPU2):
– Now, CPU2 also needs X. Issues a BusRd.
– CPU1's cache snoops the BusRd request. Since CPU1 has X in Exclusive
state, it knows another cache wants a copy. CPU1's cache changes its
state from Exclusive (E) to Shared (S).
 – CPU2 loads X into its cache and sets its state to Shared (S).
– Result: Both CPU1 and CPU2 have clean, identical copies of X, and both
are in the Shared state.
3. CPU1 Writes to X (S -> M for CPU1, S -> I for CPU2):
– CPU1 wants to modify X. It finds X in Shared state.
– CPU1 issues a BusUpgr (Bus Upgrade) or BusRdX (Bus Read Exclusive
with Invalidate) request on the bus.
– CPU2's cache snoops this request. Since CPU2 has X in Shared state, it
immediately invalidates its copy of X (S -> I).
– CPU1 then writes to its local copy of X and changes its state from Shared
(S) to Modified (M).
– Result: CPU1 now has the only valid copy, which is dirty (Modified).
CPU2's copy is invalid.
4. CPU2 Reads X after CPU1 Writes (I -> S for CPU2, M -> S for CPU1):
– CPU2 now wants to read X (its copy is Invalid). Issues a BusRd.
– CPU1's cache snoops this BusRd. Since CPU1 has X in Modified state, it
intervenes:
• CPU1 writes its modified data for X back to main memory.
• CPU1 changes its state from Modified (M) to Shared (S).
– CPU2 then loads the now-updated X from main memory into its cache and
sets its state to Shared (S).
– Result: Both CPU1 and CPU2 now have identical, clean copies of X, and
both are in the Shared state.
The MESI protocol effectively manages cache consistency by defining clear states and
transitions, ensuring that all processors always work with the most up-to-date data. This
balance between performance (avoiding main memory access for Exclusive writes) and
correctness (invalidating stale copies) makes it a cornerstone of modern CPU design.