Architecture - revision history

Dank: /* Register-level parallelism */

2012-04-20T06:46:23Z

← Older revision		Revision as of 06:46, 20 April 2012
Line 17:		Line 17:
	===Bit-level parallelism===		===Bit-level parallelism===
	===Register-level parallelism===		===Register-level parallelism===
	* See the [[SIMD page]].		* See the [[SIMD\|SIMD page]].

	===Instruction Level parallelism===		===Instruction Level parallelism===

Dank: /* Register-level parallelism */

2012-04-20T06:46:01Z

← Older revision		Revision as of 06:46, 20 April 2012
Line 17:		Line 17:
	===Bit-level parallelism===		===Bit-level parallelism===
	===Register-level parallelism===		===Register-level parallelism===
	* See the [[SIMD]] ~~page~~.		* See the [[SIMD page]].

	===Instruction Level parallelism===		===Instruction Level parallelism===
	===Memory Level parallelism===		===Memory Level parallelism===

Dank: /* Stored Programs */

2011-12-09T10:50:20Z

Stored Programs

← Older revision		Revision as of 10:50, 9 December 2011
Line 4:		Line 4:
	*Reliable (the probability of undetected and detected errors can be meaningfully bounded), and		*Reliable (the probability of undetected and detected errors can be meaningfully bounded), and
	*Reprogrammable at a purely symbolic, as opposed to physical, level		*Reprogrammable at a purely symbolic, as opposed to physical, level
	Digital, finite transformations will be performed by processing units connected to memories (stores) and I/O devices.		[[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).		*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).
	*By '''finite''', we mean that a given store can contain only a [http://en.wikipedia.org/wiki/Finite_set finite set] of strings having finite [http://en.wikipedia.org/wiki/Shannon's_source_coding_theorem Shannon Entropy] -- essentially, finite integers. By combining the two, our domain becomes finite sets of finite [http://en.wikipedia.org/wiki/Algorithmic_complexity_theory algorithmic complexity theory] (or so I understand things to work) -- the so-called [http://en.wikipedia.org/wiki/Computable_number computable numbers].		*By '''finite''', we mean that a given store can contain only a [http://en.wikipedia.org/wiki/Finite_set finite set] of strings having finite [http://en.wikipedia.org/wiki/Shannon's_source_coding_theorem Shannon Entropy] -- essentially, finite integers. By combining the two, our domain becomes finite sets of finite [http://en.wikipedia.org/wiki/Algorithmic_complexity_theory algorithmic complexity theory] (or so I understand things to work) -- the so-called [http://en.wikipedia.org/wiki/Computable_number computable numbers].
	*'''Processing units''' expose simple functional building blocks (maps from finite sets of integers to finite sets of integers) and communication primitives through which connected devices might be manipulated. An [http://en.wikipedia.org/wiki/Instruction_set_architecture instruction set architecture (ISA)] defines the syntax and semantics of these finite languages.		*'''Processing units''' expose simple functional building blocks (maps from finite sets of integers to finite sets of integers) and communication primitives through which connected devices might be manipulated. An [http://en.wikipedia.org/wiki/Instruction_set_architecture instruction set architecture (ISA)] defines the syntax and semantics of these finite languages.

Dank: /* Caches */

2010-04-21T00:16:10Z

Caches

← Older revision		Revision as of 00:16, 21 April 2010
Line 40:		Line 40:
	Similarly, the main memory's cache is often split into an instruction cache and data cache, with their own ports (and possibly different implementations and sizes), yielding improved access times and fewer structural hazards (instructions can be fetched, while in another unit data are accessed, without structural hazards or expensive logic). A unified cache can make more complete use of the memory available, however, especially for very small programs, effectively trading the risk of conflicts for greater capacity.		Similarly, the main memory's cache is often split into an instruction cache and data cache, with their own ports (and possibly different implementations and sizes), yielding improved access times and fewer structural hazards (instructions can be fetched, while in another unit data are accessed, without structural hazards or expensive logic). A unified cache can make more complete use of the memory available, however, especially for very small programs, effectively trading the risk of conflicts for greater capacity.

	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:		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 (configured on the x86 via [[MTRR]]s or [[PAT]]s) 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.		* 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.
	* Write-back: the write is only applied to the cache. Memory is updated when the line is replaced. Minimizes latency for the attached execution unit -- potential write throughput is equivalent to that of the cache. Saves memory bandwidth and power, but requires a coherency protocol (with its own state requirements). Minimally, a dirty bit indicates that the line need be written back upon eviction. In the presence of multiple, independent caches at the same level of a store abstraction, full cache coherency protocols such as MESI are used. Write-back caches also tend to employ write buffers (so that reads might be prioritized; see below), also known as "victim buffers" by AMD (not to be concerned with victim caches, small fast direct-mapped stores into which all evicted lines go, not just dirty ones -- the goal of this latter is to minimize the impact of conflict misses, not eliminate blocking on writebacks).		* Write-back: the write is only applied to the cache. Memory is updated when the line is replaced. Minimizes latency for the attached execution unit -- potential write throughput is equivalent to that of the cache. Saves memory bandwidth and power, but requires a coherency protocol (with its own state requirements). Minimally, a dirty bit indicates that the line need be written back upon eviction. In the presence of multiple, independent caches at the same level of a store abstraction, full cache coherency protocols such as MESI are used. Write-back caches also tend to employ write buffers (so that reads might be prioritized; see below), also known as "victim buffers" by AMD (not to be concerned with victim caches, small fast direct-mapped stores into which all evicted lines go, not just dirty ones -- the goal of this latter is to minimize the impact of conflict misses, not eliminate blocking on writebacks).

Dank at 19:33, 22 March 2010

2010-03-22T19:33:58Z

← Older revision		Revision as of 19:33, 22 March 2010
Line 77:		Line 77:
	[[Category: x86]]		[[Category: x86]]
	[[Category: CS GRE Prep]]		[[Category: CS GRE Prep]]
			[[CATEGORY: Hardware]]

Dank: /* Memory Hierarchies */

2010-03-22T19:06:40Z

Memory Hierarchies

← Older revision		Revision as of 19:06, 22 March 2010
Line 29:		Line 29:
	** In a computer architecture context, "cache" usually refers only to the (possibly-multilevel) caches of main memory.		** In a computer architecture context, "cache" usually refers only to the (possibly-multilevel) caches of main memory.
	** In an OS context, "cache" might refer to any store.		** In an OS context, "cache" might refer to any store.
	* 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.		* 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 devices\|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).		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).

Dank: /* Virtual Memory */

2010-03-17T08:10:04Z

Virtual Memory

← Older revision		Revision as of 08:10, 17 March 2010
Line 70:		Line 70:

	====Virtual Memory====		====Virtual Memory====
	[[File:Memoryhierarchy.png\|right\|alt="Diagram of address translation"]]		[[File:Memoryhierarchy.png\|thumb\|right\|alt="Diagram of address translation"]]

	==See Also==		==See Also==

Dank: /* Memory Hierarchies */

2009-12-09T19:23:49Z

Memory Hierarchies

← Older revision		Revision as of 19:23, 9 December 2009
Line 26:		Line 26:
	Processor clocking and even instruction set design is intimately related to access times of the lowest-level cache of the main memory.		Processor clocking and even instruction set design is intimately related to access times of the lowest-level cache of the main memory.
	* Stores: large, off-chip memories. System [[DRAM]] provides a volatile store (this is typically what's meant by "main memory"), while ferromagnetic and optical disks provide non-volatile, slower, larger stores (often called "secondary memory"). As stores get larger, access times usually increase; taken to an extreme, the Internet is just a highly unreliable, massively-distributed store exhibiting wildly varying access times: a memory for all mankind.		* Stores: large, off-chip memories. System [[DRAM]] provides a volatile store (this is typically what's meant by "main memory"), while ferromagnetic and optical disks provide non-volatile, slower, larger stores (often called "secondary memory"). As stores get larger, access times usually increase; taken to an extreme, the Internet is just a highly unreliable, massively-distributed store exhibiting wildly varying access times: a memory for all mankind.
	* [[Architecture#Caches\|Caches]]: Submemories. Performance-critical components of a store's abstraction -- like any abstraction's internals, their user [[Cache-oblivious algorithms\|oughtn't need know them]] to make use of the abstraction, but [[Cache-aware algorithms\|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.		* [[Architecture#Caches\|Caches]]: Submemories. Performance-critical components of a store's abstraction -- like any abstraction's internals, their user [[Cache-oblivious algorithms\|oughtn't need know them]] to make use of the abstraction, but [[Cache-aware algorithms\|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.
	** In a computer architecture context, "cache" usually refers only to the (possibly-multilevel) caches of main memory.		** In a computer architecture context, "cache" usually refers only to the (possibly-multilevel) caches of main memory.
	** In an OS context, "cache" might refer to any store.		** In an OS context, "cache" might refer to any store.
	* 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.		* 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).		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).

	====Caches====		====Caches====

Dank: /* Caches */

2009-12-09T19:23:18Z

Caches

← Older revision		Revision as of 19:23, 9 December 2009
Line 33:		Line 33:

	====Caches====		====Caches====
	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:		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:
	* inclusive: the lower level is a strict subset of data available in the higher level		* inclusive: the lower level is a strict subset of data available in the higher level
	* exclusive: the caches share no data		* exclusive: the caches share no data
Line 41:		Line 41:

	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:		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.		* 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.
	* Write-back: the write is only applied to the cache. Memory is updated when the line is replaced. Minimizes latency for the attached execution unit -- potential write throughput is equivalent to that of the cache. Saves memory bandwidth and power, but requires a coherency protocol (with its own state requirements). Minimally, a dirty bit indicates that the line need be written back upon eviction. In the presence of multiple, independent caches at the same level of a store abstraction, full cache coherency protocols such as MESI are used. Write-back caches also tend to employ write buffers (so that reads might be prioritized; see below), also known as "victim buffers" by AMD (not to be concerned with victim caches, small fast direct-mapped stores into which all evicted lines go, not just dirty ones -- the goal of this latter is to minimize the impact of conflict misses, not eliminate blocking on writebacks).		* Write-back: the write is only applied to the cache. Memory is updated when the line is replaced. Minimizes latency for the attached execution unit -- potential write throughput is equivalent to that of the cache. Saves memory bandwidth and power, but requires a coherency protocol (with its own state requirements). Minimally, a dirty bit indicates that the line need be written back upon eviction. In the presence of multiple, independent caches at the same level of a store abstraction, full cache coherency protocols such as MESI are used. Write-back caches also tend to employ write buffers (so that reads might be prioritized; see below), also known as "victim buffers" by AMD (not to be concerned with victim caches, small fast direct-mapped stores into which all evicted lines go, not just dirty ones -- the goal of this latter is to minimize the impact of conflict misses, not eliminate blocking on writebacks).

Dank: /* Caches */

2009-12-09T19:15:24Z

Caches

← Older revision		Revision as of 19:15, 9 December 2009
Line 62:		Line 62:
	* Parallelizing: interleaved/banked cache		* Parallelizing: interleaved/banked cache

	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:		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:
	* Associativity beyond 8-way is useless, except for very small (a few K at most) caches		* Associativity beyond 8-way is useless, except for very small (a few K at most) caches
	* For caches less than a hundred K or so, miss rate for fKb under 2-way associativity ~= miss rate for 2fKb direct mapped		* For caches less than a hundred K or so, miss rate for fKb under 2-way associativity ~= miss rate for 2fKb direct mapped