Harvard, Register vs Accumulator, Control Units, RISC/CISC, Multiprocessing & DSP
Open in the Padhaiko app6.1 Harvard architecture
In computer organization, computer architectures are classified fundamentally by how memory and data paths are arranged between the Central Processing Unit (CPU) and storage. The two foundational architectural models are the Von Neumann (Princeton) Architecture and the Harvard Architecture.
Von Neumann Architecture and the Von Neumann Bottleneck
Developed by John von Neumann in 1945, this model uses a single unified physical memory space that stores both program instructions and application data.
- Shared Bus Structure: A single set of address, data, and control buses connects the CPU to memory.
- Sequential Instruction-Data Fetch: Because instructions and data share the same physical bus, the CPU cannot fetch an instruction and read or write data memory simultaneously. Every memory access must occur sequentially in separate machine cycles.
- The Von Neumann Bottleneck: As CPU clock speeds advanced into gigahertz ranges while memory access speeds improved much more slowly, the shared memory bus became the primary limiting factor constraining overall computer throughput. The processor spends a large fraction of execution cycles stalled waiting for memory operations to complete over the single shared bus.
Harvard Architecture
Named after the Harvard Mark I relay-based computer (designed by Howard Aiken in 1944), this architecture provides physically separate memory spaces and independent bus systems for program instructions and operational data:
- Instruction Memory (Program Memory): Accessed via a dedicated Instruction Address Bus and Instruction Data Bus.
- Data Memory: Accessed via an independent Data Address Bus and Data Data Bus.
VON NEUMANN ARCHITECTURE HARVARD ARCHITECTURE
+-----------------------+ +-----------------------+
| CPU | | CPU |
+-----------+-----------+ +-----+-----------+-----+
| | |
Shared Bus Instruction Bus Data Bus
| | |
+-----------v-----------+ +-----v-----+ +---v-----+
| Unified Memory | |Program Mem| |Data Mem |
| (Instructions & Data) | +-----------+ +---------+
+-----------------------+Advantages of Harvard Architecture
- Simultaneous Instruction and Data Access: The CPU can fetch the next instruction word from instruction memory at the exact same clock edge that it is reading or writing an operand in data memory.
- Different Word Widths and Technologies: Instruction memory and data memory do not need to share the same bit width, access timings, or storage technology. For instance, in many microcontrollers (e.g., Microchip PIC), instruction words are 14 or 16 bits wide while data words are 8 bits wide.
- Higher Throughput: Eliminates memory bus contention, enabling consistent single-cycle instruction execution in pipelined processors.
Modified Harvard Architecture in Modern Processors
Pure Harvard architecture is widely used in embedded microcontrollers (AVR, PIC) and Digital Signal Processors (DSPs). However, modern general-purpose microprocessors (x86, ARM) implement a Modified Harvard Architecture:
- At the execution core level, the processor uses separate Level 1 Instruction Cache (L1 I-cache) and Level 1 Data Cache (L1 D-cache) with independent internal buses, providing all the performance benefits of Harvard architecture.
- Beyond the L1 cache, the hierarchy unifies into shared L2/L3 caches and a single main system memory (DRAM), preserving the programming flexibility and unified address space of the Von Neumann model.
| Aspect | Von Neumann Architecture | Harvard Architecture |
|---|---|---|
| Memory Space | Single unified memory storing both instructions and data | Physically separate memories for instructions and data |
| Bus System | Single shared bus for instructions and data transfers | Dedicated, separate buses for instruction and data paths |
| Memory Access | Sequential; cannot fetch instruction and data simultaneously | Simultaneous; instruction fetch and data transfer overlap |
| Throughput & Speed | Slower; limited by the Von Neumann bottleneck | Faster; higher instruction execution bandwidth |
| Memory Bit Width | Instruction and data words must share the same physical bus width | Instruction and data word lengths can differ (e.g., 14-bit code, 8-bit data) |
| Hardware Complexity | Simpler controller circuitry and lower pin/trace count | Higher pin count and duplicated internal address/data buses |
| Representative Systems | General-purpose personal computers, early microprocessors (8085, 8086) | Digital Signal Processors (TI TMS320), microcontrollers (PIC, AVR) |
6.2 Accumulator based and register based architecture
Processors are classified according to the internal organization of their CPU storage operands and where arithmetic and logical instructions obtain their inputs.
There are four classical instruction set architectures:
- Stack-Based Architecture (Zero-Address)
- Accumulator-Based Architecture (One-Address)
- Register-Memory Architecture (Two-Address)
- Register-Register / Load-Store Architecture (Three-Address)
1. Stack-Based Architecture (Zero-Address)
- Principle: Operands are implicitly retrieved from the top of an internal hardware stack, and the result is pushed back onto the stack.
- Instruction Format: Arithmetic instructions require zero explicit operand addresses (e.g.,
ADD,MUL). Explicit addresses are used only forPUSH <mem>andPOP <mem>. - Advantages: Very short, compact instruction words; high code density; ideal for simple expression parsers and virtual machines (e.g., Java Virtual Machine - JVM bytecode, Pascal p-code).
- Disadvantage: The top of the stack becomes a performance bottleneck; random access to intermediate variables is difficult.
2. Accumulator-Based Architecture (One-Address)
- Principle: One operand is implicitly assumed to reside in a dedicated central register called the Accumulator (A).
- Instruction Format: Instructions specify exactly one explicit memory or register operand address (e.g.,
ADD B,ADD M,LDA 2050H). The accumulator supplies the first operand, and the ALU writes the computation result back into the accumulator. - Example: Intel 8085, MOS 6502.
- Advantages: Compact instruction encoding (only one memory address per instruction); simple internal datapath.
- Disadvantages: High memory traffic; the accumulator is a severe bottleneck because every calculation must overwrite it, requiring frequent temporary saves to memory.
3. General-Purpose Register (GPR) Architectures
Modern processors utilize a collection of multiple General-Purpose Registers (GPRs) instead of a single accumulator. GPR architectures are divided into two categories:
Register-Memory Architecture (Two-Address)
- Principle: Instructions can specify two operands, where one operand may be a memory location and the other a CPU register (e.g.,
ADD AX, [BX],MOV BX, [1000H]). - Example: Intel 8086, x86 architecture, Motorola 68000.
- Advantages: Programs can perform arithmetic directly on memory variables without requiring explicit load instructions; compact code length.
- Disadvantages: Instructions have variable execution lengths and variable formats, complicating pipeline design.
Register-Register / Load-Store Architecture (Three-Address)
- Principle: Arithmetic and logic operations are performed strictly between CPU registers. Memory is accessed exclusively through dedicated
LOADandSTOREinstructions. - Instruction Format: Instructions specify three register operands: destination register and two source registers (e.g.,
ADD R1, R2, R3performsR1 = R2 + R3). - Example: MIPS, ARM, RISC-V, SPARC.
- Advantages: Uniform, fixed-length instruction encoding; simple, predictable single-cycle execution; ideal for deep hardware pipelining.
- Disadvantage: Higher code expansion; requires more instructions to accomplish a task because memory variables must first be loaded into registers.
| Feature | Stack Architecture | Accumulator Architecture | Register-Memory (CISC) | Register-Register (RISC) |
|---|---|---|---|---|
| Address Fields per ALU Instruction | 0 addresses (implicit TOS) | 1 address (implicit Accumulator) | 2 addresses (one can be memory) | 3 addresses (all registers) |
| Operand Location | Top of Stack | Accumulator & Memory/Reg | Register & Memory | Registers only |
| Memory Access by ALU | None (only PUSH/POP) | One memory operand allowed | Direct in ALU instructions | None (only LOAD/STORE) |
| Code Density | Very High | High | Medium | Low (more instructions) |
| Pipeline Friendliness | Low | Low | Moderate | Excellent (ideal for pipeline) |
| Typical Example | JVM, Burroughs B5500 | Intel 8085, 6502 | Intel 8086, x86 | MIPS, ARM, RISC-V |
6.3 Hardwired and microprogrammed control unit
The Control Unit (CU) is the supervisory component of a microprocessor that directs the flow of data through the processor datapath by generating timing signals and control pulses (e.g., register load enables, ALU function selects, bus direction enables, memory read/write strobes).
Control units are implemented using two radically different design methodologies:
- Hardwired Control Unit
- Microprogrammed Control Unit
1. Hardwired Control Unit
In a hardwired control unit, the control logic is realized directly as fixed, physical combinational hardware circuits (using logic gates, decoders, multiplexers, and sequence counters) or Programmable Logic Arrays (PLAs).
- Principle of Operation:
- The instruction opcode is loaded into the Instruction Register (IR) and decoded by an Opcode Decoder.
- A step/sequence counter generates a continuous sequence of timing pulses (T1, T2, T3, ...).
- Combinational logic gates evaluate the decoded opcode, current timing step, and processor status flags simultaneously to generate the required control output signals.
- Advantages:
- Maximum Speed: Because signals propagate purely through semiconductor logic gates without memory lookups, hardwired control units achieve the fastest possible switching speeds and clock frequencies.
- Efficient for simple, fixed-length RISC architectures.
- Disadvantages:
- Inflexibility: The architecture is permanently frozen in silicon. Correcting design flaws or adding new instructions requires physical redesign and re-fabrication of the integrated circuit.
- Complex and costly to design for large, variable-length CISC instruction sets.
2. Microprogrammed Control Unit
Pioneered by Maurice Wilkes in 1951, microprogramming replaces hardwired logic gates with software-like control programs stored in a dedicated high-speed internal memory called the Control Store (or Micro-ROM).
- Principle of Operation:
- Every machine instruction opcode acts as an address pointer that vectors to a routine in the Control Store.
- Each word in the Control Store is called a Microinstruction, and the complete sequence of microinstructions that implements a machine instruction is called a Microprogram.
- A microinstruction contains two main fields:
- Control Field: Emits individual micro-operation control bits that drive ALU and datapath gates.
- Next-Address Field: Determines the address of the next microinstruction to fetch (using a microprogram counter or branch logic).
MICROPROGRAMMED CONTROL UNIT BLOCK DIAGRAM
+--------------------------------------+
Opcode =====>| Microinstruction Address Generator |
| (Mapping Logic / Multiplexer) |
+------------------+-------------------+
|
v
+--------------------------------------+
| Control Address Register (CAR) |
+------------------+-------------------+
|
v
+--------------------------------------+
| Control Store Memory (Micro-ROM) |
+------------------+-------------------+
|
v
+--------------------------------------+
| Control Buffer Register (CBR) |
+---------+------------------+---------+
| |
v v
Control Signals Next Address Field
(To Datapath) (Feedback to Address Gen)Horizontal versus Vertical Microprogramming
Microinstructions are formatted in two distinct arrangements based on control bit encoding:
| Aspect | Horizontal Microprogramming | Vertical Microprogramming |
|---|---|---|
| Bit Representation | Unencoded / Direct; each bit in the microinstruction directly drives one hardware control line | Highly encoded; control signals are grouped and encoded into binary fields |
| Word Width | Very wide; typically 48 to 128+ bits per microinstruction | Narrow; typically 16 to 32 bits per microinstruction |
| Decoder Requirements | Zero or minimal decoding logic required | Requires decoders (e.g., 3-to-8 decoder for 8 ALU functions) |
| Execution Speed | Extremely fast; control signals emerge immediately upon clock edge | Slower; incurs propagation delay through decoding logic |
| Parallelism | High concurrency; multiple independent datapath operations trigger in one cycle | Limited concurrency; mutually exclusive operations per field |
| Control Store Size | Requires larger memory capacity due to wide word width | Requires smaller, more economical control store memory |
| Parameter | Hardwired Control Unit | Microprogrammed Control Unit |
|---|---|---|
| Implementation | Fixed combinational logic gates, decoders, PLAs | Micro-ROM (Control Store) holding microprograms |
| Operating Speed | Extremely fast (limited only by gate propagation delay) | Slower (limited by Control Store memory access time) |
| Design Flexibility | Very rigid; modifications require chip re-masking | Highly flexible; instructions modified by updating ROM microcode |
| Instruction Set Support | Ideal for simple, uniform RISC instruction sets | Ideal for complex, variable-length CISC instruction sets |
| Chip Silicon Area | Small for simple sets; exponentially large for complex sets | Compact and modular even for complex instruction sets |
| Cost & Prototyping | High initial design and debugging cost | Low development cost; straightforward emulation and testing |
| Representative CPUs | RISC processors (MIPS, ARM, RISC-V), Intel 8085 | CISC processors (Intel 8086, VAX-11/780, IBM System/360) |
6.4 RISC and CISC
The two dominant philosophies in microprocessor instruction set design are CISC (Complex Instruction Set Computer) and RISC (Reduced Instruction Set Computer).
CISC (Complex Instruction Set Computer)
The CISC philosophy emerged in the 1960s and 1970s when computer memory was scarce and expensive, and compilers were primitive.
- Design Philosophy: Provide rich, high-level, multi-cycle instructions so that high-level language statements (e.g., string copies, complex mathematical loops) map directly to single assembly instructions.
- Key Characteristics:
- Variable-length instructions (e.g., 1 byte to 15 bytes in x86).
- Memory operands can be directly embedded within arithmetic and logic instructions (e.g.,
ADD [BX+DI+10H], AX). - Extensive variety of complex addressing modes (register indirect, base-index with displacement, scaled index).
- Implemented using microprogrammed control units.
- Emphasis on hardware complexity to minimize code size.
RISC (Reduced Instruction Set Computer)
The RISC philosophy emerged in the early 1980s (pioneered by John Hennessy at Stanford and David Patterson at UC Berkeley) based on empirical studies showing that 80% of program execution time was spent executing only 20% of simple instructions (load, store, add, branch).
- Design Philosophy: Keep instructions simple, uniform, and minimal so that every instruction can execute in a single clock cycle, enabling deep and efficient hardware pipelining.
- Key Characteristics:
- Fixed-Length Instructions: Typically 32 bits for all instructions, drastically simplifying instruction fetch and decode logic.
- Load-Store Architecture: Memory access is restricted strictly to dedicated
LOADandSTOREinstructions; all arithmetic and logic operations execute between general-purpose registers. - Large Register File: Features 32 to 128 general-purpose registers to minimize memory traffic.
- Hardwired Control Unit: Maximizes clock speeds by eliminating microcode ROM lookup delays.
- Few, Simple Addressing Modes: Typically limited to register, immediate, and base-plus-displacement.
- Single-Cycle Execution via Pipelining: Each instruction is divided into balanced stages so that a new instruction enters the pipeline every clock cycle.
| Aspect | CISC Architecture | RISC Architecture |
|---|---|---|
| Instruction Length | Variable (1 byte to 15 bytes) | Fixed (uniform 32 bits) |
| Instruction Execution Time | Multi-cycle (varies from 1 to over 100 cycles) | Single-cycle nominal throughput (via pipelining) |
| Memory Access | Embedded directly in arithmetic/logic instructions | Load-Store architecture (only LOAD/STORE access memory) |
| Addressing Modes | Many complex modes (10 to 20+ modes) | Few simple modes (typically 3 to 5 modes) |
| Control Unit Type | Microprogrammed Control Unit | Hardwired Control Unit |
| Register Count | Small register file (8 to 16 general-purpose registers) | Large register file (32 to 128 general-purpose registers) |
| Code Size | Compact machine code; fewer instructions per task | Larger binary footprint; requires more instructions |
| Pipelining | Difficult to pipeline efficiently due to variable length | Naturally suited for deep instruction pipelining |
| Representative Processors | Intel 8086, Pentium, Core i7, Motorola 68000 | MIPS, ARM, RISC-V, SPARC, PowerPC |
Instruction Pipelining in RISC
Instruction pipelining is an implementation technique where multiple instructions are overlapped in execution, analogous to an industrial assembly line.
The Classic 5-Stage RISC Pipeline
Clock Cycle: 1 2 3 4 5 6 7
Instruction 1: [IF] [ID] [EX] [MEM] [WB]
Instruction 2: [IF] [ID] [EX] [MEM] [WB]
Instruction 3: [IF] [ID] [EX] [MEM] [WB]
Instruction 4: [IF] [ID] [EX] [MEM] [WB]
Instruction 5: [IF] [ID] [EX] [MEM] [WB]- IF (Instruction Fetch): Fetches instruction from instruction cache into Instruction Register; increments PC.
- ID (Instruction Decode / Register Read): Decodes opcode and reads source operand values from register file.
- EX (Execution / ALU): ALU performs the arithmetic operation, calculates effective memory address, or evaluates branch conditions.
- MEM (Memory Access): Reads data from or writes data to data cache (active only for load/store instructions).
- WB (Write Back): Writes computation result or loaded memory data back into destination register.
Pipeline Speedup Formula
For a pipeline with k stages executing N instructions:
- Clock cycles required on an unpipelined processor: Cycles_unpipelined = N x k
- Clock cycles required on a pipelined processor (ideal): Cycles_pipelined = k + (N - 1)
- Ideal Speedup factor (S): S = (N x k) / (k + N - 1)
For very large N (N -> infinity), the speedup approaches the number of stages: S_max = k
Pipeline Hazards
Events that prevent the pipeline from executing instructions at its maximum throughput of one instruction per cycle are called Pipeline Hazards:
- Structural Hazards (Resource Conflicts): Occur when two overlapping instructions attempt to access the same physical hardware resource simultaneously (e.g., a single-port memory attempting to fetch an instruction and read a data operand simultaneously). Mitigated by using Harvard architecture (separate instruction and data caches).
- Data Hazards (Data Dependencies): Occurs when an instruction requires the result of a prior instruction that has not yet completed its write-back stage:
- RAW (Read After Write): Most common. Resolved by Hardware Data Forwarding (Bypassing), where the ALU result from the EX or MEM stage is routed directly back to the ALU input of the next stage without waiting for register write-back.
- Control Hazards (Branch Penalties): Caused by branch or jump instructions that change the Program Counter, rendering already-fetched instructions in the pipeline invalid. Mitigated using Branch Prediction (predicting whether a branch is taken or not taken), Branch Target Buffers (BTB), and Delayed Branching.
6.5 Introduction to multiprocessing/multitasking
Multiprocessing
Multiprocessing refers to a computer hardware architecture featuring two or more independent Central Processing Units (CPUs) or processor cores that execute machine instructions concurrently.
Memory Organization Models
- Tightly Coupled Multiprocessing (Shared Memory / UMA):
- All processors share a common physical main memory and a unified address space across a high-speed system bus or crossbar switch.
- Also known as Symmetric Multiprocessing (SMP) or Uniform Memory Access (UMA), where all CPUs enjoy identical access latency to any memory location.
- Loosely Coupled Multiprocessing (Distributed Memory / NUMA):
- Each processor has its own private physical memory.
- Processors share no common address space and coordinate tasks by exchanging data packets across high-speed interconnection networks (Message-Passing Interface / Clusters).
Bus Arbitration in Shared-Memory Multiprocessors
When multiple CPUs share a common system bus, only one processor can drive the bus at any given instant. A hardware Bus Arbiter resolves conflicting bus requests:
- Daisy Chaining: Processors are connected in series along a bus grant line. The processor physically closest to the arbiter receives the grant first (fixed priority based on physical location).
- Independent Request/Grant: Each processor has dedicated bus request and bus grant lines connected to a centralized priority arbiter (supports dynamic, programmable priority).
- Polling (Round-Robin): The arbiter steps through processor IDs in round-robin order, granting fair access without starvation.
Multitasking
Multitasking is an operating system software technique that enables a single CPU to execute multiple independent tasks (processes or threads) concurrently by interleaving their execution over small slices of time (time-slicing).
Context Switching
When the operating system schedules a new process to run:
- An interrupt (such as a periodic timer tick) suspends the running process.
- The OS saves the current process complete execution state—including general registers, program counter, stack pointer, and processor flags—into a memory data structure called the Process Control Block (PCB).
- The OS scheduler selects the next ready process from the scheduling queue.
- The OS loads the register states from the new process PCB into the physical CPU registers.
- The CPU resumes execution of the new process at its restored Program Counter.
6.6 Digital signal processor
A Digital Signal Processor (DSP) is a specialized microprocessor architected specifically to perform high-speed, repetitive numerical mathematics on digitized real-time analog signals (e.g., audio, speech, radar, sonar, biomedical electrocardiograms, image processing, telecommunications).
Unlike general-purpose microprocessors, which optimize for conditional branching, multitasking, and operating system management, a DSP optimizes for massive mathematical throughput on streaming arrays of numbers.
Key Architectural Features of a DSP
- Hardware Multiply-Accumulate (MAC) Unit: Signal processing algorithms (such as Finite Impulse Response - FIR filters, Infinite Impulse Response - IIR filters, and Fast Fourier Transforms - FFT) consist fundamentally of sum-of-products operations: y[n] = sum(h[k] * x[n-k]) for k = 0 to N-1 A DSP contains a dedicated hardware multiplier and adder that computes
P = P + (A * B)in a single clock cycle. - Modified Harvard Architecture with Multiple Buses: DSPs feature independent program memory and multiple independent data memory banks (e.g., Data Memory X and Data Memory Y). This allows the processor to fetch an instruction and two distinct data operands simultaneously in one clock cycle.
- Circular Addressing Mode: DSPs incorporate dedicated Address Generation Units (AGUs) that implement circular FIFO buffers in hardware. When a pointer increments past the buffer boundary, it automatically wraps around to the beginning with zero software instruction overhead.
- Bit-Reversed Addressing Mode: Fast Fourier Transform (FFT) algorithms require input or output data arrays to be reordered according to the bit-reversed indices of their binary addresses. DSPs include hardware address units that automatically generate bit-reversed addresses in zero clock cycles.
- Hardware Barrel Shifter: Allows data words to be shifted or rotated by an arbitrary number of bit positions in a single clock cycle, essential for dynamic range scaling and fixed-point overflow prevention.
- Zero-Overhead Hardware Loops: Dedicated hardware loop counters and registers execute tight repetitive loops without incurring branch delay penalties or condition-check instructions.
| Aspect | General-Purpose Processor (GPP) | Digital Signal Processor (DSP) |
|---|---|---|
| Primary Design Goal | Broad computational versatility, OS support, multitasking | Maximum mathematical throughput on streaming signals |
| Arithmetic Unit | Standard ALU (multi-cycle multiplication) | Dedicated single-cycle Multiply-Accumulate (MAC) unit |
| Memory Architecture | Von Neumann or cache-based Modified Harvard | Multi-bus Harvard architecture (simultaneous multi-operand fetch) |
| Addressing Modes | Standard addressing (direct, indirect, base-index) | Specialized addressing (circular buffers, bit-reversed for FFT) |
| Looping Support | Software conditional branch instructions (LOOP, JNZ) | Zero-overhead hardware looping registers |
| Typical Applications | Desktops, servers, laptops, smartphones (Intel Core, AMD Ryzen) | Audio processors, radar/sonar, modem basebands, motor controllers (TI TMS320) |
Worked Examples
Arithmetic Expression Evaluation Across Stack, Accumulator, and Register Architectures
Evaluate the arithmetic expression: X = (A + B) * (C - D) across three distinct microprocessor architectures:
- Stack-Based Architecture (Zero-Address)
- Accumulator-Based Architecture (One-Address)
- Register-Register / Load-Store Architecture (Three-Address)
Write the assembly instruction sequences for each architecture. Assume memory locations A, B, C, D contain values 10, 5, 8, and 2 respectively, and verify the numerical result of X.
Stack-Based Architecture (Zero-Address): Operands are pushed onto the stack; ALU operations pop the top two values and push the result.
PUSH A
PUSH B
ADD
PUSH C
PUSH D
SUB
MUL
POP XTotal instructions = 8 instructions. Execution trace:
- PUSH A (10), PUSH B (5) -> Stack: [10, 5]
- ADD -> Pops 5 and 10, pushes 15 -> Stack: [15]
- PUSH C (8), PUSH D (2) -> Stack: [15, 8, 2]
- SUB -> Pops 2 and 8, pushes 6 -> Stack: [15, 6]
- MUL -> Pops 6 and 15, pushes 90 -> Stack: [90]
- POP X -> Stores 90 into X.
Accumulator-Based Architecture (One-Address): One operand is implicitly the Accumulator. Intermediate results must be saved to a temporary memory variable (T).
LOAD A
ADD B
STORE T
LOAD C
SUB D
MUL T
STORE XTotal instructions = 7 instructions. Execution trace:
- LOAD A (10) -> Acc = 10
- ADD B (5) -> Acc = 15
- STORE T -> Memory T = 15
- LOAD C (8) -> Acc = 8
- SUB D (2) -> Acc = 6
- MUL T (15) -> Acc = 90
- STORE X -> Memory X = 90.
Register-Register / Load-Store Architecture (Three-Address): Arithmetic operations occur strictly between registers R1, R2, R3, R4.
LOAD R1, A
LOAD R2, B
ADD R1, R1, R2
LOAD R3, C
LOAD R4, D
SUB R3, R3, R4
MUL R1, R1, R3
STORE X, R1Total instructions = 8 instructions. Execution trace:
- R1 = 10, R2 = 5 -> R1 = 10 + 5 = 15
- R3 = 8, R4 = 2 -> R3 = 8 - 2 = 6
- R1 = 15 * 6 = 90
- STORE X, R1 -> Memory X = 90.
Stack architecture takes 8 instructions; Accumulator architecture takes 7 instructions (requiring temporary storage T); Load-Store architecture takes 8 instructions with zero memory interference during arithmetic. The verified result is X = 90.
RISC Pipeline Speedup and CPI Calculation
A 5-stage RISC microprocessor pipeline (IF, ID, EX, MEM, WB) executes a benchmark program of 100,000 instructions.
- On an equivalent unpipelined processor, every instruction requires exactly 5 clock cycles.
- On the pipelined processor, under ideal conditions, one instruction completes every clock cycle (CPI = 1.0).
- In this specific program, due to data hazards and branch delays, 20% of the instructions experience a 1-cycle pipeline stall.
Calculate:
- The total clock cycles required by the unpipelined processor.
- The average Cycles Per Instruction (CPI) of the pipelined processor.
- The total clock cycles required by the pipelined processor.
- The actual speedup factor achieved by pipelining.
Calculate Unpipelined Execution Cycles: Cycles_unpipe = N x k = 100,000 x 5 = 500,000 cycles
Calculate Average CPI of Pipelined Processor: CPI_pipe = CPI_ideal + Stall Cycles per Instruction CPI_pipe = 1.0 + (0.20 x 1 cycle) = 1.0 + 0.20 = 1.2 cycles/instruction
Calculate Total Pipelined Execution Cycles: Accounting for pipeline fill overhead (k - 1 = 4 cycles) and stall penalties: Cycles_pipe = (k - 1) + (N x CPI) = 4 + (100,000 x 1.2) = 120,004 cycles For large N, this is approximately 120,000 cycles.
Calculate Actual Speedup Factor: Speedup = Cycles_unpipe / Cycles_pipe = 500,000 / 120,004 = 5.0 / 1.2 = 4.167
- Unpipelined cycles = 500,000.
- Average pipelined CPI = 1.2.
- Total pipelined cycles = 120,004.
- Speedup = 4.17x over the unpipelined processor.
Digital Signal Processor (DSP) FIR Filter Performance Comparison
A 64-tap Finite Impulse Response (FIR) digital filter computes each output sample using: y[n] = sum(h[k] * x[n-k]) for k = 0 to 63 This calculation requires exactly 64 Multiply-Accumulate (MAC) operations per sample.
Compare the performance of:
- A General-Purpose Processor (GPP) where each MAC iteration requires 12 clock cycles (including load, multiply, add, pointer increment, and loop condition check).
- A Digital Signal Processor (DSP) equipped with a single-cycle MAC unit, dual data-memory buses, and zero-overhead hardware looping, completing 1 MAC operation per clock cycle.
Both processors operate at a clock frequency of 200 MHz. Calculate the clock cycles and processing time required per output sample on each processor.
Calculate Clock Cycles per Output Sample:
- GPP: Cycles = 64 taps x 12 cycles/tap = 768 clock cycles.
- DSP: With single-cycle MAC and hardware looping, each tap takes 1 clock cycle: Cycles = 64 taps x 1 cycle/tap = 64 clock cycles.
Calculate Processing Time per Sample at 200 MHz: Clock period: T_clk = 1 / (200 MHz) = 1 / (200 x 10^6 Hz) = 5 ns
- Execution Time on GPP: T_GPP = 768 x 5 ns = 3840 ns = 3.84 microseconds
- Execution Time on DSP: T_DSP = 64 x 5 ns = 320 ns = 0.32 microseconds
Performance Ratio: Speedup of DSP over GPP = 768 / 64 = 12x The DSP is exactly 12 times faster.
GPP requires 768 cycles (3.84 microseconds per sample); DSP requires 64 cycles (0.32 microseconds per sample). The DSP executes the filter 12 times faster due to its single-cycle MAC unit and hardware looping.
Exercises
Exercises
Compare Harvard Architecture and Von Neumann (Princeton) Architecture. What is the Von Neumann bottleneck, and how do modern superscalar microprocessors overcome it while maintaining backward software compatibility?
Comparison of Architectures:
- Memory Spaces: Von Neumann uses a single physical memory holding both program instructions and application data. Harvard uses separate physical memories for instructions and data.
- Bus Configuration: Von Neumann shares a single address and data bus between instructions and data. Harvard provides independent address and data buses for instruction and data paths.
- Execution Concurrency: In Von Neumann, instruction fetch and operand read/write must happen sequentially. In Harvard, instruction fetch and operand transfer occur simultaneously.
- Word Size Flexibility: Harvard allows different word widths for code and data; Von Neumann restricts both to the same bus width.
The Von Neumann Bottleneck: Because processor execution speeds increase faster than memory bus speeds, the shared bus in a Von Neumann architecture becomes saturated. The processor spends idle wait cycles waiting for instructions and data over the single bus.
Solution in Modern Processors (Modified Harvard Architecture): Modern processors (x86, ARM) implement a Modified Harvard Architecture:
- The internal core contains separate Level 1 Instruction Cache (L1 I-cache) and Level 1 Data Cache (L1 D-cache), providing simultaneous fetch and read/write bandwidth.
- Beyond L1 cache, the memory system unifies into shared L2/L3 caches and a single main system memory, preserving the standard unified memory programming model.
Von Neumann uses a unified memory and shared bus, creating a bus bandwidth bottleneck. Harvard uses separate memories and buses for parallel access. Modern processors use a Modified Harvard architecture (split L1 instruction/data caches with unified L2/L3/RAM) to eliminate the bottleneck while maintaining software compatibility.
Compare Hardwired Control Units and Microprogrammed Control Units across six architectural parameters. Explain the difference between Horizontal and Vertical microprogramming.
Comparison of Control Units:
| Parameter | Hardwired Control Unit | Microprogrammed Control Unit |
|---|---|---|
| 1. Implementation | Combinational logic gates, decoders, PLAs | Micro-ROM (Control Store) holding microprograms |
| 2. Operating Speed | Maximum speed (gate delay only) | Slower (Control Store access time) |
| 3. Design Flexibility | Completely rigid; changes require chip refabrication | Highly flexible; changes made by updating ROM microcode |
| 4. Instruction Complexity | Best suited for simple, uniform RISC instructions | Best suited for complex CISC instruction sets |
| 5. Silicon Area | Small for simple RISC; grows exponentially with complexity | Modular and compact even for complex sets |
| 6. Prototyping Cost | High initial design and debugging cost | Low development cost; easy to emulate and update |
Horizontal versus Vertical Microprogramming:
- Horizontal Microprogramming: Each bit in the microinstruction word directly drives an individual control line without decoding. Offers maximum parallelism and high speed, but produces very wide control words (48 to 128+ bits).
- Vertical Microprogramming: Control signals are grouped into mutually exclusive fields and decoded via decoders (e.g., 3-to-8 decoder). Produces narrower microinstruction words (16 to 32 bits), reducing ROM size at the expense of decoding delay.
Hardwired control uses fixed logic gates for maximum speed and rigidity (RISC). Microprogrammed control uses a micro-ROM for flexibility and complex instruction sets (CISC). Horizontal microcode is wide, unencoded, and fast; vertical microcode is narrow, decoded, and compact.
Compare RISC and CISC microprocessor architectures across five key design principles. Describe the three primary types of pipeline hazards (Structural, Data, and Control) and the hardware/compiler methods used to resolve them.
Comparison of RISC and CISC:
- Instruction Format: RISC uses fixed-length instructions (e.g., 32 bits); CISC uses variable-length instructions (1 to 15 bytes).
- Memory Model: RISC uses a Load-Store model (only LOAD/STORE touch memory); CISC allows arithmetic instructions to access memory directly.
- Instruction Complexity: RISC provides simple, single-cycle instructions; CISC provides multi-cycle, complex instructions.
- Register File: RISC provides 32 to 128 general-purpose registers; CISC has fewer registers (8 to 16).
- Control Unit: RISC uses hardwired control; CISC uses microprogrammed control.
Three Primary Pipeline Hazards and Resolutions:
- Structural Hazards: Hardware resource conflicts (e.g., single memory port accessed for fetch and data).
- Resolution: Separate L1 instruction and data caches (Harvard architecture).
- Data Hazards: An instruction depends on the result of an earlier uncompleted instruction (RAW dependency).
- Resolution: Hardware Data Forwarding (Bypassing) routes the ALU output directly to the next stage ALU input; compiler instruction scheduling fills delay slots.
- Control Hazards: Branch and jump instructions alter the PC, invalidating pre-fetched instructions.
- Resolution: Dynamic Branch Prediction, Branch Target Buffers (BTB), and Delayed Branching.
RISC features fixed-length instructions, Load-Store architecture, and hardwired control; CISC features variable-length instructions, direct memory operands, and microcode. The three hazards are Structural (resolved by split caches), Data (resolved by forwarding), and Control (resolved by branch prediction).
Explain why a standard General-Purpose Processor (GPP) is inefficient for real-time digital signal processing compared to a dedicated Digital Signal Processor (DSP). Describe the operational roles of the MAC unit, circular addressing, and bit-reversed addressing.
Why GPPs are Inefficient for Signal Processing: Signal processing algorithms (audio filtering, speech synthesis, radar analysis) are dominated by repetitive Multiply-Accumulate loops over continuous sample streams. In a GPP:
- Multiplication requires multiple clock cycles.
- Instructions and data compete for cache bandwidth over unified buses.
- Array pointer wrapping and boundary checks require multiple conditional branch instructions per sample, wasting clock cycles.
Specialized DSP Architectural Enhancements:
- Multiply-Accumulate (MAC) Unit: Performs multiplication and addition
P = P + (A * B)in a single clock cycle using dedicated hardware array multipliers and accumulators. - Circular Addressing: Specialized Address Generation Units (AGUs) implement ring buffers in hardware. When a pointer increments past the buffer end, hardware automatically wraps it to the start with zero instruction overhead.
- Bit-Reversed Addressing: Fast Fourier Transform (FFT) algorithms require array indices to be scrambled in bit-reversed order (e.g., index 001B points to 100B). Dedicated hardware generates bit-reversed addresses in zero clock cycles, eliminating software re-indexing loops.
GPPs lack single-cycle multiplication and incur high branching overhead for buffers. DSPs excel through single-cycle hardware MAC units, circular addressing for zero-overhead FIFO buffers, and bit-reversed addressing for instant FFT indexing.
A 5-stage RISC processor pipeline has individual stage propagation delays of:
- Instruction Fetch (IF) = 150 ps
- Instruction Decode (ID) = 120 ps
- Execution (EX) = 160 ps
- Memory Access (MEM) = 140 ps
- Write Back (WB) = 110 ps
The pipeline register delay between each stage is 20 ps.
- Determine the minimum clock cycle time of the pipelined processor.
- Determine the clock cycle time of an equivalent unpipelined processor.
- Calculate the maximum theoretical speedup for a program of 10,000 instructions assuming no pipeline stalls.
Determine Minimum Clock Cycle Time of Pipelined Processor: The clock period of a pipelined processor is determined by the slowest (bottleneck) stage plus the pipeline register latch overhead: Clock Cycle_pipe = max(Stage Delays) + Register Delay max(150, 120, 160, 140, 110) ps = 160 ps (EX stage) Clock Cycle_pipe = 160 ps + 20 ps = 180 ps
Determine Clock Cycle Time of Unpipelined Processor: An unpipelined processor completes all five stages in a single long clock cycle without inter-stage register overhead: Clock Cycle_unpipe = 150 + 120 + 160 + 140 + 110 = 680 ps
Calculate Theoretical Speedup for 10,000 Instructions:
- Total unpipelined time: T_unpipe = 10,000 x 680 ps = 6,800,000 ps
- Total pipelined time (with k = 5 stages and N = 10,000): T_pipe = (k + N - 1) x 180 ps = (5 + 10,000 - 1) x 180 ps = 10,004 x 180 = 1,800,720 ps
- Speedup factor: Speedup = T_unpipe / T_pipe = 6,800,000 / 1,800,720 = 680 / 180 = 3.778
- Pipelined clock cycle = 180 ps (160 ps EX stage + 20 ps register).
- Unpipelined clock cycle = 680 ps.
- Maximum speedup = 3.78x.