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

Dkarpur: /* Prefetching */

2012-04-11T17:52:36Z

Prefetching

← Older revision		Revision as of 17:52, 11 April 2012
Line 67:		Line 67:
	[[File:PrefetchImp.png\|thumb\|right\|upright\|300px\|Figure 2.3. Prefetch Implementation]]		[[File:PrefetchImp.png\|thumb\|right\|upright\|300px\|Figure 2.3. Prefetch Implementation]]
	Prefetching the lowest miss address stream in the cache hierarchy has many advantages, particularly in a CMP system. First, in a CMP, the L2 cache is often shared by all processors on the chip. Consequently, prefetching the L2 miss address stream can share prefetch history among the processors, resulting in larger history tables. Second, prefetching L2 miss addresses reduces contention on the cache ports, which is becoming increasingly important as the number of processors per chip grows. Before a prefetch is sent to the memory subsystem, it must access the L2 directory. Since the L2 miss address stream has the fewest memory references it will generate less prefetches and access the cache ports less often. Last, prefetching into the L1 is relatively insignificant, since modern out-of-order processors can tolerate most L1 data cache misses with relatively little performance degradation. Prefetching in a CMP is more difficult than in a uniprocessor system. In addition to limited bandwidth and increased latency (as described earlier), cache coherency protocols play an important role in CMP prefetching.		Prefetching the lowest miss address stream in the cache hierarchy has many advantages, particularly in a CMP system. First, in a CMP, the L2 cache is often shared by all processors on the chip. Consequently, prefetching the L2 miss address stream can share prefetch history among the processors, resulting in larger history tables. Second, prefetching L2 miss addresses reduces contention on the cache ports, which is becoming increasingly important as the number of processors per chip grows. Before a prefetch is sent to the memory subsystem, it must access the L2 directory. Since the L2 miss address stream has the fewest memory references it will generate less prefetches and access the cache ports less often. Last, prefetching into the L1 is relatively insignificant, since modern out-of-order processors can tolerate most L1 data cache misses with relatively little performance degradation. Prefetching in a CMP is more difficult than in a uniprocessor system. In addition to limited bandwidth and increased latency (as described earlier), cache coherency protocols play an important role in CMP prefetching.

			==Disadvantages of Prefetching==

			1. Increased Complexity and overhead of handling the perfetching algorithms. Performance must be improved significantly to counterbalance this overhead and complexity or the efforts are not worthwhile.

			2. 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.

			3. If prefetched data is stored in the data cache, then cache conflict or cache pollution, can become a significant burden.

	= '''Consistency models''' <ref>http://titanium.cs.berkeley.edu/papers/kamil-su-yelick-sc05.pdf</ref> <ref>http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf</ref>=		= '''Consistency models''' <ref>http://titanium.cs.berkeley.edu/papers/kamil-su-yelick-sc05.pdf</ref> <ref>http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf</ref>=

Dkarpur: /* Conclusions ftp://ftp.cs.wisc.edu/markhill/Papers/icpp90_seqcon.pdf */

2012-04-11T17:45:32Z

Conclusions ftp://ftp.cs.wisc.edu/markhill/Papers/icpp90_seqcon.pdf

← Older revision		Revision as of 17:45, 11 April 2012
Line 231:		Line 231:

	= '''Conclusions''' <ref>ftp://ftp.cs.wisc.edu/markhill/Papers/icpp90_seqcon.pdf</ref>=		= '''Conclusions''' <ref>ftp://ftp.cs.wisc.edu/markhill/Papers/icpp90_seqcon.pdf</ref>=
			In this article all the different techniques for prefetching and its relation to sequential consistency have been discussed in terms of how they are able to support multiprocessors today. A decent effort has been made to discuss the relative weaknesses and strengths of different models. What we can conclude is that there is no one best model, only the model that best fits the application, architecture, and programmer. The choice is between a very strict consistency model such as SC and other relaxed consistency models. The sequential memory model is the easiest model to use for parallel computing.

			For an novice programmer who does not fully understand the problems inherent with memory consistency and cannot implement explicit mechanisms for synchronization, a sequentially consistent system may be the only possible model that will result in program correctness. There will be a significant penalty in performance, however, which could negate even the advantage of using a parallel system in the first place. Across a wide range of applications, the Relaxed Consistency models would average the best performance, but at greater programmer effort.

	A memory model for shared-memory multiprocessor systems most commonly assumed by programmers is that of sequential consistency. Strong ordering has been believed to be a sufﬁcient condition for implementing sequential consistency. As a necessary condition for a practical implementation of sequential consistency, it has been widely believed that a processor should not be allowed to issue an access until all effects of its previous access are observed.		A memory model for shared-memory multiprocessor systems most commonly assumed by programmers is that of sequential consistency. Strong ordering has been believed to be a sufﬁcient condition for implementing sequential consistency. As a necessary condition for a practical implementation of sequential consistency, it has been widely believed that a processor should not be allowed to issue an access until all effects of its previous access are observed.

Dkarpur: /* External links */

2012-04-11T16:33:13Z

External links

← Older revision		Revision as of 16:33, 11 April 2012
Line 271:		Line 271:
	7. [http://www.ee.ryerson.ca/~courses/ee8207/prefetchprj3.pdf Hardware Prefetching Schemes]		7. [http://www.ee.ryerson.ca/~courses/ee8207/prefetchprj3.pdf Hardware Prefetching Schemes]

	8. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.1422&rep=rep1&type=pdf ]		8. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.1422&rep=rep1&type=pdf Sequential Prefetching in Shared Memory Processors ]

	9. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.1229&rep=rep1&type=pdf ]		9. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.1229&rep=rep1&type=pdf Software Controlled prefetching in Shared Memory Processors]

	10. [http://www.cs.cmu.edu/~tcm/thesis/subsection2_10_3_2.html]		10. [http://www.cs.cmu.edu/~tcm/thesis/subsection2_10_3_2.html Relaxed consistency models]

	=References=		=References=
	<references/>		<references/>

Dkarpur: /* External links */

2012-04-11T16:30:42Z

External links

← Older revision		Revision as of 16:30, 11 April 2012
Line 270:		Line 270:

	7. [http://www.ee.ryerson.ca/~courses/ee8207/prefetchprj3.pdf Hardware Prefetching Schemes]		7. [http://www.ee.ryerson.ca/~courses/ee8207/prefetchprj3.pdf Hardware Prefetching Schemes]

			8. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.1422&rep=rep1&type=pdf ]

			9. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.1229&rep=rep1&type=pdf ]

			10. [http://www.cs.cmu.edu/~tcm/thesis/subsection2_10_3_2.html]

	=References=		=References=
	<references/>		<references/>

Dkarpur: /* Fixed Sequential Prefetchinghttp://www.springerlink.com/content/lu0755310187318n/ */

2012-04-11T16:22:51Z

Fixed Sequential Prefetchinghttp://www.springerlink.com/content/lu0755310187318n/

← Older revision		Revision as of 16:22, 11 April 2012
Line 25:		Line 25:

	==Fixed Sequential Prefetching<ref>http://www.springerlink.com/content/lu0755310187318n/</ref>==		==Fixed Sequential Prefetching<ref>http://www.springerlink.com/content/lu0755310187318n/</ref>==
	By fixed sequential prefetching we mean .that K consecutive blocks are prefetched into the SLC on a reference to a block, i.e., blocks n + 1 ... n + K are prefetched upon a reference to block n, if they are not present in the cache. Sequential prefetching has been extensively studied in the context of uniprocessors,but to our knowledge, have never been considered for general applications on multiprocessors. Although many sequential strategies have been proposed for uniprocessors, we have restricted ourselves to prefetching on a miss in the SLC. When a reference misses in the SLC, the miss request is sent to memory, and the cache is searched for the K consecutive blocks directly following the missing block in the address space. The blocks among the K consecutive blocks that are not present in the SLC and have no pending requests in the SLWB are prefetched. We refer to K as the degree of prefetching.		By fixed sequential prefetching we mean that K consecutive blocks are prefetched into the SLC on a reference to a block, i.e., blocks n + 1 ... n + K are prefetched upon a reference to block n, if they are not present in the cache. Sequential prefetching has been extensively studied in the context of uniprocessors,but to our knowledge, have never been considered for general applications on multiprocessors. Although many sequential strategies have been proposed for uniprocessors, we have restricted ourselves to prefetching on a miss in the SLC. When a reference misses in the SLC, the miss request is sent to memory, and the cache is searched for the K consecutive blocks directly following the missing block in the address space. The blocks among the K consecutive blocks that are not present in the SLC and have no pending requests in the SLWB are prefetched. We refer to K as the degree of prefetching.
	[[File:untitled1.png\|thumb\|center\|upright\|350px\|Figure 2.2. The fixed sequential prefetching mechanism]]		[[File:untitled1.png\|thumb\|center\|upright\|350px\|Figure 2.2. The fixed sequential prefetching mechanism]]

Rchakar: /* Sufficient Conditions for Preserving Sequential Consistency Parallel Computer Architecture: A Hardware/Software Approach. - David E. Culler, University of California, Berkeley; Jaswinder Pal Singh, Princeton University */

2012-04-11T15:56:30Z

Sufficient Conditions for Preserving Sequential Consistency Parallel Computer Architecture: A Hardware/Software Approach. - David E. Culler, University of California, Berkeley; Jaswinder Pal Singh, Princeton University

← Older revision		Revision as of 15:56, 11 April 2012
Line 133:		Line 133:
	Of course, an implicit assumption throughout is that a read returns the last value that was written to that same location (by any process) in the interleaved total order.		Of course, an implicit assumption throughout is that a read returns the last value that was written to that same location (by any process) in the interleaved total order.

	===''Sufficient Conditions for Preserving Sequential Consistency ''~~<ref>Parallel Computer Architecture: A Hardware/Software Approach. - David E. Culler, University of California, Berkeley; Jaswinder Pal Singh, Princeton University</ref>~~===		===''Sufficient Conditions for Preserving Sequential Consistency ''===

	It is possible to define a set of sufficient conditions that the system should obey that will guarantee		It is possible to define a set of sufficient conditions that the system should obey that will guarantee

Rchakar: /* Prefetching under Consistency Modelshttp://www.csl.cornell.edu/courses/ee572/gharachorloo.icpp91.pdf */

2012-04-11T15:29:47Z

Prefetching under Consistency Modelshttp://www.csl.cornell.edu/courses/ee572/gharachorloo.icpp91.pdf

← Older revision		Revision as of 15:29, 11 April 2012
Line 223:		Line 223:
	Let us first consider the code segment in example 4.1. This code segment resembles a producer process updating the values of two memory locations. Given a system with sequential consistency, each access is delayed for the previous access to be performed. The first three accesses miss in the cache, while the unlock access hits due to the fact that exclusive ownership was gained by the previous lock access. Therefore, the four accesses take a total of 301 cycles to perform. In a system with release consistency, the write accesses are delayed until the lock access is performed, and the unlock access is delayed for the write accesses to perform. However, the write accesses are pipelined. Therefore, the accesses take 202 cycles.		Let us first consider the code segment in example 4.1. This code segment resembles a producer process updating the values of two memory locations. Given a system with sequential consistency, each access is delayed for the previous access to be performed. The first three accesses miss in the cache, while the unlock access hits due to the fact that exclusive ownership was gained by the previous lock access. Therefore, the four accesses take a total of 301 cycles to perform. In a system with release consistency, the write accesses are delayed until the lock access is performed, and the unlock access is delayed for the write accesses to perform. However, the write accesses are pipelined. Therefore, the accesses take 202 cycles.

	The prefetch technique described in this section boosts the performance of both the sequential and release consistent systems. Concerning the loop that would be used to implement the lock synchronization, we assume the branch predictor takes the path that assumes the lock synchronization succeeds. Thus, the lookahead into the instruction stream allows locations A and B to be prefetched in read-exclusive mode. Regardless of the consistency model, the lock access is serviced in parallel with prefetch for the two write accesses. Once the result for the lock access returns, the two write accesses will be satisfied quickly since the locations are prefetched into the cache. Therefore, with prefetching, the accesses complete in 103 cycles for both SC and RC. For this example, prefetching boosts the performance of both SC and RC and also equalizes the performance of the two models.
			The prefetch technique described in this section boosts the performance of both the sequential and release consistent systems. Concerning the loop that would be used to implement the lock synchronization, we assume the branch predictor takes the path that assumes the lock synchronization succeeds. Thus, the lookahead into the instruction stream allows locations A and B to be prefetched in read-exclusive mode. Regardless of the consistency model, the lock access is serviced in parallel with prefetch for the two write accesses. Once the result for the lock access returns, the two write accesses will be satisfied quickly since the locations are prefetched into the cache. Therefore, with prefetching, the accesses complete in 103 cycles for both SC and RC. For this example, prefetching boosts the performance of both SC and RC
			and also equalizes the performance of the two models.


	We now consider the second code segment in example 4.2. This code segment resembles a consumer process reading several memory locations. There are three read accesses within the critical section. As shown, the read to location D is assumed to hit in the cache, and the read of array E depends on the value of D to access the appropriate element. For simplicity, we will ignore the delay due to address calculation for accessing the array element. Under SC, the accesses take 302 cycles to perform. Under RC, they take 203 cycles. With the prefetch technique, the accesses take 203 cycles under SC and 202 cycles under RC. Although the performance of both SC and RC are enhanced by prefetching, the maximum performance is not achieved for either model. The reason is simply because the address of the read access to array E depends on the value of D and although the read access to D is a cache hit, this access is not allowed to perform (i.e., the value can not be used by the processor) until the read of C completes (under SC) or until the lock access completes (under RC). Thus, while prefetching can boost performance by pipelining several accesses that are delayed due to consistency constraints, it fails to remedy the cases where out-of-order consumption of return values is important to allow the processor to proceed efficiently.		We now consider the second code segment in example 4.2. This code segment resembles a consumer process reading several memory locations. There are three read accesses within the critical section. As shown, the read to location D is assumed to hit in the cache, and the read of array E depends on the value of D to access the appropriate element. For simplicity, we will ignore the delay due to address calculation for accessing the array element. Under SC, the accesses take 302 cycles to perform. Under RC, they take 203 cycles. With the prefetch technique, the accesses take 203 cycles under SC and 202 cycles under RC. Although the performance of both SC and RC are enhanced by prefetching, the maximum performance is not achieved for either model. The reason is simply because the address of the read access to array E depends on the value of D and although the read access to D is a cache hit, this access is not allowed to perform (i.e., the value can not be used by the processor) until the read of C completes (under SC) or until the lock access completes (under RC). Thus, while prefetching can boost performance by pipelining several accesses that are delayed due to consistency constraints, it fails to remedy the cases where out-of-order consumption of return values is important to allow the processor to proceed efficiently.

Rchakar: /* Prefetching under Consistency Models */

2012-04-11T14:51:28Z

Prefetching under Consistency Models

← Older revision		Revision as of 14:51, 11 April 2012
Line 199:		Line 199:


	='''Prefetching under Consistency Models'''=		='''Prefetching under Consistency Models'''<ref>http://www.csl.cornell.edu/courses/ee572/gharachorloo.icpp91.pdf</ref>=

	In the hardware prefetching technique, hardware issues prefetches for any memory operations that are in the reorder buffer but are not yet permitted by the consistency model to actually issue to the memory system.		In the hardware prefetching technique, hardware issues prefetches for any memory operations that are in the reorder buffer but are not yet permitted by the consistency model to actually issue to the memory system.

Rchakar: /* Prefetching under Consistency Models */

2012-04-11T14:50:34Z

Prefetching under Consistency Models

← Older revision		Revision as of 14:50, 11 April 2012
Line 209:		Line 209:
	Example 4.1:		Example 4.1:
	lock L (miss)		lock L (miss)
	write A (miss)		write A (miss)
	write B (miss)		write B (miss)
	unlock L (hit)		unlock L (hit)

	Example 4.2:		Example 4.2:
Line 217:		Line 217:
	read C (miss)		read C (miss)
	read D (hit)		read D (hit)
	read E[D] (miss)		read E[D] (miss)
	unlock L (hit)		unlock L (hit)

Rchakar: /* Prefetching under Consistency Models */

2012-04-11T14:49:18Z

Prefetching under Consistency Models

← Older revision		Revision as of 14:49, 11 April 2012
Line 208:		Line 208:

	Example 4.1:		Example 4.1:
	lock L (miss)		lock L (miss)
	write A (miss)		write A (miss)
	write B (miss)		write B (miss)
	unlock L (hit)		unlock L (hit)

	Example 4.2:		Example 4.2:
	lock L (miss)		lock L (miss)
	read C (miss)		read C (miss)
	read D (hit)		read D (hit)
	read E[D] (miss)		read E[D] (miss)
	unlock L (hit)		unlock L (hit)