Architecture: Difference between revisions

Digital, finite transformations will be performed by processing units connected to memories (stores) and I/O devices.

*By '''digital''', we mean that [http://en.wikipedia.org/wiki/Irrational_number irrational numbers] cannot be faithfully reproduced in variables, nor [http://en.wikipedia.org/wiki/Analog_signal analog signals] in samples -- we can work directly (without approximation) only with [http://en.wikipedia.org/wiki/Countable_set countable sets] (see the [[real computing]] of Blum et al for another perspective).

===Instruction Level Parallelism===

===Thread Level Parallelism===

* [[Architecture#Caches|Caches]]: Submemories. Performance-critical components of a store's abstraction -- like any abstraction's internals, their user oughtn't need know them to make use of the abstraction, but might require intimate knowledge to make full and efficient use! SRAM close to or on the chip serves as (often multiple-level) caches for main system DRAM. A section of DRAM is often used as a "page cache" for system disk (system DRAM as a whole, however, is *not* a cache of disk. Swap is a part of virtual memory implementation and not germane to discussion of cache). Caches take advantage of predictable access patterns (temporal clustering, spatial clustering, software and hardware prefetching) to provide faster access to a subset of the memory abstraction. In exchange, they add complexity, draw power, and often consume both large swaths of a system's transistor budget and prime real estate. In the absence of accurate prediction (very random patterns, woefully undersized cache, etc), the memory system is said to be thrashing, and performance can be substantially worsened relative to an uncached memory. Usually, however, caches lead to drastic performance improvements.

* Data units: Generally known as registers, this memory is directly available to execution units. It is capable of being updated every cycle, although such a supply might be impossible. Read and write ports directly connects the register file to combinatorial hardware and main memory. On some architectures, instructions can directly reference memory.

Memory hierarchies are highly discretized. Storage offered by different memories usually involves quantitative shifts measured in orders of magnitude, as does time required to access them -- nanoseconds for small on-die SRAMs, microseconds for uncached access to system DRAM, milliseconds for hard drive accesses, fractions of a second for network transfers (hey, it still beats the post office).

Given the tradeoff and potentialities involved in cache design, and the wide gap between access times of different stores, caches are often multitiered. Current processors often support three levels of hardware cache; almost all disks provide a few megabytes of DRAM as a cache well before, and for different purposes than, the operating system introduces a page cache. Among the levels of a multitiered cache, two levels can be:

Reads are the common case -- 1 instruction cache hit (barring trace caches, etc) for every instruction issued, and loads usually substantially outweighing stores for data cache (or unified cache) access. They're also faster (assuming the data is in cache): the processor needn't specify the width of the load, and the data can be loaded while the tag is being checked -- if the tag doesn't match, no harm is done. Writes must wait for the tag to be verified. Write-combining can be performed in unflushed write buffers or dirty lines of a write-back cache, saving memory bandwidth. Writing policies include:

* Write-through: the write propagates out throughout the store abstraction (ie, from L1 cache, over an exclusive L2 cache, to system DRAM). Simple to implement, as writes need no buffers and loads resulting in evictions never force writebacks. Cache and backing store exhibit data coherence (observers never see a different value in memory than what's in cache), a useful property in the presence of multiple cores or DMA. In order to write at the full speed of the cache, writes must be buffered; for a load which overwhelms the write buffer, or in its absence, the processor will see write stalls above and beyond the cache timings even for cached data.

A cache hit occurs when data being referenced is valid in the cache; otherwise the reference is a cache miss. A bit is typically devoted to determining validity of a cacheline. The cache is initialized so that all lines are marked invalid. As lines are loaded, they become valid. In the absence of cache coherency protocols, lines once valid will remain valid (but might change address); other processors' writes might invalidate lines in a multicore system. Misses are categorized into four types:

Avoiding address translation introduces aliasing: a single cacheline worth of backing store might be represented twice in a cache, since each process (usually) has its own virtual memory. It also forces page access settings to be copied into the cache from the TLB, and PID-tagging lest cache flushes be required upon context switches. Thus, VIPT -- Virtual-Index, Physical-Tag -- translation is performed in parallel with indexing based solely upon the page offset (shared between physical and virtual addresses), and physical addresses are used beyond the lowest-level cache (PIPT, Physical-Index Physical-Tag). Adding capacity incurs transistor and power cost, and can slightly increase access penalty. Increasing associativity can increase access penalty even more, and also has hardware costs.Augmenting either can actually decrease hit rates for a given workload, due to the interactions between addresses and cache geometry. There's four rules of thumb here: