5 Great Ideas in Computer Architecture
- Abstraction (Layers of Representation/Interpretation)
- Moore’s Law (Designing through trends)
- Principle of Locality (Memory Hierarchy)
- Parallelism & Amdahl’s law (which limits it)
- Dependability via Redundancy
ENIAC (U.Penn., 1946)
First Electronic General-Purpose Computer
EDSAC (Cambridge, 1949)
First General Stored-Program Computer
Two’s Complement 补码
One’s Complement 反码
CPP (C Pre-Processor)
CPP replaces comments with a single space
CPP commands begin with “#”
Constants can be found at: Code, static, or stack
String Literals can be found at: Static or stack
Undefined Behavior: “heisenbugs”
In contrast to “Bohrbugs” which are deterministic
C pass basic parameters “by value”
C Program’s address space:
Stack Heap StaticData Code
Realloc Can Move Data
Anything you put explicitly in quotes becomes a constant string. For efficiency, these strings are stored as read only global variables. It is undefined behavior to write to a constant string, But fortunately it is usually an immediate crash.
Why Do Memory Leaks Slow Things Down?
Memory leaks lead to fragmentation. As a consequence you use more memory, and its more scattered around. Computers are designed to access contiguous memory.
Instruction set architecture (ISA) specifies the set of commands (instructions) a computer can execute.
RISC-V: 32bit Instruction, 32 registers.
RISC-V does not require that integers be word aligned.
Instructions must be word aligned, or half-word aligned if the 16b optional © instruction set is also enabled.
NOP add x0 x0 x0
12bits imm, immediates are “sign extended”
Shift right arithmetic is sign extended,
Shift Right Logical is not, insert 0s.
Six Fundamental Steps in Calling a Function (The Calling Convention)
Put parameters in a place where function can access them
Transfer control to function
Acquire (local) storage resources needed for function
Perform desired task of the function
Put result value in a place where calling code can access it and maybe restore any registers you used
Return control to point of origin.
(Note: a function can be called from several points in a program, including from itself.)
Prologue ○ Before function begins ○ Stores saved registers that the function will use ○ Decrement the stack pointer to allocate space on the stack ○ If the function calls another function during its routine, also needs to store ra
Epilogue ○ After function completes ○ Restores saved registers that the function used ○ Increment the stack pointer to free space on the stack ○ If the function called another function during its routine, also needs to restore ra
a0-a7, ra, t0-t6
sp, s0-s11, (ra), (fp(s0), gp, tp)
Functions called with jal, return with jr ra.
R-format for register-register arithmetic/logical operations
I-format for register-immediate ALU operations and loads, JALR
S-format for stores
B-format for branches
U-format for 20-bit upper immediate instructions
J-format for jumps
Immediate is always sign-extended to 32-bits before use in an arithmetic operation. (Unless unsigned)
PC-Relative Addressing: Use the immediate field as a two’s-complement offset relative to PC.
RISC-V conditional branches can only reach ± 2^10 × 32-bit instructions either side of PC
Syntax of Multiplication (signed):
mul rd, rs1, rs2
mulh rd, rs1, rs2
If you do mulh/mul back to back, the architecture can fuse them.
Syntax of Division (signed):
div rd, rs1, rs2
rem rd, rs1, rs2
Compiler converts a single HLL file into a single assembly language file.
Assembler removes pseudoinstructions, converts what it can to machine language, and creates a checklist for the linker (relocation table). A .s file becomes a .o file.
- Does 2 passes to resolve addresses, handling internal forward references
Assembler Directives .text: Subsequent items in user text
.data: Subsequent items in user data
.globl sym: declares sym global, can reference in other files
.string str: store str in memory and null-terminate it
.word w1…wn: store n 32-bit ints in successive memory words
Linker combines several .o files and resolves absolute addresses.
- Enables separate compilation, libraries that need not be compiled, and resolves remaining addresses
Loader loads executable into memory and begins execution.
In reality, loader is the operating system (OS). And these days, the loader actually does a lot of the linking.
Symbol table contains labels that can be used across other files.
And relocation table contains labels within this file of which addresses are not yet resolved.
The loader reads the header of the executable file to determine the size of text and data segments, not the object files.
j label == jal x0 label
jr reg == jalr x0 reg