1BP: 1-bit branch predictor
4 C's - compulsory Misses: the first time a block is accessed by the cache 4 C's - capacity Misses: blocks must be evicted due to the size of the cache.
4 C's - coherence Miss: processors are accessing the same block. Processor A writes to the block. Even though Processor B has the block in its cache, it is a miss, because the block is no longer up-to-date.
4 C's - conflict Misses: associated with set associative and direct mapped caches - another data address needs the cache block and must replace the data currently in the cache.
ALAT: advance load table - stores advance information about load operations
aliasing: in the BTB, when two addresses overlap with the same BTB entry, this is called aliasing. Aliasing should be kept to <1%.
ALU: arithmetic logic unit
AMAT: average memory access time
AMAT: Average Memory Access Time = hit time + miss rate * miss penalty
Amdahl's Law: an equation to determine the improvement of a system when only a portion of the system is improved.
architectural registers: registers (Floating point and General Purpose) that are visible to the programmer.
ARF: architectural register file or retirement register file
Asynchronous Message Passing: a processor requests data, then continues processing instructions while message is retrieved.
BHT: branch history table - records if branch was taken or not taken.
blocking cache: the cache services only one block at a time, blocking all other requests BTB: branch target buffer - keeps track of what address was taken last time the processor encountered this instruction.
cache coherence definition #1: Definition #1 - A read R from address X on processor P1 returns the value written by the most recent write W to X on P1 if no other processor has written to X between W and R.
cache coherence definition #2: Definition #2 - If P1 writes to X and P2 reads X after a sufficient time, and there are no other writes to X in between, P2’s read returns the value written by P1’s write.
cache coherence definition #3: Definition #3 - Writes to the same location are serialized:two writes to location X are seen in the same order by all processors.
cache hit: desired data is in the cache and is up-to-date cache miss: desired data is not in the cache or is dirty
cache thrashing: when two or more addresses are competing for the same cache block. The processor is requesting both addresses, which results in each access evicting the previous access. CDB: common data bus
check pointing: store the state of the CPU before a branch is taken. Then if the branch is a misprediction, restore the CPU to correct state. Don't store to memory until it is determined this is the correct branch.
CISC Processor: complex instruction set CMP: chip multiprocessor
coarse multi-threading: the thread being processed changes every few clock cycles consistency: order of access to different addresses
control hazard: branching and jumps cannot be executed until the destination address is known CPI: cycle per instruction
CPU: central processing unit
Dark Silicon: the gap between how many transistors are on a chip and how many you can use simultaneously. The simultaneous usage is determined by the power consumption of the chip. data hazard: the order of the program is changed which results in data commands being out of order, if the instructions are dependent - then there is a data hazard.
DDR SDRAM: double data rate synchronous dynamic RAM dependency chain: long series of dependent instructions in code
directory protocols: information about each block state in the caches is stored in a common directory.
DRAM: dynamic random access memory
DSM: distributed shared memory - all processors can access all memory locations Enterprise class: used for large scale systems that service enterprises
error: defect that results in failure
error forecasting: estimate presence, creation, and consequences of errors error removal: removing latent errors by verification
exclusion property: each cache level will not contain any data held by a lower level cache explicit ILP: compiler decides which instruction to execute in parallel
failure: the cause of an error
fault avoidance: prevent an occurrence of faults by construction
fault tolerance: prevent faults from becoming failures through redundancy faults: actual behavior deviates from specified behavior
FIFO: first in first out
fine multi-threading: the thread being processed changes every cycle FLOPS: floating point operations per second
Flynn's Taxonomy: classifications of parallel computer architecture, SISD, SIMD, MISD, MIMD
FPR: floating point register FSB: front side bus
Geometric Mean: the nth root of the product of the numbers global miss rate: (the # of L2 misses)/(# of all memory misses) GPR: general purpose register
hit latency: time it takes to get data from cache. Includes the time to find the address in the cache and load it on the data lines
ilp: instruction level programming
inclusion property: each level of cache will include all data from the lower level caches IPC: instructions per cycle
Iron Law: execution time is the number of executed instructions N (write N in in the ExeTime for Single-Cycle), times the CPI (write x1), times the clock cycle time (write 2ns) so we get N2ns (write =N2ns) for single-cycle.
Iron Law: instructions per program depends on source code, compiler technology, and ISA. CPI depends upon the ISA and the micro architecture. Time per cycle depends upon the micro architecture and the base technology.
iron law of computer performance: relates cycles per instruction, frequency and number of instructions to computer performance
ISA: instruction set architecture
Itanium architecture: an explicit ILP architecture, six instructions can be executed per clock cycle
Itanium Processor: Intel family of 64-bit processors that uses the Itanium architecture LFU: least frequently used
ll and sc: load link and store conditional, a method using two instructions ll and sc for ensuring synchronization.
local miss rate: # of L2 misses/ # of L1 misses
locality principle: things that will happen soon are likely to be similar to things that just happened.
loop interchange: used for nested loops. Interchange the order of the iterations of the loop, to make the accesses of the indexes closer to what is actually the layout in memory
LRU: least recently used LSQ: load store queue
MCB: memory conflict buffer - "Dynamic Memory Disambiguation Using the Memory Conflict Buffer", see also "Memory Disambiguation"
MEOSI Protocol: modified-exclusive-owner-shared-invalid protocol, the states of any cached block.
MESI Protocol: modified-exclusive-shared-invalid protocol, the states of any cached block. Message Passing: a processor can only access its local memory. To access other memory locations is must send request/receive messages for data at other memory locations. meta-predictor: a predictor that chooses the best branch predictor for each branch. MIMD: multiple instruction stream, multiple data streams
MISD: multiple instruction streams, single data stream
miss latency: time it takes to get data from main memory. This includes the time it takes to check that it is not in the cache and then to determine who owns the data, and then send it to the CPU.
mobo: mother board
Moore's Law: Gordon E. Moore observed the number of transistors on an integrated circuit board doubles every two years.
MPKI: Misses per Kilo Instruction
MSI Protocol: modified-shared-invalid protocol, the states of any cached block. MTPI: message transfer part interface
MTTF: mean time to failure MTTR: mean time to repair
multi-level caches: caches with two or more levels, each level larger and slower than the previous level
mutex variable: mutually exclusive (mutex), a low level synchronization mechanism. A thread acquires the variable, then releases it upon completion of the task. During this period no other thread can acquire the mutex.
NMRU: not most recently used
non-blocking caches: if there is a miss, the cache services the next request while waiting for memory
NUMA: non-uniform memory access, also called a distributed shared memory OOO: out of order
OS: operating system
PAPT: physically addressed, physically tagged cache - the cache stores the data based on its physcial address
PC: program counter
PCI: peripheral component interconnect
Pentium Processor: x86 super scalar processor from Intel
physical registers: registers, FP and GP that are not visible to the programmer pipeline burst cache:
pipelined cache: a pipelined burst cache uses 3 clock cycles to transfer the first data set from a cache block, then 1 clock cycle to transfer each of the rest. The pipeline and the 'burst'. (3-1-1-1) PIPT: physically indexed, physically tagged cache.
Power: Power = 1/2C V^2 * f Alpha
Power Architecture: performance optimization with enhanced RISC
Power vs Performance Equation:
pre-fetch buffer: when getting data from memory, get all the data in the row and store it in a buffer.
pre-fetching cache: instructions are fetched from memory before they are needed by the cpu " Prescott Processor: Based on the Netburst architecture. It has a 31 stage pipeline in the core. The high penatly paid for mispredictions is supposedly offset with a Rapid Execution Engine. It also has a trace execution cache, this stores decoded instructions and then reuses them instead of fetching and decoding again.
PRF: physical register file
pseudo associative cache: an address is first searched in 1/2 of the cache. If it is not there, then it is searched in the other half of the cache.
RAID: redundant array of independent disks
RAID 0: strips of data are stored on disks - alternating between disks. Each disk supplies a portion of the data, which usually improves performance.
RAID 1: the data is replicated on another disk. Each disk contains the data. Which ever disk is free responds to the read request. The write request is written to one disk and then mirrored to the other disk(s).
RAID 2 and RAID 3: the data is striped on disks and Hamming codes or parity bits are used for error detection. RAID 2 and RAID 3 are not used in any current application
RAID 4: Data is striped in large blocks onto disks with a dedicated parity disk. It is used by the NetApp company.
RAID 5: Data is striped in large blocks onto disks, but there is no dedicated parity disk. The parity for each block is stored on one of the data blocks.
RAR: read after read RAS: return address stack RAT: register alias table
RAT: *(another RAT in multiprocessing) register allocation table RAW: read after write
RDRAM: direct random access memory
relaxed consistency: some instructions can be performed ooo and still maintain consistency reliability: measure of continuous service accomplishment
reservation stations: function unit buffers
RETO: return from interrupt
RF: register file
RISC Processor: reduced instruction set - simple instructions of the same size. Instructions are executed in one clock cycle
ROB: re-order buffer RS: reservation station
RWX: read - write- execute permissions on files
SHARC processor: floating point processors designed for DSP applications SIMD: singe instruction stream, multiple data streams
simultaneous multi-threading: instructions from different threads are processed, even in the same cycle
SISD: single instruction stream , single data stream SMP: symmetric multiprocessing
SMT: simultaneous multi threading
snooping protocols: A broadcast network - caches for each processor watch the bus for addresses in their cache.
SPARC processor: Scalable Processor Architecture -a RISC instruction set processor
spatial locality: if we access a memory location, nearby memory locations have a tendency to be accessed soon.
Speedup: how much faster a modified system is compared to the unmodified system. SPR: special purpose registers - such as program counter, or status register
SRAM: static random access memory
structural hazard: the pipeline contains two instructions attempting to access the same resource.
super scalar architecture: the processor manages instruction dependencies at run-time. Executes more than one instruction per clock cycle using pipelines.
synchronization: "a system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations for each individual processor appear in the order specified by the program." Quote by Leslie Lamport
Synchronous Message Passing: a processor requests data then waits until the data is received before continuing.
tag: the part of the data address that is used to find the data in the cache. This portion of the address is unique so that it can be distinguished from other lines in the cache.
temporal locality: if a program accesses a memory location, it tends to access the same location again very soon.
TLB: translation look aside buffer - a cache of translated virtual memory to physical memory addresses. TLB misses are very time consuming
Tomasulo's Algorithm: achieve high performance without using special compilers by using dynamic scheduling
tournament predictor: a meta-predictor
trace caches: sets of instructions are stored in a separate cache. These are instructions that have been decoded and executed. If there is a branch in the set, only the taken branch instructions are kept. If there is a misprediction the trace stops.
trace scheduling: rearranging instructions for faster execution, the common cases are scheduled tree, tournament, dissemination barriers: types of structures for barriers