Computer System Organization (EC-504 (B)) - Unit 1 Short Notes

1.0 FUNDAMENTAL COMPUTER ORGANIZATION & THE VON NEUMANN MODEL

1.1 Von Neumann Architecture (Princeton Architecture)

• Definition: A stored-program digital computer architecture where instructions and data share the same memory unit and are transferred over a common bus.

• Key Components:

  • Memory: Stores both instructions and data.

  • Arithmetic Logic Unit (ALU): Performs arithmetic and logical operations.

  • Control Unit (CU): Fetches, decodes, and controls instruction execution.

  • Input/Output (I/O) Equipment: Communicates with the external world.

  • System Bus: Interconnects all major components (Address, Data, Control).

• Stored-Program Concept: The fundamental idea that a sequence of instructions (a program) can be stored in memory and executed automatically by the CPU.

• Sequential Execution Model: Instructions are typically fetched and executed one after another from successive memory addresses, unless a branch/jump instruction alters the flow.

• Block Diagram:

  DiagramSEARCH: von neumann architecture block diagram

[!TIP] Exam Focus: Be prepared to draw and label the block diagram. Explain the role of each component and the significance of the stored-program concept.

1.2 Basic Functional Units & Interconnection

• System Bus Structure:

  • Address Bus: Carries memory/I/O addresses from CU to memory/I/O. Unidirectional. Width determines maximum addressable memory locations: $$\displaystyle 2^{\text{address bits}} $$.

  • Data Bus: Carries data between CPU, memory, and I/O. Bidirectional. Width determines word size (amount of data transferred per cycle).

  • Control Bus: Carries control signals (Read, Write, Interrupt, Clock) to coordinate operations.

• Common Bus System: A single set of lines (bus) used for transferring addresses, data, and control signals between multiple registers and memory. Requires multiplexers to select the source for bus inputs.

  DiagramSEARCH: common bus system with multiplexers

• Register Organization:

  • General Purpose Registers (R0...Rn-1): Used for operands and intermediate results.

  • Special Purpose Registers:

    • Program Counter (PC): Holds the address of the next instruction to fetch.

    • Memory Address Register (MAR): Holds the address for a memory read/write.

    • Memory Data Register (MDR): Holds data read from or to be written to memory.

    • Instruction Register (IR): Holds the currently fetched instruction (opcode & address fields).

    • Accumulator (AC): A dedicated register for ALU operations (common in simple designs).

• Role of Key Registers in Fetch Cycle:

  1. CU places PC content on address bus → MAR.

  2. Memory read signal activated → data from memory[PC] → MDR.

  3. MDR content → IR.

  4. PC incremented to point to next instruction.

2.0 INSTRUCTION EXECUTION CYCLE & ADDRESSING

2.1 Instruction Cycle Phases

The cycle repeats continuously. A typical Fetch-Decode-Execute cycle:

1. Fetch: PC → MAR → Memory → MDR → IR, PC ← PC + 1.

2. Decode: CU interprets IR (opcode), determines operation and addressing mode.

3. Execute: CU generates control signals to perform the operation (e.g., ALU operation, memory access, register transfer).

4. Store/Write-back: Result is written to destination (register or memory).

• Timing & Control: Each phase occurs in one or more clock cycles (T-states). A state machine in the CU sequences these cycles.

• Flowchart:

  DiagramSEARCH: instruction cycle flowchart fetch decode execute

2.2 Instruction Format & Word Size

• Components:

  • Opcode Field: Specifies the operation (e.g., ADD, LOAD). Number of bits $n$ determines max instructions: $$\displaystyle 2^n $$.

  • Address Field(s): Specifies operand location(s). Length depends on address space size.

  • Mode Field: Specifies addressing mode (if used).

• Relationship: If address bus is A bits, memory has $$\displaystyle 2^A $$ locations. Address field must have at least A bits to reference any location.

• Calculation Example (from past paper): 16-bit instruction, 6-bit opcode, 2-address format.

  • Address field per address = $$\displaystyle (16 - 6)/2 = 5 $$ bits.

  • Max instructions = $$\displaystyle 2^6 = 64 $$.

  • Addressable locations per field = $$\displaystyle 2^5 = 32 $$.

2.3 Addressing Modes

• Definition: Specifies how the operand address in the instruction is interpreted to find the effective address (EA) of the actual operand.

• Common Modes & Examples:

[!TIP] Exam Focus: Be able to give an example for each mode and state its primary use case (e.g., immediate for constants, indirect for pointers, indexed for arrays). Know the trade-off between instruction length and execution time.

3.0 CONTROL UNIT DESIGN

3.1 Hardwired Control Unit

• Design: Implemented using logic gates (AND, OR, NOT) and flip-flops. It's a fixed, physical circuit.

• Operation:

  • Instruction Decoder: Converts opcode bits into a set of instruction signals (I₁, I₂, ...).

  • Timing (State) Machine: A counter or sequencer generates timing signals (T₁, T₂, ...) for each clock cycle of the instruction.

  • Control Signal Generation: Each control signal (e.g., PCin, MARin, Read) is generated by a Boolean expression combining instruction signals and timing signals.

    • Example: PCin = I₁T₁ + I₂T₁ + ... (Load PC on T1 for these instructions).

• Advantages: Very fast (no memory access for microcode).

• Disadvantages: Inflexible (difficult to modify/add instructions), complex to design for complex ISAs, hard to debug.

• Boolean Expression Example (from past paper): Given a table, derive expressions like S5 = I₁T₁ + I₂T₁ + I₃T₁ + I₄T₁ (if S5 active in T1 for all instructions).

3.2 Microprogrammed Control Unit

• Core Concept: Control signals are stored as microinstructions in a special Control Memory (CM). The CU executes a microprogram (a sequence of microinstructions) to implement each machine instruction.

• Micro-instruction vs. Machine Instruction:

  • Machine Instruction: User-visible operation (e.g., ADD). Stored in main memory.

  • Microinstruction: Low-level control signal specification. Stored in control memory. One machine instruction = many microinstructions.

• Micro-instruction Format:

  • Vertical Micro-instructions:

    • Encoded control fields (e.g., 4 bits to select one of 16 ALU operations).

    • Fewer bits per microinstruction, more sequential microinstructions per machine instruction.

    • Slower but more compact CM.

  • Horizontal Micro-instructions:

    • One bit per control signal (or few groups).

    • Many bits, can activate many operations in parallel.

    • Faster (more parallelism) but requires larger CM.

  • Common Fields:

    1. Control Field: Bits for each control signal (horizontal) or encoded fields (vertical).

    2. Next Address Field: Specifies address of next microinstruction (for sequential flow).

    3. Branch/Condition Field: Used for conditional branching (e.g., based on status flags like Zero, Carry).

• Micro-program Sequencer:

  • Function: Generates the address of the next microinstruction to be fetched from CM.

  • Components & Operation:

    1. Control Address Register (CAR): Holds current microinstruction address.

    2. Mapping Logic: Maps the opcode from IR to the starting address of that instruction's microprogram routine in CM.

    3. Branch Logic: Modifies the next address based on the Condition Field and status bits (e.g., if (Zero=1) then CAR ← BranchAddress).

    4. Incrementer: Provides CAR + 1 for sequential execution.

  • Block Diagram:

    DiagramSEARCH: microprogram sequencer block diagram

• Advantages: Flexible (easy to modify by changing microcode), simpler to design/debug, supports complex ISAs.

• Disadvantages: Slower (extra memory access for each microinstruction).

3.3 Comparative Analysis: Hardwired vs. Microprogrammed

[!TIP] Exam Focus: Know the Boolean expression generation method for hardwired control (e.g., (Ij + Ik) Tn). Be able to draw and explain the microprogram sequencer block diagram and its components. The comparison table is a high-frequency question.

4.0 ARITHMETIC & LOGIC UNIT (ALU) & MICRO-OPERATIONS

4.1 Micro-operations

• Definition: The elementary operations performed on data stored in registers (e.g., transfer, arithmetic, logic, shift).

• Classification:

  • Register Transfer: Move data between registers (e.g., R1 ← R2).

  • Arithmetic: ADD, SUB, INC, DEC.

  • Logic: AND, OR, XOR, NOT, CLR (clear).

  • Shift: SHL (shift left), SHR (shift right), ROL (rotate left).

• Register Transfer Language (RTL): A symbolic notation to describe micro-operations.

  • Example: R1 ← R1 + R2 (Arithmetic)

  • Example: MAR ← PC (Register Transfer)

  • Example: R2 ← SHL R2 (Shift)

4.2 Arithmetic Circuit Design

• Building Blocks:

  • Half-Adder (HA): Adds 2 bits. Sum = $A \oplus B$, Carry = $A \cdot B$.

  • Full-Adder (FA): Adds 3 bits (A, B, Cin). Sum = $$\displaystyle A \oplus B \oplus C_{in} $$, Carry = $$\displaystyle (A \cdot B) + (C_{in} \cdot (A \oplus B)) $$.

• Binary Adders:

  • Ripple-Carry Adder: FAs connected in series. Carry "ripples" through. Simple but slow (propagation delay ∝ n).

  • Carry-Lookahead Adder: Generates carries in parallel using Generate (G = A·B) and Propagate (P = A⊕B) signals. Faster, more complex hardware.

• Multiplication Algorithm (Sequential/Add-and-Shift):

  1. Initialize product register to 0.

  2. For each bit of multiplier (from LSB to MSB):

     • If multiplier bit = 1, add multiplicand to product.

     • Shift product and multiplier right (or multiplicand left).

  3. Final product is in the product register.

  • Challenges: Speed (n cycles for n-bit multiplier), handling signed numbers ( Booth's algorithm), partial product accumulation, large hardware for parallel multipliers.

4.3 Floating-Point Arithmetic (IEEE 754)

• Format (Single Precision, 32-bit):

  • Sign (1 bit): 0=positive, 1=negative.

  • Exponent (8 bits): Biased (bias = 127). Actual exponent = Stored Exponent - 127.

  • Mantissa/Fraction (23 bits): Implicit leading 1 (normalized). Represents $1.F$.

  • Value = $$\displaystyle (-1)^S \times 1.F \times 2^{(E-127)} $$.

• Floating-Point Addition/Subtraction Steps:

  1. Align Exponents: Shift the mantissa of the number with the smaller exponent right until exponents are equal. (Loss of precision).

  2. Add/Subtract Mantissas: Perform integer addition/subtraction on aligned mantissas.

  3. Normalize Result: Shift result left/right to restore form $1.F$. Adjust exponent accordingly.

  4. Round: Apply rounding mode (e.g., round to nearest even) to fit mantissa back into 23 bits. May cause re-normalization.

  5. Check for Overflow/Underflow.

• Flowchart:

  DiagramSEARCH: floating point addition flowchart

• Challenges: Precision loss (alignment, rounding), overflow/underflow, non-associativity ($ (a+b)+c \neq a+(b+c) $), complex hardware.

4.4 Decimal & Integer Arithmetic

• BCD (Binary-Coded Decimal) Addition:

  • Add BCD digits as binary.

  • If result > 9 or carry out, add 6 (0110) to correct to valid BCD.

• Signed Integer Representation:

  • Sign-Magnitude: MSB is sign, rest magnitude. Two zeros (+0, -0). Subtraction complex.

  • 1's Complement: Negative = bitwise complement. End-around carry needed. Two zeros.

  • 2's Complement (Most Common): Negative = complement + 1. Single zero. Addition/subtraction same circuit. Range: $$\displaystyle -2^{n-1} $$ to $$\displaystyle 2^{n-1}-1 $$.

• ALU Handling: A single 2's complement adder/subtractor circuit can handle both addition and subtraction (using 2's complement of subtrahend).

5.0 MEMORY SYSTEMS & HIERARCHY

5.1 Memory Hierarchy Concept

• Principle of Locality:

  • Temporal Locality: Recently accessed items likely to be accessed again soon.

  • Spatial Locality: Access to an item likely to be followed by access to nearby items.

• Hierarchy Levels (Speed ↓, Capacity ↑, Cost/bit ↓):

  Registers → L1 Cache → L2 Cache → Main Memory (RAM) → Secondary Storage (SSD/HDD)

• Significance: Exploits locality to bridge the speed gap between fast CPU and slow main memory. Optimizes cost/performance—use small, fast, expensive memory where it counts (cache).

• Average Memory Access Time (AMAT):

$$\boxed{AMAT = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}}$$

*   **Hit Time:** Time to access data in the current level (e.g., cache access time).

*   **Miss Rate:** Fraction of accesses not found in current level.

*   **Miss Penalty:** Time to access the next lower level and deliver the block (including transfer).

5.2 Cache Memory Organization

• Purpose: Small, fast memory between CPU and main memory. Stores copies of frequently used main memory blocks. Transparent to programmer.

• Cache Mapping Techniques:

  • Direct Mapping:

    • Each memory block maps to exactly one cache line (set).

    • Index = Block Address mod (Number of Cache Blocks).

    • Tag stored in cache line to identify which memory block is present.

    • Pros: Simple, cheap. Cons: High conflict misses (two hot blocks mapping to same line).

  • Associative Mapping (Fully Associative):

    • A memory block can be placed in any cache line.

    • Tag must be compared with all tags in cache (parallel comparators).

    • Pros: Lowest conflict misses. Cons: Complex, expensive, slow search.

  • Set-Associative Mapping (Compromise):

    • Cache divided into n-way sets (e.g., 2-way, 4-way).

    • Block maps to a specific set (like direct), but can go into any line within that set.

    • Index = Block Address mod (Number of Sets).

    • Tag compared only with tags in the selected set.

    • Replacement Policy: When a set is full, choose a victim. LRU (Least Recently Used) is common.

    • Pros: Balance of cost and performance. Cons: More complex than direct.

• Cache Performance:

  • Hit Ratio (h): Fraction of accesses found in cache. Miss Rate = 1 - h.

  • Write Policies:

    • Write-Through: Data written to both cache and main memory simultaneously. Simple, consistent, but slow (writes go to RAM).

    • Write-Back (Write-Behind): Data written only to cache. Cache line marked "dirty". Written to main memory only when evicted. Faster writes, but more complex (need dirty bits).

• Cache vs. Associative Memory:

  • Cache: Location-addressable. You give an address, it tells you if data is there (tag match).

  • Associative Memory (Content-Addressable Memory - CAM): Content-addressable. You give data, it tells you the address where it's stored. Used for fast lookups (e.g., TLB).

5.3 Virtual Memory

• Concept: Gives each program the illusion of having a large, contiguous private address space, larger than physical RAM, by using secondary storage (disk).

• Implementation via Paging:

  • Logical (Virtual) Address Space: Divided into fixed-size Pages.

  • Physical Address Space: Divided into fixed-size Frames (same size as page).

  • Page Table: Per-process table mapping Virtual Page Number (VPN) → Physical Frame Number (PFN). Stored in main memory.

  • Address Translation: CPU generates virtual address → MMU (Memory Management Unit) uses page table to get physical address.

  • Translation Lookaside Buffer (TLB): A small, fast associative cache for page table entries. Crucial for performance—avoids slow memory lookup on every access.

    • TLB Hit: Fast translation.

    • TLB Miss: Page table walk (multiple memory accesses) → Page Fault if page not in memory (OS handles, brings page from disk).

• Benefits: Larger address space, memory protection (per-page permissions), efficient RAM use (only needed pages in memory).

• Fragmentation:

  • Internal Fragmentation: Wasted space within allocated region (e.g., last page of a process not full). Occurs in paging.

  • External Fragmentation: Wasted space between allocated regions. Occurs in segmentation (variable-size segments).

5.4 Memory Mapping & I/O Mapping

• Memory-Mapped I/O:

  • I/O device registers are mapped into the main memory address space.

  • CPU uses regular LOAD/STORE instructions to access I/O.

  • Pros: No special I/O instructions; all memory access instructions work. Cons: Uses up memory address space; memory and I/O share bus bandwidth.

• I/O-Mapped (Isolated) I/O:

  • I/O has a separate address space and special IN/OUT instructions.

  • Pros: Memory address space not reduced; I/O operations don't interfere with memory accesses. Cons: Requires special instructions; less uniform programming model.

• Effect on Program Execution: In memory-mapped I/O, a program reads/writes to specific memory addresses to communicate with devices, making I/O appear as simple memory access.

6.0 INPUT/OUTPUT (I/O) ORGANIZATION & DATA TRANSFER

6.1 I/O Interface & Asynchronous Data Transfer

• I/O Interface Role: Acts as an intermediary between CPU/memory and I/O devices. Provides:

  • Handshaking: Signals to coordinate data transfer (e.g., Data Ready, Acknowledge).

  • Buffering: Temporary storage to match speed differences (e.g., device buffer).

  • Signal Conversion: Voltage levels, serial/parallel conversion.

• Asynchronous vs. Synchronous Transfer:

  • Synchronous: Data transfer timed by a common clock. Devices must operate at same speed. Simple, used for internal buses.

  • Asynchronous: Transfer controlled by handshaking signals. Devices operate at independent speeds. Used for I/O.

• Asynchronous Transfer Modes:

  1. Program-Controlled I/O (Polling):

     • CPU repeatedly reads device status register in a loop until device is ready.

     • Flowchart:

       DiagramSEARCH: programmed I/O polling flowchart

     • Pros: Simple. Cons: CPU waits (wastes cycles), inefficient.

  2. Interrupt-Driven I/O:

     • CPU initiates I/O, then continues executing other instructions.

     • Device interrupts CPU when ready (or on error).

     • Interrupt Service Cycle: CPU finishes current instruction, saves context (PC, PSW), jumps to Interrupt Service Routine (ISR), handles I/O, returns.

     • Pros: CPU not idle. Cons: Overhead of context save/restore per interrupt. Poor for high-speed/large data.

  3. Direct Memory Access (DMA):

     • Goal: Transfer large blocks of data between I/O and memory without CPU intervention.

     • DMA Controller Block Diagram:

       DiagramSEARCH: DMA controller block diagram

     • Operation:

       a. CPU initializes DMA: sets source, destination, byte count, starts transfer.

       b. DMA controller takes over the system bus (requests control via HOLD/HLDA signals).

       c. DMA controller performs data transfers directly between I/O device and memory (reads/writes).

       d. DMA controller releases bus, interrupts CPU on completion.

     • Advantages over Interrupt: CPU overhead is O(1) per block (init + completion interrupt), not O(n) per word. High bandwidth for block transfers.

     • CPU Overhead Calculation (from past paper):

       • Total cycles for transfer = N words.

       • CPU cycles for init = C_i.

       • CPU cycles for interrupt handling = C_h.

       • Fraction of CPU time = $$\displaystyle \frac{C_i + C_h}{\text{Total time for N words}} $$.

       • Total time ≈ N / (Bus bandwidth in words/cycle) (if DMA uses bus fully).

6.2 I/O Processor (IOP)

• Role: A dedicated processor (often a simple CPU) that handles I/O operations completely, offloading the main CPU.

• Block Diagram & Interaction:

  DiagramSEARCH: I/O processor block diagram

  • IOP has its own local memory (for IOP program & buffers).

  • Communicates with main CPU via interrupts and shared memory.

  • Communicates with I/O devices via device controllers.

  • CPU loads IOP with I/O program, IOP executes it independently, interrupts CPU on completion/completion of complex sequences.

• Comparison with DMA:

  • DMA: Simple block mover, controlled by CPU for each transfer.

  • IOP: Can execute complex I/O programs (e.g., formatting, error correction), handle multiple devices, more autonomous.

6.3 Data Transfer Modes: Duplexity

• Simplex: One-way only. Example: Keyboard → CPU, Printer ← CPU.

• Half-Duplex: Two-way, but not simultaneous. Example: Walkie-talkie, early Ethernet (shared medium).

• Full-Duplex: Simultaneous two-way. Example: Telephone, modern Ethernet (switched), USB.

6.4 I/O Bus & Bandwidth

• Bus Bandwidth: Maximum data transfer rate of the bus.

$$\boxed{\text{Bandwidth (bytes/sec)} = \text{Bus Frequency (Hz)} \times \text{Data Width (bytes)} \times \text{Transfers per cycle}}$$

*   For simple bus: Bandwidth = Frequency × (Data Width / 8).

• Justification Example (from past paper):

  • Old bus: 33 MHz, 32 bits = 4 bytes → Bandwidth = 33e6 × 4 = 132 MB/s.

  • Video card needs 128 MB/s. Yes, possible (132 > 128), but leaves little margin for other devices (disk 40 MB/s). Total needed = 128+40 = 168 MB/s > 132 MB/s → bottleneck.

7.0 ADVANCED ARCHITECTURAL CONCEPTS

7.1 Instruction Pipelining

• Principle: Overlap the execution of multiple instructions by dividing the instruction cycle into stages (segments). Each stage works on a different instruction simultaneously.

• Typipeline Stages (5-stage):

  1. IF (Instruction Fetch): Get instruction from memory (using PC).

  2. ID (Instruction Decode): Decode opcode, read registers from register file.

  3. EX (Execute): Perform ALU operation (e.g., add, branch target calc).

  4. MEM (Memory Access): Read/write data memory (for load/store).

  5. WB (Write Back): Write result back to destination register.

• Advantages: Increased throughput (instructions per cycle ideally = 1). Improved performance (Speedup ≈ number of stages for long sequences).

• Limitations & Hazards:

  • Structural Hazards: Resource conflict (e.g., two instructions need memory in same cycle). Solution: Duplicate resources (separate instruction/data caches - Harvard architecture).

  • Data Hazards: Instruction depends on result of previous instruction not yet available.

    • RAW (Read-After-Write): True data dependency. Solution: Forwarding (bypassing), stalls (bubbles).

    • WAR (Write-After-Read): False dependency (out-of-order exec). Solution: Register renaming.

    • WAW (Write-After-Write): False dependency. Solution: Renaming.

  • Control Hazards: Caused by branches/jumps. Next instruction unknown until branch resolved. Solution: Branch prediction, delayed slots, speculative execution.

• Pipeline Performance:

  • Ideal Speedup (S) ≈ Number of stages (k) for long instruction streams.

  • Efficiency = (Speedup) / k. Decreases due to hazards causing stalls.

7.2 Parallel Processing & Multiprocessors

• Flynn's Taxonomy:

  • SISD: Single Instruction, Single Data (Uniprocessor). Von Neumann.

  • SIMD: Single Instruction, Multiple Data. Vector Processors, GPUs. One instruction operates on multiple data elements (vectors) simultaneously.

  • MISD: Multiple Instruction, Single Data. Rare (e.g., some fault-tolerant systems).

  • MIMD: Multiple Instruction, Multiple Data. Multiprocessors, multicore, clusters. Each processor has its own instruction stream.

• MIMD Organization:

  • Shared Memory: Processors communicate by reading/writing common memory locations.

    • Bus-Based: Simple, but bus contention limits scalability. Snooping caches (cache coherence protocols like MESI).

    • Directory-Based: Scalable. Central/mapped directory tracks cache line states.

  • Distributed Memory: Each processor has local memory. Communicate via message passing (e.g., clusters). No cache coherence problem, but programming harder.

• Vector Processors (SIMD):

  • Concept: Have vector registers (hold many elements, e.g., 64x64-bit). Single vector instruction (e.g., VADD V1, V2, V3) performs operation on all elements in parallel.

  • Architecture: Vector functional units (pipelines), strided memory access (load/store vector from/to memory with strides).

  • Applications: Scientific computing (matrix ops), computer graphics (vertex transforms), media processing (audio/video codecs).

  • Comparison with Scalar: Much higher throughput for data-parallel tasks, but inefficient for scalar code with branches.

7.3 Interconnection Structures

• Purpose: Connect multiple CPUs, memory modules, and I/O in parallel systems.

• Types:

  • Shared Bus: Simple, low cost. Bottleneck for many processors.

  • Multi-Port Memory: Memory with multiple independent ports. Expensive, limited ports.

  • Crossbar Switch: Non-blocking. Each processor can connect to any memory module simultaneously via a grid of switches. Scalable but complex (O(n²) switches for n processors).

  • Hypercube: Processors as nodes of an n-dimensional cube. Each node connected to n others. Logarithmic diameter (good for message routing). Used in some supercomputers.

  • Mesh/Torus: 2D/3D grid. Simple wiring, used in many-core chips (e.g., Tilera, some GPUs).

END OF UNIT 1 NOTES