Elements of Computing Systems: Basic Computer Architecture

Early History of Computing Systems

  • 17th Century (Hardware-Only / Single Purpose):     * Blaise Pascal (1623–1662):         * Invented the Pascal's Calculator (Pascaline) in 1652.         * Functions: Addition and Subtraction.     * Gottfried Leibniz (1646–1716):         * Invented the Leibniz Calculator in 1673.         * Functions: Addition, Subtraction, Multiplication, and Division.         * Significance: Created side benefits in mechanical engineering and the advancement of gears.
  • 19th Century (Programmable / General Purpose):     * Jacquard Loom (1804): Introduced the major innovation of punched cards, conceptually representing software.     * Charles Babbage's Analytic Engine (1837): Furthered the concept of general-purpose programmable hardware.
  • 20th Century (Modern Digital Computers):     * Key Innovators: John Von Neumann, John Atanassof, Konrad Zuse, Howard Aiken, John Mauchly, J. Presper Eckert.     * Colossus (1945): First digital, programmable computer (United Kingdom).     * ENIAC (1946): First digital, programmable, stored-program computer (University of Pennsylvania). It borrowed key concepts from earlier innovators.     * Women of ENIAC: Kathleen McNulty, Jean Jennings, Frances Snyder, Marlyn Wescoff, Frances Bilas, and Ruth Lichterman. They pioneered reusable code, subroutines, flowcharts, and other programming innovations.     * Compilation Pioneers: Adele Koss and Grace Hopper (associated with Harvard Mark I).

Basic Computer Architecture Components

  • Definition: Computer architecture refers to the structure and design of a computer system, defining how components connect and work together.
  • Central Processing Unit (CPU): Known as the "brain." Performs instructions and calculations.     * Control Unit (CU): Directs the operation of the processor.     * Arithmetic Logic Unit (ALU): Performs arithmetic and logical operations.
  • Memory: Stores data and programs currently in use.     * Primary Memory: Random Access Memory (RAM).     * Secondary Memory: Hard drives (HDD) or Solid-State Drives (SSD).
  • Input Devices: Allow users to provide data/commands (Keyboard, Mouse, Scanner, Joystick).
  • Output Devices: Present processing results (Monitor, Printer, Speaker, Headphones).
  • Bus: The communication channel (address, data, and control buses) connecting components for data transmission.
  • Stored Program Concept: One of the most important ideas in computer science history; computer memory stores both the program instructions and the data values.

Registers and Control

  • Registers: Containers that hold bits. The bit-width and quantity vary by computer.     * Data Registers: Hold data values.     * Address Register: Holds memory addresses.     * Instruction Register: Holds the current instruction being executed.
  • Instruction Execution:     * By default, the CPU executes the next instruction sequentially.     * Program Counter (PC): Points to the next instruction address.     * Branching:         * Unconditional Branching: Always jumps to a specific location (e.g., goto LOOP).         * Conditional Branching: Jumps only if a meeting condition is met (e.g., if R1 > 0 goto CONT).     * Symbolic Programs: Use labels (e.g., CONT, LOOP) instead of physical addresses. They are easier to develop, more readable, and relocatable.

The Hack Computer Architecture

  • Memory Map:     * RAM 16K: Address space from 0 to 16383.     * Screen: 8K memory map (16-bit registers) from address 16384 to 24575. This maps directly to the physical screen pixels.     * Keyboard: A single 16-bit register at address 24576. It outputs the character code of the pressed key (or 0 if none).
  • The Hack Character Set (Specific Codes):     * Space: 32     * Digits 0–9: 48–57     * Uppercase A–Z: 65–90     * Lowercase a–z: 97–122     * Special Keys: Newline (128), Backspace (129), Left Arrow (130), Up Arrow (131), Right Arrow (132), Down Arrow (133), Home (134), End (135), Page Up (136), Page Down (137), Insert (138), Delete (139), Esc (140), F1–F12 (141–152).
  • ROM32K (Instruction Memory): A read-only 32K chip pre-loaded with the program. The A register addresses it.
  • Registers in Hack:     * A Register: Address register.     * D Register: Data register.     * M: Refers to the currently selected RAM register (RAM[A]).

Machine Language: Hack Instructions

  • A-Instruction (Addressing):     * Symbolic: @xxx (where xxx is a decimal 0–32767 or a symbol).     * Binary: 0vvvvvvvvvvvvvvv (15-bit value).     * Purpose: Enters a constant, sets the stage for C-instructions targeting memory (M), or sets jump destinations.
  • C-Instruction (Computation):     * Symbolic: dest = comp ; jump     * Binary Format: 111accccccdddjjj     * Opcode: Leftmost bit is 1.     * Comp Field (acccccc): Determines what the ALU computes.         * If a=0, ALU uses the A register.         * If a=1, ALU uses M (data memory).     * Dest Field (ddd): Where to store results (A, D, M, or combinations like ADM).     * Jump Field (jjj): Determines the next instruction based on ALU output (JGT, JEQ, JGE, JLT, JNE, JLE, JMP).

Instruction Set Architecture (ISA)

  • Definition: The interface between hardware and software.
  • Addressing Modes:     * Immediate Addressing: Data is in the instruction (e.g., ADD R1, #5).     * Register Addressing: Operand is in a register (e.g., MOV R2, R3).     * Direct Addressing: Instruction contains the memory offset (e.g., LOAD R4, 500).     * Indirect Addressing: Instruction contains the address of the effective address (e.g., ADD R7, (R8)).
  • RISC vs. CISC:     * RISC (Reduced Instruction Set Computing): Simple, register-based, one instruction per cycle (CPI ≈ 1). Examples: Mobiles, Tablets.     * CISC (Complex Instruction Set Computing): Large set of complex instructions, memory-to-memory transfers, multiple cycles. Examples: Desktops, Laptops.     * CISC vs. RISC Comparison:         * CISC: Hardware emphasis, multiple instruction sizes, fewer registers, difficult pipelining.         * RISC: Software emphasis, uniform instruction set, more registers, easy pipelining.

Machine Language: MIPS

  • Format: 32-bit instructions.
  • Standard Fields:     * Opcode (6 bits): Basic operation.     * rs (5 bits): 1st source register.     * rt (5 bits): 2nd source register.     * rd (5 bits): Destination register.     * shamt (5 bits): Shift amount.     * funct (6 bits): Function selector (specific variant of opcode).
  • Instruction Types:     * R-type (Register): op, rs, rt, rd, shamt, funct.     * I-type (Immediate): op, rs, rt, address/immediate.     * J-type (Jump): op, target address.
  • MIPS Registers (32 bits wide):     * $zero (0): Constant 0.     * v0−v0-v1 (2-3): Function results.     * a0−a0-a3 (4-7): Function arguments.     * t0−t0-t9 (8-15, 24-25): Temporaries.     * s0−s0-s7 (16-23): Saved registers.     * $sp (29): Stack pointer.     * $ra (31): Return address.

CPU Performance and CPI Metric

  • CPI (Cycles Per Instruction): Measures average clock cycles per instruction.     * Formula:         \text{CPI} = \frac{\text{Total Clock Cycles}}{\text{Instruction Count}}     
  • Types of CPI:     * Static CPI: Average cycles based on the instruction set simulation.     * Dynamic CPI: Actual cycles during execution, accounting for real-time changes.
  • Performance Comparison:     * Performance=1Execution Time\text{Performance} = \frac{1}{\text{Execution Time}}     * Speedup=PerformanceAPerformanceB=Execution TimeBExecution TimeA\text{Speedup} = \frac{\text{Performance}_A}{\text{Performance}_B} = \frac{\text{Execution Time}_B}{\text{Execution Time}_A}
  • The CPU Equation:     *         \text{CPU Time} = \text{Instruction Count } (I) \times \text{CPI} \times \text{Clock Cycle Time } (C)     
  • Numerical Example:     * I=10,000,000I = 10,000,000     * CPI=2.5\text{CPI} = 2.5     * Clock Rate=200 MHz→C=1200×106=5×10−9 s\text{Clock Rate} = 200\,MHz \rightarrow C = \frac{1}{200 \times 10^6} = 5 \times 10^{-9}\,s     * CPU Time=107×2.5×5×10−9=0.125 s\text{CPU Time} = 10^7 \times 2.5 \times 5 \times 10^{-9} = 0.125\,s

Datapath Design for Single Clock

  • Concept: Each instruction is completed in exactly one single clock cycle.
  • Five Stages of the Datapath:     1. Instruction Fetch (IF): Obtain instruction from memory via PC.     2. Instruction Decode (ID): Determine action and read registers.     3. Execute (EX): ALU performs computation or comparison.     4. Memory Access (MEM): Handle load/store from data memory.     5. Register Write (WB): Write the result back to the register file.
  • Clock Cycle Timing Calculation:     * Clock cycle time must be ≥\geq delay of the longest instruction path.     * Example: Instruction Memory (200 ps200\,ps) + Reg Read (100 ps100\,ps) + ALU (150 ps150\,ps) + Data Memory (250 ps250\,ps) + Reg Write (50 ps50\,ps)       \approx 750\,ps          * Maximum Frequency (ff)       = \frac{1}{750\,ps} \approx 1.33\,GHz     

Assembler and Symbol Resolution

  • Definition: Software that converts assembly language (mnemonics) into binary machine code.
  • Assembler Implementation (Two-pass Algorithm):     1. Initialization: Create a symbol table and add predefined symbols.         * Predefined Hack Symbols: R0-R15 (mapped to 0-15), SCREEN (16384), KBD (24576), SP, LCL, ARG, THIS, THAT.     2. First Pass: Scan labels (e.g., (LOOP)) and map them to the memory address of the next instruction (line number).     3. Second Pass: Translate instructions. If a variable is encountered (a symbol neither predefined nor a label), assign it a memory address starting at 16.
  • Architecture: Consists of a Parser (reads and parses), Code (generates binary), SymbolTable (handles symbols), and the Assembler Driver.