Lecture Notes: Computer Organization

COMP1003 Computer Organisation

Prof. Haipeng GUO

Lec01-03

What is a Computer?

• Definition:
  A computer is an electronic, digital, general-purpose machine that follows follows a step-by-step list (computer program) of instructions for solving a problem
  计算机是一个电子的、数字化的通用机器，它按照逐步指令程序解决问题。

---

Turing Machine

1936年，Alan Turing。

• Definition:
  Turing machine, which is the abstract model of all computers

• Components:

  • a tape divided into cells
  • a moving read/write head
  • a state register storing the state of the Turing machine
  • a finite table of instruction

The Church-Turing Thesis: All things that can be computed can be computed by a Turing machine

Universal Turing Machine: a Turing machine that could simulate all other Turing machines.

It is programmable – so it is a computer!

A computer is a Universal Turing Machine!

---

Historical Development

• Generation Zero: Mechanical Calculating Machines (1642-1945)
• The First Generation: Vacuum Tube Computers (1945-1953)
• The Second Generation: Transistor Computers (1954-1965)
• The Third Generation: Integrated Circuit (IC) Computers (1965-1980)
• The Fourth Generation: VLSI(Very-Large-Scale Integration) Computers (1980-)

---

Von Neumann Architecture

Also called stored-program architecture

Both data and program are stored in the memory

• Components:
  CPU (control unit, ALU, registers), memory, and an I/O system.
  CPU（控制单元，算术逻辑单元，寄存器）、内存和I/O系统。

• von Neumann Bottleneck:
  The speed difference between the CPU and memory creates a delay, as the CPU is faster than memory.

---

Von Neumann Execution Cycle

• also called the fetch-decode-execute cycle
  • the control unit fetch the next instruction from the memory
  • the instruction is decoded into a language that the ALU understands
  • data operands are fetched from the memory into the registers inside CPU
  • the ALU executes the instruction and places the result into the registers or memory

---

Abstraction

The essence of abstraction is preserving information that is relevant in a given context, and forgetting information that is irrelevant in that context.

---

Levels of Transformations

Problem –(Software Design)-> Algorithm –(Programming)-> Program –(Compiling/Interpreting)-> Instr Set Architecture

Problem: What you want to do
Algorithm: step-by-step procedure to solve the problem
Program: a computer program that implements the algorithm using some programming languages

---

The Machine Levels

• Instruction Set Architecture (ISA): instructions that a CPU can execute
• Microarchitecture: implementation of ISA
• Circuits: Details of electrical circuits
• Devices (transistors): Circuits are built by interconnecting transistors
• Bits: Transistors operate on bits (“0” or “1”) that represent data and information

---

Signed Interger Representation

• Sign-magnitude：原码，最高位是符号位，剩下表示大小
• 1’s complement：正数的话同原码。负数的话，在原码基础上，符号位不变，剩下取反。
• 2’s complement：正数的话同原码。负数的话，在原码基础上，符号位不变，剩下取反，再加一。

Real Number Representation

以下是 IEEE754 Single Point Precision Numbers 的示例

单精度浮点数，32 bits。从左到右，1 个 bit 表示 sign，8 个 bit 表示 exponent，23 个 bit 表示 fraction。

$$
(-1)^{sign} \times (1 + fraction) \times 2 ^ {exponent - 127}
$$

• e.g. $(12.375)_{10}$ to float
  • $(12.375){10} = (1100.011){2} = 1.100011 \times 2 ^ 3$
  • Sign bit = 0
  • Exponent: $3 + 127 = 130 = 1000 0010$
  • Mantissa: 1000 1100 0000 0000 000
  • Answer: 0 1000 0010 1000 1100 0000 0000 000

---

Lec04-06

• Integrated Circuits (IC)
  The integration of large numbers of tiny transistors into a small chip

Two Types of Circuits

• Combinational logic circuits
  • Its output depends solely on its current input.
  • No storage, memoryless
• Sequential logic circuits
  • Its output depends not only on its current input, but also on its current state (previous input)
  • Can remember previous input, storage devices

---

Combinational logic circuits

Decoder

• A decoder uses the inputs and their respective values to select one specific output line.

  • from a set of n inputs to a maximum of 2^n outputs
  • for a given input, one unique output line is asserted, or set to 1, while the other output lines are set to zero

• All memory addresses in a computer are specified as binary numbers.

  • When a memory address is referenced (whether for reading or for writing), the computer first has to determine the actual address.
    在计算机中，所有内存地址都用二进制数字表示。当计算机需要读取或写入某个内存地址时，它首先必须确定该地址的实际位置。
  • This is done using a decoder
    这个过程通常是通过解码器完成的。计算机将地址作为输入传递给解码器，解码器然后将正确的内存单元激活，以便进行数据读取或写入。

Multiplexer

A multiplexer behaves like a channel selector

It selects a single output from several inputs.

The particular input chosen for output is determined by the value of the multiplexer’s control lines.

To be able to select among n inputs, log2 n control lines are needed

---

Sequential logic circuits

Sequential Circuits = Combinational Circuits + Memory

memory

What exactly is memory?

• Write: You should be able to change (write) the value
  that’s saved.
• Hold the value: It should be able to hold a value.
• Read: You should be able to read the value that
  was saved.

---

Lec07-??

Finite State Machine

The concept of state:

• The output of a sequential circuit is a function of the current input and the previous state
• The state is stored in the storage element

A system is a finite state machine if it has the following five properties:

• A finite number of states
• A finite number of external inputs
• A finite number of external outputs
• An explicit specification of all allowed state transitions
  所有合法状态转换的明确规范
• An explicit specification of the rules for each external output value
  每个外部输出值的规则的明确规范

Turing Machine vs FSM

• A Turing machine = a FSM + a tape memory.
• Each transition may be accompanied by an
  operation on the tape (move, read, write).
• Its total possible configurations are arbitrarily large, regardless of the size of the program; it expands towards infinity.
  它的总可能配置是任意大的，与程序的大小无关；它会向无穷大扩展。
• Turing machines have more computational power than FSM.
  图灵机比 FSM 具有更强的计算能力。

---

Microarchitecture

• Micro-architecture transfers the ISA into an implementation
• An architecture is a collection of circuits connected together

The von Neumann Architecture

The Stored Program Computer

• Memory stores not only data, but coded instructions that make up a computer program
  内存不仅存储数据，还存储组成计算机程序的编码指令
• CPU fetches and executes – interprets - successive instructions of the program
  CPU 获取并执行 - 解释 - 程序的连续指令
• Program is simply data for the interpreter – as in a Universal Turing Machine!
  程序只是解释器的数据 - 就像通用图灵机一样！
• Single expandable resource pool – main memory – constrains both data and program size
  单个可扩展资源池 - 主内存 - 限制数据和程序大小

Memory

• Array of stored bits
• Address - unique (n-bit) identifier of location
• Contents - m-bit value stored in location
• Basic Operations
  • LOAD – read a value from a memory location
  • STORE – write a value to a memory location

Interface to Memory

• How does CPU get data to/from memory?
  1. MAR: Memory Address Register (D flip-flops)
  2. MDR: Memory Data Register (D flip-flops)

CPU

• The brain of the computer
• It is the part that actually executes the machine instructions
• Inside the CPU
  • Data path
    • Registers
      • PC, IR, MAR, MDR
    • ALU
    • DataBus 数据总线
  • Control Path
    • CU
      • 解析当前指令并生成相应的控制信号，控制指令的执行过程。
      • a finite state machine coordinates execution of the program
    • IR (instruction register)
      • 存储当前执行的指令，用于CU解码和生成控制信号。
    • PC (program counter)
      • 存储下一条要执行指令的地址，每执行完一条指令，PC会更新指向下一条指令地址。PC可以在跳转指令下由CU修改。

---

LC-3

LC-3 是一种简化的教学计算机架构（Little Computer 3），用于帮助学习和理解计算机组成原理。它是一种虚拟的计算机模型，不用于实际应用，而是为了帮助学生掌握计算机指令执行、内存管理和CPU工作原理等基础概念。LC-3架构的指令集和寄存器设计都尽可能简单，以便于学习和理解。

LC-3 计算机架构：

• LC-3 特点：LC-3拥有16位的指令和16位的数据，总共支持15条基本指令，使用简单的寄存器和内存结构，适合教学。
• Input and Output
  – Keyboard (KBDR & KBSR)
  – Monitor (DDR & DSR)
• Memory
  • Address space: 2^16 memory locations
  • Addressability: 16-bit addressable, MAR and MDR
    内存：LC-3的内存地址空间为16位，意味着可以访问的地址范围是0到65535（即64 KB的内存）。
• The Processing Unit
  • ALU (ADD, AND, NOT)
  • 8 generał register (R0, R1, …, R7)
    寄存器：LC-3有8个通用寄存器（R0到R7），其中每个寄存器都是16位，用于存储操作数和结果。
• The Control Unit
  • The FSM that directs all the activities
  • The instruction Register (IR) and Program
  • Program Counter (PC)

---

Instruction

One instruction specifies two things:

• opcode: operation to be performed
  操作码：要执行的操作
• operands: data/locations to be used for operation
  操作数：用于操作的数据/位置

A computer’s instructions and their formats is known as its Instruction Set Architecture (ISA).
计算机的指令及其格式被称为其指令集架构 (ISA)。