Computer Organization and Architecture

Pipeline execution time

A pipeline overlaps the execution of successive instructions, so once the pipeline is full, ideally one instruction completes every clock cycle. The clock period must be long enough for the slowest stage, and any pipeline register (latch) between stages adds its delay to that period, so \tau = \max_i t_i + t_{\text{latch}}.

For a k-stage pipeline that runs n independent instructions with no stalls, the first instruction needs k cycles and each later instruction finishes one cycle after the one before it. The total time is therefore T = (k + n - 1)\,\tau.

Stalls raise the average number of cycles per instruction. The effective CPI equals the ideal CPI of 1 plus the average stall cycles per instruction. When the two designs run at the same clock, the speed-up is simply the ratio of their CPI values. If the clock frequencies differ, compare the time per instruction, \text{CPI}/f, instead.

Control hazards cost a fixed penalty for each branch. A branch predictor removes that penalty only for correctly predicted branches, so the remaining stall cost is proportional to the fraction of branches that are mispredicted.

Data hazards are classified by the order of register accesses in program order. In a RAW (read after write) dependence, a later instruction reads a register that an earlier instruction writes; this is the true dependence. In a WAR (write after read) dependence, a later instruction writes a register that an earlier one reads. In a WAW (write after write) dependence, both instructions write the same register. For example, if I1 writes R7 and I2 then reads R7, I2 has a RAW dependence on I1.

Without operand forwarding, a dependent instruction must wait until the producer has written its result back, which lengthens the stall. With forwarding, the value is routed directly from the producing stage to the consuming EX stage, so the wait is reduced to the producer's own execution time.

A multi-cycle EX stage that is not pipelined acts as a structural bottleneck. An operation that needs t ns occupies the stage for \lceil t/\tau \rceil cycles, and the instructions behind it wait \lceil t/\tau \rceil - 1 extra cycles each. Adding these extra cycles over all instructions of each type gives the total stall count.

Direct-mapped cache address mapping

In a direct-mapped cache, every memory block has exactly one possible cache line. The byte address is split into three fields: the offset chooses a byte inside a block, the index chooses the line, and the remaining high-order bits form the tag, which is stored with the line and compared on every access. For a cache of 2^{m} bytes with blocks of 2^{b} bytes and an a-bit address, the number of lines is 2^{m-b}, the index has m-b bits, the offset has b bits, and the tag has a-m bits.

The total storage needed for tags is the number of lines multiplied by the tag width. The same relations run backward: given the tag, index and offset widths, the memory size is 2^{\text{tag}+\text{index}+\text{offset}} bytes, and the cache size is 2^{\text{index}} times the block size.

Two addresses conflict when they have the same index but different tags, because they compete for the same line. If conflicting words are accessed alternately, every access misses. Words that lie in a block already loaded hit as long as that block is not evicted. For example, in a 1 KB direct-mapped cache with 32-byte blocks, addresses 0x0040 and 0x0440 both have index 2 but tags 0 and 1, so alternating between them misses every time.

The index of a block is its block number taken modulo the number of lines, and the block number is the address divided by the block size, rounded down. Because the index always satisfies index < number of lines, the number of lines must exceed the index value that an address produces, which bounds the cache size from below.

Addressing modes and instruction size

An addressing mode tells the processor where an operand is found. In immediate mode, the constant is stored inside the instruction, so the operand is the value itself. In register mode, the operand is a register. In register indirect mode, a register holds the address of the operand. In direct (absolute) mode, the memory address is given in the instruction. Base with displacement adds a constant offset to a base register, and base with index adds the contents of an index register, often scaled by the element size.

High-level language constructs map onto these modes. A literal constant is immediate, a pointer dereference is indirect, an array element is reached by base plus index, and a field of a record or structure is reached by base plus displacement.

• displacement — a constant offset added to a base address. e.g. a local variable stored 8 bytes below the frame base.
• indirect — the register or memory word holds the address rather than the data. e.g. a load through a register that holds a pointer.

The size of an instruction depends on its opcode and on each operand field. In a fixed-length format, a register field needs \lceil \log_2 R \rceil bits for R registers, and a mode field needs \lceil \log_2 M \rceil bits for M addressing modes. The opcode receives the bits that remain after these fields and any immediate are subtracted from the total, and it can encode 2^{\text{opcode bits}} operations.

For a short program with a counter-controlled loop, first determine how many times the loop body executes from the counter and its decrement. Then track the address used on each iteration, which is given by a pointer register that is incremented each time.

Set-associative cache address breakdown

In a set-associative cache, the lines are grouped into sets, and a block may be placed in any line of its set. With A-way associativity, the number of sets is S = \dfrac{\text{cache size}}{\text{block size} \times A}. The offset selects the byte inside the block, the index selects the set, and the tag is the remaining high-order part of the address. The index and offset together address the portion of the cache that belongs to one way, so the tag width is a - \log_2(\text{cache size}/A) bits.

If the tag width and block size are known, the index width is the address length minus the tag and offset widths. The number of sets is 2^{\text{index}}, and the associativity is the total number of blocks divided by the number of sets.

For a fixed cache size, increasing the associativity by a factor K = 2^{L} reduces the number of sets by 2^{L}. The index shrinks by L bits and the tag grows by L bits, so the tag width of the set-associative cache equals the direct-mapped tag width plus L. A direct-mapped cache is the special case with A = 1.

DMA cycle stealing

In cycle-stealing DMA, the DMA controller takes the system bus for one cycle at a time and moves one word or character between the device and main memory, while the CPU continues to execute in the remaining cycles. The data transfer rate therefore equals the number of stolen cycles per second multiplied by the number of bits moved per stolen cycle. If a fraction p of the f processor cycles per second is used by DMA and each stolen cycle moves b bits, the rate is p \cdot f \cdot b bits per second.

Burst mode differs because the DMA controller holds the bus for an entire block. Burst mode gives higher throughput for bulk transfer because bus arbitration is paid once per block rather than once per word.

Programmed I/O keeps the CPU busy polling the device and copying each word, so its CPU utilization is lower than that of interrupt-driven I/O, which lets the CPU do other work until the device signals. A vectored interrupt supplies the address of the service routine directly from the interrupt vector, so the CPU starts the ISR sooner than with a non-vectored interrupt, where the CPU must identify the source first.

Average memory access time

The average memory access time (AMAT) is the expected time for one memory reference. For a single cache, \text{AMAT} = t_{\text{hit}} + m \cdot t_{\text{penalty}}, where m = 1 - h is the miss rate and t_{\text{penalty}} is the miss penalty.

Because the miss rate is 1 - h, an optimization that increases the hit time must be compensated by a higher hit rate. The minimum acceptable hit rate h' is found by requiring t'_{\text{hit}} + (1 - h')\,t_{\text{penalty}} \le t_{\text{hit}} + (1-h)\,t_{\text{penalty}}, and solving for h'.

For a multilevel hierarchy with local miss rates, the AMAT can be written in nested form as \text{AMAT} = t_1 + m_1\,(t_2 + m_2\,t_{\text{mem}}), where m_1 is the L1 miss rate and m_2 is the local L2 miss rate. The miss penalty of L1 is itself an average access time of L2 and main memory. Care is needed to distinguish a local hit rate, measured over the references that reach that level, from a global one, measured over all processor references.

Instruction format and immediate field bits

In a fixed-width instruction format, the bit budget is the sum of all fields. A field that must distinguish N items needs \lceil \log_2 N \rceil bits. A register field for R registers therefore takes \lceil \log_2 R \rceil bits, and an opcode for N operations takes \lceil \log_2 N \rceil bits. Whatever remains after the opcode, register and mode fields is available for the immediate value or address.

When an ISA has two instruction types, a single type bit is often added in the opcode field, and the operations of each type are counted separately. Each type's operations need \lceil \log_2 N_{\text{type}} \rceil bits.

Not every register field is needed for every instruction. An instruction with only one register operand leaves more bits for the immediate field than one with two register operands.

Variable-length opcodes must be prefix-free, so that no opcode is the prefix of another. A p-bit opcode in a k-bit field occupies 2^{k-p} of the 2^{k} patterns. Counting the patterns taken by each opcode group gives the number of opcodes that remain for another instruction type.

Write-back vs write-through cache policies

A write-through cache writes every store to the cached copy and to main memory at the same time. Main memory is therefore always current, and no line is ever dirty. Consequently, evicting a line from a write-through cache never triggers a memory write, and no dirty bit is required.

A write-back cache updates only the cache on a write hit, sets the dirty bit of the block, and copies the block to memory when it is evicted. A write hit therefore changes the dirty bit but does not transfer data to memory. A dirty block can be the LRU victim of a read miss, in which case the read miss must write that block back before the new block is loaded.

• dirty bit — a flag set when a cached block has been modified and differs from memory.
• LRU — least recently used; the replacement policy that evicts the block untouched for the longest time.

Because a write-through victim is always clean, a miss in a write-through cache never causes a write back of the victim.

Inclusive cache write policies

In an inclusive hierarchy, L2 holds a copy of every block that is in L1, and L2 is normally the larger cache. When L1 is write-through, L2 is always up to date with every write, so no L1 line is dirty. A read miss in L1 therefore replaces only clean lines and sends nothing back to L2.

Write-through caches are usually paired with no-write allocate, where a write miss goes directly to the next level without loading the block. Write-back caches are usually paired with write allocate, which fetches the block on a write miss. This pairing is a common convention rather than a strict requirement, so a statement that says a policy must be used with a particular cache is false.

Endianness and byte ordering

Endianness is the order in which the bytes of a multi-byte value are stored in memory. A little-endian machine stores the least significant byte at the lowest address, while a big-endian machine stores the most significant byte first. For a 2-byte value stored at two consecutive addresses, let b_0 be the byte at the lower address and b_1 the byte at the higher address. The little-endian value is 256\,b_1 + b_0, and the big-endian value is 256\,b_0 + b_1.

The difference between the two readings is 255\,(b_1 - b_0). The little-endian value is therefore exactly 255 larger than the big-endian value when b_1 = b_0 + 1. For example, if the bytes stored are 0x10 at the lower address and 0x11 at the higher address, the little-endian value is 0x1110 and the big-endian value is 0x1011, and their difference is 0xFF, which is 255.

DMA based I/O transfer

Direct memory access (DMA) lets a dedicated controller move a block of data between an I/O device and main memory without the CPU handling each word. The CPU only programs the controller with the memory address, the transfer count and the direction, and it is notified by an interrupt when the transfer completes. Because the CPU is not involved in each word, DMA gives the highest throughput for bulk transfers such as reading a large block from a hard disk into memory.

This contrasts with programmed I/O, where the CPU copies each word itself, with interrupt-driven I/O, where the CPU runs a service routine for each event, and with polling, where the CPU repeatedly checks the device status. Each of these methods involves the CPU for every unit of data, which lowers the throughput for bulk data.

Polling I/O overhead

Polling is a programmed I/O method in which the CPU repeatedly reads a device status register to find out whether the device needs service. Each check is called a poll, and it consumes CPU time whether or not the device has anything to report. The total time spent on I/O in one second is therefore the number of polls per second multiplied by the time of one poll, plus the processing time for every event that the polls actually detect.

The overhead depends on two things: how often the device is polled and how long each poll takes. For example, if a device is polled every 5 ms and each poll takes 50 μs, the CPU spends 50\ \mu s / 5\ ms = 0.01 of its time just checking, that is 1 percent. Keep the units consistent before dividing, because mixing ms and μs is the most common mistake.

Interrupts remove the periodic checks. The CPU does useful work until the device raises a request, so the overhead is proportional to the number of events rather than to the polling frequency. When two schemes are compared for the same event rate, add up the time per event under each scheme and then take the ratio.