CSC/ECE 506 Spring 2012/10a jp - Revision history

Scanjee: /* == */

2013-04-02T00:46:17Z

← Older revision		Revision as of 00:46, 2 April 2013
Line 62:		Line 62:

	Increasing the cache block size increases the likelihood of two processors sharing data from the same block and hence false sharing is more likely to arise. Sequential prefetching can take advantage of spatial locality without introducing some of the problems associated with large cache blocks. The simplest sequential prefetching schemes are variations upon the one block lookahead (OBL) approach which initiates a prefetch for block b+1 when block b is accessed. For example, a large block may contain one word which is frequently referenced and several other words which are not in use. Assuming an Least recently used (LRU) replacement policy, the entire block will be retained even though only a portion of the block’s data is actually in use. If this large block were replaced with two smaller blocks, one of them could be evicted to make room for more active data. The reason prefetch-on miss is less effective is illustrated in Figure beside where the behavior of each algorithm when accessing three contiguous blocks is shown. Here, it can be seen that a strictly sequential access pattern will result in a cache miss for every other cache block when the prefetchon-miss algorithm is used but this same access pattern results in only one cache miss when employing a tagged prefetch algorithm.		Increasing the cache block size increases the likelihood of two processors sharing data from the same block and hence false sharing is more likely to arise. Sequential prefetching can take advantage of spatial locality without introducing some of the problems associated with large cache blocks. The simplest sequential prefetching schemes are variations upon the one block lookahead (OBL) approach which initiates a prefetch for block b+1 when block b is accessed. For example, a large block may contain one word which is frequently referenced and several other words which are not in use. Assuming an Least recently used (LRU) replacement policy, the entire block will be retained even though only a portion of the block’s data is actually in use. If this large block were replaced with two smaller blocks, one of them could be evicted to make room for more active data. The reason prefetch-on miss is less effective is illustrated in Figure beside where the behavior of each algorithm when accessing three contiguous blocks is shown. Here, it can be seen that a strictly sequential access pattern will result in a cache miss for every other cache block when the prefetchon-miss algorithm is used but this same access pattern results in only one cache miss when employing a tagged prefetch algorithm.


	==='''Prefetching on Multiprocessors'''===		==='''Prefetching on Multiprocessors'''===

Japlemmo: /* Prefetching and Consistency Models */

2012-04-05T02:42:12Z

Prefetching and Consistency Models

← Older revision		Revision as of 02:42, 5 April 2012
Line 144:		Line 144:

	A more modern and innovative technique, stealth prefetching<ref>http://arnetminer.org/publication/stealth-prefetching-53889.html</ref>, attempts to deal with issues surrounding the increase of interconnection bandwidth and increased memory latency. It also helps to avoiding the problem of using bandwidth to prematurely access shared data that will later result in state downgrades. Basically, this technique attempts to focus on specific regions of memory in a more coarsely designed fashion to identify which segments are heavily used by multiple processors and which ones are not. Lines that are not being shared by multiple processors are more aggressively brought nearer to the local processor, thus improving performance by as much as 20%. With the increased use of fast multiprocessors, this alleviates some of the bandwidth bottlenecks.		A more modern and innovative technique, stealth prefetching<ref>http://arnetminer.org/publication/stealth-prefetching-53889.html</ref>, attempts to deal with issues surrounding the increase of interconnection bandwidth and increased memory latency. It also helps to avoiding the problem of using bandwidth to prematurely access shared data that will later result in state downgrades. Basically, this technique attempts to focus on specific regions of memory in a more coarsely designed fashion to identify which segments are heavily used by multiple processors and which ones are not. Lines that are not being shared by multiple processors are more aggressively brought nearer to the local processor, thus improving performance by as much as 20%. With the increased use of fast multiprocessors, this alleviates some of the bandwidth bottlenecks.

	~~=='''References'''==~~

	~~<references></references>~~

	=='''Definitions'''==		=='''Definitions'''==
Line 156:		Line 152:

	3) '''SPARC''' - SPARC (from Scalable Processor Architecture) is a RISC instruction set architecture (ISA) developed by Sun Microsystems and introduced in mid-1987.		3) '''SPARC''' - SPARC (from Scalable Processor Architecture) is a RISC instruction set architecture (ISA) developed by Sun Microsystems and introduced in mid-1987.

			=='''References'''==

			<references></references>

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

Japlemmo: /* Definitions */

2012-04-05T02:41:06Z

Definitions

← Older revision		Revision as of 02:41, 5 April 2012
Line 151:		Line 151:
	=='''Definitions'''==		=='''Definitions'''==

	1) '''Linked List'''		1) '''Linked List''' - In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence

	2) '''Cache Pollution'''		2) '''Cache Pollution''' - Cache pollution describes situations where an executing computer program loads data into CPU cache unnecessarily, thus causing other needed data to be evicted from the cache into lower levels of the memory hierarchy, potentially all the way down to main memory, thus causing a performance hit.

	3) '''SPARC'''		3) '''SPARC''' - SPARC (from Scalable Processor Architecture) is a RISC instruction set architecture (ISA) developed by Sun Microsystems and introduced in mid-1987.

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

Japlemmo: /* Definitions */

2012-04-05T02:39:00Z

Definitions

← Older revision		Revision as of 02:39, 5 April 2012
Line 151:		Line 151:
	=='''Definitions'''==		=='''Definitions'''==

	1) ''''''		1) '''Linked List'''

	2)		2) '''Cache Pollution'''

	3)		3) '''SPARC'''

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

Japlemmo: /* Cache Sizing */

2012-04-05T02:38:14Z

Cache Sizing

← Older revision		Revision as of 02:38, 5 April 2012
Line 102:		Line 102:
	==='''Cache Sizing'''===		==='''Cache Sizing'''===

	Increasing the dimensions of the cache greatly improves the performance of prefetching. This can be done either through increasing the cache size itself or increasing set associativity. A small cache size is a significant problem with prefetching because conflict misses increase dramatically. Any benefit you might derive from having fewer cache lookup misses is negated by this higher incidence of conflict miss. The following study assembled some benchmarks for a given SPARC processor that utilized prefetching. The following graph shows various levels of cache misses based on various cache sizes. With 16K and 32K cache sizes, prefetching reduces cache misses to fairly close to 0, which the number of misses without prefetching is rather high.		Increasing the dimensions of the cache greatly improves the performance of prefetching. This can be done either through increasing the cache size itself or increasing set associativity. A small cache size is a significant problem with prefetching because conflict misses increase dramatically. Any benefit you might derive from having fewer cache lookup misses is negated by this higher incidence of conflict miss. The following study assembled some benchmarks for a given SPARC(See [[#Definitions]]) processor that utilized prefetching. The following graph shows various levels of cache misses based on various cache sizes. With 16K and 32K cache sizes, prefetching reduces cache misses to fairly close to 0, which the number of misses without prefetching is rather high.

	For example, the following study of a BioInformatics application showed the effects of prefetching cache misses based on the size of the L1 cache. As can be seen, cache size has a major impact on the miss rate and, subsequently, performance in the system.<ref>http://www.nikolaylaptev.com/master/classes/cs254.pdf</ref>		For example, the following study of a BioInformatics application showed the effects of prefetching cache misses based on the size of the L1 cache. As can be seen, cache size has a major impact on the miss rate and, subsequently, performance in the system.<ref>http://www.nikolaylaptev.com/master/classes/cs254.pdf</ref>

Japlemmo: /* Prefetching Disadvantages */

2012-04-05T02:37:34Z

Prefetching Disadvantages

← Older revision		Revision as of 02:37, 5 April 2012
Line 94:		Line 94:
	Additional issues, for example, came about with the increasing popularity of multicore architectures. In a single core architecture, prefetching requests are able to originate simply from one core. With multiple cores, prefetching requests can originate from a variety of different cores. This puts additional stress on memory to not only deal with regular prefetch requests but also to handle prefetch from different sources, thus greatly increasing the overhead and complexity of logic. Additionally, coherence algorithms must account not only for typical sequential consistency issues, but also account for the possibility of data in yet another location, the location of prefetched data. Flushing data becomes significantly more complicated and cumbersome.		Additional issues, for example, came about with the increasing popularity of multicore architectures. In a single core architecture, prefetching requests are able to originate simply from one core. With multiple cores, prefetching requests can originate from a variety of different cores. This puts additional stress on memory to not only deal with regular prefetch requests but also to handle prefetch from different sources, thus greatly increasing the overhead and complexity of logic. Additionally, coherence algorithms must account not only for typical sequential consistency issues, but also account for the possibility of data in yet another location, the location of prefetched data. Flushing data becomes significantly more complicated and cumbersome.

	Lastly, and most importantly, is the following ongoing conflict: If prefetched data is stored in the data cache, then cache conflict (or cache pollution), can become a significant burden. This is because the current and predictive sets of data must exist in the cache at the same time. Without prefetching, you could use some of this additional space to simply increase the cache size itself. The solution here would be to add extra hardware to act as a buffer to prevent utilizing this cache space. This, however, requires extra hardware and utilizes precious CPU space at a time when cost pressures in the PC world were becoming more acute.		Lastly, and most importantly, is the following ongoing conflict: If prefetched data is stored in the data cache, then cache conflict (or cache pollution(See [[#Definitions]])), can become a significant burden. This is because the current and predictive sets of data must exist in the cache at the same time. Without prefetching, you could use some of this additional space to simply increase the cache size itself. The solution here would be to add extra hardware to act as a buffer to prevent utilizing this cache space. This, however, requires extra hardware and utilizes precious CPU space at a time when cost pressures in the PC world were becoming more acute.

	=='''Prefetching Improvements'''==		=='''Prefetching Improvements'''==

Japlemmo: /* Memory Pattern Recognition */

2012-04-05T02:35:55Z

Memory Pattern Recognition

← Older revision		Revision as of 02:35, 5 April 2012
Line 118:		Line 118:
	Effective memory pattern recognition algorithms can go a long way towards resolving issues with prefetching values unnecessarily (ie ones that might not be used in a sufficient timeframe). One example is the stride technique. For example, memory addresses that are sequential in nature, like an array, would all be brought in together as a unit since more than likely most or all of these elements will be utilized. This is an improvement over a more conservative prefetcher that may just assume memory located together will be used. The more conservative version has been known to have a much higher incidence of bringing in unnecessary blocks of data.		Effective memory pattern recognition algorithms can go a long way towards resolving issues with prefetching values unnecessarily (ie ones that might not be used in a sufficient timeframe). One example is the stride technique. For example, memory addresses that are sequential in nature, like an array, would all be brought in together as a unit since more than likely most or all of these elements will be utilized. This is an improvement over a more conservative prefetcher that may just assume memory located together will be used. The more conservative version has been known to have a much higher incidence of bringing in unnecessary blocks of data.

	Another variation of this is the linked memory reference pattern. Linked lists and tree structures are most often associated with this type. Generally, occurrences of code similar to ptr = ptr->next are considered as one structure and subsequently brought into memory together.<ref>http://www.bergs.com/stefan/general/papers/general.pdf</ref>		Another variation of this is the linked memory reference pattern. Linked lists(See [[#Definitions]]) and tree structures are most often associated with this type. Generally, occurrences of code similar to ptr = ptr->next are considered as one structure and subsequently brought into memory together.<ref>http://www.bergs.com/stefan/general/papers/general.pdf</ref>

	For example, instead of:		For example, instead of:

Japlemmo: /* Prefetching and Consistency Models */

2012-04-05T02:31:49Z

Prefetching and Consistency Models

← Older revision		Revision as of 02:31, 5 April 2012
Line 148:		Line 148:

	<references></references>		<references></references>

			=='''Definitions'''==

			1) ''''''

			2)

			3)

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

Japlemmo: /* References */

2012-04-05T02:24:41Z

References

← Older revision		Revision as of 02:24, 5 April 2012
Line 148:		Line 148:

	<references></references>		<references></references>

	~~12. https://lwn.net/Articles/252125/~~

	~~14. http://www.hpcaconf.org/hpca11/papers/20_x_spracklen-prefetching-revised.pdf~~

	~~15. http://ilab1.korea.ac.kr/papers/international_journal/Reducing%20cache%20conflicts%20in%20data%20cache%20prefetching.pdf~~

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

Japlemmo: /* References */

2012-04-05T02:24:00Z

References

← Older revision		Revision as of 02:24, 5 April 2012
Line 148:		Line 148:

	<references></references>		<references></references>

	~~10. http://www.multicoreinfo.com/prefetching-multicore-processors/~~

	12. https://lwn.net/Articles/252125/		12. https://lwn.net/Articles/252125/