Glossary¶
Terms used in this book, in alphabetical order
A¶
- Absorption
- The Boolean theorem \(x + xy = x\) (dual \(x(x+y) = x\)), the most useful single simplification rule: a term that needs \(x\) adds nothing when \(x\) alone already makes the output 1.
- Accumulator (AC)
- The 16-bit main processor register of the basic computer; one operand of every arithmetic or logic operation is
AC, and the result is written back into it. - Active-low output
- An output that is asserted by being driven to 0 while idle at 1; the usual form of NAND decoders and of chip-select lines, and a naming convention, not a fault.
- Adder-and-logic circuit
- The combinational circuit at the input of
AC, fed byACandDR(andINPR), that performs add, AND, transfer, complement and shift; it is not a source for the common bus. - Adder-subtractor
- A parallel adder with an XOR gate on every \(B\) input and a mode line \(M\) also wired to the first carry-in, so that \(M = 0\) gives \(A + B\) and \(M = 1\) gives \(A + B' + 1 = A - B\).
- Address decoding
- Splitting the address bus so that the low-order lines select a word inside a chip while the high-order lines feed a decoder whose outputs drive the chip-select lines.
- Address register (AR)
- The 12-bit register that holds the memory address for the next read or write; the memory's address input is wired to
ARand to nothing else. - Addressing mode
- A rule for interpreting the address field of an instruction before the operand is referenced, giving programming flexibility (pointers, arrays, relocatable code) and shorter address fields.
- Amdahl's law
- The speedup on n processors of a program whose fraction p can be parallelised is S = 1 / ((1 − p) + p/n); the serial fraction sets a ceiling of 1/(1 − p).
- Arithmetic shift
- A shift that preserves the sign of a 2's-complement number: a left shift appends 0 (multiply by 2), a right shift copies the sign bit into the vacated place (divide by 2).
- ASCII
- A 7-bit character code of 128 symbols (letters, digits, punctuation, control codes), usually stored in an 8-bit byte whose extra bit is often a parity bit; 'A' is 41 hex, 'a' is 61 hex and '0' is 30 hex.
- Associative memory (CAM)
- A memory searched by content rather than by address: the argument register is compared in parallel with every stored word, under the mask of the key register, and each matching word sets its bit in the match register.
- Average access time
- For a cache, \(t_{avg} = h\,t_c + (1-h)\,t_m\), where \(h\) is the hit ratio, \(t_c\) the cache time and \(t_m\) the main-memory time.
B¶
- Base (radix) \(r\)
- The number of distinct digits in a positional number system; the place values are powers of \(r\) and the value of a numeral is \(\sum a_i r^i\).
- Baud rate
- The number of bits transmitted per second on a serial line, including start, stop and parity bits.
- BCD (binary-coded decimal)
- A weighted 8-4-2-1 code in which each decimal digit occupies its own four-bit group; only 0000 to 1001 are legal and 1010 to 1111 are unused.
- Biased exponent
- A floating-point exponent stored with a constant added (127 for IEEE single precision) so that it is always non-negative and needs no sign bit of its own.
- Binary parallel adder
- A chain of \(n\) full adders in which the carry-out of each stage is the carry-in of the next, adding two \(n\)-bit numbers; also called the ripple-carry adder.
- BSA (branch and save return address)
- The memory-reference instruction that calls a subroutine: it stores
PCinM[EA]and then setsPC ← EA + 1; the subroutine returns with an indirectBUNthrough its first word. - Bubble
- An idle slot inserted into a pipeline when a hazard forces a segment to wait or an instruction to be discarded; bubbles are why real speedup falls below the number of segments.
- Burst transfer
- A DMA mode in which the controller keeps the bus and moves the entire block in one go; it is the fastest mode but locks the CPU out of memory for the whole burst.
- Bus request (BR) and bus grant (BG)
- The two signals by which a DMA controller asks the CPU for the buses and the CPU, having finished its bus cycle and floated its lines, hands them over.
C¶
- Cache coherence
- The hardware mechanism that keeps copies of the same memory block consistent across the private caches of the cores of a multicore processor.
- Cache memory
- A small, very fast SRAM between the CPU and main memory that holds copies of recently used blocks, so that most references are served at cache speed.
- Canonical form
- An expression in which every term contains every variable, either as a sum of minterms (\(\sum m\)) or a product of maxterms (\(\prod M\)); it is unique for a given function.
- Carry look-ahead
- A technique that forms every carry directly from the generate and propagate signals (\(C_{i+1} = G_i + P_iC_i\), expanded), so that the carry delay no longer grows in proportion to the word length.
- Carry propagation delay
- The time a carry takes to ripple through the stages of an adder; about 2 gate delays per stage, so \(2n\) gate delays for an \(n\)-bit ripple adder.
- Characteristic equation
- The Boolean equation for the next state \(Q(t+1)\) of a flip-flop in terms of its inputs and present state, for example \(Q(t+1) = JQ' + K'Q\) for the JK flip-flop.
- Characteristic table
- A table giving the next state \(Q(t+1)\) of a flip-flop for every combination of its inputs and present state; it answers the analysis question "what happens?".
- Chip select (CS)
- An input that enables a memory or other chip; in a large memory it is driven by a decoder on the high-order address lines.
- Circulate instruction (CIR, CIL)
- A register-reference instruction that rotates the 17-bit ring formed by AC and the extended bit E one place right (CIR) or left (CIL); no bit is lost.
- CISC
- Complex instruction set computer: a design with many (100 to 250) complex, variable-length instructions, many addressing modes, memory operands and microprogrammed control, as in the VAX and x86.
- Code converter
- A combinational circuit whose input is a word in one binary code and whose output is the corresponding word in another, such as BCD to Excess-3 or binary to Gray.
- Combinational circuit
- A circuit whose outputs depend only on the present inputs, with no memory and no feedback; a truth table describes it completely.
- Common bus
- The single set of 16 lines shared by memory and six registers; exactly one unit drives it per clock pulse, chosen by
S2S1S0, and any register whoseLDis enabled copies it. - Consensus theorem
- The identity \(AB + A'C + BC = AB + A'C\): the term \(BC\) is redundant logically, although it may be needed to remove a static hazard.
- Control address register (CAR)
- The register of a microprogrammed control unit that holds the address of the next microinstruction to be read from the control memory.
- Control function
- A Boolean condition written before a colon (for example
D3T4) that says when the microoperations after the colon take place. - Control hazard
- A pipeline hazard caused by a branch: PC changes, so instructions already fetched behind the branch are wrong and must be discarded or flushed.
- Control memory
- The ROM (or RAM) of a microprogrammed control unit that holds the microinstructions; it is distinct from main memory and is invisible to the programmer.
- Control word
- The set of bits read from control memory, one per control line plus sequencing fields, that drives the datapath for one clock pulse; another name for a microinstruction.
- CPU-time equation
- CPU time = instruction count × cycles per instruction × clock period, the product that decides which of two machines runs a program faster.
- Cycle stealing
- A DMA mode in which the controller takes the bus for one word at a time and returns it, slowing the CPU slightly instead of stopping it.
D¶
- Daisy chain
- A serial priority scheme in which the interrupt acknowledge passes from device to device through PI and PO lines, so that the device nearest the CPU has the highest priority.
- Data hazard
- A pipeline hazard in which an instruction needs a result that an earlier instruction still in the pipeline has not yet produced; remedied by forwarding or stalling.
- Data register (DR)
- The 16-bit register that holds the operand read from memory or about to be written; the second input of the adder-and-logic circuit.
- Decoder
- A combinational circuit with \(n\) inputs and \(2^n\) outputs that asserts exactly one output, output \(i\) being the minterm \(m_i\); a minterm generator.
- DeMorgan's theorems
- \((x+y)' = x'y'\) and \((xy)' = x' + y'\); to complement an expression, complement each variable and swap AND with OR.
- Demultiplexer (DEMUX)
- A circuit that routes one data input to one of \(2^n\) outputs chosen by \(n\) select lines; the same circuit as a decoder with enable, the data line acting as the enable.
- Diminished-radix complement (\((r-1)\)'s complement)
- For an \(n\)-digit number \(N\), the value \((r^n - 1) - N\); in binary the 1's complement (invert every bit) and in decimal the 9's complement.
- Direct addressing
- Addressing with
I = 0, in which the address field of the instruction is itself the effective address. - Direct memory access (DMA)
- Transfer of a block directly between a device and memory under the control of a DMA controller, with the CPU involved only at the start and at the final interrupt.
- Dirty bit
- The bit set in a write-back cache line when it is modified; only dirty lines are written to main memory when they are replaced.
- DMA controller
- The simple controller, with an address register, a word-count register and a control register, that moves data between a device and memory using the buses it is granted.
- Don't-care condition (X)
- An input combination that cannot occur or whose output is never used; on a Karnaugh map it may be taken as 0 or 1, whichever enlarges a group.
- Duality
- Swapping AND with OR and 0 with 1 in an expression, leaving the variables alone; every valid identity stays valid when dualised.
E¶
- Edge-triggered
- Responding to its inputs only at one instant, the rising or falling edge of the clock; flip-flops are edge-triggered, latches are level-triggered.
- Effective address (EA)
- The address of the operand that an instruction actually uses: the address field when
I = 0, andM[address field]whenI = 1. - Efficiency (of a pipeline)
- The speedup divided by the number of segments, \(S/k\): the fraction of the ideal speedup actually achieved.
- Enable input
- A line that holds every output of a decoder inactive when it is not asserted; it is what allows small decoders to be expanded into large ones.
- Encoder
- The inverse of a decoder: it has \(2^n\) inputs and \(n\) outputs and produces the binary code of the one active input line.
- End carry
- The carry out of the most significant position when a complement is added; discarded in \(r\)'s-complement subtraction, where its presence also shows that the result is positive.
- End-around carry
- In \((r-1)\)'s-complement subtraction, the end carry is added back into the least significant digit to obtain the positive result.
- Escape code (opcode 111)
- The opcode that says the operation is selected by one bit of the low 12 bits instead; with
I = 0it gives register-reference instructions and withI = 1input-output instructions. - Essential prime implicant
- A prime implicant that is the only one covering some particular 1 of the function, so it must appear in every minimal sum of products.
- Excess-3
- A non-weighted, self-complementing decimal code in which each digit is encoded as its BCD value plus 3 (0011).
- Excess-3 code
- A decimal code in which each digit \(d\) is stored as the four-bit binary value of \(d + 3\).
- Excitation table
- A table giving the flip-flop inputs required to cause each transition \(Q \to Q(t+1)\); it answers the design question "what must I apply?" and carries don't-cares.
- Expanding opcode
- A scheme in which an unused opcode value acts as an escape, so that the bits of a missing address field become extra opcode bits and more instructions can be encoded.
F¶
- Firmware
- The complete set of microprograms held in control memory that implement a machine's instruction set.
- Fixed-point representation
- A representation in which the radix point is assumed to sit at a fixed place (for integers, just right of the least significant bit), so that range and resolution are fixed.
- Flags (FGI, FGO)
- The input flag FGI (a character is waiting in INPR) and the output flag FGO (the printer is ready for another character in OUTR); they let the CPU synchronise with slow devices.
- Flip-flop
- A one-bit, edge-triggered storage element with two stable states, built from cross-coupled gates; the memory element of synchronous sequential circuits.
- Floating-point representation
- A representation of a number as \(\pm\) mantissa \(\times\) radix\(^{\text{exponent}}\), in which the point "floats" so that one word can cover a very wide range of magnitudes.
- Full adder
- A circuit that adds three bits (two operands and a carry-in) and gives a sum \(S = A \oplus B \oplus C_{in}\) and a carry-out \(C_{out} = AB + C_{in}(A \oplus B)\).
- FULL and EMTY
- The two flip-flops of a register stack that are set when the stack is full or empty, needed because the 6-bit stack pointer wraps from 63 to 0.
- Full subtractor
- A circuit computing \(A - B - B_{in}\), giving the difference \(D = A \oplus B \oplus B_{in}\) and a borrow \(B_{out} = A'B + A'B_{in} + BB_{in}\).
G¶
- General register organization
- A CPU organization in which general-purpose registers are connected through two buses (A and B) to a shared ALU whose result is loaded into one register selected by a decoder.
- Generate and propagate
- The signals \(G_i = A_iB_i\) (stage \(i\) makes a carry by itself) and \(P_i = A_i \oplus B_i\) (stage \(i\) passes an incoming carry on) used by a carry look-ahead adder.
- GPU
- Graphics processing unit: a many-core processor with thousands of simple cores that execute the same instruction on groups of threads (SIMD or SIMT), built for throughput.
- Gray code
- A non-weighted cyclic code in which successive values differ in exactly one bit; used for shaft encoders and for the row and column order of Karnaugh maps.
H¶
- Half adder
- A circuit that adds two bits, with \(S = A \oplus B\) and \(C = AB\); it has no carry input.
- Handshaking
- Two-wire asynchronous transfer control in which every action by one unit is acknowledged by the other, so the slower unit sets the pace and a missing reply is detected by a timeout.
- Hardwired control
- A control unit built as a fixed network of decoders, gates and flip-flops; fast, but changing it means redesigning the circuit.
- Hazard
- A condition (structural, data or control) that stops a pipeline from accepting or completing an instruction every cycle.
- Hidden bit
- The leading 1 of a normalised binary mantissa, which is understood rather than stored, giving one extra bit of precision at no cost.
- Hit ratio
- The fraction of memory references found in the cache, hits divided by hits plus misses.
I¶
- IEEE-754 single precision
- A 32-bit floating-point format with 1 sign bit, an 8-bit exponent field with bias 127 and 23 fraction bits, with value \((-1)^S \times 1.F \times 2^{E-127}\).
- Indirect addressing
- Addressing with
I = 1, in which the address field points to a word that holds the effective address; the basic computer follows exactly one level of indirection. - Input-output instruction
- One of the six instructions INP, OUT, SKI, SKO, ION and IOF, recognised by opcode 111 with I = 1 (codes
Fxxx) and executed at \(T_3\) under the control function \(p = D_7IT_3\). - Instruction code
- The group of bits, one 16-bit word in the basic computer, that tells the computer what operation to perform and on what: the opcode, the mode bit and the address.
- Instruction cycle
- The repeated sequence of fetch, decode, effective-address (indirect) and execute phases that the processor performs for every instruction.
- Instruction pipeline
- A pipeline that overlaps instruction processing in four segments: FI (fetch instruction), DA (decode and calculate address), FO (fetch operand) and EX (execute).
- Instruction register (IR)
- The 16-bit register that holds the instruction being executed; bits 12-14 feed the operation decoder and bit 15 sets
I. - Interrupt cycle
- The three microoperations \(RT_0\), \(RT_1\), \(RT_2\) that save PC in memory word 0, set PC to 1 and clear IEN and R when \(R = 1\).
- Interrupt flip-flop (R)
- The flip-flop that, when set by \(T_0'T_1'T_2'(IEN)(FGI + FGO)\), makes the next cycle an interrupt cycle instead of an ordinary instruction fetch.
- Interrupt-enable flip-flop (IEN)
- The master switch of the interrupt system: set by ION, cleared by IOF and by the interrupt cycle; while it is 0, device flags are ignored.
- I/O interface
- The circuit between the I/O bus and a device that resolves differences of signal, speed, data format and operating mode, and presents data, status and control registers to the CPU.
- I/O processor (IOP)
- A processor with its own direct memory access that executes I/O programs held in memory and interrupts the CPU only when a whole operation is complete; in mainframes it is called a channel.
- Isolated I/O
- An arrangement in which I/O ports have their own address space, reached with separate IN and OUT instructions and I/O read and write control lines.
- ISZ (increment and skip if zero)
- The memory-reference instruction that adds 1 to a memory word and skips the next instruction if the result is zero; with a negative count it builds a loop.
J¶
- JK flip-flop
- A flip-flop that sets (\(J=1\), \(K=0\)), resets (\(J=0\), \(K=1\)), holds (00) or toggles (11), so that no input combination is forbidden.
K¶
- Karnaugh map
- A truth table drawn in Gray-code order so that adjacent cells differ in one variable, allowing a minimal sum of products to be read off by grouping adjacent 1s.
L¶
- Latch
- A level-triggered storage element that is transparent while its enable input is active, so its output follows its input during that time.
- Latency
- The time one task takes from start to finish; pipelining does not reduce it.
- Load/store architecture
- An organization in which only LOAD and STORE instructions access memory and every other instruction works register to register.
- Locality of reference
- The tendency of programs to reuse the same addresses (temporal locality) and nearby ones (spatial locality), which makes caches and the memory hierarchy effective.
M¶
- Mantissa (significand)
- The significant digits of a floating-point number; its width sets the precision.
- Mapping (cache)
- The rule deciding where a main-memory block may be placed in the cache: one line (direct), any line (associative), or any line of one set (set-associative).
- Maxterm
- An OR term containing every variable once that is 0 for exactly one input combination; \(M_i = m_i'\).
- Memory address map
- The table that assigns a range of addresses to each RAM and ROM chip by means of the high-order address lines.
- Memory hierarchy
- The ordering of storage by speed, cost and capacity: registers, cache, main memory and auxiliary memory.
- Memory stack
- A stack held in a portion of main memory with a processor register as stack pointer; by convention it grows towards lower addresses, so a push decrements SP.
- Memory-mapped I/O
- An arrangement in which device registers occupy ordinary memory addresses, so load and store instructions serve for I/O at the cost of part of the address space.
- Metastability
- An unpredictable, unsettled output of a flip-flop or latch that results from a violation of setup or hold time, or from releasing an SR latch from its forbidden state.
- Microinstruction
- One word of control memory, specifying a set of microoperations to be performed together in one clock pulse and the address of the next microinstruction.
- Microoperation
- An elementary operation on data in registers, completed in one clock pulse: a register transfer, arithmetic, logic or shift operation.
- Microprogram
- The collection of microinstructions that implements the instruction set; one routine typically implements one machine instruction.
- Microprogrammed control
- A control unit that reads its control signals from a control memory as microinstructions; slower than hardwired control but flexible.
- Minterm
- An AND term containing every variable once that is 1 for exactly one input combination; a variable is unprimed where the row has a 1 and primed where it has a 0.
- Multicore processor
- A single chip with two or more independent cores, each able to execute its own instruction stream, usually with private L1 and L2 caches and a shared L3 cache.
- Multiplexer (MUX)
- A data selector with \(2^n\) data inputs, \(n\) select lines and one output; it connects the addressed input to the output and can realise any Boolean function.
N¶
- Normalisation
- Shifting a floating-point mantissa (and adjusting the exponent) so that its leading digit is non-zero, which gives a unique representation and the maximum precision.
O¶
- One-hot code
- A code in which exactly one bit is 1; in
7xxxandFxxxinstructions each of the low 12 bits selects one operation, so the hex codes are powers of two. - One-hot field
- A group of bits in which each bit selects one operation, as in the twelve low bits of a register-reference or input-output instruction, so every code is a power of two.
- Opcode (operation code)
- The field of an instruction (bits 14-12 here) that specifies which operation is to be performed.
- Overflow
- A signed result that falls outside the representable range, so that the stored sign is wrong; detected as \(V = C_{in} \oplus C_{out}\) of the sign bit and possible only for like-signed operands.
- Overflow (V)
- For signed numbers, a result that is out of range, detected as \(V = C_n \oplus C_{n-1}\); distinct from the carry-out, which is the unsigned out-of-range flag.
P¶
- Page table
- The table that translates a virtual page number into a frame number, with a presence bit that is 0 when the page is not in main memory.
- Parallel load
- A register control that, through a feedback multiplexer on each flip-flop, chooses between loading new data (Load = 1) and reloading the present value (Load = 0).
- Parity bit
- An extra bit added to a code word so that the number of 1s is even (or odd); it detects any single-bit error but cannot correct it.
- Pipeline segment
- One stage of a pipeline that performs part of the processing and passes the result, through a register, to the next stage.
- Positive and negative logic
- Conventions for naming the two voltage levels: in positive logic the higher level is 1, in negative logic the lower level is 1; a positive-logic AND gate is a negative-logic OR gate.
- Power wall
- The limit on clock frequency set by power and heat, since dynamic power grows as C·V²·f and a higher f needs a higher V; it ended frequency scaling and led to multicore.
- Prime implicant
- A group of 1s on a Karnaugh map (a product term) that cannot be enlarged into a bigger legal group.
- Priority encoder
- An encoder that, when several inputs are active, encodes the highest-priority one, and that has a valid output \(V\) distinguishing "code 0" from "no input".
- Priority interrupt
- A system that decides which of several simultaneous interrupt requests is served first, in software by polling or in hardware by a daisy chain or a priority encoder.
- Product of sums (POS)
- An expression made of OR terms ANDed together, such as \((A+B)(A'+C)\); the canonical form is the product of the maxterms where \(F = 0\).
- Program counter (PC)
- The 12-bit register that holds the address of the next instruction; it is incremented during fetch at
T1. - Program status word (PSW)
- The collection of the status bits, the interrupt-enable bit and the CPU mode that is saved on the stack, together with the PC, when an interrupt occurs.
- Programmed input-output
- Transfer of data in which the program repeatedly tests a device flag (for example SKI followed by BUN back) until the device is ready; correct but wastes processor time.
- Programmed I/O
- Transfer in which the CPU repeatedly tests an interface flag in a busy-wait loop and moves every word itself.
R¶
- Race-around
- The repeated toggling of a level-triggered JK flip-flop with \(J = K = 1\) during one clock pulse, which leaves the final state unpredictable; cured by master-slave or edge triggering.
- Radix complement (\(r\)'s complement)
- For an \(n\)-digit number \(N\), the value \(r^n - N\), equal to the \((r-1)\)'s complement plus 1; in binary the 2's complement and in decimal the 10's complement.
- Radix point
- The dot that separates the integer part of a number from its fractional part.
- RAM (random-access memory)
- Volatile read/write memory in which every word takes the same access time; static RAM (SRAM) uses latch cells and dynamic RAM (DRAM) uses a capacitor that must be refreshed.
- Register
- A group of \(n\) flip-flops with a common clock that stores an \(n\)-bit word.
- Register stack
- A stack built from a small bank of registers with a stack pointer and the FULL and EMTY flags; fast but of fixed size.
- Register window
- The set of registers visible to a procedure (locals, inputs, outputs and globals); adjacent windows overlap, so a caller's output registers are the callee's input registers and parameters pass without memory access.
- Register-reference instruction
- An instruction with opcode 111 and I = 0 (codes
7xxx) that operates on registers only and finishes at \(T_3\) under the control function \(r = D_7I'T_3\); there are twelve. - Reverse Polish notation (RPN)
- Postfix notation in which the operator is written after its operands; it needs no parentheses and is evaluated with a stack.
- RISC
- Reduced instruction set computer: few simple fixed-length instructions, load/store access to memory, many registers, single-cycle execution, hardwired control and easy pipelining, as in ARM, MIPS and RISC-V.
- RISC-V
- An open-standard RISC instruction set with 32 registers (x0 hard-wired to zero), fixed 32-bit instructions in six formats, no condition flags and a modular set of extensions.
- ROM (read-only memory)
- Non-volatile memory built as a decoder followed by a programmable OR array, so that it stores a truth table; types are mask ROM, PROM, EPROM, EEPROM and flash.
S¶
- Seek time and rotational latency
- The time to move a disk's read/write head to the required track, and the time for the required sector to rotate under it, on average half a revolution.
- SELA, SELB, SELD, OPR
- The four fields of the control word: the register on the A bus, the register on the B bus, the destination register (3 bits each) and the ALU operation (5 bits).
- Self-complementing code
- A decimal code, such as Excess-3 or 2421, in which inverting all four bits of a digit's code word gives the code word of its 9's complement.
- Sequence counter (SC)
- The 4-bit counter whose decoded output gives the timing signals
T0toT15; it is cleared bySC ← 0to end an instruction. - Sequential circuit
- A circuit whose outputs depend on the present inputs and on stored state; a synchronous one is combinational logic plus flip-flops, feedback and a clock.
- Service routine
- The short program, started at memory location 1 by the interrupt cycle, that deals with the interrupting device and returns with ION followed by an indirect BUN 0.
- Setup time and hold time
- The intervals before and after the active clock edge during which a flip-flop's data input must stay stable; violating them can cause metastability.
- Shift register
- A register whose bits move one position per clock; SISO, SIPO, PISO and PIPO describe whether data enters and leaves serially or in parallel.
- Sign bit
- The leftmost bit of a signed number: 0 means positive and 1 means negative.
- Sign extension
- Widening a 2's-complement number by replicating its sign bit into the new high-order positions so that the value is unchanged.
- Signed-2's-complement
- The standard machine representation of signed integers, in which a negative number is the 2's complement of its magnitude; one zero and a range of \(-2^{n-1}\) to \(+(2^{n-1}-1)\).
- Signed-magnitude
- A representation with a sign bit followed by the magnitude, unchanged for negative numbers; it has two zeros.
- SIMD and SIMT
- Single instruction, multiple data (one instruction applied to many data items) and NVIDIA's single instruction, multiple threads (a warp of threads executing in lock-step).
- Skip instruction
- An instruction (SPA, SNA, SZA, SZE, SKI, SKO) that adds one to PC when its condition is true, so that the next instruction is skipped; the basis of every conditional branch.
- Space-time diagram
- A grid of segments (or instructions) against clock cycles showing which task each segment handles in each cycle; \(k\) segments and \(n\) tasks take \(k + n - 1\) cycles.
- Speedup
- The ratio of non-pipelined to pipelined time, \(S = n\,t_n/((k + n - 1)\,t_p)\); its limit is \(t_n/t_p\), which equals \(k\) for a perfectly balanced pipeline.
- SR latch
- Two cross-coupled NOR (or NAND) gates that store one bit; the input pair \(S = R = 1\) (NOR form) is forbidden because its release is a race.
- Stack pointer (SP)
- The register that holds the address of the top item of a stack; PUSH and POP change SP.
- Static-1 hazard
- A momentary 0 on an output that should stay at 1 when one input changes, caused by unequal path delays; it shows on a map as two adjacent 1s not covered by a common term.
- Status bits (C, S, Z, V)
- The carry, sign, zero and overflow flip-flops set by the ALU (C = C8, S = F7, Z = all-zero result, V = C7 ⊕ C8) that conditional branch instructions test.
- Stored-program concept
- The idea that instructions and data are held in the same memory and the control unit fetches and executes the instructions one by one, so a program can be changed without rewiring the machine.
- Strobe
- A single control pulse that tells the destination when data on the bus is valid; it gives no acknowledgement.
- Structural hazard
- A pipeline hazard in which two segments need the same hardware in the same cycle, typically memory for FI and FO; remedied by separate instruction and data memories or caches.
- Sum of products (SOP)
- An expression made of AND terms ORed together, such as \(AB + A'C\); the canonical form is the sum of the minterms where \(F = 1\).
T¶
- T flip-flop
- A toggle flip-flop: \(T = 0\) holds the state and \(T = 1\) complements it, \(Q(t+1) = T \oplus Q\); a JK flip-flop with \(J\) and \(K\) tied together.
- Tag, index and word
- The fields of a cache address: the tag identifies the block, the index (or set field) selects the line or set, and the word selects the item inside the block.
- Temporary register (TR)
- The 16-bit scratch register used by the control unit, for example to hold
PCduring the interrupt cycle. - Throughput
- The number of tasks completed per unit time; pipelining raises it by completing one task every clock cycle once the pipeline is full.
- Time-division multiplexing
- Sharing one wire among several signals by connecting each to it in turn, using a multiplexer and demultiplexer driven by the same repeating select code.
- Timing signal
- One of the outputs
T0toT15of the 4-to-16 decoder onSC; exactly one is active at a time and each marks one clock pulse of an instruction. - Truth table
- A complete list of the output for every combination of the inputs; a circuit with \(n\) inputs has \(2^n\) rows.
U¶
- Universal gate
- A gate from which every Boolean function can be built; NAND and NOR are universal (NOT is one gate, AND two, OR three), XOR is not.
- Universal shift register
- A shift register with a 4:1 multiplexer on each stage and two mode bits that choose hold, shift right, shift left or parallel load.
V¶
- Virtual memory
- The technique of using main memory as a cache for the disk, dividing the address space into pages and memory into frames, with page faults handled by the operating system.
W¶
- Warp
- A group of typically 32 GPU threads that execute the same instruction in lock-step (AMD calls it a wavefront); if the threads take different branches the warp executes both paths in turn.
- Weighted code
- A binary code in which each bit position has a fixed weight, so that a digit is the weighted sum of its bits (BCD with weights 8-4-2-1 is the standard example).
- Write-back and write-through
- Cache write policies: write-back updates only the cache (setting a dirty bit) and writes memory on replacement; write-through updates cache and memory on every write.