Computer Architecture: Instruction Sets, Pipelining and Memory Systems

I kept these computer architecture notes to move beyond the basic computer model of the organization course and to evaluate ISA design, pipelining, the memory hierarchy, arithmetic, I/O and parallel execution as parts of the same system. The original notes were written during the 2013-2015 study period. Examples involving later processor families and standards were added during subsequent technical revisions rather than being presented as part of the original version.

Unit 1: CISC and RISC Central Processing Units

Instruction set architecture

Computer architecture begins with the instruction set architecture (ISA), the contract visible to software. An ISA defines the operations a processor can execute, the programmer-visible registers, data types, addressing modes, instruction encodings, privilege levels, exception behavior and usually the architectural memory model.

The ISA should be distinguished from the microarchitecture. Two processors can implement the same ISA while using different pipeline depths, cache organizations, execution units, branch predictors and scheduling mechanisms. Software observes the architectural contract; performance depends heavily on how that contract is implemented.

CISC and RISC

CISC (Complex Instruction Set Computer) historically refers to architectures with relatively rich instruction sets, numerous addressing modes and, often, variable-length instructions. RISC (Reduced Instruction Set Computer) developed around regular instruction formats, load/store execution, large register files and an organization that is convenient for pipelining and compiler scheduling.

The classical distinction is useful but should not be treated as an absolute classification of modern processors. Contemporary x86-64 cores decode complex instructions into internal micro-operations and execute them in wide out-of-order engines. RISC-derived ISAs such as AArch64 and RISC-V may include substantial vector, cryptographic, atomic and virtualization extensions.

Typical historical tendencies are:

| Property | CISC tendency | RISC tendency | | --- | --- | --- | | Instruction set | Large and heterogeneous | More regular | | Instruction length | Often variable | Often fixed or regular | | Memory operands | Some instructions operate directly on memory | Arithmetic normally uses registers; memory accessed by load/store | | Addressing modes | Numerous | Fewer and more regular | | Decode | Potentially complex | Usually simpler | | Pipeline design | Historically more difficult | Regular formats simplify pipeline implementation |

CISC characteristics

Classical CISC designs emphasize code density and expressive instructions. Typical characteristics include many instruction forms, several addressing modes, variable-length encodings, operations that can combine address calculation with arithmetic, and strong backward compatibility. These features can reduce static instruction count but make fetch and decode more complicated.

Modern x86-64 demonstrates why the ISA/microarchitecture distinction matters. The architectural interface remains complex, while implementations internally use techniques commonly associated with high-performance RISC cores: micro-operations, register renaming, speculative execution, multiple execution ports and out-of-order scheduling.

RISC characteristics

A classical RISC design favors regularity:

• load/store memory access,
• register-to-register arithmetic,
• a relatively large general-purpose register set,
• regular instruction formats,
• a limited set of fundamental addressing modes,
• compiler-friendly instruction semantics,
• efficient pipelining.

A simplified load/store sequence is:

LOAD  R1, [A]
LOAD  R2, [B]
ADD   R3, R1, R2
STORE [C], R3

The arithmetic operation does not directly modify a memory operand. Loads and stores form the explicit memory interface.

Does one instruction take one clock cycle?

The statement that a RISC instruction executes in one clock cycle is an oversimplification. A single instruction can have a latency of several cycles, especially for cache misses, multiplication, division or floating-point operations. In an ideal pipeline, however, once the pipeline is full, one instruction may complete every cycle. Superscalar machines may retire more than one instruction per cycle under favorable conditions.

The distinction is therefore between:

• latency, the time required for one operation to complete,
• throughput, the number of operations completed per unit time.

PowerPC and Power ISA

PowerPC originated as a RISC architecture developed by IBM, Motorola and Apple. Its later evolution continues under Power ISA. It remains a RISC-derived architecture; describing PowerPC as a hybrid CISC/RISC ISA is misleading. Later Power ISA versions include extensive privileged, vector and numerical facilities, but the architectural lineage remains RISC.

Register windows

Register windows are an important historical optimization, most closely associated with SPARC. Rather than saving a large set of registers to memory on every procedure call, the processor changes the visible register window. A subset of the caller's output registers overlaps with the callee's input registers.

Caller
[ global | local | out ]
                   ||||||
Callee
            [ in | local | out ]

This can make procedure calls and parameter transfer efficient. Register windows are not a required RISC property. AArch64 and RISC-V, for example, rely on ABI-defined register and stack conventions instead.

If G is the number of global registers, L the local registers, and C the registers shared with adjacent windows, the visible window can be modeled as:

Window size = G + L + 2C

A finite implementation can overflow after deep call nesting, at which point register state must be spilled to memory.

Instruction classes

Processor instructions can be grouped broadly into:

1. data-transfer instructions,
2. data-processing instructions,
3. program-control instructions.

Data transfer includes load, store, move, stack operations and address generation. Data processing includes integer arithmetic, logic, shifts, comparisons, bit operations, floating-point operations and vector operations. Program control includes conditional and unconditional branches, procedure calls, returns, traps and privileged transitions.

Addressing modes

An addressing mode defines how an instruction locates an operand. Common forms include:

• immediate,
• register,
• direct or absolute memory,
• register indirect,
• base plus displacement,
• indexed,
• base plus index,
• PC-relative.

The effective address can be represented generally as:

EA = base + index * scale + displacement

Not every ISA implements every combination. Rich CISC encodings often express complex address calculations directly, while RISC instruction formats tend to keep them regular.

CISC and RISC programming differences

At source-language level, modern compilers hide much of the architectural distinction. The important differences emerge in generated code, calling conventions, code density, register pressure, vectorization and memory-access patterns. A smaller instruction count does not automatically imply a faster program; instruction latency, throughput, cache behavior, dependencies and available execution resources matter.

The basic performance equation

A useful first-order CPU performance model is:

CPU time = Instruction count * CPI * Clock cycle time

or equivalently:

CPU time = Instruction count * CPI / Clock frequency

Reducing instruction count can increase CPI, increasing clock frequency can require a deeper pipeline, and a deeper pipeline can increase branch-misprediction cost. Architecture is therefore a system of trade-offs rather than a single-variable optimization problem.

Program control and status flags

Architectural status registers commonly encode arithmetic conditions and control state. Typical condition flags include:

• zero,
• negative/sign,
• carry,
• overflow.

Carry and overflow must not be confused. Carry is primarily meaningful for unsigned arithmetic, whereas signed overflow indicates that the mathematical result is outside the representable signed range.

For an n-bit unsigned addition:

0 <= result <= 2^n - 1

For an n-bit two's-complement signed value:

-2^(n-1) <= result <= 2^(n-1) - 1

Procedure calls, stacks and ABI

A procedure call requires more than changing the program counter. The implementation must preserve enough state to return correctly and must agree on how arguments, return values and registers are handled. Typical mechanisms involve:

• a return-address register or stack entry,
• stack-frame construction,
• caller-saved and callee-saved registers,
• argument registers,
• alignment rules,
• exception-unwinding conventions.

These rules belong to an ABI (Application Binary Interface). An ISA states what the processor can do; an ABI establishes how separately compiled software components use those facilities compatibly.

Interrupts and exceptions

An interrupt changes control flow because an event requires processor attention. Hardware interrupts are commonly asynchronous with respect to the current instruction stream. Exceptions are usually synchronous consequences of instruction execution, such as an invalid opcode, page fault or protection violation. Terminology varies by architecture, so the architectural manual is authoritative.

An interrupt or exception entry generally involves:

1. identifying the event,
2. preserving architectural state,
3. changing privilege or execution context if necessary,
4. obtaining a handler address from a vector or equivalent mechanism,
5. transferring control to the handler,
6. restoring state on return.

The key difference from an ordinary subroutine is that an interrupt can occur outside normal program control and may require privilege changes and additional state management.

Processor state and privilege modes

The complete architectural state includes more than general-purpose registers. It can include the program counter, status registers, control registers, vector registers, floating-point state and memory-management state. Operating systems depend on privilege separation so that user applications cannot directly execute operations that would compromise isolation. The exact privilege model differs between ISAs, but the distinction between restricted application execution and privileged system control is fundamental.

Unit 2: Sequential and Vector Processors

Parallel processing and Flynn's classification

Performance can be increased by exploiting different kinds of parallelism. Flynn's taxonomy classifies computers according to the number of instruction and data streams:

• SISD: Single Instruction, Single Data,
• SIMD: Single Instruction, Multiple Data,
• MISD: Multiple Instruction, Single Data,
• MIMD: Multiple Instruction, Multiple Data.

The categories are conceptual. A modern system can contain several forms simultaneously: SIMD vector instructions within each core and MIMD execution across cores, for example.

Instruction-level parallelism

Instruction-level parallelism (ILP) exists when independent instructions can overlap in execution. Pipelining is the basic mechanism; superscalar issue, out-of-order scheduling and speculation extend it.

Consider:

R1 = R2 + R3
R4 = R5 - R6
R7 = R1 * R8

The first two operations are independent and may execute concurrently. The third depends on the first and cannot use R1 before the required value is available.

Pipeline

A simple instruction pipeline can be divided into stages such as:

IF -> ID -> EX -> MEM -> WB

where instruction fetch, decode, execution, memory access and write-back are overlapped for different instructions.

If there are k stages and each stage takes time t, the latency of a single instruction in the idealized pipeline is approximately:

Latency = k * t

After filling, the ideal throughput approaches one completed instruction per t rather than one instruction per k*t.

For n instructions in a balanced ideal k-stage pipeline:

T_pipeline = (k + n - 1) * t

Without pipelining:

T_nonpipeline = n * k * t

Actual machines lose some of the theoretical gain because stages are not perfectly balanced and hazards cause stalls or flushes.

Pipeline efficiency and clock period

An idealized efficiency measure is the useful stage occupancy divided by total available stage-time. As the number of instructions becomes large, pipeline utilization can approach its ideal level, but stage imbalance limits the clock period:

T_clock >= max(stage delay) + register overhead

A very deep pipeline may increase clock frequency but also increases register overhead and the cost of control-flow recovery.

Space-time diagrams

A space-time diagram places pipeline stages on one axis and time on the other. It makes overlapping execution, bubbles and hazards visible. It is useful for reasoning about when operands become available and whether forwarding can remove a stall.

Arithmetic pipelines and multiple functional units

Long arithmetic operations can themselves be pipelined. Floating-point addition, for example, can contain exponent comparison, alignment, significand arithmetic, normalization and rounding stages. High-performance processors also contain multiple functional units, such as integer ALUs, address-generation units, floating-point units and vector units. Independent operations can therefore execute simultaneously when dependencies and issue resources permit.

Pipeline hazards

A hazard is a condition that prevents the next operation from proceeding according to the ideal pipeline schedule.

Three traditional categories are:

• structural hazards, caused by competition for the same hardware resource,
• data hazards, caused by dependencies between instructions,
• control hazards, caused by uncertainty in control flow.

For a read-after-write dependency:

ADD R1, R2, R3
SUB R4, R1, R5

SUB requires the value produced by ADD.

Forwarding and stalls

Forwarding or bypassing sends a result directly from a producing stage to a consuming stage instead of waiting for architectural write-back. If the required value is still unavailable, the pipeline must insert a stall or bubble.

Load-use dependencies are a common example because a loaded value may become available later than a simple ALU result.

Control hazards and branch prediction

Conditional branches determine which instructions should be fetched next. Waiting until every branch resolves would waste substantial pipeline capacity. Branch prediction guesses the likely outcome and target so fetching can continue speculatively.

If the prediction is correct, useful work continues. If it is wrong, speculative instructions are discarded and the correct path must be fetched. The penalty generally grows with the amount of unresolved speculative work.

Historical techniques such as delayed branches and delayed loads exposed pipeline timing directly to software. Modern high-performance ISAs and implementations generally prefer hardware mechanisms that avoid making such timing a permanent software contract.

RISC and pipelining

Regular instruction sizes, explicit load/store semantics and simpler decode paths historically made RISC designs attractive for pipelining. The association is not exclusive: modern CISC implementations are deeply pipelined as well, often after translating architectural instructions into regular internal operations.

Out-of-order execution

An out-of-order processor can execute a younger instruction before an older one when dependencies allow it, while preserving the architectural behavior required by the ISA. A simplified design involves:

• instruction fetch and decode,
• register renaming,
• dispatch to scheduling structures,
• execution when operands become ready,
• retirement in architectural order.

This hides latency, especially when cache misses or long arithmetic operations block only part of the instruction window.

Register renaming

Register renaming removes false dependencies caused by reuse of architectural register names. It maps architectural registers onto a larger set of physical registers. True data dependencies remain, but write-after-read and write-after-write name conflicts can disappear.

Vector processing

Vector processors apply one instruction to multiple data elements. Instead of explicitly issuing a scalar instruction for every element, software can express operations on vectors:

C[i] = A[i] + B[i]

A vector architecture can perform many element operations through vector registers and pipelined functional units. This is well suited to numerical algorithms with regular data parallelism.

SIMD and vector architectures

SIMD describes the general concept of one instruction acting on multiple data values. Vector ISAs are one implementation of SIMD. Fixed-width SIMD uses registers of a particular width; scalable vector architectures may define execution in terms of an implementation-dependent vector length.

Important concepts include:

• vector length,
• element width,
• masks or predicates,
• strided and indexed memory access,
• reduction operations,
• chaining between functional units.

Vector length, masking and chaining

The vector length determines how many elements participate in an operation. A mask enables conditional element processing without scalar branches. Chaining allows one vector operation to begin consuming elements produced by another before the complete source vector has finished, reducing pipeline gaps when the implementation supports it.

Memory banking and interleaving

Vector execution can demand more memory bandwidth than a single memory bank provides. Interleaving consecutive addresses across independent banks permits several accesses to be serviced concurrently when their bank pattern does not conflict.

If successive elements map to different banks, effective bandwidth increases. Poor strides can repeatedly target the same bank and create conflicts.

Dot products and matrix multiplication

The dot product:

s = sum(a[i] * b[i])

contains parallel multiplications followed by a reduction. Matrix multiplication consists of many such structured multiply-accumulate operations and is therefore a natural target for SIMD, vector processors, GPUs and specialized matrix hardware. Performance is governed not only by arithmetic throughput but by data reuse and the memory hierarchy.

Array processors, GPUs and supercomputers

Array processors organize many processing elements for data-parallel work. GPUs evolved into massively parallel throughput processors with many execution lanes, hardware scheduling and a memory hierarchy designed for large numbers of concurrent threads. Their programming model differs from classical vector machines, but both exploit data parallelism.

A supercomputer is not defined by one specific architecture. Modern systems combine multicore CPUs, wide vectors, accelerators, high-bandwidth memory and high-speed interconnects. System-level performance therefore depends on communication, memory bandwidth, synchronization and workload decomposition as much as peak arithmetic rate.

Unit 3: Computer Arithmetic

Number representations

A processor stores finite bit patterns, so arithmetic is always performed within a representation. Understanding that representation is necessary for interpreting overflow, comparison and conversion behavior.

For an unsigned n-bit integer:

0 <= x <= 2^n - 1

For two's-complement signed integers:

-2^(n-1) <= x <= 2^(n-1) - 1

Sign-magnitude, one's complement and two's complement

Historical signed representations include sign-magnitude and one's complement. Both have positive and negative zero, which complicates arithmetic. Two's complement provides one representation for zero and allows addition and subtraction to share ordinary binary adder structures.

Negating a two's-complement value conceptually means inverting the bits and adding one. The most negative value has no positive counterpart in the same width, an edge case important in software and hardware arithmetic.

Sign extension

When a signed two's-complement value is widened, the high bits are filled with copies of the sign bit. Zero extension is appropriate for unsigned values. Using the wrong extension changes the numeric value.

Addition and signed overflow

Binary addition naturally produces a carry out of the most significant bit. For unsigned arithmetic, that carry is relevant to range overflow. Signed overflow occurs when two operands with the same sign produce a result with the opposite sign.

An equivalent two's-complement hardware test compares the carry into and out of the sign bit.

Subtraction

Subtraction can be implemented as addition of the two's complement:

a - b = a + (~b + 1)

This enables an arithmetic logic unit to reuse much of its addition hardware.

Multiplication

Binary multiplication is based on partial products. A straightforward unsigned implementation tests multiplier bits, conditionally adds shifted multiplicands and accumulates the result. Hardware multipliers accelerate the reduction of partial products using tree structures and pipelining.

Signed multiplication requires correct sign treatment and sufficient result width. Multiplying two n-bit values may require up to 2n result bits.

Booth's algorithm

Booth recoding reduces repeated additions for runs of ones in a two's-complement multiplier. A run such as:

00111100

can be represented by a difference of shifted powers of two rather than four separate partial additions. Modified Booth techniques are widely used as part of high-performance multiplication structures.

Division

Binary division resembles long division and can be implemented through repeated shift, subtract and restore decisions. Restoring division restores the partial remainder after an unsuccessful subtraction. Non-restoring division avoids an immediate restoration and compensates in a later iteration.

Division by zero must be handled architecturally; it is not a normal quotient-producing arithmetic case.

Fixed-point arithmetic

Fixed-point formats assign an implicit scaling factor to an integer representation. If F fractional bits are used, the represented value can be interpreted as:

value = integer / 2^F

Fixed-point arithmetic is attractive when deterministic cost, bounded precision and simple hardware are important. Scaling, saturation and overflow policy must be designed explicitly.

Floating-point arithmetic

Floating-point represents values approximately as a sign, significand and exponent. IEEE 754 binary formats define encodings, rounding modes, exceptional values and arithmetic behavior.

For a normalized binary floating-point number:

value = (-1)^sign * significand * 2^exponent

IEEE 754 binary32 and binary64

The widely used formats are:

| Format | Sign | Exponent | Fraction | | --- | ---: | ---: | ---: | | binary32 | 1 | 8 | 23 | | binary64 | 1 | 11 | 52 |

Normalized values use an implicit leading significand bit. Subnormal values allow representation close to zero with reduced precision.

Special encodings represent:

• positive and negative infinity,
• quiet or signaling NaNs depending on encoding and operation,
• positive and negative zero,
• subnormal values.

Floating-point addition

Addition generally requires:

1. comparing exponents,
2. aligning significands,
3. adding or subtracting significands,
4. normalizing,
5. rounding,
6. checking exceptional cases.

The alignment step explains why adding a very small value to a very large one can have no representable effect.

Floating-point multiplication and division

Multiplication combines significand multiplication with exponent addition and normalization. Division combines significand division with exponent subtraction. Both operations require rounding and handling of zero, infinity and NaN cases.

Rounding and fused multiply-add

IEEE 754 defines several rounding directions; round-to-nearest with ties to even is commonly the default. Fused multiply-add (FMA) computes:

a * b + c

with a single final rounding rather than rounding the product and then the sum separately. This can improve both precision and performance in numerical kernels.

Unit 4: Input/Output Organization

Purpose of an I/O system

The processor and memory are not sufficient for a usable computer. I/O mechanisms connect the computing core to storage devices, networks, displays, sensors and other peripherals while coping with large differences in device speed and protocol.

An I/O subsystem must address:

• device selection,
• control and status transfer,
• data movement,
• buffering,
• synchronization,
• error reporting,
• protection.

Devices and interfaces

Devices differ significantly in bandwidth, latency, transfer granularity and control model. A keyboard produces small event-driven transfers; an NVMe SSD can sustain large queues of block operations; a network interface may use DMA rings and interrupts; a display adapter can continuously consume memory bandwidth.

The I/O interface hides device-specific electrical and protocol details behind registers, queues or command descriptors understood by software.

Character encoding

Text-oriented I/O depends on an encoding such as ASCII or Unicode encodings. Character encoding belongs to the interpretation of data, not to the electrical transfer mechanism itself. Mixing these levels leads to incorrect assumptions about byte count and character count.

System buses and I/O commands

A bus or interconnect carries addresses, data and control information between components. Traditional bus diagrams are conceptually useful even though modern systems often use packetized point-to-point fabrics.

I/O commands commonly express operations such as:

• read data,
• write data,
• read status,
• write control information.

Isolated and memory-mapped I/O

In isolated I/O, a processor uses a separate I/O address space and dedicated instructions. In memory-mapped I/O (MMIO), device registers occupy addresses in the processor's address space and are accessed through load/store-like operations.

MMIO simplifies the instruction model but requires correct memory attributes and ordering. Device registers cannot generally be treated like ordinary cacheable RAM.

Strobe and handshake control

A strobe protocol signals when data should be sampled but may not explicitly acknowledge receipt. A handshake adds request/acknowledge coordination, allowing components with different timing characteristics to exchange data reliably.

Synchronous and asynchronous communication

Synchronous communication uses a shared or recovered timing relationship. Asynchronous serial communication frames data using conventions such as start and stop bits rather than a continuously shared clock. Serial communication uses fewer physical lines and is dominant at high external link speeds; parallel communication remains useful within chips and local buses but is harder to scale over distance because of skew and signal-integrity constraints.

FIFO buffering

A FIFO (First In, First Out) buffer decouples producer and consumer timing. It can absorb bursts, cross clock or scheduling boundaries and reduce the need for strict cycle-by-cycle synchronization. Buffer depth must be selected with throughput, burst size and acceptable latency in mind.

Programmed I/O

With programmed I/O, the CPU explicitly checks device state and transfers data through device registers. It is simple and appropriate for low-rate or infrequent control operations, but continuous polling wastes processor time for high-volume transfers.

Interrupt-driven I/O

Interrupt-driven I/O allows the CPU to perform other work and receive notification when a device requires service. Interrupts reduce unnecessary polling but introduce handler and context-switch overhead. High-rate devices therefore often combine interrupts with batching and DMA.

When polling is useful

Polling is not inherently inferior. It can be effective when event rates are extremely high, when very low latency is required, or when the expected wait is shorter than the cost of sleeping and waking. High-performance networking systems sometimes deliberately poll queues for this reason.

Direct memory access

DMA (Direct Memory Access) lets a device or DMA engine transfer data between the device and memory without the CPU copying each word. The CPU usually prepares descriptors, buffer addresses and transfer lengths, then the DMA engine performs the data movement.

DMA addresses may be physical or may pass through an IOMMU translation layer. The distinction matters for isolation, virtualization and scatter/gather mappings.

Cache coherence and DMA

If the CPU cache and a DMA device can observe different copies of memory, software or hardware must establish coherence. Coherent platforms may handle this automatically for supported mappings. Non-coherent systems require explicit cache maintenance. The programmer must follow the platform's DMA API rather than assume cache behavior.

DMA controllers and bus mastering

A DMA controller can arbitrate for memory transfers on behalf of devices. Modern PCIe devices often act as bus masters, issuing memory transactions directly after software configures queues and mappings. This increases throughput but makes protection through IOMMU and privilege boundaries important.

Interrupt priority

When several devices request service, the system needs a priority mechanism. Historical approaches include daisy-chain priority and parallel priority encoders. Modern systems use programmable interrupt controllers and message-signaled mechanisms.

MSI and MSI-X

PCIe devices can use Message Signaled Interrupts (MSI) or MSI-X, in which the device generates an interrupt by issuing a memory write with a defined message format rather than toggling a dedicated interrupt pin. MSI-X supports more independent vectors and is particularly useful for multiqueue devices distributed across CPU cores.

I/O processors

An I/O processor or intelligent controller can execute substantial parts of a device protocol independently. The general idea survives in storage controllers, network processors, GPUs and other accelerators: offload specialized work while coordinating through shared memory and queues.

Unit 5: Main Memory Organization

Memory hierarchy

No single memory technology simultaneously provides minimum latency, maximum capacity, non-volatility and minimum cost. Computer systems therefore use a hierarchy:

Registers
L1 cache
L2 cache
L3 / last-level cache
Main memory
Persistent storage
Remote or archival storage

Upper levels are smaller and faster. Lower levels provide greater capacity at higher access cost.

Locality

The hierarchy works because programs exhibit temporal locality and spatial locality. Temporal locality means recently used data is likely to be used again. Spatial locality means nearby addresses are likely to be accessed. Cache lines exploit spatial locality by transferring blocks rather than isolated bytes.

SRAM and DRAM

SRAM stores state in bistable circuits and does not require periodic refresh while powered. It is fast but area-expensive, making it suitable for caches and small on-chip memories.

DRAM stores information as charge and requires refresh. Its higher density makes it appropriate for main memory despite greater latency and more complicated timing.

ROM, firmware and non-volatile memory

Read-only and non-volatile memories preserve data without normal power. Firmware can reside in flash or other non-volatile technology and initializes hardware before transferring control to a boot loader or operating system. Contemporary systems use several non-volatile technologies with different endurance, latency and update characteristics.

HDD, SSD and tape

Persistent storage forms another hierarchy. Magnetic disks offer large capacity with mechanical seek latency. SSDs remove mechanical movement and provide much higher random-access performance but require flash-translation, wear management and garbage collection. Tape remains relevant for archival capacity and sequential transfer economics.

Content-addressable memory

CAM (Content-Addressable Memory) searches by content rather than by address. Associative lookup is useful in structures such as TLBs and networking tables, although fully associative hardware is area- and power-intensive.

Cache organization

A cache stores copies of memory blocks called cache lines. An access that finds the required line is a hit; otherwise it is a miss.

A basic performance expression is:

AMAT = Hit time + Miss rate * Miss penalty

This simplified equation is useful for reasoning about why a small reduction in miss rate can matter when the miss penalty is large.

Mapping organizations

Three classical cache mappings are:

• direct mapped,
• fully associative,
• set associative.

For an address divided into tag, index and offset, the offset selects a byte within a line, the index selects the set, and the tag distinguishes which memory block occupies that set.

Direct mapping is simple but can suffer conflict misses. Full associativity minimizes placement restrictions but requires expensive comparison. Set associativity is the common compromise.

Replacement policies

When all ways in a set are occupied, a replacement policy chooses a victim. Common concepts include LRU or approximations of it, FIFO and random replacement. Exact LRU can become expensive at high associativity, so real processors often use approximations.

Write policies

With write-through, updates are propagated to the next memory level immediately. With write-back, a modified line is marked dirty and written when evicted. Write-back reduces lower-level traffic but requires dirty-state management.

On a write miss, policies include write allocate, which brings the line into the cache, and no-write allocate, which writes to the lower level without allocating the line. Policy combinations depend on workload and hierarchy design.

Multilevel caches

Modern processors use multiple cache levels. L1 prioritizes latency, while lower levels are larger and slower. Inclusive, exclusive and non-inclusive organizations describe relationships between levels. Shared last-level caches introduce additional questions of contention, partitioning and coherence.

Virtual memory

Virtual memory separates the address used by a process from the physical address of storage. Pages are mapped through page tables, enabling protection, relocation, sparse address spaces and controlled sharing.

A virtual address can be viewed conceptually as:

virtual page number | page offset

Translation maps the virtual page number to a physical frame while preserving the offset.

Multilevel page tables

A flat page table for a large virtual address space would consume substantial memory. Multilevel page tables allocate lower-level structures only for populated portions of the address space. The exact number of levels and page sizes are architectural choices.

TLB

A Translation Lookaside Buffer (TLB) caches recent virtual-to-physical translations. A TLB hit avoids a page-table walk. A TLB miss may require several memory references before the original data access can proceed, so translation behavior is an important component of memory performance.

Page faults

A page fault occurs when translation or access conditions require operating-system intervention. A fault can indicate that a page is not resident, that a mapping must be created, or that an access violates protection. Not every page fault implies disk I/O.

Page replacement

When memory pressure requires eviction, the operating system chooses pages according to a replacement strategy. FIFO is easy to implement but can perform poorly. LRU expresses temporal locality but exact implementation is expensive; operating systems generally use approximations informed by hardware reference information and workload behavior.

MMU and protection

The Memory Management Unit (MMU) performs address translation and enforces page permissions. Typical permissions distinguish read, write and execute access and user versus privileged execution. Memory protection is therefore not an optional performance feature; it is central to process isolation and system security.

Unit 6: Multiprocessor Systems

Why multiple processors?

Increasing clock frequency alone is constrained by power, thermal behavior and memory latency. Multiple cores and processors provide another path to performance, but only when workloads contain exploitable parallelism.

A multiprocessor contains multiple processing elements cooperating within a system. A multicomputer or distributed system places stronger emphasis on separate memories and message-based communication. Modern platforms often combine shared-memory nodes with distributed communication between nodes.

Shared and distributed memory

In a shared-memory system, processors access a common address space. In a distributed-memory system, each node owns local memory and communicates explicitly. Hybrid systems use both models.

UMA and NUMA

UMA (Uniform Memory Access) presents approximately uniform memory-access cost. NUMA (Non-Uniform Memory Access) provides faster access to local memory than to memory attached to another node or socket.

NUMA affects software design. A thread that repeatedly accesses remote pages may achieve substantially lower bandwidth and higher latency than one operating on local memory. Thread placement and first-touch allocation can therefore influence performance.

Interconnection structures

Processors, caches, memory controllers and I/O devices require an interconnect. Classical structures include:

• common buses,
• multiport memories,
• crossbars,
• multistage networks,
• meshes and other topologies,
• hypercube-style networks.

On-chip systems increasingly use scalable networks-on-chip rather than a single shared bus. The appropriate topology depends on endpoint count, bandwidth, latency, routing complexity, area and power.

Bus arbitration

When several masters request the same shared resource, arbitration chooses who proceeds. Policies can be fixed-priority, round-robin or dynamically weighted. Fixed priority can starve lower-priority requesters; round-robin improves fairness but may not express urgency. Real systems often combine quality-of-service policies with topology-specific arbitration.

Interprocessor communication and synchronization

Shared-memory processors communicate by reading and writing memory, but correct coordination requires synchronization. Atomic operations provide indivisible read-modify-write behavior. They are used to implement locks, semaphores, reference counters and lock-free algorithms.

A critical section must ensure that shared invariants are not concurrently corrupted. A simple spin lock may repeatedly test an atomic state until ownership becomes available. Spinning is useful only when waits are expected to be short; longer waits generally require scheduler-assisted blocking.

Test-and-set and atomic primitives

Historical examples use test-and-set. Modern ISAs provide richer primitives such as compare-and-swap or load-reserved/store-conditional. The exact primitive is less important than its ordering semantics and the algorithm built on top of it.

Cache coherence

Private CPU caches create a fundamental problem: several cores may hold copies of the same memory line. Cache coherence keeps these copies consistent according to a protocol.

A coherent system must manage cases such as:

• a core reading a line another core has modified,
• ownership transfer before a write,
• invalidation of stale copies,
• write-back of modified data.

Snooping and directory protocols

In a snooping protocol, caches observe coherence transactions on a shared interconnect. This is practical for relatively small systems but becomes difficult to scale with many participants.

A directory protocol records which nodes hold copies and sends targeted coherence messages. Directory designs reduce broadcast traffic and are better suited to larger systems, at the cost of directory storage and protocol complexity.

MESI and MOESI

The MESI family names common cache-line states:

• Modified,
• Exclusive,
• Shared,
• Invalid.

MOESI adds an Owned state, allowing one cache to retain responsibility for a modified value while other caches hold shared copies. Real processors may use more elaborate internal states, but these models remain useful for understanding coherence.

Coherence versus consistency

Coherence and memory consistency are different. Coherence concerns the ordering and visibility of operations to the same memory location. A memory-consistency model defines the permitted ordering relationships among operations to different locations as observed by multiple processors.

A system can be cache-coherent while still implementing a relaxed memory model. Concurrent software therefore requires language- and ISA-level synchronization rather than relying on intuitive source-code order.

Memory ordering

Compilers and processors may reorder operations when doing so preserves single-thread semantics. Synchronization operations establish ordering constraints required by concurrent algorithms. Modern ISAs differ in the strength of their default ordering and the fences or acquire/release operations they provide.

Later revisions of these notes include examples from RISC-V's formal memory-model work. These examples are technical updates to the original architecture notes, not claims about the 2013-2015 version.

DMA coherence in multiprocessor systems

I/O devices can also participate in the memory system through DMA. Whether device traffic is coherent with CPU caches depends on the platform. Coherent accelerators simplify shared-memory programming, while non-coherent devices require explicit synchronization and cache maintenance. IOMMU translation adds another layer of address isolation and remapping.

Overall Framework

The subjects in computer architecture are tightly connected rather than independent chapters. ISA choices determine the software-visible contract. Microarchitecture tries to execute that contract efficiently through pipelining, speculation, parallel functional units and caches. The memory hierarchy reduces average access time but introduces locality, translation and coherence concerns. I/O moves data between the processor-memory system and external devices, frequently through DMA. Multiprocessor systems add another dimension: synchronization and memory ordering become part of correctness, not merely performance.

A useful way to read the architecture as a whole is therefore:

ISA
  -> instruction execution
      -> pipelining and ILP
          -> arithmetic and vector units
              -> cache and virtual memory
                  -> I/O and DMA
                      -> multiprocessor coherence and synchronization

Performance must be evaluated across this chain. A wider execution core cannot compensate for a memory-bound workload indefinitely; a large cache does not remove synchronization costs; more cores do not improve a sequential dependency chain. The architecture is effective only when computation, data movement and parallelism are balanced for the workload.