Programs on the machine

ACompressed recap

🧾

Trace programs in a table; IC = setup + iterations × body + end (the last not-taken branch counts); memory references = instruction words fetched + data accesses; cycles = Σ executions × cycles. Instruction addresses are running sums of sizes. Stack grows downward with SP at the top item: PUSH decrements then stores; POP loads then increments. CALL pushes the next instruction's address and jumps; RET pops into the PC. Frames hold return address, saved registers and locals. RISC: fixed length, load/store, few modes, CPI ≈ 1; CISC: variable length, memory operands, many modes.

BMerged rule card

1.3.1 Tracing programs: registers, memory and flags; counting memory references and cycles

• Trace values in a table: one row per iteration.
• IC = setup + iterations × body + end (the final not-taken branch counts).
• Memory references = Σ instruction words fetched + data accesses.
• Cycles = Σ (executions × cycles of that instruction).
• Instruction addresses: running sum of sizes.

1.3.2 Stack, subroutine call and return; RISC vs CISC

• Downward stack, SP at top: PUSH = SP −= w, M[SP] ← X; POP = X ← M[SP], SP += w.
• CALL: push return address (next instruction), PC ← target. RET: PC ← pop.
• Recursion depth = active calls × frame size; count calls carefully (f(10)…f(0) = 11).
• RISC: fixed length, load/store, few modes, many registers, CPI ≈ 1. CISC: the opposite.

CInterleaved GATE-style questions

Q1NAT2 marksCounting cycles

A loop body of 4 instructions (cycles 2, 1, 1, 3) runs 10 times; setup is 2 instructions of 1 cycle each; one HALT of 1 cycle ends it. Total cycles?

Numerical answer: ________

Q2NAT1 markMemory references

A loop of 6 one-word instructions runs 20 times; each iteration makes 2 data accesses. Ignoring code outside the loop, how many memory references?

Numerical answer: ________

Q3NAT2 marksMemory update

In Lesson 1.3.1's memory-updating loop, M[3000] holds 4 instead of 6 (everything else unchanged). What is M[2001] at the end?

Numerical answer: ________

Q4NAT1 markReturn address

CALL instructions are 4 bytes. A program at address 400 has CALL F at 412. What is pushed?

Numerical answer: ________

Q5NAT2 marksStack depth

SP starts at 0x1000 (4096). Each call pushes a return address (4 bytes) and saves 2 registers (4 bytes each). What is SP (in decimal) while the third nested call is running?

Numerical answer: ________

Q6MCQ1 markRISC vs CISC

Compared with a CISC version of the same program, a RISC version typically has:

• (A) more instructions and higher CPI
• (B) fewer instructions and lower CPI
• (C) more instructions and lower CPI
• (D) fewer instructions and higher CPI

Q7MCQ1 markPOP

With a downward-growing stack and SP pointing at the top item, POP R1 does:

• (A) SP ← SP − 4; R1 ← M[SP]
• (B) R1 ← M[SP]; SP ← SP − 4
• (C) R1 ← M[SP]; SP ← SP + 4
• (D) SP ← SP + 4; R1 ← M[SP]

Q8NAT2 marksInstruction count

How many instructions execute? MOV R1, #0 · MOV R2, #10 · LOOP: ADD R1, R1, R2 · SUB R2, R2, #1 · BNZ R2, LOOP · HALT.

Numerical answer: ________

DAnswer Vault