Computer Architecture & Organisation (IFT222) - Comprehensive Study Guide

Fundamentals of Computer Systems, Architecture, and Organisation

• Definitions of a Computer:

  • Definition 1: A programmable device that stores, retrieves, and processes data.

  • Definition 2: A machine or device that performs processes, calculations, and operations based on instructions provided by a software or hardware program.

  • Definition 3: A sophisticated electronic calculating machine that accepts data, processes according to internally stored instructions, and produces output information.

• Primary Functions of a Computer:

  • Input: Accepting data.

  • Output: Producing resulting information.

  • Processing: Manipulating data through calculations.

  • Storage: Retaining data for future use.

• Basic Components of a Personal Computer (PC):

  • Central Processing Unit (CPU).

  • Memory.

  • Circuit board (Motherboard).

  • Storage.

  • Input/Output (I/O) devices.

• Computer Architecture vs. Computer Organisation:

  • Computer Architecture: Refers to attributes visible to a programmer that have a direct impact on the logical execution of a program. It answers the question: "What does the computer do?"

    • Examples: Instruction set, number of bits for data types, I/O mechanisms, and addressing techniques.

  • Computer Organisation: Refers to the operational units and their interconnections that realize architectural specifications. It answers the question: "How does the computer do it?"

    • Examples: Control signals, interfaces, and memory technology (e.g., whether a multiplication is performed by a special hardware unit or repeated addition).

• Instruction Set Architecture (ISA):

  • The core interface between hardware and software.

  • Defines: Executable instructions, formats (ADD, LOAD, STORE), data types (integer, floating point), registers, and addressing modes.

  • Real-Life Applications: Software compatibility (ARM for mobile, x86 for Windows), OS optimization, and game engine performance.

• System Design Styles:

  • Von Neumann Architecture: Uses a single, shared memory and bus for both program instructions and data. Simple for designers and programmers but can suffer from bottlenecks.

  • Harvard Architecture: Uses separate address spaces and memory buses for instructions and data. Enables simultaneous access (parallelism) and increases security by preventing the execution of data as code.

Data Representation in Digital Computers

• Binary Foundation: Computers use electronic circuits where high voltage represents '1' and low voltage represents '0'.

• Number Systems:

  • Decimal (Base 10): Digits 0–9. Positional notation based on powers of 10.

  • Binary (Base 2): Digits (bits) 0 and 1. Positional notation based on powers of 2. Eight bits equals one Byte.

  • Hexadecimal (Base 16): Symbols 0–9 and A–F (where A=10, B=11, C=12, D=13, E=14, F=15). Used as a compact shorthand for binary (1 hex digit = 4 binary bits).

  • Octal (Base 8): Digits 0–7.

• Base Conversion Methods:

  • Decimal to Base $r$: Repeatedly divide the integer by $r$ and collect remainders in reverse order. For fractions, repeatedly multiply by $r$ and collect the integer parts in order.

  • Hex to Binary: Replace each hex digit with its 4-bit binary equivalent (e.g., $A3H = 10100011B$).

  • Binary to Hex: Group bits in fours starting from the right and replace with the corresponding hex digit.

  • Base $r$ to Decimal: Use positional expansion: $d_{n-1} \times r^{n-1} + ... + d_0 \times r^0$.

• Integer Representation:

  • Unsigned Integers: Represent 0 and positive values. Range for $n$ bits: $0$ to $2^n - 1$.

  • Signed Integers: Represent positive, negative, and zero. The most-significant bit (msb) is the sign bit (0 for positive, 1 for negative).

    • Sign-Magnitude: The first bit is the sign; the rest is the magnitude. Drawback: Two representations of zero ($+0$ and $-0$).

    • 1's Complement: For negative numbers, invert all bits of the positive magnitude. Drawback: Two representations of zero.

    • 2's Complement: Standard in modern systems. For negative numbers, invert all bits of the positive magnitude and add 1. Benefit: Single representation of zero; subtraction is performed using addition logic.

• Overflow and Underflow:

  • Overflow: Occurs when an arithmetic result is too large for the allocated bits (e.g., $127 + 2 = 129$ in an 8-bit signed system results in a negative number, signalling an error).

  • Underflow: Occurs in floating-point operations when the result is too close to zero to be represented.

Floating Point and Other Data Representations

• Floating Point Notation: Represented as $F \times r^E$, where $F$ is the mantissa (fraction), $r$ is the radix, and $E$ is the exponent.

• IEEE-754 Standards:

  • 32-bit Single-Precision: 1 sign bit, 8 exponent bits (excess-127 bias), 23 fraction bits. $N = (-1)^S \times 1.F \times 2^{E-127}$.

  • 64-bit Double-Precision: 1 sign bit, 11 exponent bits (excess-1023 bias), 52 fraction bits. $N = (-1)^S \times 1.F \times 2^{E-1023}$.

  • Denormalized Form: Used when the exponent is all zeros to represent numbers very close to zero.

• Binary Coded Decimal (BCD): Each decimal digit is represented by a 4-bit binary group. Types include 8421, 5421, and 4221 (weights). Example: Decimal 9.2 in 8421 BCD is $1001.0010$.

• Excess-3 Code: A non-weighted, self-complementing code. Calculated by adding 3 to each decimal digit and converting to binary. Useful for arithmetic.

• Alphanumeric Representations:

  • ASCII: 7-bit code (128 characters) for unique text representation.

  • EBCDIC: 8-bit character encoding used mainly by IBM mainframes.

  • Unicode: Modern standard for global text representation.

Instruction Set Architecture (ISA) Details

• Basic Instruction Types:

  • Load/Store: Moving data between registers and memory (Source remains unchanged; destination is updated).

  • Arithmetic/Logic: Performing tasks like ADD, SUB, AND, OR, XOR.

  • Test/Branch: Decision-making using condition codes (Zero, Carry, Negative).

• Instruction Formats:

  • Opcode: Specifies the operation.

  • Address/Operand: Indicates data or location.

  • Mode Field: Specifies how the effective address is generated.

• CPU Organization Styles:

  • Single Accumulator: Uses one implied register (AC) for all operations. Instruction: $ADD\,X$ means $AC \leftarrow AC + M[X]$.

  • General Register: Uses multiple registers. Can be 2-address ($ADD\,R1, R2$) or 3-address ($ADD\,R1, R2, R3$).

  • Stack-Based: Uses Last-In-First-Out (LIFO). Operations (PUSH/POP) occur at the top of the stack. computational instructions like ADD use no address (zero-address).

• Addressing Modes:

  • Immediate: The operand is a constant within the instruction.

  • Direct: The address field contains the actual memory address.

  • Indirect: The address field points to a memory location containing the effective address.

  • Register: The operand is in a specified register.

  • Register Indirect: The register contains the address of the operand.

  • Relative: Effective address = $PC + constant$.

  • Indexed: Effective address = $Index\,Register + constant$.

Processor Design and Internal Components

• Major CPU Components:

  • Registers: Small, high-speed storage. Includes General Purpose (GPRs) and Special Purpose (PC, IR, MAR, MDR, ACC, Flag/Status).

  • Arithmetic Logic Unit (ALU): Performs calculations and comparisons.

  • Control Unit (CU): Generates timing and control signals.

• Control Unit Implementations:

  • Hardwired Control: Uses fixed logic gates and decoders. Very fast but inflexible; typical of RISC.

  • Microprogrammed Control: Control signals are stored as "microcode" in control memory. Slower but highly flexible and easier to update; typical of CISC.

• Instruction Cycle Phases:

  1. Fetch: Get instruction from memory address in PC; increment PC.

  2. Decode: CU interprets the opcode.

  3. Execute: ALU performs operation.

  4. Memory Access: Load/Store if required.

  5. Write Back: Result stored in register/memory.

CPU Performance Metrics

• Clock Speed (Rate): Cycles per second (Hz). $Clock\,Period = \frac{1}{Clock\,Speed}$.

• CPUTime Formulas:

  • $CPU\,Time = \frac{Total\,Clock\,Cycles}{Clock\,Speed}$

  • $CPU\,Time = Instruction\,Count \times CPI \times Clock\,Cycle\,Time$

• Cycles Per Instruction (CPI): Average cycles to execute one instruction. $CPI = \frac{Total\,Cycles}{Instruction\,Count}$.

• MIPS (Millions of Instructions Per Second): Raw instruction rate. $MIPS = \frac{Instruction\,Count}{Execution\,Time \times 10^6}$.

• Benchmarking Suites: SPEC (CPU/int/fp), TPC (Database), LINPACK (Floating-point world rankings).

• Amdahl's Law: Predicts maximum speedup when only part of a system is improved.

  • $S = \frac{1}{(1 - P) + (P / k)}$ where $P$ is the parallelizable fraction and $k$ is the speedup factor.

Pipelining Concepts and Hazards

• Definition: Rearranging hardware to increase throughput by overlapping instruction execution phases.

• RISC 5-Stage Pipeline: Instruction Fetch (IF) $\rightarrow$ Instruction Decode (ID) $\rightarrow$ Execute (EX) $\rightarrow$ Memory Access (MEM) $\rightarrow$ Write Back (WB).

• Pipeline Performance Formulas:

  • $Total\,Time = (k + (n - 1)) \times t_p$, where $k$ = stages, $n$ = tasks, $t_p$ = clock cycle time.

  • $Speedup = \frac{Non-pipelined\,Time}{Pipelined\,Time}$.

• Pipeline Hazards:

  • Structural Hazard: Hardware resource conflict (e.g., two instructions needing memory at once). Solution: Register renaming or separating code and data memory.

  • Control Hazard (Branch Hazard): Caused by delay in knowing branch targets. Solution: Branch prediction or delay slots.

  • Data Hazard: Dependency on a result not yet written.

    • RAW (Read After Write): Most common. Solution: Operand Forwarding (bypassing).

    • WAR (Write After Read): Anti-dependency.

    • WAW (Write After Write): Output dependency.

Computer Memory Organisation

• Memory Hierarchy:

  1. Registers: Fastest, smallest, most expensive (inside CPU).

  2. Cache: High speed (DRAM/SRAM mix).

  3. Main Memory: Medium speed, larger capacity (DRAM).

  4. Secondary Storage: Slowest, largest, cheapest (HDD/SSD/Tape).

• Access Methods:

  • Sequential: Linear sequence (Tape).

  • Direct: Reaches general vicinity, then searches (Hard Disk).

  • Random: Constant access time regardless of location (RAM/ROM).

  • Associative: Retrieval based on content match rather than address (Cache).

• Semiconductor Memory Types:

  • DRAM (Dynamic RAM): Stores data as charge on capacitors; requires periodic refreshing; high density; used for main memory.

  • SRAM (Static RAM): Uses flip-flop logic; faster; no refresh needed; used for cache.

  • ROM (Read-Only Memory): Non-volatile.

    • PROM: Programmable once.

    • EPROM: Erasable via UV light.

    • EEPROM: Electrically erasable.

    • Flash Memory: Erases in blocks; used in USB/SSDs.

• Cache Mapping Functions:

  • Direct Mapping: Each memory block maps to exactly one cache line ($i = j\,mod\,m$). Causes conflict thrashing.

  • Associative Mapping: Block can reside in any cache line. Requires complex tag searching.

  • Set-Associative Mapping: Combines both; block maps to a specific set of lines.

Advanced Processor Architectures

• RISC (Reduced Instruction Set Computer):

  • Emphasis on software/compiler.

  • Small, fixed-length instructions (32-bit).

  • One-cycle execution; highly pipelined.

  • Large register set; Hardwired control.

  • Examples: ARM, MIPS, SPARC.

• CISC (Complex Instruction Set Computer):

  • Emphasis on hardware.

  • Large, variable-length instructions.

  • Complex multi-step instructions; Microprogrammed control.

  • Memory-to-memory operations.

  • Examples: Intel x86, VAX, IBM 370.

• Parallel Processing Models (Flynn’s Taxonomy):

  • SISD: Single instruction, single data (Traditional PC).

  • SIMD: Single instruction, multiple data (Vector processors, GPUs).

  • MISD: Multiple instruction, single data (Fault-tolerant systems).

  • MIMD: Multiple instruction, multiple data (Multi-core, Distributed systems).

• Network Topologies:

  • Mesh: Grid arrangement.

  • Ring: Circular loop.

  • Star: Central hub nodes.

  • Hypercube: Multi-dimensional cube; efficient for high-scale communication.

Questions and Discussion

In-Text Questions & Answers

• Q: Why are registers faster than main memory?

  • A: They are located inside the CPU and use faster circuitry, whereas main memory requires bus communication.

• Q: Why is microprogrammed control more flexible?

  • A: Its behavior is defined by microprograms in memory, which can be modified without changing hardware.

• Q: What happens if an arithmetic operation exceeds register size?

  • A: An overflow flag is set in the status register.

• Q: Why is MIPS a misleading metric?

  • A: It ignores instruction complexity and varies across architectures.

• Q: Difference between ASCII and EBCDIC?

  • A: ASCII is 7-bit and globally standardized; EBCDIC is 8-bit and specific to IBM mainframes.

• Q: Why use the 2’s complement?

  • A: It eliminates the double zero representation and allows the same hardware logic for addition and subtraction.

• Q: What is the primary focus of computer architecture?

  • A: Functional behavior and logical design visible to the programmer.

Self-Assessment Tasks

• Problem: Convert 18.6875 to Binary.

  • Steps: $18D = 10010B$. For $.6875$: $.6875 \times 2 = 1.375$ (1), $.375 \times 2 = 0.75$ (0), $.75 \times 2 = 1.5$ (1), $.5 \times 2 = 1.0$ (1). Result: $10010.1011B$.

• Problem: IEEE-754 Single Precision.

  • Given: Pattern $0\,10000000\,110...$.

  • S=0 (Positive). E=128 ($128 - 127 = 1$). Fraction = 1.11 (binary) = 1.75. Result: $+1.75 \times 2^1 = +3.5D$.