PadhaikoAll subjects

Introduction

Computer Organization and Architecture (ENCT 303)

Open in the Padhaiko app

1.1 Organization and architecture

In computer engineering, designing and analyzing a computer system requires separating what a system does from how its hardware components are built and connected.

Definition

Computer Architecture vs. Computer Organization

AspectComputer ArchitectureComputer Organization
PerspectiveLogical design visible to the programmerPhysical hardware realization transparent to the programmer
Core ConcernWhat the computer does (instruction set, addressing, data types)How the computer does it (circuits, control signals, bus paths, memory technology)
Design FocusCompatibility across a processor familyCost, speed, power efficiency, and implementation trade-offs
ExampleWhether the CPU provides a hardware MUL instructionWhether multiplication uses a dedicated multiplier unit or repeated addition

For example, the x86 architecture has remained broadly compatible across decades of processor generations so legacy binaries still run, while the internal organization (cache hierarchy, pipelining, execution units) has changed drastically from the 8086 to modern processors.

1.2 Structure of a computer, single processor, multi-core computer

Every general-purpose computer performs four basic functions: data processing, data storage, data movement, and control. To accomplish these, a computer is organized hierarchically into four top-level structural components:

  1. Central Processing Unit (CPU): Controls the operation of the computer and performs its data processing functions. Often simply referred to as the processor.
  2. Main Memory: Stores both data and instructions while programs are executing (stored-program concept).
  3. I/O (Input/Output): Moves data between the computer and its external environment (disks, keyboards, network interfaces, displays).
  4. System Interconnection: Provides communication pathways among the CPU, main memory, and I/O—commonly implemented via a system bus (data, address, and control lines) or point-to-point interconnects.

Within a single-processor (traditional CPU), the internal structure comprises:

As transistor density grew under Moore's law, raising clock frequency further hit power and thermal limits (the power wall). Designers shifted from single-core scaling to multi-core computers.

Definition

Multi-Core Computer Terminology

AspectSingle-Processor ComputerMulti-Core Computer
Execution UnitsOne CPU core per chipMultiple independent cores on a single die
ConcurrencyTime-sliced multitasking on one coreTrue hardware parallelism across multiple cores
Cache HierarchyPrivate L1/L2 caches serving one corePrivate per-core L1 (and often L2) plus shared L3 cache
Power & Thermal EfficiencyHigh frequency needed for performance ()Lower clock per core at higher aggregate throughput

1.3 Performance assessment

Evaluating computer performance requires looking beyond raw clock frequency to actual execution time, throughput, and workload-averaged metrics.

1.3.1 Clock speed and instruction per second

A processor's operations are synchronized by a periodic electronic pulse called the system clock.

Let a program consist of an instruction count (total machine instructions executed). If the processor takes an average of clock cycles per instruction, then:

When a program contains distinct instruction classes, where class is executed times and requires cycles per instruction:

where is the relative frequency (fraction) of instruction class .

1.3.2 Instruction execution rate, means, and Amdahl's law

Definition

CPI, MIPS, and MFLOPS Rates

Limitation: MIPS cannot compare machines with different instruction sets (e.g., RISC vs. CISC) because a complex instruction does more work than a simple one, and MIPS varies inversely with program complexity.

When summarizing performance across a benchmark suite of programs, choosing the right mean depends on whether the underlying measurements are times or rates, and whether results are absolute or normalized:

Statistical Means for Performance Benchmarks
Metric TypeFormulaCorrect Use Case
Arithmetic Mean (AM)Summarizing execution times across equally weighted programs (total time )
Weighted Arithmetic MeanSummarizing execution times when programs run with unequal frequency
Harmonic Mean (HM)Summarizing rate metrics (MIPS, MFLOPS, speed) where each benchmark executes the same amount of work
Geometric Mean (GM)Summarizing normalized speedups or ratios relative to a reference machine (order-independent of reference choice)
Theorem

Amdahl's Law and Speedup

Let Speedup () be the ratio of execution time before an enhancement () to execution time after the enhancement ():

Suppose a fraction of the original execution time can be sped up by a factor (for instance, parallelized across processors so ), while the remaining fraction cannot be improved (strictly sequential). Then:

Even as , the overall speedup is strictly bounded by the serial fraction:

1.4 Computer function

The fundamental function of a stored-program computer is the continuous execution of instructions stored in main memory.

1.4.1 Instruction fetch and execute

At its simplest level, instruction processing consists of two repeating steps:

  1. Fetch Cycle:
    • The Program Counter (PC) holds the memory address of the next instruction to fetch.
    • The processor reads the instruction from memory into the Instruction Register (IR).
    • Unless altered by a jump or branch, the PC is incremented to point to the next sequential instruction.
  2. Execute Cycle:
    • The control unit decodes the opcode in the IR and activates the required control signals.
    • Execution may involve four categories of actions:
      • Processor-memory: Transfer data between CPU and main memory.
      • Processor-I/O: Transfer data between CPU and an I/O module.
      • Data processing: Perform an arithmetic or logical operation in the ALU.
      • Control: Alter the execution sequence by updating the PC (jumps, calls, returns).

1.4.2 Instruction cycle state diagram

Real processors break the fetch-execute process into finer sub-states and handle indirect addressing and interrupts:

States in the Instruction Cycle State Diagram
StateRole in Instruction Execution
Instruction Address Calculation (iac)Determine address of the next instruction (usually or branch target)
Instruction Fetch (if)Read the instruction from its memory location into the processor's IR
Instruction Operation Decoding (iod)Analyze the opcode to determine the operation type and operand specifiers
Operand Address Calculation (oac)Compute effective memory address if an operand uses indirect or indexed addressing
Operand Fetch (of)Fetch each required operand from memory or I/O into internal registers
Data Operation (do)Perform the ALU operation specified by the instruction
Operand Store (os)Write the result back into memory or send it to an I/O module
Interrupt Check / Interrupt (int)After completing execution, check for pending interrupts; if enabled and present, save context (PC, PSW) and branch to the Interrupt Service Routine (ISR)

Notice that Operand Address Calculation and Operand Fetch may repeat in a loop for instructions with multiple operands or multi-level indirect addressing, and Operand Store may occur before returning to Interrupt Check (or directly to Instruction Address Calculation if no interrupt is pending).

1.5 Computer component, interconnection structure, bus interconnection, PCI

To function as an integrated system, the CPU, main memory, and I/O modules must exchange specific signals over an interconnection structure.

The three types of transfers supported by any interconnection structure are:

Definition

System Bus Interconnection

A bus is a shared communication pathway connecting two or more devices. Because it is a shared medium, only one device can transmit successfully at a time, while multiple devices may read the signal. A classical system bus consists of 50 to hundreds of parallel lines grouped into three functional classes:

  1. Data Bus: Bidirectional lines carrying data or instruction words between source and destination. Its width (e.g., 32 bits, 64 bits) determines how many bits transfer in a single cycle.
  2. Address Bus: Unidirectional lines (driven by the CPU or DMA controller) specifying the source/destination memory address or I/O port. A width of address lines addresses up to locations.
  3. Control Bus: Lines regulating access to and use of the data and address lines (e.g., Memory Read, Memory Write, I/O Read, I/O Write, Bus Request, Bus Grant, Interrupt Request, Clock, Reset).

Single-bus designs suffer from propagation delay and bus contention when many high-speed and low-speed devices share one bus. Modern systems therefore use multiple-bus hierarchies (processor bus, high-speed local/system bus, expansion bus bridged via a bus bridge/controller).

PCI (Peripheral Component Interconnect)

PCI is a high-bandwidth, processor-independent bus standard designed to connect high-speed peripherals (graphics, network, storage controllers) without overloading the processor's local bus:

1.6 RISC architecture, overlapped register windows, Berkeley RISC

In the late 1970s and early 1980s, empirical studies of compiled programs revealed that programmers and compilers overwhelmingly used simple instructions (loads, stores, simple ALU ops, branches) and spent significant execution time on procedure calls and returns (saving/restoring registers and passing parameters). This motivated Reduced Instruction Set Computer (RISC) design.

AspectCISC (Complex Instruction Set Computer)RISC (Reduced Instruction Set Computer)
Instruction ComplexityLarge set of complex, multi-cycle instructionsSmall, uniform set of simple single-cycle instructions
Instruction FormatVariable-length instructionsFixed-length instructions (e.g., 32 bits) for fast decoding
Memory AccessMemory-to-memory operations allowedLoad/Store architecture (only Load and Store access memory; ALU ops use registers)
Addressing ModesMany complex addressing modesFew simple addressing modes (register, immediate, base-displacement)
Control UnitTypically microprogrammedHardwired control unit for high-speed execution
Register FileRelatively few general-purpose registersLarge register file (often organized as register windows)

Overlapped Register Windows & Berkeley RISC

To eliminate expensive memory traffic during procedure calls and returns, Berkeley RISC (RISC-I / RISC-II, developed at UC Berkeley by Patterson and Séquin) introduced overlapped register windows:

For windows, global registers, local registers per window, and overlapping (in/out) registers per boundary:

(In Berkeley RISC-II: , , , and , yielding visible registers per procedure and total physical registers.)

Worked Out Examples

Example 1

1 (6 marks)

A processor running at executes a benchmark program of instructions with the following dynamic instruction mix:

Compute:

  1. The average
  2. Total CPU execution time (in ms)
  3. The rate
  4. The rate if of the executed instructions are floating-point operations.

Computing the average CPI: Multiply each instruction class's cycle count by its relative frequency:

Computing total CPU execution time: Using with and :

Computing MIPS and MFLOPS rates:

Answer:

, Execution time , , and .

Example 2

2 (6 marks)

  1. A program spends of its execution time in a parallelizable kernel and in strictly sequential code. If the kernel is parallelized linearly across cores, find the overall speedup using Amdahl's law and the theoretical maximum speedup as .
  2. Two machines and execute two benchmarks with times (in seconds): and . Compare their arithmetic mean execution time and the geometric mean of 's execution times normalized to .

Applying Amdahl's law for speedup: Here, parallelizable fraction , serial fraction , and enhancement factor :

Finding the asymptotic speedup limit:

Computing arithmetic and geometric means:

Normalized execution-time ratios of relative to are and :

(Notice that has a smaller total/arithmetic mean time of vs. , whereas the geometric mean of normalized ratios scores them equally at .)

Answer:

Overall speedup ; maximum possible speedup . Arithmetic means are and , while the geometric mean of normalized to is .

Example 3

3 (4 marks)

A Berkeley RISC-style processor is designed with register windows, global registers, local registers per window, and registers in each overlap (in/out) area. Determine:

  1. How many registers are directly addressable by an active procedure?
  2. How many total physical registers must be implemented in the CPU register file?

Counting registers visible to the current procedure: An active procedure accesses global registers, its own local registers, incoming parameter registers (in), and outgoing parameter registers (out):

Counting total physical registers in the chip: Each of the windows contributes unique local registers plus unique overlap registers (since the out registers of window are the same physical registers as the in registers of window , arranged circularly), plus the shared global registers:

Answer:

An active procedure sees registers, and the processor requires total physical registers.

Exercises

Exercise — Introduction to COA

Question 1

Distinguish between computer architecture and computer organization with suitable examples. Explain why modern processors transitioned from single-core high-frequency scaling to multi-core architectures.

Distinguishing architecture from organization:

  • Computer Architecture covers attributes directly visible to the programmer that affect logical program execution: instruction set, data types, addressing modes, and I/O mechanisms.
  • Computer Organization covers the hardware units and interconnections that implement the architecture: control signals, bus interfaces, memory technologies, and ALU implementation.
  • Example: Including a DIV instruction in the ISA is an architectural decision; implementing it with dedicated hardware dividers versus iterative shift-and-subtract microcode is an organizational decision.

Explaining the transition to multi-core processors:

  • Dynamic power dissipation in CMOS chips follows , where is capacitance, is voltage, and is clock frequency.
  • Pushing higher caused extreme heat density (the power wall), while memory access latency failed to keep pace (the memory wall) and instruction-level parallelism saturated (the ILP wall).
  • Integrating multiple independent cores on a single die allows parallel thread execution at lower individual clock frequencies and voltages, delivering higher overall throughput within thermal limits.
Answer:

Computer architecture defines programmer-visible logical attributes (ISA, addressing, data types), whereas computer organization defines transparent hardware realization (control signals, datapaths, memory tech). Multi-core designs replaced aggressive single-core frequency scaling because power density (), memory latency, and diminishing instruction-level parallelism hit physical limits; multiple lower-clocked cores provide higher aggregate throughput within a manageable thermal envelope.

Question 2

A processor runs a program containing instructions composed of register-to-register ops ( cycle), branch/jump ops ( cycles), and memory ops ( cycles). Calculate the average CPI, total CPU execution time in milliseconds, and the MIPS rate.

Calculating the weighted average CPI:

Calculating CPU execution time and MIPS rate:

Answer:

Average , execution time , and execution rate .

Question 3
  1. A processor achieves on benchmark and on benchmark , where both benchmarks contain the exact same number of instructions. Find the true average MIPS rate across both benchmarks using the appropriate mean.
  2. If of a workload is enhanced to run times faster, what is the overall speedup according to Amdahl's law?

Selecting and computing the harmonic mean for equal-work rates: Because MIPS is a rate metric (work per unit time) and both benchmarks have equal instruction counts, the harmonic mean yields total instructions divided by total time:

Applying Amdahl's law: With enhanced fraction and enhancement speedup :

Answer:

The true average execution rate is (harmonic mean), and the overall Amdahl speedup is .

Question 4

Explain the instruction fetch and execute cycle with reference to the instruction cycle state diagram. How are indirect operands and interrupts accommodated in this diagram?

Describing the basic fetch-execute states:

  1. Instruction Address Calculation (iac): Computes the address of the next instruction (incrementing PC or loading a branch target).
  2. Instruction Fetch (if): Reads the instruction word from main memory into the Instruction Register (IR).
  3. Instruction Operation Decoding (iod): Decodes the opcode to determine the required operation and operand specifiers.
  4. Operand Address Calculation (oac) and Operand Fetch (of): Computes effective addresses and reads operands from memory or I/O.
  5. Data Operation (do): Executes the arithmetic, logical, or control operation.
  6. Operand Store (os): Writes results back to memory or I/O.

Accommodating indirect operands and interrupts:

  • Multiple/Indirect Operands: After of or os, control loops back to oac whenever an instruction specifies multiple operands or multi-level indirect addressing (fetching a pointer address first, then fetching the actual data).
  • Interrupts: At the completion of os (or do if no memory store occurs), the CPU enters an Interrupt Check step. If an enabled interrupt request is active, the processor enters the Interrupt (int) state—saving the current PC and processor status word (PSW) on the stack and loading the Interrupt Service Routine (ISR) address into the PC before starting the next fetch cycle.
Answer:

The instruction cycle progresses through iac -> if -> iod -> oac -> of -> do -> os -> (int) -> iac. Indirect or multiple operands loop back through oac -> of, while interrupts are checked right after execution/store so the CPU can save context and transfer control to an ISR before fetching the next instruction.

Question 5
  1. Summarize the role of data, address, and control buses in a computer interconnection structure, and state two key features of the PCI bus.
  2. A RISC CPU uses overlapped register windows with global registers, local registers per window, and overlap registers. Calculate the number of registers visible per procedure and the total physical registers in the CPU.

Describing system bus lines and PCI features:

  • Data Bus: Bidirectional lines carrying instruction words and data; width sets bits transferred per cycle.
  • Address Bus: Unidirectional lines specifying the target memory address or I/O port ( lines address locations).
  • Control Bus: Lines coordinating timing, read/write direction, bus arbitration, and interrupts.
  • PCI Features: (i) Multiplexed address/data lines (AD) to reduce pin count with burst transfers; (ii) Centralized arbitration and Plug-and-Play configuration registers independent of processor type.

Computing RISC register window counts:

Answer:
  1. Data, address, and control buses carry information, target locations, and timing/arbitration signals respectively; PCI features multiplexed address/data burst transfers and processor-independent Plug-and-Play arbitration.
  2. Visible registers per procedure ; total physical registers .
Central Processing Unit (CPU) →