Instruction set architecture and formats

Why it exists

Software never sees transistors. It sees an instruction set architecture (ISA): the list of instructions, the registers, the ways to name memory and the data formats. Everything below the ISA (pipelines, caches, the number of ALUs) can change between processor generations while old programs keep running, and everything above it (compilers, operating systems) is written against it. Choices made in the ISA decide code size, how fast the hardware can be, and how hard the compiler's job is. GATE asks you to classify an ISA by its operand storage, to count instructions or memory references for an expression, to compute address bits, and to know what endianness and alignment mean.

Prerequisites

You need the instruction cycle from the instruction cycle and two's complement numbers from signed number representation.

Precise definitions

ISA. The programmer-visible interface of a processor: the instruction set and its encoding, the registers (number, width, special roles), the data types, the memory model (address size, byte order, alignment), the addressing modes, and how exceptions and interrupts are handled. The organization (how it is built) and the hardware (the technology) are separate and may change while the ISA stays.

Classification by operand storage. Where do the operands of an arithmetic instruction live?

Fewer explicit operands make instructions shorter and decoding simpler but need more instructions or more memory traffic; more explicit operands do more work per instruction but make instructions long and slow to decode.

Number of addresses in an instruction. Three-address: $X \leftarrow Y \circ Z$. Two-address: $X \leftarrow X \circ Y$ (the destination is also a source). One-address: uses an implied accumulator. Zero-address: stack operands. Instruction formats and the opcode space are treated in formats and expanding opcodes.

Types of operations. Data transfer (load, store, move, push, pop), arithmetic and logic (add, subtract, multiply, shifts, compare, and so on), control flow (jump, conditional branch, call, return), system (traps, privileged instructions, I/O), and floating point.

Memory model.

• Byte addressing. Each address names one byte. A memory with an $n$-bit address holds $2^n$ bytes. With a word-addressable memory each address names a word, so $n$ address bits name $2^n$ words.
• Endianness. Which byte of a multi-byte value goes at the lowest address. Little-endian: the least significant byte at the lowest address. Big-endian: the most significant byte first. The value $\texttt{0x12345678}$ at address $a$ is stored (lowest address first) as 78 56 34 12 in little-endian and 12 34 56 78 in big-endian.
• Alignment. A $k$-byte datum is aligned if its address is a multiple of $k$. Aligned accesses are one memory transfer; misaligned ones may need two, or may be forbidden. Compilers add padding to keep structure fields aligned.

Control-flow conditions. Two styles: condition codes (flags N, Z, C, V set by arithmetic and compare instructions, then tested by conditional branches: see fixed-point arithmetic for how unsigned and signed comparisons use $C$ and $N \oplus V$) and compare-and-branch (one instruction compares two registers and branches, with no flags).

Instruction length. Fixed length (all instructions the same size, such as 4 bytes) makes fetch and decode simple and pipelining easy; variable length gives smaller programs but harder decoding.

Cost of the ISA choice. Execution time = instruction count $\times$ CPI $\times$ clock period. The ISA mainly sets the first factor and limits the others.

How it works

The best way to see the difference between ISA classes is to run the same expression, $X = (A + B) \times (C + D)$, on each of them. The animation shows the zero-address (stack) machine: ADD and MUL carry no operand addresses at all, they work on the top of the stack, with the stack growing toward lower addresses.

The five instruction sequences (written out in the examples below) are each executed by a small interpreter and give the same answer. The cost differs:

(Code bytes assume a 1-byte opcode and 2-byte memory addresses, and 4-byte fixed instructions for the load-store machine. The point is the comparison, not the absolute numbers: the stack and register machines touch memory least, the memory-memory machines need the fewest instructions but the most data traffic.)

Worked examples

#include <stdio.h>
#include <stdint.h>
#include <stddef.h>
 
struct padded { char c; int i; char d; };
struct packed_order { int i; char c; char d; };
 
int main(void) {
    union { uint32_t word; uint8_t byte[4]; } u = { 0x12345678u };
    printf("word 12345678 is stored as bytes %02X %02X %02X %02X (byte 0 first)\n", u.byte[0], u.byte[1], u.byte[2], u.byte[3]);
    printf("so this machine is %s-endian\n", u.byte[0] == 0x78 ? "little" : "big");
    printf("struct padded: size %zu, offsets %zu %zu %zu\n", sizeof(struct padded), offsetof(struct padded, c), offsetof(struct padded, i), offsetof(struct padded, d));
    printf("struct packed_order: size %zu, offsets %zu %zu %zu\n", sizeof(struct packed_order), offsetof(struct packed_order, i), offsetof(struct packed_order, c), offsetof(struct packed_order, d));
    uint32_t swapped = ((u.word & 0xFF) << 24) | ((u.word & 0xFF00) << 8) | ((u.word >> 8) & 0xFF00) | (u.word >> 24);
    printf("the same bytes read in the other order: %08X\n", swapped);
    return 0;
}

word 12345678 is stored as bytes 78 56 34 12 (byte 0 first)
so this machine is little-endian
struct padded: size 12, offsets 0 4 8
struct packed_order: size 8, offsets 0 4 5
the same bytes read in the other order: 78563412

Cheat box

Traps and GATE patterns

Connections

The fields that fit into one instruction word and the number of opcodes available are the subject of instruction formats and expanding opcodes. How an operand is named is addressing modes. The contrast between the two main philosophies of ISA design is RISC versus CISC, and the hardware that runs each instruction is described in the datapath. The flags are the same ones produced by the adder of fixed-point arithmetic.

PYQs

If the numerical value of a 2-byte unsigned integer
on a little endian computer is 255 more than that
on a big endian computer, which of the following
choices represent(s) the unsigned integer on a little
endian computer?

Consider a processor P whose instruction set
architecture is the load-store architecture. The
instruction format is such that the first operand of
any instruction is the destination operand. Which
one of the following sequences of instructions
corresponds to the high-level language statement
Z = X + Y?
Note: X, Y, and Z are memory operands. R0, R1,
and R2 are registers.

An application executes 6.4 × 108 number of
instructions in 6.3 seconds. There are four types of
instructions, the details of which are given in the
table. The duration of a clock cycle in nanoseconds
is
(rounded off to one decimal place).

Instruction
type
Clock cycles
required per
instruction
(CPI)
Number of
instruction
executed
Branch
2
2.25 × 108
Load
5
1.20 × 108
Store
4
1.65 × 108
Arithmetic
3
1.30 × 108
3 3
Computer Organization and Architecture

Which of the following is/are part of an Instruction
Set Architecture of a processor?

Consider the given C-code and its corresponding
assembly code, with a few operands U1-U4 being
unknown. Some useful information as well as the
semantics of each unique assembly instruction is
annotated as inline comments in the code. The
memory is byte-addressable.

;assembly code (; indicates comments)
;r1-r5 are 32-bit integer registers
//C-code
;initialize r1=0, r2=10
;initialize r3, r4 with base address of a, b
L01: jeq r1, r2, end ;if(r1==r2) goto end
L02: lw, r5, 0(r4) ;r5 <- Memory[r4+0]
int a[10], b[10], i;
L03: sh1, r5, r5, U1 ;r5 <- r5 << U1
// int is 32 bit
L04: sw, r5, 0(r3) ;Memory[r3+0] <- r5
for(i=0; i<10; i++)
L05: add, r3, r3, U2 ;r3 <- r3+U2
a[i] = b[i] * 8;
L06: add, r4, r4, U3
L07: add, r1, r1, 1
L08: jmp U4 ;goto U4
L09: end
Which one of the following options is a CORRECT
replacement for operands in the position (U1, U2,
U3, U4) in the above assembly code?

In a simplified computer the instructions are:

OP Rj, Ri
Perform Rj OP Ri and store the result in
register Rj
OP m, Ri
Perform val OP Ri and store the result in
register Ri
val denotes the content of the memory
location m
MOV
m, Ri
Moves the content of memory location
m to register Ri
MOV
Ri, m
Moves the content of register Ri to
memory location m

The computer has only two registers, and OP is either
ADD or SUB. Consider the following basic block:

t1 = a + b

t2 = c + d

t3 = e - t2

t4 = t1 - t3
Assume that all operands are initially in memory. The
final value of the computation should be in memory.
What is the minimum number of MOV instructions in
the code generated for this basic block?

Self-check

Revision card

References