Chapter 1 A Tour of Computer System

Compilation System

Take C language as an example linux > gcc hello.c -o hello.

• Pre-processor (cpp)

  $\text{.c}\to \text{.i}$ Handles include/define, strips off comments and conditional compilation #ifdef

• Compiler (cc1)

  $\text{.i}\to \text{.s}$ Scan/parse/semantic check/code gen/opt

• Assembler (as)

  $\text{.s}\to \text{.o}$ From assembly to machine code

• Linker (ld) $\text{.o}\to \text{Executable}$

  Relocation & reference resolution [重定位 & 引用解析]

Hardware Organization of a System

DMA (Direct Memory Access) is usually used for high-spped and bulk data transfers, controlled by system programmers.

• System Bus

  Transfer data in fixed-size blocks called words (4/8 bytes on a 32/64 bit system)

Memory Hierarchy

The localities of cache: Temporal Locality & Spatial Locality.

Abstractions in Computer Systems (Virtualization)

Virtualization is often related to multiplicity, fake versions, and sharing.

• Process & Thread

  Multiple processes can run concurrently on the same system, and each process appears to have exclusive use of the hardware.

  Context switching with OS Kernel.

  A process can actually consist of multiple execution units, called threads. Threads shares the same code and global data.

• Virtual Memory

  Program Code & Data, Shared Libraries, Heap, Stack, Kernel Virtual Memory from bottom to top.

  • Virtual address space canve greater than the physical memory.

  • Memory serves as a cache for virtaul memory.

  • Support multiprogramming.

  • Allow multiple processes to share data.

• File

Import Themes

Amdahl's Law (Quantifying the performance improvement ceiling)

$T_{new}=(1-\alpha )T_{old}+\frac{\alpha T_{old}}{k}=T_{old}(1-\alpha +\frac{\alpha }{k})$

$S=\frac{T_{old}}{T_{new}}=\frac{1}{1-\alpha +\frac{\alpha }{k}}$

Concurrency and Parallelism

• Concurrency It refers to the general concept of a system having multiple, simultaneous activities, which do not necessarily execute at the same time, but may interleave in time to create the logical impression of simultaneity.

• Parallelism It refers to the use of concureency to make a system run faster.

ILP and DLP

• Instruction-Level e.g. Parallelism pipelining, superscalar, out-of-order execution.

• Data-Level Parallelism e.g. Single Insruction Multiple Data (SIMD), Vector instructions.

Chapter 2 Representing and Manipulating Information

Information Storage

• Words

  $w$ word size $⟺$ $[0,2^w)$ virtual address space

• Addressing and Byte Ordering Big endian & Little endian

• ABI Application Binary Interface

  It is based on three key components : the computer ISA, the OS, and the calling convention. ABI incompatibility will occur due to differences between operating systems.

Integer Representaions

Sizes of Data Type in C/C++

Unsigned Encodings

Suppose a vector $\mathrm{x}=[x_{w-1},x_{w-2},\cdots ,x_0]$, then $B2{\mathrm{U}}_{\mathrm{w}}(x)=\sum _{i=0}^{w-1}{x}_i\cdot 2^i$

Two's Complement Encodings

Inverse form (1's Complement) For a negative number, keep the signed the same and invert the rest.
two zero exits & end-round carry out issues (hte end carry-out bit needs to add back to the LSB)

2's Complement For a negative number, keep the sign the same, invert the rest and add 1.

Suppose a vector $\mathrm{x}=[x_{w-1},x_{w-2},\cdots ,x_0]$, then $B2{\mathrm{T}}_{\mathrm{w}}(x)=-x_{w-1}\cdot 2^{w-1}+\sum _{i=0}^{w-2}{x}_i\cdot 2^i$

Conversions between Signed and Unsigned

$$T2{\mathrm{U}}_{\mathrm{w}}(x)=\{\begin{array}{l}x+2^w,x<0\\ x,x\ge 0\end{array}U2{\mathrm{T}}_{\mathrm{w}}(u)=\{\begin{array}{l}u,x\le Tma{x}_w\\ u-w^w,x>Tma{x}_w\end{array}$$

For a $n$-bit 2's complemetn signed binary numeral system:

• Minimum $-2^{n-1}$, corresponding to binary $\text{100}\cdots \text{0}$ (A special case that does not satisfy the invert bits and add 1 rule used for other negative numbers).
• Maximum $2^{n-1}-1$, corresponding to binary $\text{011}\cdots \text{1}$.

Sign Extension

Small to Big

• Zero extension of unsigned numbers

• Sign extension of two's complement numbers

  $B2{\mathrm{T}}_{\mathrm{w}}([x_{w-1},x_{w-2},\cdots ,w_0])=B2{\mathrm{T}}_{\mathrm{w}+\mathrm{k}}([x_{w-1},x_{w-1},\cdots ,x_{w-1},x_{w-1},x_{w-2},\cdots ,x_0])$

  Since $B2{\mathrm{T}}_{\mathrm{w}+1}-B2{\mathrm{T}}_{\mathrm{w}}=(-x_{w-1}\cdot 2^w+x_{w-1}\cdot 2^{w-1})-x_{w-1}\cdot 2^{w-1}=0$, by induction, we can proof it.

Big to Small

• $B2{\mathrm{U}}_{\mathrm{k}}(x)=B2{\mathrm{U}}_{\mathrm{w}}(x)\mathrm{mod}{2}^k$

• $B2{\mathrm{T}}_{\mathrm{k}}(x)=U2{\mathrm{T}}_{\mathrm{w}}(B2{\mathrm{U}}_{\mathrm{w}}(x)\mathrm{mod}{2}^k)$

Integer Arithmetic

Addition

$$x+y_w^u=\{\begin{array}{l}x+y,x+y<2^w\\ x+y-2^w,2^w\le x+y<2^{w+1}\end{array}$$

$$x+y_w^t=\{\begin{array}{l}x+y-2^w,2^{w-1}\le x+y\\ x+y,-2^{w-1}\le x+y<2^{w-1}\\ x+y+2^w,x+y<-2^{w-1}\end{array}$$

Additive Inverse

$x+x^{\prime }=0\text{or}{2}^w$

$$-x_w^u=\{\begin{array}{l}x,x=0\\ 2^w-x,x>0\end{array}-x_w^t=\{\begin{array}{l}x,x>Tmi{n}_w\\ Tmi{n}_w,x=Tmi{n}_w\end{array}$$

• For two numbers A, B, the overflow occurs when (NOT (sign_A XOR sign_B)) AND (sign_A XOR new_sign) == 1. (Two operands have the same sign but the result has a different sign.)

• One Bit Full Adder

  $S_i=A_i+B_i+\text{carry\_in}\text{carry\_out}=(A_i\&B_i)|(\text{carry\_in}\&(A_i\oplus B_i))$

• Carry Lookahead Adder

  $$\{\begin{array}{l}{g}_i=(A_i\cdot B_i)\\ p_i=(A_i\oplus B_i)\\ C_1=g_0+(p_0\cdot C_0)\\ C_2=g_1+(p_1\cdot g_0)+(p_1\cdot p_0\cdot C_0)\\ C_3=g_2+(p_2\cdot g_1)+(p_2\cdot p_1\cdot g_0)+(p_2\cdot p_1\cdot p_0\cdot C_0)\\ ⋮\end{array}$$

  

Multipilication

$$\begin{gathered} x\times y_w^u=(x\cdot y)\mathrm{mod}{2}^k \\ x\times y_w^t=U2{\mathrm{T}}_{\mathrm{w}}((x\cdot y)\mathrm{mod}{2}^k) \end{gathered}$$

Division (by a power of 2)

Unsigned numbers use logical shift, while two's complement numbers use arithmetic shift to achieve sign-preserving extension.

Right shift performs integer division by powers of two :

• $x\le 0x>>k=\lfloor \frac{x}{2^k}\rfloor$

• $x<0(x+(1<<k)-1)>>k=\lceil \frac{x}{2^k}\rceil$

Floating Point

Floating-Point Representation

$V=(-1{)}^s\times M\times 2^E$

s (sign) : The number is positive ($s=0$) or negative ($s=1$).

M (fraction) : A binary fraction.

E (exponent) : $2^E$ weight.

$\text{bias (float)}=127\text{bias(double)}=1023$ ($\text{bias}=2^{k-1}-1$)

Comparison (postive number)

Rounding

Floating Point Operations

Lack of Associativity & Lack of Distributivity

Precision (IEEE 754-2008 Standard Formats)

FMA/FMAC

Fused Multiply and Add (FMA) or Fused Multiply and Accumulate (FMAC) combines multiply and add in one instruction ($A\times B+C$).

1. Partial Product Generation
2. Partial Product Reduction
3. Final add together with the last step of reduction
4. Normalization & Rounding

Use -mfma -ffp-contract=fast to enable FMA.

Chapter 3 Machine-Level Representation of Programs

Machine-Level Representation of Programs

RISC

Principles

1. Simplicity favors regularity
2. Smaller is faster
3. Make common cases fast
4. Good design demands good compromises

[RSA should be scalable, flexible, and extensible.]

Instruction Types in RV32I

• Three operand instruction format.

• X0 is always zero.

• 32 means Address cability/Integer register length.

• Immediate

  • $\text{R}$ type No immediate.
  • $\text{B,I}$ type 12 bits immediate. Shift instructions are I-type but repurpose the immediate field as a 5-bit shift amount for RV32I (6-bit for RV64I). inst[30] distinguishes arithmetic from logical right shift, while inst[31:26] are fixed to zero except inst[30] (Range: $\pm 4\text{KB}$).
  • $\text{S}$ type The 12‑bit immediate is split into high 7 bits (immediate) and low 5 bits (immed). (maintain regularity)
  • $\text{J}$ type 20 bits immediate.

• LUI loads a 20‑bit immediate into the upper bits of a register; AUIPC adds a 20‑bit immediate to the current PC for position‑independent addressing. (When the lower 12 bits of a 32‑bit constant are $\ge \text{0x800}$, addi sign‑extends them, causing an incorrect result. The assembler automatically adjusts the upper 20 bits when using the li pseudo‑instruction.) (Range: $4\text{GB}$)

• Jump

  • jal

    • $rd\leftarrow PC+4$, $PC\leftarrow PC+\text{sign-extend}(\{\text{inst}[31],\text{inst}[19:12],\text{inst}[20],\text{inst}[30:21]\})\times 2$ (Jumps are 2-byte aligned, so last bit is implicit zero).
    • Range: $\pm 1\text{MB}$.
    • Beyond 1MB: Use AUIPC + JALR.

  • jalr

    • $rd\leftarrow PC+4$, $PC\leftarrow (rs1+\text{sign-extend}(\text{inst}[31:20]))\&\sim 1$ ($\sim 1$ clears LSB to ensure 2‑byte alignment).

Data Alignment

• No cache line crossing
• No double TLB (Translation Lookaside Buffer) misses
• No double page faults come from a single memory instruction execution
• Better cache line utilization

Stack / Frame Alignments

• Defined by ABI (e.g., RISC‑V psABI: 16‑byte)
• CRT aligns sp before main ()

Compiler Reordering

• Independent Variables (Rearrangement Allowed)

• Struct Fields (Rearrangement Forbidden)

  • Binary compatibility
  • Pointer arithmetic
  • Interoperability

PC-relative Addressing

Branch instructions use PC‑relative addressing with a 12‑bit signed offset (in 2‑byte units). Since branch targets are always multiples of 2, encoding in 2‑byte units doubles the reachable range without losing information.

$$\text{Target Address}=\text{PC}+\text{sign\_extend}(12\text{-bit immediate})\times 2$$

Calling Convention

Leaf routines use args & caller‑saved only (no save/restore).

CISC

Size of Data Type in IA32

Register

Operands

• Immediate

• Register

• Memory Reference Immediate & Base Register & Index Register & Scale Factor (1,2,4,8)

Operation code

• Movement

  • $\text{mov}\text{S,D}$ [movb, movw, movl, movq, movabsq]

    Source operand (Immedita, Register, Memory); Destination operand (Register, Memory)

    Two operands of a move instruction cannot both be memory references. (It is necessary to first move the source memory reference into a register, and then move it to the destination memory reference.)

    movl writes 32 bits of data to the lower half and then automatically zero-extends the value into the upper 32 bits. (In x86-64, any instruction that generates a 32-bit result for a register will set the upper 32 bits of that register to zero.)

    movq can only be 32 bits (sign-extended to 64 bits), whereas movabsq can be 64-bit but the destination must be a register.

  • $\text{movz}\text{S, R}$ [movzbw, movzbl, movzwl, movzbq, movzwq]

    movzlq does not exist because of movl instruction.

  • $\text{movs}\text{S, R}$ [movsbw, movsbl, movswl, movsbq, movswq, movslq, cltq]

    cltq same as movslq %eax, %rax

• Stack

  let a quad number be the example

  • $\text{pushq}S$

    subq $8 %rsp
    movq %rbq,(%rsp)
    

  • $\text{popq}S$

    movq (%rsq),%rax
    addq $8, %rsp
    

Load Effective Address

$\text{leaq}S,D$

Computes effective address and stores it in destination register

Unary Operations

Binary Operations

Shift Operations

Shift instructions can shift by an immediate value, or by a value placed in the single-byte register %cl.

Condition Code

• $\text{CF}$ Carry Flag [check for overflow in unsigned operations]

• $\text{ZF}$ Zero Flag

• $\text{SF}$ Sign Flag

• $\text{OF}$ Overflow Flag

• $\text{cmpS D}$

  Similar to sub, but it only sets the condition codes without changing the value of the destination register.

  When S == D, $\text{ZF}=1$.

  It will set the condition codes based on the result of $D-S$.

• $\text{testS D}$

  Similar to and, but it only sets the condition codes without changing the value of the destination register.

  When S & D == 0, $\text{ZF}=1$.

Set Instructions

Jump Instructions

Conditional Move Instructions

Loop

do-while, while, and for loops can be implemented by combining conditional tests and jumps.

Switch

switch is compiled into a jump table. The execution time of the switch statement is irrelevant to the number of cases.

Transfer Control

Data Transfer

The registers' names depend on the size of the data type being passed.

If a function has more than 6 integer parameters, the additional arguments must be passed on the stack. Note that the argument 7 is located at the top of the stack. All stack-passed arguments are aligned to multiples of 8 bytes.

Pointer

Notes:

1. &E[i] - E yields type long (specifically ptrdiff_t) because pointer subtraction returns the number of elements between them as a signed integer.

2. int* uses movq (not movl) because pointers are 64-bit addresses in x86-64.

Nested Arrays

T D[R][C] $\&D[R][C]=x_D+L(C\cdot i+j)$, $L$ is the size of data type T in bytes.

Struture & Union

Structure

Notes:

1. The address of any K-byte basic object must be a multiple of $K$.

2. The offset of the first member is always 0 in a structure.

3. The compilers probably add some bytes at the end of a structure to ensure that each element in an array of structures could satisfy its alignment requirements.

Union

The total size of a union equals the size of its largest field.

Application

Buffer Overflow

Three protection mechanisms to thwart buffer overflow attacks:

• Stack Randomization Address-Space Layout Randomization (ASLR)

• Stack Corruption Detection Place a random canary value between local buffers and critical stack data to detect buffer overflows.

• Limiting Executable Code Regions

Dynamic Stack Frame

%rbp is base pointer/frame pointer dynamic stack frame

Floating-point Code

Chapter 4 Processor Architecture

Logic Design and Hardware Control Language (HCL)

Logic Gate

CMOS

Process

$\text{Fetch}\to \text{Decode}\to \text{Execute}\to \text{Memory}\to \text{Write Back}\to \text{Update}$

For Y86-84 :

1. Fetch

   • Read instruction bytes from memory using PC:
     • icode:ifun (instruction specifier)
     • rA, rB (register specifiers)
     • valC (8-byte constant)
   • Compute next instruction address → valP

2. Decode

   • Read up to two operands from registers
   • rA, rB → valA, valB
   • For popq, pushq, call, ret: also read from %rsp

3. Execute

   • Compute (ALU/address/stack) → valE
   • Set condition codes
   • Conditional moves: check CC, update dest register
   • Jumps: decide branch

4. Memory

   • Write to memory
   • Read from memory → valM

5. Write Back

   • Write up to two results to registers

6. Update

   • Set PC to next instruction address

Pipelining

• Throughput the number of instructions in one second.

  GIPS: Giga-Instructions Per Second

• Circuit Retiming

  Repositions registers within a design to optimize performance or area, without altering the system’s input/output behavior. It changes the state encoding by moving delays (registers) across combinational logic elements.

Hazards

The dependency between instructions may lead to incorrect computation results.

Data Hazards

• Stalling

  Stalling prevents data hazards by pausing the pipeline until required operands are ready. This approach is simple but reduces performance.

• Data Forwarding (Bypassing)

  Data forwarding allows a result computed in a later pipeline stage to be passed directly to an earlier stage as a source operand.

• Load/Use Hazards

  A load/use hazards occurs when an instruction requires a value that is still being loaded from memory by the previous instruction. Since the memory read completes late in the pipeline, forwarding cannot resolve the dependency in time, causing a stall.

Control Hazards

Control hazards occur when the processor cannot determine the next instruction's address during the fetch stage. In a pipelined processor, this typically happens for ret instructions and mispredicted conditional jumps.

• ret Inserting bubbles to wait for the return address to be determined.

• Conditional Jump Branch mispredictions are handled by cancelling the erroneously fetched instructions through the insertion of pipeline bubbles (or via instruction squashing) in the decode and execute stages.

Pipelined Y86-64 Implementations

Fetch Stage

1. Sequential Execution

halt, nop, rrmovq, irmovq , mrmovq, Opq, pushq, popq, covXX, addq

2. Jump Execution

call, jxx (The Select PC mechanism is employed to correct branch mispredictions.)

3. ret

Decode Stage

The selection logic chooses between the merged valA/valP signals and one of five forwarding sources (e_valE, m_valM, M_valE, W_valM, or W_valE) based on the instruction type and hazard detection. If no forwarding is triggered, d_rvalA (the register file read) is used as the default value.

Pipeline Control Logic

• Stall

  Keep the state of the pipeline registers unchanged. When the stall signal is set to 1, the register will retain its previous state.

• Insert Bubbles

  Setting the state of the pipeline registers to a value equivalent to a nop instruction. When the bubble signal is set to 1, the state of the register will be set to a fixed reset configuration.

Load/Use Data

A one-cycle pipeline stall is required between an instruction that reads a memory value in the execute stage and a subsequent instruction that uses that value in the decode stage.

Mispredicted Branches

When a branch is mispredicted as taken, the pipeline must squash the incorrectly fetched instructions from the target path and redirect fetching to the correct fall-through address.

Processing ret

The pipeline must stall until the ret instruction reaches the write-back stage.

Exception Handling

When an instruction triggers an exception, all subsequent instructions must be prevented from updating programmer-visible state, and execution must halt once the exception-causing instruction reaches the write-back stage.

Chapter 5 Optimizing Program Performance

Capabilities and Limitations of Optimizing Compilers

Memory Aliasing

The two pointers probably reference the same memory address.

Function Calls

Performance

CPE: Cycles Per Element.

Understanding Modern Processors

Instruction Control Unit (ICU) & Execution Unit (EU)

The ICU reads instructions from the instruction cache and uses branch prediction to speculatively fetch and decode future instructions in advance. This speculative execution mechanism allows the processor to start executing operations along the predicted program path before the actual branch outcome is known. If the prediction is incorrect, all speculative results are discarded and execution restarts from the correct branch target.

Decoded instructions are broken down into micro-operations, which are then sent to the EU for execution. The EU includes arithmetic units and dedicated load/store units, each with address calculation logic, to perform memory operations via the data cache.

All along, the retirement unit tracks instruction progress to ensure sequential program semantics are preserved. Instructions remain in a queue until their results are ready and all relevant branch predictions are verified. Only then are results committed to the architectural registers. If a branch was mispredicted, the affected instructions are flushed and their results discarded, preventing any erroneous state change in the program.

Register renaming allows out-of-order execution by assigning unique tags to instruction results. When a later instruction needs a register value, it uses the tag to get the result directly once ready, avoiding waits for register writes and enabling speculative execution.

Each operation is characterized by the following metrics:

• latency It represents the total time required to complete the operation.

• Issue time It indicates the minimum number of clock cycles needed between two consecutive operations of the same type.

• Capacity It refers to the number of functional units capable of executing that operation.