Instruction cycle

Why it exists

A computer does not know what a program is. It has a memory full of numbers and a small loop built into the hardware: take the number the program counter points to, treat it as an instruction, do what it says, and move on. Every program ever run is this loop repeated billions of times per second. The instruction cycle is that loop. Understanding it explains what the processor registers are for, why a jump is just an assignment to the program counter, why indirect addressing costs an extra memory access, and why the pipeline (a later topic) is an attempt to run several cycles at once. GATE questions ask which register holds what, what the PC contains at a given moment, how many memory accesses or clock cycles an instruction takes, and what the register transfers of a given instruction are.

Prerequisites

You need registers and their load and shift operations from registers and shift registers, and a picture of memory as numbered words.

Precise definitions

Stored-program computer (von Neumann architecture). Instructions and data are kept in the same memory and both are binary words. The processor fetches an instruction exactly as it fetches data; what the word means depends only on when it is used. A Harvard architecture has separate instruction and data memories (so an instruction and a data word can be fetched at the same time); modern caches are usually split this way.

The registers of the basic processor.

The instruction cycle repeats these phases:

1. Fetch. Read the instruction at the address in PC into IR and advance PC.
2. Decode. The control unit examines the opcode (and addressing-mode bits) in IR and decides which micro-operations follow.
3. Indirect cycle (only for indirect addressing). Read the word at the given address to get the effective address of the operand.
4. Execute. Carry out the operation: read an operand, use the ALU, write a result, or change PC.
5. Interrupt check. If an enabled interrupt is pending, save PC and jump to the interrupt handler before fetching the next instruction (interrupts).

Register-transfer notation (RTL). A micro-operation is written $\text{destination} \leftarrow \text{source}$; $M[\text{MAR}]$ means the memory word at that address. The fetch of the basic machine is:

$\text{MAR} \leftarrow \text{PC};\quad \text{MDR} \leftarrow M[\text{MAR}];\quad \text{IR} \leftarrow \text{MDR};\quad \text{PC} \leftarrow \text{PC} + 1 .$

Several transfers that use different buses and do not depend on each other can happen in the same clock (for example $\text{PC} \leftarrow \text{PC}+1$ alongside the memory read), so the number of clocks for a fetch depends on the design. Here every transfer takes one clock so that each is visible.

Key facts about the PC. After the fetch, PC points to the next instruction (the address after the current one, i.e. current address plus the instruction length), not to the one being executed. A jump or taken branch simply overwrites PC with the target address; an untaken conditional branch leaves it alone. This is why PC-relative offsets are measured from the next instruction.

Memory references per instruction. Every instruction costs at least 1 (its own fetch). A direct memory operand adds 1 read or write. An indirect operand adds 1 more read (to get the address). An instruction using only registers or an immediate operand adds none.

Cost. If each micro-operation takes one clock, the cycle counts (for the basic machine in the animations) are: fetch 4, decode 1, then execute 3 for a direct load, add or store, 1 for a halt, and 2 more clocks for an indirect operand (indirect cycle). The average clocks per instruction is CPI, and execution time is $\text{instructions} \times \text{CPI} \times \text{clock period}$ (performance).

How it works

The animation runs this program on a small accumulator machine with 16-bit words (indirect bit, 3-bit opcode, 12-bit address): LDA 8, ADD 9, STA 10, HLT, with 5 at address 8 and 7 at address 9. Watch the PC: after each fetch it already points to the next instruction. Registers that just changed are amber; the memory row that just changed is amber too.

With indirect addressing the instruction LDA (5) does not contain the operand's address, but the address of a word that contains it. The machine needs an extra memory read, visible as the extra steps after decoding.

Worked examples

#include <stdio.h>
#include <stdint.h>
 
/* the accumulator machine of the animation: 16-bit words, I | opcode(3) | address(12) */
enum { HLT, LDA, STA, ADD, SUB, JMP, JZ, LDI };
 
static uint16_t mem[4096];
static int reads, writes;
 
static uint16_t rd(uint16_t a) { reads++; return mem[a]; }
static void wr(uint16_t a, uint16_t v) { writes++; mem[a] = v; }
 
static void run(const char *name, int verbose) {
    uint16_t pc = 0, ir, ac = 0, mar;
    int ni = 0;
    reads = writes = 0;
    printf("%s\n", name);
    for (;;) {
        mar = pc;
        ir = rd(mar);                      /* fetch: MAR <- PC, MDR <- M[MAR], IR <- MDR */
        pc++;                              /* PC <- PC + 1 */
        int ind = ir >> 15, op = (ir >> 12) & 7;
        uint16_t addr = ir & 0xFFF;
        ni++;
        if (verbose) printf("  executing %04X at %03X (PC is now %03X)\n", ir, mar, pc);
        if (op == HLT) break;
        if (op == LDI) { ac = addr; continue; }
        mar = addr;
        if (ind) mar = rd(mar) & 0xFFF;    /* indirect cycle: one more memory read */
        switch (op) {
        case LDA: ac = rd(mar); break;
        case STA: wr(mar, ac); break;
        case ADD: ac = (uint16_t)(ac + rd(mar)); break;
        case SUB: ac = (uint16_t)(ac - rd(mar)); break;
        case JMP: pc = mar; break;
        case JZ: if (ac == 0) pc = mar; break;
        }
    }
    printf("  AC = %u, %d instructions, %d memory reads, %d memory writes\n", ac, ni, reads, writes);
}
 
int main(void) {
    /* direct: LDA 8; ADD 9; STA 10; HLT, with M[8] = 5 and M[9] = 7 */
    mem[0] = 0x1008; mem[1] = 0x3009; mem[2] = 0x200A; mem[3] = 0x0000; mem[8] = 5; mem[9] = 7;
    run("direct", 1);
    printf("  M[10] = %u\n", mem[10]);
    /* indirect: LDA (5); STA 11; HLT, with M[5] = 10 and M[10] = 42 */
    for (int i = 0; i < 16; i++) mem[i] = 0;
    mem[0] = 0x9005; mem[1] = 0x200B; mem[2] = 0x0000; mem[5] = 0x000A; mem[10] = 42;
    run("indirect", 1);
    printf("  M[11] = %u\n", mem[11]);
    /* a loop: count down from 3, with M[21] = 1 */
    for (int i = 0; i < 32; i++) mem[i] = 0;
    mem[0] = 0x7003; mem[1] = 0x2014; mem[2] = 0x1014; mem[3] = 0x6008; mem[4] = 0x4015; mem[5] = 0x2014; mem[6] = 0x5002; mem[8] = 0x0000; mem[21] = 1;
    run("loop", 0);
    return 0;
}

direct
  executing 1008 at 000 (PC is now 001)
  executing 3009 at 001 (PC is now 002)
  executing 200A at 002 (PC is now 003)
  executing 0000 at 003 (PC is now 004)
  AC = 12, 4 instructions, 6 memory reads, 1 memory writes
  M[10] = 12
indirect
  executing 9005 at 000 (PC is now 001)
  executing 200B at 001 (PC is now 002)
  executing 0000 at 002 (PC is now 003)
  AC = 42, 3 instructions, 5 memory reads, 1 memory writes
  M[11] = 42
loop
  AC = 0, 20 instructions, 27 memory reads, 4 memory writes

Cheat box

Traps and GATE patterns

Connections

The shape of an instruction (its fields) and the choice of operands are the topic of instruction set architecture and addressing modes. The registers and buses that carry out these micro-operations are the datapath, and the unit that produces the control signals for each step is a hardwired or microprogrammed control unit, itself a state machine. Pipelining overlaps the fetch of the next instruction with the execution of the current one, and interrupts are the extra check at the end of the cycle.

PYQs

Consider the following instruction sequence
where registers R1, R2 and R3 are general
purpose and MEMORY [X] denotes the content
at the memory location X .

Instruction
Semantics
Instruction
Size
(bytes)
MOV
R1,(5000)
R1 ←
MEMORY[5000]
4
MOV
R2,(R3)
R2
←MEMORY[R3]
4
ADDR2,
R1
R2 ← R1 + R2
2
MOV
(R3), R2
MEMORY[R3]←
R2
4
INC R3
R3 ← R3 + 1
2
DEC R1
R1 ← R1 - 1
2
BNZ 1004
Branch if not zero
to the given
absolute address
2
HALT
Stop
1

Assume that the content of the memory location
5000 is 10 , and the content of the register R3 is
3000 . The content of each of the memory
locations from 3000 to 3010 is 50 . The
instruction sequence starts from the memory
location 1000. All the numbers are in decimal
format. Assume that the memory is byte
addressable.
After the execution of the program, the content
of memory location 3010 is

The following are some events that occur after a
device controller issues an interrupt while the
process L is under execution.
(P) The processor pushes the process status of L
onto the control stack.
(Q) The processor finishes the execution of the
current instruction.
(R) The processor executes the interrupt service
routine.
(S) The processor pops the process status of L
from the control stack.
(T) The processor loads the new PC value based
on the interrupt.
Which one of the following is the correct order
in which these events above occur?

Consider the following program segment. Here
R1, R2 and R3 are the general purpose registers.

Instruction
Operation
Instruction
Size (no.
of words)

MOV
R1,(3000)
R1 ← M3000]
2
LOOP:
MOV
R2,(R3)
R2←M[R3]
1

ADD R2,R1
R2 ← R1 + R2
1

MOV
(R3),R2
M[R3] ←R2
1

INC R3
R3←R3+1
1

DEC R1
R1 ← R1 - 1
1

BNZLOOP
Branch on not zero
2

HALT
Stop
1

Assume that the content of memory
location 3000 is 10 and the content of the
register R3 is 2000. The content of each of
the memory locations
from 2000 to 2010 is 100. The program is
loaded from the memory location 1000. All
the numbers are in decimal.
Assume that the memory is word addressable. The
number of memory references for accessing the
data in executing the program completely is

Consider a three-word machine instruction:
ADD A [R0], @B
The first operand (destination) "A [R0]" uses
indexed addressing mode with R0 as the index
register.
The second operand (source) "@B" uses indirect
addressing mode.
A and B are memory addresses residing at the
second and the third words, respectively.
The first word of the instruction specifies the
opcode, the index register designation, and the
source and destination addressing modes.
Computer Organization and Architecture

During execution of the ADD instruction, the two
operands are added and stored in the destination
(first operand).
The number of memory cycles needed during the
execution cycle of the instruction is:

Consider the following data path diagram

Consider an instruction: R0 ← R1 + R2. The
following steps are used to execute it over the given
data path. Assume that the PC is incremented
appropriately. The subscripts r and w indicate read
and write operations, respectively.
1. R2r TEMP1r, ALUadd, TEMP2w
2. R1r TEMP1w,
3. PCr, MARw, MEMr
4. TEMP2r, R0w
5. MDRr, IRw
Which one of the following is the correct order of
execution of the above steps?

Consider the following sequence of micro
-
operations.
MBR ← PC
MAR ← X
PC ← Y
Memory ← MBR
Which one of the following is a possible operation
performed by this sequence?
Computer Organization and Architecture

Self-check

Revision card

References