본문으로 건너뛰기

Instructions: Language of the Computer

2.1 Introduction​

1) Instruction Set​

Instruction: A command encoded in binary that tells a processor which operation to perform.

Instruction Set Architecture (ISA): The interface between hardware and low-level software that defines instructions, registers, data types, addressing modes, and memory behavior.

Stored-Program Concept: The principle that instructions and data are both represented as numbers and stored in memory.

MIPS: A RISC instruction set architecture used in this chapter to explain fundamental computer instructions.

Design Principle 1 — Simplicity Favors Regularity: Regular instruction structures make hardware simpler to design and implement.

2.2 Operations of the Computer Hardware​

1) Arithmetic Instructions​

Operand: A value or storage location used as an input to or output from an instruction.

add: A MIPS instruction that adds two register values and stores the result in a register.

add $s0, $s1, $s2    # $s0 = $s1 + $s2

sub: A MIPS instruction that subtracts one register value from another and stores the result in a register.

sub $s0, $s1, $s2    # $s0 = $s1 - $s2

Design Principle 2 — Smaller Is Faster: A small hardware structure can generally be accessed faster than a large one.

2.3 Operands of the Computer Hardware​

1) Registers​

Register: A small and fast storage location inside the processor.

Register File: The collection of registers that processor instructions can read and write.

Word: The natural unit of data processed by an architecture; a word is 32 bits in the MIPS architecture used here.

2) Memory Operands​

Byte Addressing: A memory organization in which each byte has its own address.

Alignment: The requirement that a data item begin at an address appropriate for its size.

Load Word (lw): A MIPS instruction that copies a 32-bit word from memory into a register.

lw $s0, 8($sp)       # $s0 = Memory[$sp + 8]

Store Word (sw): A MIPS instruction that copies a 32-bit word from a register into memory.

sw $s0, 8($sp)       # Memory[$sp + 8] = $s0

Effective Address: The memory address calculated by adding an offset to a base-register value.

Effective address=Base address+Offset\text{Effective address} = \text{Base address} + \text{Offset}

3) Immediate Operands​

Immediate Operand: A constant value encoded directly inside an instruction.

addi: A MIPS instruction that adds an immediate value to a register value.

addi $s0, $s1, 10    # $s0 = $s1 + 10

Constant Zero Register ($zero): A MIPS register whose value is always 0.

2.4 Signed and Unsigned Numbers​

1) Unsigned Integers​

Unsigned Integer: An integer representation that uses all bits for zero or positive values.

0≤x≤2n−10 \le x \le 2^n-1

2) Two's Complement​

Two's Complement: A signed representation in which the most significant bit has a negative weight.

−2n−1≤x≤2n−1−1-2^{n-1} \le x \le 2^{n-1}-1

Two's-Complement Negation: Invert every bit and add 1 to obtain the negative of a value.

Sign Extension: Increasing a signed value's width by copying its sign bit into the new upper bits.

3) Overflow​

Overflow: A condition in which an arithmetic result cannot be represented with the available number of bits.

Signed Addition Overflow: Overflow occurs when two operands with the same sign produce a result with the opposite sign.

2.5 Representing Instructions in the Computer​

1) Machine Instruction Encoding​

Instruction Format: The arrangement and meaning of the bit fields within a machine instruction.

Opcode: The instruction field that identifies the operation to perform.

R-format: A 32-bit MIPS instruction format mainly used for register-to-register operations.

oprsrtrdshamtfunct
6 bits5 bits5 bits5 bits5 bits6 bits

I-format: A 32-bit MIPS instruction format used for immediate, load/store, and branch instructions.

oprsrtimmediate
6 bits5 bits5 bits16 bits

Design Principle 3 — Good Design Demands Good Compromises: Instruction formats balance regularity, instruction width, register count, and immediate range.

2.6 Logical Operations​

1) Bitwise Operations​

Bitwise AND (and): Produces 1 only where both corresponding operand bits are 1.

Bitwise OR (or): Produces 1 where either corresponding operand bit is 1.

Bitwise NOR (nor): Produces the inverse of the bitwise OR result.

Mask: A bit pattern used to select, clear, or set particular bits.

2) Shift Operations​

Logical Shift Left (sll): Moves bits left and inserts zeros on the right.

Logical Shift Right (srl): Moves bits right and inserts zeros on the left.

2.7 Instructions for Making Decisions​

1) Conditional Branches​

Conditional Branch: An instruction that changes control flow only when a condition is true.

Branch if Equal (beq): Branches when two register values are equal.

Branch if Not Equal (bne): Branches when two register values are different.

Basic Block: A sequence of instructions with no branch into the middle and no branch out except at the end.

2) Unconditional Jumps​

Jump (j): A MIPS instruction that unconditionally changes execution to a target address.

3) Comparison​

Set on Less Than (slt): Writes 1 when one signed register value is less than another and 0 otherwise.

Unsigned Comparison (sltu): Performs the comparison by interpreting both operands as unsigned values.

2.8 Supporting Procedures in Computer Hardware​

1) Procedure Calls​

Procedure: A reusable sequence of instructions that performs a task and can be called from another part of a program.

Return Address: The instruction address at which execution resumes after a procedure finishes.

Jump and Link (jal): Jumps to a procedure and saves the return address in $ra.

Jump Register (jr): Jumps to the address stored in a register; jr $ra commonly returns from a procedure.

2) Calling Convention​

Calling Convention: Rules defining how procedures pass arguments, return values, preserve registers, and use the stack.

RegistersPurposePreservation rule
$a0–$a3ArgumentsUsed to pass parameters
$v0–$v1Return valuesUsed to return results
$raReturn addressSet by jal
$s0–$s7Saved valuesCallee restores them if changed
$t0–$t9TemporariesCallee may overwrite them

3) Stack and Memory Allocation​

Stack: A last-in, first-out memory area used for procedure-local data, saved registers, and return information.

Stack Pointer ($sp): A register that points to the current top of the stack.

Stack Frame: The portion of the stack allocated for one active procedure call.

Heap: A memory area used for dynamically allocated data whose lifetime is controlled at runtime.

2.9 Communicating with People​

1) Character Representation​

Character Encoding: A mapping between characters and numerical values.

ASCII: A character encoding for basic English letters, digits, punctuation, and control characters.

Unicode: A universal character standard that assigns a code point to characters from many writing systems.

UTF-8: A variable-length Unicode encoding that represents a code point with one to four bytes.

2) Byte Load and Store​

Load Byte (lb): Loads one byte from memory and sign-extends it to a register.

Load Byte Unsigned (lbu): Loads one byte from memory and fills the upper register bits with zeros.

Store Byte (sb): Stores the least significant byte of a register in memory.

2.10 MIPS Addressing for 32-bit Immediates and Addresses​

1) Large Constants​

Load Upper Immediate (lui): Places a 16-bit immediate in the upper half of a register and fills the lower half with zeros.

2) Program Addresses​

Program Counter (PC): A processor register containing the address of the instruction being executed or the next instruction.

PC-Relative Addressing: Calculates a branch target by adding a signed offset to the program counter.

Addressing Mode: A rule used by an instruction to locate an operand or target address.

ModeOperand or address source
Register addressingValue in a register
Immediate addressingConstant inside the instruction
Base addressingRegister value plus offset
PC-relative addressingProgram counter plus offset
Pseudodirect addressingPC upper bits plus jump field

2.11 Parallelism and Instructions: Synchronization​

Data Race: Concurrent accesses to the same data, including at least one write, whose result depends on execution timing.

Atomic Operation: An operation that appears to execute as one indivisible step.

Lock: A synchronization mechanism that allows only one task at a time to enter a critical section.

Critical Section: Code that accesses shared data and must not be executed concurrently by multiple tasks.

Load Linked (ll) and Store Conditional (sc): A pair of MIPS instructions used to implement an atomic read-modify-write operation.

2.12 Translating and Starting a Program​

1) Translation Process​

Compiler: Translates high-level source code into assembly code, machine code, or an intermediate representation.

Assembler: Translates assembly language into machine code and produces an object file.

Pseudoinstruction: An assembly instruction that the assembler expands into one or more real machine instructions.

Object File: A file containing machine code, symbols, and relocation information.

Symbol Table: A table containing names such as labels and global variables and information required to resolve them.

Relocation Information: Information identifying addresses that must be adjusted after final code and data locations are known.

2) Linking and Loading​

Linker: Combines object files and libraries, resolves external symbols, and produces an executable file.

Executable File: A complete program in a form that an operating system can load and execute.

Loader: Places an executable in memory, initializes its execution state, and starts it.

Static Linking: Copies required library code into the executable before execution.

Dynamic Linking: Connects shared-library code to a program at load time or runtime.

3) Program Translation Pipeline​

Program Translation Pipeline: Source code passes through compilation, assembly, linking, and loading before the processor executes it.

Source code→Assembly code→Object files→Executable→Running program\text{Source code} \rightarrow \text{Assembly code} \rightarrow \text{Object files} \rightarrow \text{Executable} \rightarrow \text{Running program}

2.13 C and Assembly Language​

Instruction Sequence: An ordered group of machine instructions that implements a higher-level operation.

Register Allocation: The compiler process of assigning program values to a limited number of processor registers.

Spilling: Moving a value from a register to memory because there are not enough registers.

2.14 Arrays versus Pointers​

Array Indexing: Accessing an array element by calculating its address from the base address, index, and element size.

Element address=Base address+(Index×Element size)\text{Element address} = \text{Base address} + (\text{Index} \times \text{Element size})

Pointer: A value that stores the memory address of an object.

Pointer Arithmetic: Arithmetic that moves a pointer between elements according to the element size.

2.15 Compiling C and Interpreting Java​

Ahead-of-Time Compilation (AOT): Translation of a program into machine code before execution begins.

Interpreter: A program that reads and executes another program during runtime.

Java Virtual Machine (JVM): An abstract execution environment that runs Java bytecode.

Bytecode: A portable intermediate instruction representation executed by a virtual machine.

Just-in-Time Compilation (JIT): Compilation of code into native machine code while a program is running.

2.16–2.18 Other Instruction Set Architectures​

Reduced Instruction Set Computer (RISC): An ISA approach emphasizing simple, regular instructions and efficient execution.

Complex Instruction Set Computer (CISC): An ISA approach containing more varied and complex instructions and addressing modes.

ARM: A widely used RISC ISA found in mobile, embedded, and general-purpose systems.

x86: A widely used ISA that preserves compatibility with earlier generations of Intel-compatible processors.

Backward Compatibility: The ability of a newer processor to execute software built for an older version of its ISA.

2.19 Fallacies and Pitfalls​

Powerful Instruction Fallacy: A more complex individual instruction does not necessarily make the entire program faster.

Assembly Language Performance Fallacy: Hand-written assembly is not always faster than compiler-generated code.

Byte-Addressing Pitfall: Consecutive 32-bit words in byte-addressed memory have addresses that differ by four, not one.

Sign-Extension Pitfall: Extending a signed value with zeros instead of copies of its sign bit changes negative values.

2.20 Essential Relationships​

Hardware-Software Interface: Software communicates with processor hardware through the ISA.

Register-Memory Relationship: Arithmetic instructions operate primarily on registers, while load and store instructions transfer data between registers and memory.

Instruction Encoding: Assembly instructions are encoded into fixed-width bit fields that identify operations, registers, and constants or addresses.

Control Flow: Branch, jump, procedure-call, and return instructions determine which instruction the processor executes next.

Procedure Support: Registers, the stack, jump instructions, and calling conventions cooperate to implement function calls.

Program Translation: Source code is compiled, assembled, linked, loaded, and finally executed as machine instructions.