GATE CSE COA Formula Sheet: Cache, Pipelining, IEEE 754, Addressing

Q: What is the formula for pipeline execution time in GATE?

The cycle time τ is the largest stage delay plus the latch delay. A k-stage pipeline runs n instructions in (k + n - 1)τ, never k × n cycles. The non-pipelined time is n times the sum of the stage delays, with no latch delay. Stall cycles from hazards are added on top of k + n - 1.

By MD ANISH AHAMADUpdated 4 Oct 20267 min read

GATE CSE COA Formula Sheet: Cache, Pipelining, IEEE 754, Addressing

Computer Organization and Architecture is the most numerical core subject in GATE CSE, and most of its marks come from four formula families: cache mapping, memory access time, pipelining and number formats. This sheet goes deeper than the general GATE CSE formula sheet. Each formula is shown with a one-line worked example and the trap that costs marks.

In this guide

Key takeaways
The terms this sheet uses
Cache mapping: tag, index and offset
Average memory access time across levels
Pipelining: cycle time, total time and speedup
IEEE 754: decoding and the special values
Addressing modes and instruction encoding
Quick revision

Key takeaways

Cache mapping is three logs and a subtraction: offset from block size, index from the number of sets, and the tag takes the rest.
Hierarchical AMAT adds a lower level's time only on a miss at the level above.
A $k$ -stage pipeline runs $n$ instructions in $(k + n - 1)$ cycles, and the cycle includes the latch delay.
IEEE 754 single precision splits 32 bits as 1, 8 and 23, with bias 127 and an implicit leading 1.
A PC-relative offset is measured from the next instruction, in the units the question states.
Byte versus word addressing causes more wrong answers in this subject than any formula.

The terms this sheet uses

A block (or line) is the unit a cache moves to and from memory. A set is a group of $k$ lines, and $k$ is the associativity.
An address splits into tag, index and offset. The offset picks a byte in the block, the index picks the set, and the tag tells blocks in the same set apart.
The local miss rate of a level is its misses divided by the accesses that reach it. The global miss rate is its misses divided by all CPU accesses.
A pipeline stage does one part of an instruction. A latch (pipeline register) sits between stages and adds its own delay to every cycle.
CPI is cycles per instruction. A stall is a cycle in which an instruction cannot move forward.
The effective address (EA) is the memory address an operand is finally read from.

Here $\log$ means $\log_2$ , and KB means $2^{10}$ bytes.

Cache mapping: tag, index and offset

Work from the block outwards. The offset must address every byte of a block, the index must address every set, and the tag covers what is left.

Formula	One-line example	Watch out for
$\text{offset} = \log_2 B$	32 B blocks: 5 bits	Counts words if the memory is word-addressable
$\displaystyle \text{sets} = \dfrac{C}{k \times B}$	64 KB, 4-way, 32 B: $\displaystyle \dfrac{2^{16}}{4 \times 32} = 512$	Fully associative has one set; direct-mapped has $k = 1$
$\text{index} = \log_2(\text{sets})$	$\log_2 512 = 9$ bits	Fully associative: index $= 0$
$\text{tag} = A - \text{index} - \text{offset}$	32-bit address: $32 - 9 - 5 = 18$ bits	Use the address width, not the memory size in bytes
Block $j$ goes to set $j \bmod \text{sets}$	Block 1000 to set $1000 \bmod 512 = 488$	Mod the number of sets, not lines
Tag directory $=$ lines $\times$ (tag $+$ valid $+$ dirty $+$ LRU)	$2048 \times (18 + 1 + 1 + 2) = 45056$ bits $= 5.5$ KB	Dirty bit only for write-back

Remember: Doubling the associativity with the size and block fixed halves the sets, so the index loses one bit and the tag gains one. The offset never changes. The cache memory question guide traces hits and misses with these splits.

Average memory access time across levels

The time you always pay is the L1 time. You add the L2 time only when L1 misses, and the memory time only when L2 misses as well:

\text{AMAT} = t_1 + m_1\big(t_2 + m_2\,(t_3 + m_3\,t_{\text{mem}})\big)

Here $t_i$ is the access time of level $i$ and $m_i$ is its local miss rate.

Worked example. With $t_1 = 1$ ns, $m_1 = 0.1$ , $t_2 = 10$ ns, $m_2 = 0.2$ and $t_{\text{mem}} = 100$ ns for two levels:

\text{AMAT} = 1 + 0.1\,(10 + 0.2 \times 100) = 1 + 0.1 \times 30 = 4\text{ ns}

The global miss rate of L2 is $m_1 \times m_2 = 0.02$ .

Formula	One-line example	Watch out for
Global miss rate $= m_1 \times m_2 \times \cdots$	$0.1 \times 0.2 = 0.02$	A local rate is per access reaching that level
Misses per instruction $=$ miss rate $\times$ accesses per instruction	$0.02 \times 1.4 = 0.028$	Accesses include the instruction fetch
Parallel model: $h_1 t_1 + (1 - h_1)\,h_2 t_2 + \cdots$	Use only when the question says so	"Miss penalty" may already include the check time

Trap: Adding the L2 hit time on every access treats a hierarchical cache as if L2 were always checked. In the hierarchical model the lower level is reached only on a miss.

Pipelining: cycle time, total time and speedup

The clock must wait for the slowest stage and the latch after it. The first instruction then takes $k$ cycles and each later one adds a single cycle:

\tau = \max_i(\text{stage}_i) + t_{\text{latch}}, \qquad T_{\text{pipe}} = (k + n - 1)\,\tau, \qquad T_{\text{non-pipe}} = n \sum_i \text{stage}_i

Worked example. Stages of 4, 6, 9 and 5 ns with a 1 ns latch give $\tau = 10$ ns. For 100 instructions, $T_{\text{pipe}} = (4 + 99) \times 10 = 1030$ ns and $T_{\text{non-pipe}} = 100 \times 24 = 2400$ ns. The speedup is $2400 / 1030 \approx 2.33$ .

Formula	One-line example	Watch out for
Speedup $= T_{\text{non-pipe}} / T_{\text{pipe}}$ ; limit $= \sum \text{stage}_i / \tau$	Limit $= 24/10 = 2.4$	Equals $k$ only for equal stages and zero latch
Split the slowest stage: new $\tau = \max(\text{rest}, \text{larger half}) + t_{\text{latch}}$	Split 9 into 4.5 and 4.5: $\tau = 6 + 1 = 7$ ns	$k$ rises by one, which matters for finite $n$
Total cycles $= n + k - 1 + \text{stalls}$	5 stages, 6 instructions, 2 stalls: 12	Load-use leaves 1 stall even with forwarding
$\text{CPI} = 1 + f_b\,(1 - p) \times \text{penalty}$	$1 + 0.2 \times 0.1 \times 2 = 1.04$	Penalty is resolution stage minus 1
$\text{Time} = \text{IC} \times \text{CPI} / f$	$10^9 \times 1.04 / 2\text{ GHz} = 0.52$ s	GHz versus ns

Trap: The non-pipelined time has no latch delay, and the pipelined time is never $k \times n$ cycles. The pipelining question guide works through hazard timing diagrams.

The book's last-minute revision sheet carries the complete table for this subject, including DMA, microprogrammed control, memory interfacing and DRAM refresh, each with symbols, when it applies and its trap. It is part of the GATE CSE 2027 book.

IEEE 754: decoding and the special values

A single-precision number stores a sign bit $S$ , an 8-bit exponent field $E$ and a 23-bit fraction $F$ . For a normalised value the hardware adds an implicit leading 1:

\text{value} = (-1)^{S} \times 1.F \times 2^{E - 127}, \qquad 1 \le E \le 254

Worked example. Decode 0x40A00000. In binary the first bits are 0 10000001 0100..., so $S = 0$ , $E = 129$ and $F = 0.01_2$ . The value is $1.01_2 \times 2^{2} = 101_2 = 5$ .

Case	Rule	Watch out for
$E = 0$ , $F = 0$	$\pm 0$	Two zeros exist
$E = 0$ , $F \ne 0$	Denormal: $(-1)^{S} \times 0.F \times 2^{-126}$	No implicit 1, exponent $-126$ not $-127$
$E = 255$	$\pm\infty$ if $F = 0$ , NaN otherwise	All-ones exponent is reserved
Extremes	Smallest normal $2^{-126}$ ; smallest denormal $2^{-149}$ ; largest $(2 - 2^{-23}) \times 2^{127}$	Largest is about $3.4 \times 10^{38}$
Integers	Every integer up to $2^{24}$ is exact ( $2^{53}$ in double)	Double is 1, 11, 52 bits with bias 1023

For a custom format with $e$ exponent bits, $f$ fraction bits and bias $b$ , the largest value is $(2 - 2^{-f}) \times 2^{(2^{e} - 2) - b}$ when the all-ones exponent is reserved.

Trap: Split a hex pattern into 1, 8 and 23 bits before reading it, because hex digits straddle the field boundaries. Using bias 128 is the classic wrong answer. The number-representation side is covered in the digital logic important topics guide.

Addressing modes and instruction encoding

The addressing mode says where an operand lives. Count memory accesses by asking how many times the hardware must read memory to reach it.

Mode	Effective address	Operand memory accesses
Immediate	Operand is in the instruction	0
Register / register indirect	Operand in $R$ / $\text{EA} = R$	0 / 1
Direct / memory indirect	$\text{EA} = A$ / $\text{EA} = M[A]$	1 / 2
Indexed or displacement	$\text{EA} = A + R$	1
PC-relative	$\text{EA} = \text{PC}_{\text{next}} + \text{offset}$	1

Formula	One-line example	Watch out for
Target $= \text{PC}_{\text{next}} + \text{offset} \times \text{size}$	Branch at 2000, 4 B instructions, offset $-3$ : $2004 - 12 = 1992$	Offset is from the next instruction
Address lines $= \log_2(\text{addressable units})$	4 GB with 2-byte words: $\log_2 2^{31} = 31$	Not 32 for word-addressable memory
Chips $\displaystyle = \dfrac{\text{capacity}}{\text{chip capacity}} \times \dfrac{\text{width}}{\text{chip width}}$	$8\text{K} \times 16$ from $2\text{K} \times 8$ : $4 \times 2 = 8$	Width ratio as well as depth ratio
Signed immediate of $w$ bits: $-2^{w-1}$ to $2^{w-1} - 1$	$w = 8$ : $-128$ to $127$	Unsigned is $0$ to $2^{w} - 1$

The COA important topics guide explains which of these families past papers have asked most.

More formula sheets: all of GATE CSE · Computer Networks · Engineering Mathematics · Operating Systems

Quick revision

$\text{offset} = \log_2 B$ , $\text{sets} = C/(kB)$ , $\text{tag} = A - \text{index} - \text{offset}$ .
Block $j$ maps to set $j \bmod \text{sets}$ .
$\text{AMAT} = t_1 + m_1(t_2 + m_2\,t_{\text{mem}})$ with local miss rates.
$\tau = \max(\text{stage}) + t_{\text{latch}}$ ; $T = (k + n - 1)\tau$ ; non-pipelined time has no latch.
Branch $\text{CPI} = 1 + f_b(1 - p) \times \text{penalty}$ .
IEEE 754 single: 1, 8, 23 bits, bias 127, implicit 1; double: 1, 11, 52 bits, bias 1023.
PC-relative target $= \text{PC}_{\text{next}} + \text{offset} \times \text{size}$ .

Frequently asked questions

How do I calculate tag, index and offset bits for a cache?

Offset bits are the base-2 log of the block size in bytes. The number of sets is cache size divided by associativity times block size, and index bits are the log of the number of sets. Tag bits are whatever is left of the address. A fully associative cache has no index bits, and a direct-mapped cache has associativity one.

What is the formula for pipeline execution time in GATE?

The cycle time $\tau$ is the largest stage delay plus the latch delay. A k-stage pipeline runs n instructions in $(k + n - 1)\tau$ , never $k \times n$ cycles. The non-pipelined time is n times the sum of the stage delays, with no latch delay. Stall cycles from hazards are added on top of $k + n - 1$ .

What is the bias in IEEE 754 single precision?

The bias is 127 for single precision, which has 1 sign bit, 8 exponent bits and 23 fraction bits. Double precision has 11 exponent bits, 52 fraction bits and bias 1023. A normalised value is the implicit 1 followed by the fraction, times 2 raised to the stored exponent minus the bias. Using 128 as the bias is a common mistake.

How is AMAT calculated for a two-level cache?

In the hierarchical model you always pay the L1 time, add the L2 time only on an L1 miss, and add the memory time only on an L2 miss. With local miss rates, AMAT equals t1 plus m1 times (t2 plus m2 times the memory time). GATE questions usually intend this model unless they state that the levels are searched in parallel.

Where is a PC-relative branch offset measured from?

From the address of the next instruction, because the program counter has already been incremented when the branch executes. The target is the next-instruction address plus the offset times the instruction size, unless the question says the offset is already in bytes. Measuring from the branch instruction itself is a common trap in past papers.

Sources

Dates, fees and the syllabus are set by the GATE 2027 organising institute and can change. Always confirm at gate2027.iitm.ac.in.