Computer Organization and Architecture with MIPS

Introduction to Computer Organization and Hardware Fundamentals

• Under-the-Hood Architectural Knowledge:

  • Understanding the internal mechanics of a computer system is analogous to a driver understanding automobile mechanics (the four-cycle engine, distributor, and electrical system); although one can drive without it, the knowledge allows rapid diagnosis of failures and empowers software professionals to produce significantly more efficient code.
  • George Neville-Neil addressed the necessity of hardware awareness among software professionals in the Kode Vicious column of the March/April 2021 issue of ACM Queue.
  • The MIPS (Microprocessor without Interlocked Pipeline Stages) architecture serves as a primary model because it is simple enough to understand and program while possessing sufficient sophistication for real-world devices such as embedded systems, routers, and video game consoles.

• Digital Nature of Computer Devices:

  • Modern digital hardware stores and manipulates solely binary values: zeros ($0$) and ones ($1$).
  • All forms of data—including whole numbers, floating point numbers, textual keyboard characters, digital sound, and raster images—are composed of sequences of binary digits (bits).
  • This principle applies universally to desktop computers, laptops, tablets, smartphones, digital cameras, audio players, gaming consoles, and embedded controllers found in automobiles, medical appliances, and home equipment.

• The Central Processing Unit (CPU):

  • Computations and programmatic decisions governing instruction execution sequences occur within the CPU.
  • The primary hardware blocks of a CPU comprise registers, an arithmetic logic unit (ALU), a control unit, and internal interconnections (buses and discrete wires).
  • Registers: Dedicated, ultra-fast internal memory storage elements. While accessing random access memory (RAM) can be over $1000\times$ slower than accessing CPU hardware, registers provide single-cycle data availability.
  • In the MIPS architecture, general registers are $32\text{ bits}$ wide (one full word) and number $32$ in total (designated $0$ through $31$). Register $0$ ($\$zero$) is hardwired to all zeros ($00000000_{16}$) and cannot be modified.
  • Program Counter ($PC$): A specialized, non-programmable CPU register storing the memory address of the next instruction to be fetched and executed.
  • Datapath: The internal collective assembly of components through which data flows and is manipulated: the general register file, memory interfaces, ALU, $PC$, control unit, and the routing buses.

• Main Memory (Random Access Memory - RAM):

  • Main memory serves as proximate storage for active program code and working variables (such as numerical arrays).
  • Each byte in the memory space possesses a unique sequential numerical address; memory is thus byte-addressable.
  • A MIPS full word consists of $4\text{ bytes}$ ($32\text{ bits}$). Consecutive word addresses in MIPS memory differ by $4$ (for example, address $4024_{10}$ is immediately followed by word address $4028_{10}$).
  • Memory is volatile: it requires uninterrupted electrical power to retain binary states. Sudden interruption of electricity empties all stored states, causing immediate data loss.

• Peripheral Storage and Input/Output Devices:

  • Non-volatile Storage: Devices capable of retaining data without continuous electrical supply.
  • Magnetic Disks: Fixed (internal hard drives) or removable rotating platters holding the operating system, applications, and persistent data files.
  • Optical Disks: Removable media read and written via lasers (CD, CD-ROM, DVD); data written to optical discs is typically permanent.
  • Flash Memory: Solid-state semiconductor storage with no moving mechanical components (USB flash drives, thumb drives, internal non-removable solid-state drives in mobile devices).
  • Input and Output Classification (Memory Perspective):
  • Input: Data transfer directed into main memory from an external device (keyboards, mice, joysticks).
  • Output: Data transfer directed outward from main memory to an external device (printers, audio speakers).
  • Bidirectional / Memory-Mapped: Monitors display content continuously from a designated memory block (memory-mapped video); network interfaces (Ethernet, Wi-Fi) and USB ports exchange data in both directions.

• Software Abstraction Hierarchy:

  • Machine Language: The fundamental binary-encoded instruction sequence ($0$s and $1$s) directly decoded by the CPU. Instructions specify basic operation codes and register or memory operand addresses.
  • Assembly Language: A human-readable low-level symbolic representation where operations appear as textual mnemonics (e.g., add, sub) and memory locations use symbolic alphanumeric labels.
  • Assembler: Specialized systems software (such as the Missouri State University MARS simulator) that translates symbolic assembly language source programs into executable binary machine code.
  • High-Level Programming Languages: Languages (Java, C++, Visual Basic, Python) allowing compound operational expressions (e.g., $a \times 32 + b \times 8$) within a single statement, requiring compilation via a compiler into machine language.
  • Operating System (OS): Core software managing computational resources. Key duties include processor time multiplexing across concurrent tasks, managing access to peripheral devices, supervising the permanent filesystem, and expanding physical memory through virtual memory mechanisms. Modern examples include Microsoft Windows, Apple macOS, Linux, Android, and Apple iOS.

Number Systems, Positional Bases, and Representation Schemes

• Positional Number Representation:

  • Positional number systems, attributed historically to ninth-century Hindu and Arab mathematicians, represent quantities as polynomials of a chosen base $b$:     $\text{Value} = \sum_{i=0}^{n-1} d_i \times b^i$
  • In base $10$ (decimal), digits range from $0$ to $9$. In base $2$ (binary), numerals are restricted to $0$ and $1$. In base $8$ (octal), numerals range from $0$ to $7$. In base $16$ (hexadecimal), numerals include $0$ through $9$ augmented by $a=10$, $b=11$, $c=12$, $d=13$, $e=14$, and $f=15$.

• Binary Arithmetic Operations:

  • Addition rules:
  • $0_2 + 0_2 = 0_2$
  • $0_2 + 1_2 = 1_2$
  • $1_2 + 0_2 = 1_2$
  • $1_2 + 1_2 = 10_2$ ($0$ with carry-out of $1$ to the next higher positional column)
  • $1_2 + 1_2 + 1_2 = 11_2$ ($1$ with carry-out of $1$)
  • Subtraction rules:
  • $0_2 - 0_2 = 0_2$
  • $1_2 - 1_2 = 0_2$
  • $1_2 - 0_2 = 1_2$
  • $0_2 - 1_2 = 1_2$ after borrowing $1_2$ from the immediately adjacent high-order column (a borrowed $1$ becomes a value of $2_{10}$ in the current column).

• Octal and Hexadecimal Bit Grouping:

  • Base $8$ groups binary strings into clusters of $3\text{ bits}$ ($2^3 = 8$). When translating binary strings whose total length is not a multiple of $3$, extra bits remain on the high-order (leftmost) end.
  • Base $16$ groups binary strings into clusters of $4\text{ bits}$ ($2^4 = 16$). Any leftover bits reside on the leftmost (most significant) boundary.
  • Hexadecimal numbers are formally annotated with a base subscript ($321_{16}$ or $321_x$) or an assembly prefix (0x321).
  • In the MIPS architecture, breaking down instructions formatted across fields of lengths $6, 5, 5, 5, 5, 6$ bits requires tracking partial-hex boundaries: each $5\text{-bit}$ or $6\text{-bit}$ field requires two hexadecimal characters when isolated, but regroups into eight uniform 4-bit nibbles when viewed as a composite $32\text{-bit}$ word.

• Twos Complement Representation of Signed Integers:

  • Used across contemporary processor architectures to unify integer addition and subtraction hardware regardless of operand signs.
  • The most significant bit (MSB) acts as the sign bit: a leading $0$ indicates non-negative values; a leading $1$ indicates negative values.
  • For an $n\text{-bit}$ register word, the representable signed range is:     $-2^{n-1} \text{ to } 2^{n-1} - 1$
  • In a $4\text{-bit}$ space, the range is $-8$ ($1000_2$) to $+7$ ($0111_2$); zero is $0000_2$; negative one ($-1$) is represented by all ones ($1111_2$).
  • An automotive mechanical odometer illustrates twos complement: rolling a brand-new odometer reading of $000000$ backward by one mile rolls the digits over to $999999$, representing $-1$.
  • Negation (Complement) Algorithms:
  1. Subtraction from Zero: Compute $-x = 0 - x$, assuming an implied high-order borrow.
  2. Inversion plus One: Form the ones complement by flipping every bit ($0 \rightarrow 1$, $1 \rightarrow 0$) and add $1$ to the result ($-x = \sim x + 1$).
  3. Right-to-Left Bit Inspection: Scan bits from right to left (least significant to most significant); replicate all zeros until the first $1$ is encountered; copy that first $1$ unchanged; complement all remaining bits to the left.

• Powers of Two and Standard Prefixes:

  • Memorized baseline powers:
  • $2^0 = 1$
  • $2^1 = 2$
  • $2^2 = 4$
  • $2^3 = 8$
  • $2^4 = 16$
  • $2^5 = 32$
  • $2^6 = 64$
  • $2^7 = 128$
  • $2^8 = 256$
  • $2^9 = 512$
  • $2^{10} = 1024 = 1\text{K}$
  • Multiplicative binary scales (capitalized to distinguish from decimal prefixes):
  • $1\text{K} = 2^{10} = 1024$
  • $1\text{M} = 2^{20} = 1,048,576$
  • $1\text{G} = 2^{30} = 1,073,741,824$
  • $1\text{T} = 2^{40} = 1,099,511,627,776$
  • The magnitude of $2^n$ up to $2^{49}$ is calculated mentally: the tens digit determines the prefix ($1=\text{K}, 2=\text{M}, 3=\text{G}, 4=\text{T}$) and the units digit determines the numerical multiplier ($2^0=1, 2^1=2, 2^2=4, 2^3=8$). For example, $2^{38} = 256\text{G}$.
  • Fundamental exponent laws apply directly:
  • $x^y \times x^z = x^{y+z}$
  • $x^y / x^z = x^{y-z}$
  • $(x^y)^z = x^{y \times z}$

MIPS Assembly Language Programming

• General CPU Register Allocations and Conventions:

  • General registers store $32\text{-bit}$ values and are accessed by number ($0 to $31) or by predefined symbolic functional names:
  • $zero$ ($0): Hardwired constant $0$.
  • $at$ ($1): Assembler temporary, reserved exclusively for synthetic pseudo-operation translation.
  • $v0 - \$v1$ ($2 - $3): Subprogram expression evaluation and return values.
  • $a0 - \$a3$ ($4 - $7): Subprogram input arguments/parameters.
  • $t0 - \$t7$ ($8 - $15): Temporary registers; not preserved across subprogram calls.
  • $s0 - \$s7$ ($16 - $23): Saved temporary registers; must be preserved and restored by called functions.
  • $t8 - \$t9$ ($24 - $25): Additional temporary registers.
  • $k0 - \$k1$ ($26 - $27): Reserved for operating system kernel trap handling.
  • $gp$ ($28): Global pointer for static data addressing.
  • $sp$ ($29): Stack pointer referencing the runtime call stack boundary.
  • $fp$ ($30): Frame pointer referencing local subroutine activation frames.
  • $ra$ ($31): Function return address loaded during execution of jump and link.

• Assembly Language Syntax:

  • Statements follow the canonical syntax: assembly [label:] mnemonic operand, operand, operand [# comment]     
  • Labels provide symbolic branch and data anchors. Mnemonics identify target machine operations. Operands represent registers, immediate numerical constants, or symbolic memory targets. Comments begin with # and continue to the end of the line.

• Core R-Format Arithmetic Instructions:

  • add $rd, $rs, $rt</code>: Computes <code>Reg[$rd] = Reg[$rs] + Reg[$rt]. Trailing overflows trigger hardware exceptions in twos complement.
  • sub $rd, $rs, $rt</code>: Computes <code>Reg[$rd] = Reg[$rs] - Reg[$rt] via twos complement addition of the negated operand: Reg[$rs] + (~Reg[$rt] + 1).
  • slt $rd, $rs, $rt</code>: Set If Less Than. Sets <code>Reg[$rd] = 1 if Reg[$rs] < Reg[$rt] under signed comparison; otherwise sets Reg[$rd] = 0.

• Bitwise Logical Instructions:

  • and $rd, $rs, $rt</code>: Bitwise logical AND (<code>Reg[$rd] = Reg[rs] & Reg[rt]).
  • or $rd, $rs, $rt</code>: Bitwise logical inclusive OR (<code>Reg[$rd] = Reg[$rs] | Reg[$rt]).
  • xor $rd, $rs, $rt</code>: Bitwise logical exclusive OR (<code>Reg[$rd] = Reg[$rs] ^ Reg[$rt]).
  • nor $rd, $rs, $rt</code>: Bitwise logical NOR (<code>Reg[$rd] = ~(Reg[$rs] | Reg[$rt])).
  • not $rd, $rs: Bitwise complement pseudo-op implemented as nor $rd, $rs, $zero based on the identity ~x = ~(x | 0).
  • Bit Masking Techniques:
  • Clearing bits: Bitwise AND with a mask having zeros at target bit locations (x & 0 = 0, x & 1 = x).
  • Setting bits: Bitwise OR with a mask having ones at target bit locations (x | 1 = 1, x | 0 = x).
  • Inverting bits: Bitwise XOR with a mask having ones at target bit locations (x ^ 1 = ~x, x ^ 0 = x).
  • Symmetric Cryptography Identity: k ^ m ^ k = m enables reversible encryption and decryption via a secret key mask k.

• Shift Operations:

  • sll $rd, $rt, shamt: Shift Left Logical. Moves bits left by shamt positions, shifting in zeros at the least significant bits. Shifting left by $n$ positions performs integer multiplication by $2^n$.
  • srl $rd, $rt, shamt: Shift Right Logical. Moves bits right by shamt positions, inserting zeros at the most significant bit. Treats registers as unsigned.
  • sra $rd, $rt, shamt: Shift Right Arithmetic. Moves bits right by shamt positions, copying the original MSB (sign bit) into vacated high-order bit positions, preserving signed integrity for division by $2^n$ (valid integer division provided no active ones are discarded).

• Immediate Format Instructions and Pseudo-Operations:

  • addi $rt, $rs, constant: Adds a signed $16\text{-bit}$ immediate value (range $-32,768$ to $+32,767$) to register $rs</code>, storing the result in <code>$rt. Sign-extends the immediate operand to $32\text{ bits}$.
  • Subtraction with a constant is executed using negative constants in addi (e.g., addi $a0, $a0, -3).
  • andi $rt, $rs, constant: Zero-extends the 16-bit constant and performs bitwise AND.
  • ori $rt, $rs, constant: Zero-extends the 16-bit constant and performs bitwise OR.
  • xori $rt, $rs, constant: Zero-extends the 16-bit constant and performs bitwise XOR.
  • lui $rt, constant: Load Upper Immediate. Loads a 16-bit constant into bit positions $16..31$ of $rt, clearing bits $0..15$ to zero.
  • li $rd, constant: Load Immediate pseudo-operation. Translated to addi $rd, $zero, constant for 16-bit values. For $32\text{-bit}$ values (e.g., 0x00010003), the assembler expands it into two operations: assembly lui $at, 0x0001 ori $at, $at, 0x0003     
  • move $rd, $rs: Pseudo-operation to duplicate register content, translated to add $rd, $rs, $zero (or addu).

• Memory Reference and Assembler Directives:

  • .text: Directs the assembler to place following code within the instruction memory area.
  • .data: Directs the assembler to allocate following elements into contiguous data segment memory (starting at address 0x10010000 in MARS).
  • Allocation types: .word ($32\text{-bit}$ signed integer), .byte ($8\text{-bit}$ integer), .float ($32\text{-bit}$ single-precision float), .double ($64\text{-bit}$ double-precision float), .ascii (character string), .asciiz (null-terminated character string), .space n (allocates an uninitialized buffer of $n\text{ bytes}$).
  • lw $rt, label / lw $rt, imm($rs): Load Word. Retrieves a $32\text{-bit}$ memory value into register $rt</code>. The memory address equals <code>Reg[$rs] + imm.
  • sw $rt, label / sw $rt, imm($rs): Store Word. Writes $32\text{-bit}$ value from $rt</code> into the memory address <code>Reg[$rs] + imm.
  • la $rd, label: Load Address pseudo-op. Loads the calculated $32\text{-bit}$ effective memory address of label into $rd</code> via <code>lui</code> and <code>ori</code> targeting <code>$at.

• Transfer of Control Architecture:

  • Conditional Branching:
  • beq $rs, $rt, label: Branch to label if Reg[$rs] == Reg[$rt].
  • bne $rs, $rt, label: Branch to label if Reg[$rs] != Reg[$rt].
  • Pseudo-branches (blt, ble, bgt, bge) expand to combinations of slt using register $at followed by beq or bne:
    • blt $rs, $rt, dest expands to slt $at, $rs, $rt then bne $at, $zero, dest.
    • ble $rs, $rt, dest expands to slt $at, $rt, $rs then beq $at, $zero, dest.
    • bgt $rs, $rt, dest expands to slt $at, $rt, $rs then bne $at, $zero, dest.
    • bge $rs, $rt, dest expands to slt $at, $rs, $rt then beq $at, $zero, dest.
  • Unconditional Jumps:
  • j label: Absolute jump to label.
  • jal label: Jump and Link. Writes the address of the immediately sequential instruction (PC + 4) into return register $ra$ ($31) and jumps to label.
  • jr $rs</code>: Jump Register. Sets <code>PC = Reg[$rs]; typically jr $ra to return from subroutines.
  • Control Flow Patterns:
  • One-way Selection (if): Evaluates condition; conditionally branches around the conditional block to a forward label if false.
  • Two-way Selection (if-else): Evaluates condition; conditionally branches to the else block if false; the if block concludes with an unconditional jump (j) to bypass the else block.
  • Pretest Loops (while): Condition evaluated at the loop head via conditional branch jumping beyond the loop body if false; ends with unconditional jump (j) back to the header.
  • Posttest Loops (do-while): Loop body executes at least once; ends with a conditional branch evaluating loop continuation criteria and jumping back to the head if true.

• Subroutines, Register Conventions, and the Runtime Stack:

  • Calling convention rules specify responsibility for register preservation:
  • Subroutine input arguments pass via $a0 - \$a3$.
  • Output values return via $v0 - \$v1$.
  • Local preserved registers $s0 - \$s7$ must be saved by the called function prior to modification and restored before return.
  • Temporary registers $t0 - \$t9$ must be preserved by the calling function if needed across the call.
  • Subroutines making nested or recursive calls must save the return address $ra$ onto the runtime stack.
  • The Call Stack:
  • A LIFO data structure growing downwards toward lower memory addresses.
  • The stack pointer $sp$ holds the address of the current top of the stack.
  • Push operation: Decrements $sp$ by $4\text{ bytes}$ per register, then stores values: assembly addi $sp, $sp, -4 sw $ra, 0($sp)       

• Pop operation: Loads values from current stack positions, then increments $sp$: assembly lw $ra, 0($sp) addi $sp, $sp, 4       

  • Modular Scope and Name Conflicts: To eliminate label collision when combining distinct subprogram files, internal labels are explicitly scoped by appending function-specific suffixes (e.g., lp_strlen, done_strcmp).

• Character and String Processing:

  • Strings reside in memory as contiguous arrays of one-byte ASCII characters, terminated by an ending null byte (0x00).
  • lbu $rt, imm($rs): Load Byte Unsigned. Loads an $8\text{-bit}$ byte from memory into bits $0..7$ of $rt, filling bits $8..31$ with zeros.
  • sb $rt, imm($rs): Store Byte. Writes bits $0..7$ of register $rt into the designated byte memory address.
  • When stepping through characters of a string, memory pointers increment by $1\text{ byte}$, unlike word arrays which increment by $4\text{ bytes}$.

• Multiplication and Division Systems:

  • Multiplying two $32\text{-bit}$ integers can produce a product up to $64\text{ bits}$ long.
  • The MIPS CPU incorporates dedicated hardware registers: HI (storing the upper $32\text{ bits}$) and LO (storing the lower $32\text{ bits}$).
  • mult $rs, $rt: Signed multiplication; product deposited into {HI, LO}.
  • multu $rs, $rt: Unsigned multiplication.
  • mfhi $rd</code>: Move from <code>HI</code> into register <code>$rd.
  • mflo $rd</code>: Move from <code>LO</code> into register <code>$rd.
  • div $rs, $rt: Signed division. Computes integer quotient Reg[$rs] / Reg[$rt] into LO, and integer remainder Reg[$rs]$rt] into HI.
  • divu $rs, $rt: Unsigned division.
  • Software algorithms for platforms lacking hardware multipliers/dividers include repeated addition/subtraction, or optimized binary shift-and-add / shift-and-subtract methods processing one bit per step across 32 iterations.

• Floating Point Computing (Coprocessor 1):

  • MIPS manages floating point values via a distinct subsystem: Coprocessor 1.
  • Features $32$ independent $32\text{-bit}$ floating point registers named $f0</code> to <code>$f31. For double-precision ($64\text{-bit}$) calculations, registers pair into even-odd groupings (e.g., $f0</code> and <code>$f1, $f2</code> and <code>$f3).
  • Single-precision operations carry a .s suffix; double-precision operations carry a .d suffix.
  • Arithmetic instructions: add.s, sub.s, mul.s, div.s (format: add.s $fd, $fs, $ft).
  • Transfer operations: mov.s $fd, $fs, lwc1 $ft, imm($rs), swc1 $ft, imm($rs).
  • Comparisons set an internal 1-bit floating-point condition code flag (cc):
  • c.eq.s $fs, $ft: Sets cc = 1 if $fs == $ft, else 0.
  • c.lt.s $fs, $ft: Sets cc = 1 if $fs < $ft, else 0.
  • c.le.s $fs, $ft: Sets cc = 1 if $fs <= $ft, else 0.
  • Conditional branching inspects the condition code:
  • bc1t label: Branches if condition code is true (1).
  • bc1f label: Branches if condition code is false (0).
  • Type conversions: cvt.s.w $fd, $fs (converts integer word to float); cvt.w.s $fd, $fs (truncates float to integer word via floor). Rounding to the nearest integer is implemented by adding 0.5 prior to applying cvt.w.s.

• System Calls via MARS (syscall):

  • Invoked by writing a service code into register $v0$ and executing syscall:
  • $v0 = 1$: Print Integer (argument passed in $a0$).
  • $v0 = 2$: Print Float (argument passed in $f12$).
  • $v0 = 4$: Print String (pointer address passed in $a0$).
  • $v0 = 5$: Read Integer (input integer returned in $v0$).
  • $v0 = 6$: Read Float (input float returned in $f0$).
  • $v0 = 8$: Read String (buffer address passed in $a0$, maximum character length in $a1$).
  • $v0 = 10$: Exit / Terminate program execution normally.

MIPS Machine Language Formats and Encoding

• Primary Instruction Word Formats:

  • Every MIPS instruction occupies exactly one $32\text{-bit}$ full word divided into standardized functional fields.
  • Register (R) Format:
  • Bit range $31..26$ ($6\text{ bits}$): opcode (always 0x00 for standard R-format arithmetic/logical operations).
  • Bit range $25..21$ ($5\text{ bits}$): rs (source register identifier, $0..31$).
  • Bit range $20..16$ ($5\text{ bits}$): rt (second source operand register, $0..31$).
  • Bit range $15..11$ ($5\text{ bits}$): rd (destination register receiving result, $0..31$).
  • Bit range $10..6$ ($5\text{ bits}$): shamt (shift amount, values $0..31$).
  • Bit range $5..0$ ($6\text{ bits}$): funct (function code distinguishing specific operations under opcode = 0).
  • Ordering caveat: Assembly statements specify operands in the sequence $rd, $rs, $rt, whereas binary machine words encode them in the sequence rs, rt, rd.
  • Immediate (I) Format:
  • Bit range $31..26$ ($6\text{ bits}$): opcode.
  • Bit range $25..21$ ($5\text{ bits}$): rs (base address register or first source register).
  • Bit range $20..16$ ($5\text{ bits}$): rt (destination register for loads/immediate operations, or source register for stores).
  • Bit range $15..0$ ($16\text{ bits}$): immediate (numerical constant, address displacement, or relative branch displacement).
  • Ordering caveat: Assembly statements specify $rt, $rs, imm, whereas binary machine words place rs before rt.
  • Jump (J) Format:
  • Bit range $31..26$ ($6\text{ bits}$): opcode (0x02 for j, 0x03 for jal).
  • Bit range $25..0$ ($26\text{ bits}$): address (target absolute word address).

• Encoding Operations and Opcode/Function Specifications:

  • R-Format Functions (opcode = 0x00):
  • add: funct = 0x20
  • sub: funct = 0x22
  • and: funct = 0x24
  • or: funct = 0x25
  • xor: funct = 0x26
  • nor: funct = 0x27
  • slt: funct = 0x2a
  • sll: funct = 0x00 (rs unused/don't care)
  • srl: funct = 0x02 (rs unused/don't care)
  • sra: funct = 0x03 (rs unused/don't care)
  • mult: funct = 0x18 (rd and shamt unused)
  • div: funct = 0x1a (rd and shamt unused)
  • mfhi: funct = 0x10 (rs, rt, shamt unused)
  • mflo: funct = 0x12 (rs, rt, shamt unused)
  • jr: funct = 0x08 (rt, rd, shamt unused)
  • I-Format Opcodes:
  • addi: opcode = 0x08
  • andi: opcode = 0x0c
  • ori: opcode = 0x0d
  • xori: opcode = 0x0e
  • lui: opcode = 0x0f (rs unused)
  • lw: opcode = 0x23
  • sw: opcode = 0x2b
  • lbu: opcode = 0x24
  • sb: opcode = 0x28
  • beq: opcode = 0x04
  • bne: opcode = 0x05
  • lwc1: opcode = 0x31
  • swc1: opcode = 0x39

• Branch and Jump Address Calculations:

  • Conditional Branch Offsets:
  • Branches use relative word offsets from the instruction following the branch statement (PC + 4).
  • Because all instructions occupy $4\text{ bytes}$ (word-aligned), the lowest two bits of an instruction byte address are always 00 and are dropped.
  • Formula:       $\text{Immediate Field} = \frac{\text{Target Address} - (\text{Branch Address} + 4)}{4}$
  • Forward branches yield positive offsets; backward branches yield negative offsets (represented in 16-bit twos complement).
  • Jump Target Addresses:
  • J-format instructions hold a 26-bit absolute word field.
  • Formula:       $\text{Address Field} = \frac{\text{Absolute Target Byte Address}}{4} = \text{Target Address}[27..2]$
  • When executed, the CPU concatenates the high-order 4 bits of the current PC with the 26-bit field shifted left by 2 positions (00 appended at the bottom):       $\text{New PC} = (\text{PC}[31..28]) \;\Vert\; (\text{Address} \times 4)$

• Floating Point Instruction Formats:

  • Floating Point Register (FR) Format:
  • Bit range $31..26$: opcode = 0x11 (17 decimal, denoting Coprocessor 1).
  • Bit range $25..21$: fmt (data type: 0x10 specifies single-precision float .s).
  • Bit range $20..16$: ft (source operand register).
  • Bit range $15..11$: fs (second source operand register).
  • Bit range $10..6$: fd (destination register).
  • Bit range $5..0$: funct (0x00 for add.s, 0x01 for sub.s, 0x02 for mul.s, 0x03 for div.s, 0x32 for c.eq.s, 0x3c for c.lt.s, 0x3e for c.le.s).
  • Register order in machine language reverses the assembly syntax: assembly uses $fd, $fs, $ft, while machine code groups ft, fs, fd.
  • Floating Point Immediate (FI) Format:
  • Used for conditional branches (bc1t, bc1f).
  • Bit range $31..26$: opcode = 0x11.
  • Bit range $25..21$: fmt = 0x08.
  • Bit range $20..16$: ft (0x01 for bc1t, 0x00 for bc1f).
  • Bit range $15..0$: immediate (relative target branch word offset).

Architectural Design and Construction of a MIPS Assembler

• Bootstrapping Concept:

  • Bootstrapping is the process of writing an initial rudimentary language translator (assembler or compiler) in a low-level format, and progressively leveraging it to translate richer, more complex versions of itself.

• Structural Evolution across Development Stages:

  • Version 1a: Translates only core R-format instructions with explicit numeric register specifications ($0 to $31). Excludes labels, shift operations, comments, and pseudo-ops. Directs output straight to memory words.
  • Version 1b: Introduces support for symbolic register identifiers ($zero</code>, <code>$t0, $ra) through lookup against a hardcoded string table of 32 names.
  • Version 2a: Incorporates basic I-format (addi, andi, ori) and J-format (j, jal) instructions, plus basic branch instructions (beq, bne). parseInt is enhanced to process optional negative sign flags.
  • Version 2b: Implements a two-pass assembler structure to resolve memory referencing and branch targets:
  • Pass 1: Scans raw source code, identifies symbolic labels, records their memory addresses in a Symbol Table, and converts one-to-one pseudo-operations (move, li) into native machine equivalents within a temporary buffer (basic).
  • Pass 2: Processes the basic buffer, resolves forward and backward label addresses from the Symbol Table, calculates relative offsets, and generates final binary machine words.

• Component Functional Architecture of the Assembler:

  • skipCommaWhite: Traverses a character string from a starting memory address; steps past spaces (' '), horizontal tabs ('\t'), and commas (','); returns a pointer positioned at the first non-delimiter byte.
  • isNumeric: Checks whether the character at a given memory location falls within the ASCII interval '0' to '9' ($48_{10}$ to $57_{10}$); returns 1 if true, 0 if false.
  • parseInt: Converts a multi-character ASCII decimal numerical string into a signed binary full-word integer via iterative multiplication by $10$:     $\text{Value} = \text{Value} \times 10 + (\text{char} - \text{'0'})$
  • strcmp: Performs lexicographical character comparison between two memory strings terminated by whitespace or commas; returns zero ($0$) if identical.
  • mnemonic: Searches the internal instruction dictionary table (ops_mnemonic) for an operational mnemonic matching the source statement; initializes the output instruction with corresponding opcode and function codes; returns format status codes.
  • reg: Evaluates register text. If the leading character after $ is numeric, it calls parseInt; otherwise, it matches the name against regNames_reg using strcmp and returns the positional index ($0..31$).
  • operand: Encapsulates register parsing; shifts the parsed register index leftward using a format-dependent variable shift (sllv) by $11\text{ bits}$ (for rd), $16\text{ bits}$ (for rt), or $21\text{ bits}$ (for rs), and bitwise ORs it into the instruction word under construction.
  • lineEnd: Traverses any residual trailing characters in an assembly statement, asserting that only whitespace, newline characters (' '), or null bytes (0x00) exist prior to advancing to the next statement.

• Dependency and Linkage Management:

  • In assembly source architecture utilizing .include directives, multiple inclusions of common subroutines cause assembler symbol collision errors ("multiply defined symbols").
  • System organization requires strict call-graph discipline: each shared routine source file is included via .include exactly once within a single compilation tree.

Boolean Algebra, Digital Logic, and Circuit Design

• Boolean Algebraic Notation and Precedence:

  • Operations:
  • AND: Represented by a centered dot or direct variable juxtaposition: $x \cdot y = xy$.
  • OR: Represented by the plus sign: $x + y$.
  • NOT: Represented by a prime mark or overbar: $x'$ or $\overline{x}$.
  • XOR: Represented by the circled plus sign: $x \oplus y$.
  • Operator Precedence (in the absence of grouping parentheses):
  1. NOT ($'$)
  2. AND ($\cdot$)
  3. OR ($+$) and XOR ($\oplus$)
  • Operations of equal precedence evaluate from left to right.

• Core Axiomatic Identities and Duals:

  • The principle of duality dictates that every valid boolean identity remains valid when AND and OR operators are interchanged, and identities $0$ and $1$ are interchanged.
  • Identity Laws: $x + 0 = x$; $x \cdot 1 = x$
  • Negation Laws: $x + x' = 1$; $x \cdot x' = 0$
  • Idempotent Laws: $x + x = x$; $x \cdot x = x$
  • Constant Laws: $x + 1 = 1$; $x \cdot 0 = 0$
  • Involution Law: $(x')' = x$
  • Commutative Laws: $x + y = y + x$; $x \cdot y = y \cdot x$
  • Associative Laws: $x + (y + z) = (x + y) + z$; $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
  • Distributive Laws: $x(y + z) = xy + xz$; $x + yz = (x + y)(x + z)$
  • DeMorgan's Laws: $(x + y)' = x'y'$; $(xy)' = x' + y'$
  • Absorption Laws: $x + xy = x$; $x(x + y) = x$; $x + x'y = x + y$; $x(x' + y) = xy$
  • Consensus Laws: $xy + x'z + yz = xy + x'z$; $(x + y)(x' + z)(y + z) = (x + y)(x' + z)$

• Karnaugh Map (K-Map) Minimization:

  • A two-dimensional representation of a truth table where adjacent cells differ by exactly one binary variable (arranged via Gray Code sequences: 00, 01, 11, 10).
  • Group Sizing and Adjacency:
  • Groups must be rectangular and contain a number of cells that is an integral power of two ($1, 2, 4, 8, 16$).
  • Adjacent ones can group horizontally, vertically, wrap across opposing outer boundary edges, or merge across the four outer corners of a $4\times 4$ grid.
  • Variables that change state within an identified group drop out of the resulting simplified algebraic product term.
  • Don't-Care Outputs ($X$ or $?$):
  • Unspecified or physically impossible input states assigned arbitrary outputs ($0$ or $1$).
  • During minimization, don't-cares are treated as ones if doing so expands an existing group into a larger power of two; otherwise, they are treated as zeros to avoid generating unnecessary terms.

• Fundamental Digital Logic Gates:

  • AND Gate: Flat input edge, rounded output nose; outputs $1$ only when all inputs are $1$.
  • OR Gate: Curved input edge, pointed output tip; outputs $0$ only when all inputs are $0$.
  • Inverter (NOT): Triangle with an inversion bubble; inverts input state.
  • Exclusive OR (XOR) Gate: Double-curved input line, pointed tip; outputs $1$ when inputs differ.
  • NOR Gate: OR gate followed by an inversion bubble ($\overline{x + y}$).
  • NAND Gate: AND gate followed by an inversion bubble ($\overline{x \cdot y}$).

• Schematic Rules for Wires and Buses:

  • Crossing wires without a connection point cross freely without electrical contact. A solid dot indicates an electrical junction.
  • Contradiction Condition: Connecting two gate outputs together directly creates an indeterminate electrical conflict and is strictly prohibited without intervening multiplexing.
  • Buses: Parallel conduits conveying multi-bit signals, represented by thickened lines annotated with their bit width in parentheses (e.g., (32)). Multi-bit buses may split into sub-buses (e.g., [0..7] and [8..31]) or merge into wider aggregates.

• Combinational Logic Subsystems:

  • Sign-Extend Component: Expands an input bus of width $m$ to an output bus of width $n$ ($n > m$) by routing the input MSB (the sign bit) across all upper output bits ($m$ through $n-1$).
  • Decoder ($n \times 2^n$): Takes an $n\text{-bit}$ selection binary code and drives exactly one of its $2^n$ output lines to $1$, setting all others to $0$.
  • Encoder ($2^n \times n$): The inverse of a decoder. Accepts $2^n$ inputs (assuming only one input is asserted) and produces the corresponding $n\text{-bit}$ binary number.
  • A $4\times 2$ encoder accepts inputs $I_3, I_2, I_1, I_0$ and produces outputs $E_1, E_0$ according to:       $E_1 = I_3 + I_2$$E_0 = I_3 + I_1$
  • Multiplexer ($2^k \times n$): Routes one of $2^k$ input buses (each $n\text{ bits}$ wide) to a single $n\text{-bit}$ output bus based on a $k\text{-bit}$ control selector.
  • A $2\times 1$ multiplexer with data inputs $I_0, I_1$ and select line $S$ is defined by:       $M = S'I_0 + SI_1$
  • Binary Adders:
  • Half Adder: Adds two single-bit inputs ($x, y$), producing a Sum ($S$) and Carry ($C$):       $S = x \oplus y$$C = xy$
  • Full Adder: Adds two single-bit operands ($x, y$) plus an incoming carry ($c_{in}$):       $S = x \oplus y \oplus c_{in}$$c_{out} = xy + c_{in}(x \oplus y) = xy + xc_{in} + yc_{in}$
    • A full adder is constructed from two half adders and an OR gate.
  • Ripple-Carry Adder ($n\text{-bit}$): Cascades $n$ full adders such that $c_{out}$ of stage $i$ connects directly to $c_{in}$ of stage $i+1$.
  • Twos Complement Overflow Detection: Overflow in signed integer addition occurs if and only if the carry-in into the sign bit ($c_{in}$ of MSB) differs from the carry-out of the sign bit ($c_{out}$ of MSB):       $\text{Overflow} = c_{n-1} \oplus c_n$

• Sequential Logic Circuits:

  • Unlike combinational logic (whose outputs depend entirely on current inputs), sequential circuits incorporate internal memory and state feedback.
  • Clock Signal: A square wave oscillating continuously between $0$ and $1$. Characterized by its period $T$ (cycle duration) and frequency $f = 1/T$ (measured in Hertz, where $1\text{ GHz} = 10^9\text{ cycles/sec}$).
  • SR Latch: Constructed from two cross-coupled NOR gates with inputs Set ($S$) and Reset ($R$). When $S=0, R=0$, it retains its existing state. $S=1, R=0$ forces state $Q=1$. $S=0, R=1$ forces state $Q=0$. The condition $S=1, R=1$ is disallowed, as it produces a contradictory state where both $Q$ and $Q'$ evaluate to $0$.
  • Clocked SR Flip-Flop: Augments the SR latch with input AND gates driven by a clock signal, restricting state transitions to intervals where the clock is high ($1$).
  • D Flip-Flop: Resolves the undefined $S=R=1$ condition by routing a single Data input ($D$) directly to the Set path, and its inverted complement ($D'$) to the Reset path. State $Q$ captures the value of $D$ upon clock assertion.
  • JK Flip-Flop: Incorporates feedback from the outputs back to the input AND gates. When $J=1, K=0$, the state is set to $1$. When $J=0, K=1$, the state is reset to $0$. When $J=1, K=1$, the flip-flop toggles to its complement ($Q_{n+1} = Q_n'$).
  • Registers: Formed by grouping $n$ D flip-flops in parallel. An enabled register gates the common clock line via a Load enable line through an AND gate: Clock_In = Clock & Load.
  • Finite State Machines (FSM): Sequential systems modeling discrete operational states, transitions driven by external inputs, and outputs. Designed by assigning flip-flop states, mapping a transition table, determining logic expressions for flip-flop inputs via K-maps, and realizing feedback wiring.

Arithmetic and Logic Unit (ALU) Construction

• ALU Architectural Specifications:

  • The MIPS ALU processes two $32\text{-bit}$ input buses ($A$ and $B$) and produces one $32\text{-bit}$ output bus along with a 1-bit zero indicator ($Z$).
  • Operations are governed by a 4-bit Operation Select line:
  • 0000: Bitwise AND ($A \& B$)
  • 0001: Bitwise OR ($A \mid B$)
  • 0010: Addition ($A + B$)
  • 0110: Subtraction ($A - B$)
  • 0111: Set If Less Than (determines signed relation $A < B$)
  • 1100: Bitwise NOR ($\sim(A \mid B)$

• Internal Operational Logic per Bit-Stage ($i$):

  • Logical AND: Bitwise AND gate: $\text{AND}_i = A_i \cdot B_i$.
  • Logical OR: Bitwise OR gate: $\text{OR}_i = A_i + B_i$.
  • Logical NOR: Bitwise OR gate followed by an inverter: $\text{NOR}_i = (A_i + B_i)'$.
  • Twos Complement Addition: Full adder receiving $A_i, B_i$, and carry-in $c_i$, producing sum bit $S_i$ and carry-out $c_{i+1}$. For stage $0$, $c_0 = 0$.
  • Twos Complement Subtraction: Derived from the algebraic equivalence:     $A - B = A + (-B) = A + B' + 1$
  • Each bit of $B$ is inverted ($B_i'$) via an inverter. In stage $0$, the carry-in is hardwired to $1$ ($c_0 = 1$), executing the necessary "plus one" increment.

• Output Multiplexing and Composite ALU Layout:

  • Each bit-stage routes its candidate results ($\text{AND}_i, \text{OR}_i, S_i, D_i, \text{NOR}_i$) into a $16\times 1$ multiplexer driven by the 4-bit Operation Select signal.
  • The parallel array of 32 multiplexers forms the composite $16\times 32$ output multiplexer yielding the 32-bit Data Out bus.
  • Zero ($Z$) Flag Synthesis: Indicates whether the ALU Data Out bus equals zero. All 32 output bits enter a wide OR gate, whose output is inverted:     $Z = (\text{Out}_{31} + \text{Out}_{30} + \dots + \text{Out}_0)'$
  • Set If Less Than Synthesis (Operation Select = 0111):
  • Under signed twos complement subtraction ($A - B$), if $A < B$, the resulting difference is negative, meaning its sign bit ($D_{31}$) is $1$.
  • A $2\times 1$ multiplexer selects between the standard negated zero-detect signal and the difference sign bit ($D_{31}$), switching to $D_{31}$ when Operation Select equals 0111.

Design and Implementation of the MIPS Datapath

• Storage Components in the Datapath:

  • Register File ($32\times 32$):
  • Houses 32 general-purpose registers.
  • Inputs: A sel ($5\text{ bits}$), B sel ($5\text{ bits}$), Write Sel ($5\text{ bits}$), Data In ($32\text{ bits}$), and a control line R/W (where $1=\text{Read}$ and $0=\text{Write}$, synchronized with the system clock).
  • Outputs: A Out ($32\text{ bits}$) and B Out ($32\text{ bits}$).
  • Data Memory ($1\text{G} \times 32$):
  • Volatile RAM storing application runtime data.
  • Inputs: Address In ($32\text{ bits}$), Data In ($32\text{ bits}$), and R/W control.
  • Output: Data Out ($32\text{ bits}$).
  • Instruction Memory ($1\text{G} \times 32$):
  • Read-only storage for program instruction words.
  • Input: Address In from the Program Counter ($PC$).
  • Output: Instruction Out routed to the Instruction Register ($IR$).
  • Program Counter ($PC$): A 32-bit register providing the memory address of the current instruction.

• Subsystem Data Routing and Contradiction Resolution:

  • Connecting discrete paths for varied instructions introduces hardware bus contradictions (points where multiple distinct sources feed a common input). Each is resolved using a multiplexer:
  • ALU Input B Contradiction (MUX ALU):
  • R-Format: Second ALU operand comes from register output B Out.
  • Memory Reference (lw/sw): Second operand comes from the sign-extended 16-bit immediate displacement.
  • Resolution: A $2\times 1$ MUX (MUX ALU), controlled by signal ALUB, routes either B Out (when 1) or SignExtend(imm) (when 0) to the ALU B input.
  • Register File Data In Contradiction (MUX RF):
  • R-Format: Register write data originates from the ALU Data Out bus.
  • Load Word (lw): Register write data originates from Data Memory Data Out.
  • Resolution: A $2\times 1$ MUX (MUX RF), controlled by signal RF, selects between ALU output (when 0) and Memory output (when 1).
  • Register File Write Select Contradiction (MUX WS):
  • R-Format: The destination register is specified by IR[15..11] (rd).
  • I-Format (lw, addi): The destination register is specified by IR[20..16] (rt).
  • Resolution: A $2\times 1$ MUX (MUX WS), controlled by signal WS, selects between rd (when 0) and rt (when 1).
  • Program Counter Source Contradictions (MUX BC and MUX J):
  • Sequential Execution: Next address is $PC + 4$ (computed by a dedicated adder).
  • Conditional Branch (beq/bne): Next address is $(PC + 4) + (\text{SignExtend}(imm) \times 4)$ (computed by a second dedicated adder).
  • Resolution: MUX BC selects between $PC + 4$ (input 0) and the branch target adder (input 1).
  • Unconditional Jump (j/jal): Target address is formed from IR[25..0] padded with the upper bits of $PC$.
  • Resolution: MUX J selects between the output of MUX BC (input 1) and the jump address bus (input 0).

The Control Unit and Signal Synthesis

• Control Unit Architecture:

  • Decodes the instruction word and issues control signals across the datapath.
  • Inputs: opcode (IR[31..26], 6 bits) and funct (IR[5..0], 6 bits).
  • Primary Control Outputs:
  • RegW: Register File write control ($0=\text{Write enabled}$, $1=\text{Read only}$).
  • DW: Data Memory write control ($0=\text{Write enabled}$, $1=\text{Read only}$).
  • ALUB: Controls MUX ALU ($1=\text{Register B}$, $0=\text{Immediate field}$).
  • RF: Controls MUX RF ($0=\text{ALU Out}$, $1=\text{Data Memory Out}$).
  • WS: Controls MUX WS ($0=\text{rd field}$, $1=\text{rt field}$).
  • J: Controls MUX J ($0=\text{Jump target address}$, $1=\text{Sequential/Branch output from MUX BC}$).
  • BEQ: Indicates a branch-if-equal instruction.
  • BNE: Indicates a branch-if-not-equal instruction.
  • ALUOP: 4-bit operational code routed to the ALU.

• Control Signal Decoding Matrix:

Note: Question marks (?) represent don't-care conditions, allowing logic simplification during circuit synthesis.

• Branch Decision Logic (MUX BC Selector):

  • Subtraction is performed within the ALU for both beq and bne, driving the Zero flag ($Z$).
  • The control selection line triggering a branch transition in MUX BC is synthesized as:     $\text{MUX}_{BC} = (\text{BEQ} \cdot Z) + (\text{BNE} \cdot Z')$

• Logic Expressions for Control Output Lines:

  • Let $op_5..op_0$ represent the opcode bits, and $f_5..f_0$ represent the function bits.
  • DW (Data Memory Write, active low for sw = 101011):     $\text{DW} = (op_5 \, op'_4 \, op_3 \, op'_2 \, op_1 \, op_0)'$
  • BEQ (Opcode 000100):     $\text{BEQ} = op'_5 \, op'_4 \, op'_3 \, op_2 \, op'_1 \, op'_0$
  • BNE (Opcode 000101):     $\text{BNE} = op'_5 \, op'_4 \, op'_3 \, op_2 \, op'_1 \, op_0$
  • J (Opcode 000010):     $J = (op'_5 \, op'_4 \, op'_3 \, op'_2 \, op_1 \, op'_0)'$

The Memory Hierarchy, Caching, and Virtual Memory

• The Memory Latency Dilemma:

  • CPU arithmetic processing completes in fractional nanoseconds, while dynamic RAM accesses require tens to hundreds of nanoseconds (often a $1000\times$ speed differential).
  • Without low-latency intermediary structures, execution stalls during memory references.
  • Primary memory strategies mitigating latency include pipeline instruction prefetching (fetching instruction queues into arrays of internal registers ahead of the $PC$) and hierarchical caching.

• Memory Technology Hierarchy:

• Direct-Mapped Cache Architecture:

  • High-speed, small-capacity SRAM cache mapped to main memory in fixed-size blocks (e.g., $128\text{ bytes}$).
  • Main memory blocks map directly to specific cache blocks via modulo arithmetic:     $\text{Cache Block Number} = (\text{RAM Block Number}) \pmod{\text{Number of Cache Blocks}}$
  • A memory byte address divides into three fields:
  • tag: Upper bits identifying which specific RAM block currently occupies the cache slot.
  • cache block: Middle bits indexing the target cache line.
  • byte offset: Lower bits specifying the addressed byte within the block.
  • Cache Hit vs. Miss:
  • Hit: Tag matching confirms the requested block is present; data access completes with zero memory delay.
  • Miss: Tag mismatch requires fetching the entire containing block from main RAM, overwriting the cache entry.
  • Write Policies:
  • Write-Through: Every memory write updates the cache block and the backing DRAM simultaneously.
  • Write-Back (with Dirty Bit): Writes modify only the cache block, setting a 1-bit dirty bit. The block is written back to main memory only when it is displaced by a cache miss.

• Associative Cache Architecture:

  • Groups cache blocks into sets; an $n\text{-way}$ set associative cache organizes blocks into sets containing $n$ blocks each. (A 1-way cache is functionally direct-mapped).
  • Address breakdown consists of: tag, cache set, and byte offset.
  • A given RAM block maps to a designated set, but can be placed in any available block within that set, dramatically mitigating conflict misses caused by blocks competing for the identical cache slot.
  • Block Replacement Strategies:
  • Least Recently Used (LRU): Tracks access history and replaces the block within the set that has gone unreferenced the longest.
  • First-In, First-Out (FIFO): Evicts the block that has resided in the set the longest time.
  • Random: Selects an eviction candidate at random, preventing systemic failure modes.
  • Thrashing: Pathological operational state where contiguous access patterns cause repetitive, unending block evictions, driving miss rates toward $100\%$.

• Virtual Memory Architecture:

  • Extends available memory beyond physical RAM limits by using secondary magnetic disks or solid-state storage as backing swap space.
  • Physical memory and swap files are partitioned into units called pages (typically $8\text{K bytes}$ or $64\text{K bytes}$).
  • Page Table: An operating system lookup table indexed by the virtual page number. Translates virtual addresses to physical RAM page frames or flags a page fault if the page resides strictly on secondary storage.
  • Page Fault Handling: A page fault triggers an interrupt halting user-thread execution, initiates slow disk retrieval of the missing page into a vacant or evicted RAM page frame, updates the Page Table, and restarts the instruction.
  • Similar to caches, page management uses a dirty bit to avoid writing unaltered pages back to disk upon eviction, and relies on LRU or FIFO page-replacement policies.

Locality Principles and Program Performance

• The Principle of Locality:

  • Program performance through caching and virtual memory depends heavily on locality of reference.
  • Temporal Locality: Memory locations accessed recently have a high probability of being accessed again in the near future (e.g., loop variables, subroutine addresses).
  • Spatial Locality: Memory locations positioned close to recently accessed addresses have a high probability of being accessed shortly thereafter (e.g., sequential instruction execution, contiguous array indexing).

• Data Locality vs. Instruction Locality:

  • Instruction Locality: Preserved by sequential code execution and tight, compact loop structures. Broken by long-distance branch tables, unpredictable dynamic jumps, or scattered subroutines.
  • Data Locality: Preserved when algorithms iterate linearly across contiguous data structures.

• Algorithmic Implications and Performance Impacts:

  • Multi-dimensional arrays are allocated in row-major order (contiguous rows placed end-to-end in linear memory addresses).
  • Traversing a large two-dimensional matrix row by row processes memory sequentially, maximizing spatial locality and cache hits.
  • Traversing the identical matrix column by column incurs an address leap of an entire row width per element, potentially causing a cache miss on every access and degrading performance by several orders of magnitude.
  • Similarly, linear sequential array scans run significantly faster than random access patterns across the same data set.

Alternative Computer Architectures

• The Classical Von Neumann Model:

  • Formulated by John von Neumann in 1945, defining the stored-program computer:
  1. A central processing unit containing an Arithmetic Logic Unit and working registers.
  2. A control unit featuring an Instruction Register and Program Counter.
  3. A unified or separated primary memory storing data and program instructions.
  4. External non-volatile secondary storage.
  5. Input and output mechanisms.

• Instruction Set Architecture (ISA) Address Classifications:

  • Zero-Address Architecture (Stack Machine):
  • Instructions contain no explicit operand addresses. Operands reside on an internal hardware/memory stack.
  • Operations pop the top two stack values and push the calculated result back onto the stack.
  • Used by systems like the Burroughs B-Machine series (circa 1970).
  • Evaluating $x = (a - b) + c$: assembly Push a Push b Sub # Pops b, pops a, pushes a - b Push c Add # Pops c, pops a - b, pushes (a - b) + c Pop x       

• One-Address Architecture (Accumulator Machine):

  • Instructions contain a single memory address. A dedicated CPU register, the accumulator (Acc), serves as the implicit left operand and result destination.
  • Represented by early minicomputers such as the DEC PDP-8 (circa 1970).
  • Evaluating $x = a - (b + c)$: assembly Clr # Acc = 0 Add b # Acc = b Add c # Acc = b + c Neg # Acc = -(b + c) Add a # Acc = a - (b + c) Store x       

• Two-Address Architecture:

  • Instructions specify two operands; the first operand serves as both a source and the final destination (op1 = op1 OP op2).
  • Common in mainframe architectures (IBM 360/370) and Intel x86 microprocessors.
  • Evaluating $x = (a - b) + c$: assembly Load r1, a # r1 = a Sub r1, b # r1 = a - b Add r1, c # r1 = (a - b) + c Store r1, x       

• Three-Address Architecture:

  • Instructions designate two explicit source operands and an independent destination operand (dest = src1 OP src2).
  • Standard across modern RISC designs, including MIPS and ARM.
  • Evaluating $x = a - (b + c)$: assembly Load r1, a Load r2, b Load r3, c Add r3, r2, r3 # r3 = b + c Sub r3, r1, r3 # r3 = a - (b + c) Store r3, x       

• Memory Addressing Modes:

  • Direct Addressing: The instruction word contains the absolute memory address of the operand.
  • Indirect Addressing: The instruction word references a memory pointer word, which holds the target operand address.
  • Base-Displacement Addressing: Effective address is the arithmetic sum of a general base register plus an immediate offset. Facilitates relocatable code necessary for multiprogrammed operating systems.
  • Base-Index-Displacement Addressing: Effective address combines a base register, an index register, and an immediate displacement:     $\text{Effective Address} = \text{Reg}[\text{base}] + \text{Reg}[\text{index}] + \text{displacement}$

• The ARM (Advanced RISC Machine) Architecture:

  • Developed in the 1980s by Acorn Computers; a dominant 32-bit/64-bit load-store RISC architecture.
  • Features 32 registers (X0 to X31, where X31 / XZR is hardwired to zero). Conventions designate X0..X7 for arguments/returns, X19..X27 as callee-saved, X28 as Stack Pointer (SP), X29 as Frame Pointer (FP), and X30 as Link Register (LR).
  • Instruction formats include R, I, D (Data transfer), B (Branch), CB (Conditional Branch), and IW (Wide Immediate).
  • Memory access requires explicit load/store operations: LDUR / STUR (unscaled) and LDR / STR (scaled by word size).
  • Condition Codes and Flags:
  • ALU operations appended with an S (e.g., ADDS, SUBS) update four hardware status flags:
    • $N$ (Negative): Set if MSB of result is $1$.
    • $Z$ (Zero): Set if all bits of result are $0$.
    • $V$ (Overflow): Set if signed integer twos complement overflow occurs.
    • $C$ (Carry): Set if an unsigned carry-out occurs from the MSB.
  • Conditional branches evaluate these flags:
    • B.EQ tests $Z = 1$
    • B.NE tests $Z = 0$
    • B.LT tests $N \neq V$

• B.GE tests $N = V$

• B.LE tests $Z = 1 \text{ or } N \neq V$

  • B.GT tests $Z = 0 \text{ and } N = V$
    • Derivation of B.GT condition: When subtracting $x - y$, overflow can invert the expected sign of the result. Truth table analysis yields the logic equation:       $\text{Condition} = Z'N'V' + Z'NV = Z'(N = V)$

• The Intel x86 / Pentium Architecture:

  • Historically grounded in the 8086, 8088, 286, 386, 486, Pentium, and subsequent Core architectures. Highly backward compatible.
  • Classified as a Complex Instruction Set Computer (CISC) using a two-address model.
  • Non-orthogonal architecture: instructions exhibit asymmetries regarding which registers and addressing modes can pair with specific operations.
  • Core Registers ($32\text{-bit}$ Extended Names):
  • EAX: Accumulator for operations and function results (sub-register: AX, AH, AL).
  • EBX: Base register for pointer addressing (BX).
  • ECX: Counter for loops and variable bit-shifts (CX, CL).
  • EDX: Data register; arithmetic overflow/multiplier extension (DX).
  • EBP: Base Pointer (BP).
  • ESI: Source Index for memory streaming (SI).
  • EDI: Destination Index for memory streaming (DI).
  • ESP: Stack Pointer (SP).
  • Pentium Addressing Modes:
  • The effective address incorporates an optional scaling factor ($1, 2, 4, 8$):       $\text{Effective Address} = \text{Base} + (\text{Scale} \times \text{Index}) + \text{Displacement}$
  • Instructions:
  • Data transfer: mov dest, src (handles register-to-register, memory-to-register, immediate-to-register, and register-to-memory); lea (Load Effective Address).
  • Arithmetic: add, sub, inc, dec, cmp (evaluates subtraction, setting flags without saving the difference).
  • Multiplication/Division: mul/imul and div/idiv implicitly utilize the (EDX, EAX) register pair to hold double-length results.
  • Shifts and Rotates: shl/sal (shift left), shr (logical shift right), sar (arithmetic shift right preserving sign), rol (rotate circular left), ror (rotate circular right).
  • EFLAGS register holds status flags: OF (Overflow), SF (Sign), ZF (Zero), PF (Parity, asserted if low-order byte holds an even number of ones), CF (Carry).