CSC/ECE 506 Spring 2012/6b pa - Revision history

Pasokan: /* See More */

2012-03-06T03:43:24Z

← Older revision		Revision as of 03:43, 6 March 2012
Line 348:		Line 348:

	7.Fundamentals of Parallel Computer Architecture by Yan Sohilin Chapter 3:Shared memory parallel programming		7.Fundamentals of Parallel Computer Architecture by Yan Sohilin Chapter 3:Shared memory parallel programming

			8.Multiprocessor Cache Coherence: http://www.divms.uiowa.edu/~ghosh/4-20-06.pdf

Pasokan: /* Write Buffer Implementations */

2012-03-06T03:36:25Z

Write Buffer Implementations

← Older revision		Revision as of 03:36, 6 March 2012
Line 198:		Line 198:
	[[Image:univrw1.png\|frame\|Figure 7: Shared memory with Universal Read/Write Buffers<ref name = "univrw"/>]]		[[Image:univrw1.png\|frame\|Figure 7: Shared memory with Universal Read/Write Buffers<ref name = "univrw"/>]]

	In multiprocessors with shared memory, if each processor has an individual write buffer to handle pending writes to the memory, it become complex to handle the memory operations in case of reads that require the data written by other processors. In such a case, the memory controller will have to incorporate snoopy mechanisms to figure which processor buffer has the latest data for the corresponding read address. To avoid these complications and to increase flexibility in design, the idea of a universal read/write buffer serves the purpose. It ensures that a FIFO order is maintained among the memory operations of all processors. The universal read/write buffer can also support multiprocessor cache coherence of different protocols. The interconnection network in shared memory multiprocessor systems leads to serialization of memory requests. It also needs to deal with communication contention to individual links in the network. Implementing various cache protocols such as the MSI, MESI & MOESI in multiprocessor systems allow coherency among the various caches and also help in reducing the bus traffic thereby improving performance of these systems.~~(link to these explanations)~~.		In multiprocessors with shared memory, if each processor has an individual write buffer to handle pending writes to the memory, it become complex to handle the memory operations in case of reads that require the data written by other processors. In such a case, the memory controller will have to incorporate snoopy mechanisms to figure which processor buffer has the latest data for the corresponding read address. To avoid these complications and to increase flexibility in design, the idea of a universal read/write buffer serves the purpose. It ensures that a FIFO order is maintained among the memory operations of all processors. The universal read/write buffer can also support multiprocessor cache coherence of different protocols. The interconnection network in shared memory multiprocessor systems leads to serialization of memory requests. It also needs to deal with communication contention to individual links in the network. Implementing various cache protocols such as the MSI, MESI & MOESI in multiprocessor systems allow coherency among the various caches and also help in reducing the bus traffic thereby improving performance of these systems.<ref>http://en.wikipedia.org/wiki/MOESI_protocol</ref>
	The various states are explained as follows:		The various states are explained as follows:

Pasokan: /* Execution Time */

2012-03-06T03:35:33Z

Execution Time

← Older revision		Revision as of 03:35, 6 March 2012
Line 120:		Line 120:
	====Execution Time====		====Execution Time====

	In parallelization, the instructions are split into epochs to allow synchronization between epochs. DOALL <ref>http://www-hydra.stanford.edu/publications/shspec.pdf<ref/>loops are considered parallel epochs and serial code between DOALL loops are called sequential epochs as they have to be performed by one processor. After each epoch, a cache or buffer flush is required to update memory. A cache flush is required for writeback caches and a buffer flush is required for write-through caches with writebuffers.When a flush occurs, much of the content is invalid or has been unmodified. It takes various time to check/invalidate these lines causing differences in execution time.		In parallelization, the instructions are split into epochs to allow synchronization between epochs. DOALL <ref>http://www-hydra.stanford.edu/publications/shspec.pdf</ref>loops are considered parallel epochs and serial code between DOALL loops are called sequential epochs as they have to be performed by one processor. After each epoch, a cache or buffer flush is required to update memory. A cache flush is required for writeback caches and a buffer flush is required for write-through caches with writebuffers.When a flush occurs, much of the content is invalid or has been unmodified. It takes various time to check/invalidate these lines causing differences in execution time.

	Figure 4 shows execution times in relation to WTNB. Notice there is a WB(1) and WB here. WB(1) takes 1 cycle to check/invalidate a line while WB takes no time (or 0 cycles) to do so. WB and WB(1) have higher execution times because of the need for a cache flush. WTNB and WTB are slowed down for slow access systems because of an increased number of memory stalls. Again, WTAWB outperforms the other strategies because of not facing much degradation from a buffer flush due to its smaller buffer size.		Figure 4 shows execution times in relation to WTNB. Notice there is a WB(1) and WB here. WB(1) takes 1 cycle to check/invalidate a line while WB takes no time (or 0 cycles) to do so. WB and WB(1) have higher execution times because of the need for a cache flush. WTNB and WTB are slowed down for slow access systems because of an increased number of memory stalls. Again, WTAWB outperforms the other strategies because of not facing much degradation from a buffer flush due to its smaller buffer size.

Pasokan: /* Comparing Different Cache-Buffering systems */

2012-03-06T03:35:06Z

Comparing Different Cache-Buffering systems

← Older revision		Revision as of 03:35, 6 March 2012
Line 120:		Line 120:
	====Execution Time====		====Execution Time====

	In parallelization, the instructions are split into epochs to allow synchronization between epochs. DOALL loops are considered parallel epochs and serial code between DOALL loops are called sequential epochs as they have to be performed by one processor. After each epoch, a cache or buffer flush is required to update memory. A cache flush is required for writeback caches and a buffer flush is required for write-through caches with writebuffers.When a flush occurs, much of the content is invalid or has been unmodified. It takes various time to check/invalidate these lines causing differences in execution time.		In parallelization, the instructions are split into epochs to allow synchronization between epochs. DOALL <ref>http://www-hydra.stanford.edu/publications/shspec.pdf<ref/>loops are considered parallel epochs and serial code between DOALL loops are called sequential epochs as they have to be performed by one processor. After each epoch, a cache or buffer flush is required to update memory. A cache flush is required for writeback caches and a buffer flush is required for write-through caches with writebuffers.When a flush occurs, much of the content is invalid or has been unmodified. It takes various time to check/invalidate these lines causing differences in execution time.

	Figure 4 shows execution times in relation to WTNB. Notice there is a WB(1) and WB here. WB(1) takes 1 cycle to check/invalidate a line while WB takes no time (or 0 cycles) to do so. WB and WB(1) have higher execution times because of the need for a cache flush. WTNB and WTB are slowed down for slow access systems because of an increased number of memory stalls. Again, WTAWB outperforms the other strategies because of not facing much degradation from a buffer flush due to its smaller buffer size.		Figure 4 shows execution times in relation to WTNB. Notice there is a WB(1) and WB here. WB(1) takes 1 cycle to check/invalidate a line while WB takes no time (or 0 cycles) to do so. WB and WB(1) have higher execution times because of the need for a cache flush. WTNB and WTB are slowed down for slow access systems because of an increased number of memory stalls. Again, WTAWB outperforms the other strategies because of not facing much degradation from a buffer flush due to its smaller buffer size.

Pasokan at 03:33, 6 March 2012

2012-03-06T03:33:09Z

← Older revision		Revision as of 03:33, 6 March 2012
Line 42:		Line 42:

	=====Write Policies for Write buffers=====		=====Write Policies for Write buffers=====
	A conventional write buffer generally used for a write through cache has a FIFO organization that captures the writes as long as the buffer has space and drains them whenever the interconnection network is available in the background. Full buffers stall the processor in such scenarios. Here we can explore an enhancement to the write buffer design namely a write back write buffer[].This buffer simulates the write buffer like a second level cache for writes.		A conventional write buffer generally used for a write through cache has a FIFO organization that captures the writes as long as the buffer has space and drains them whenever the interconnection network is available in the background. Full buffers stall the processor in such scenarios. Here we can explore an enhancement to the write buffer design namely a write back write buffer<ref name="wrpol">http://ieeexplore.ieee.org.prox.lib.ncsu.edu/stamp/stamp.jsp?tp=&arnumber=236636&tag=1</ref>.This buffer simulates the write buffer like a second level cache for writes.
	The write back write buffer is useful in a scenario when there are subsequent writes to the same address. This write buffer checks the write address with its own tag store and in case of a match,stores the data in the corresponding line. Otherwise, it either allocates a new line or if the buffer is full,replace a line.Thus actual write occur only in the case of replacement lines.		The write back write buffer is useful in a scenario when there are subsequent writes to the same address. This write buffer checks the write address with its own tag store and in case of a match,stores the data in the corresponding line. Otherwise, it either allocates a new line or if the buffer is full,replace a line.Thus actual write occur only in the case of replacement lines.

Line 49:		Line 49:
	==Software Coherency through Write Policies==		==Software Coherency through Write Policies==

	===Write-Through<ref name="toussi">http://en.wikipedia.org/wiki/Cache_(computing)~~</ref><ref name="wrpol">http://ieeexplore.ieee.org.prox.lib.ncsu.edu/stamp/stamp.jsp?tp=&arnumber=236636&tag=1~~</ref>===		===Write-Through<ref name="wrpol"/><ref name="toussi">http://en.wikipedia.org/wiki/Cache_(computing)</ref>===
	{\|class="wikitable1" style="float: right;"		{\|class="wikitable1" style="float: right;"
	\|-		\|-
Line 57:		Line 57:
	In a write-through cache, the memory is updated as the cache is updated with a write. This type of update allows invalidation of cache lines to be done with no stalls because the memory already has all the updated values. However, this causes more traffic because memory is being updated every time there is a change.		In a write-through cache, the memory is updated as the cache is updated with a write. This type of update allows invalidation of cache lines to be done with no stalls because the memory already has all the updated values. However, this causes more traffic because memory is being updated every time there is a change.

	===Writeback<ref name="~~toussi~~"/><ref name="~~wrpol~~"/>===		===Writeback<ref name="wrpol"/><ref name="toussi"/>===
	In a writeback, the cache is updated with a write but memory is not. Because of this, memory can contain stale values. When a block is being replace in the cache, the memory will be updated accordingly. This policy causes more stalls than write-through policy above. When an invalidation needs to occur, the memory might not have the most up to date values. Thus, a ''cache flush'' operation occurs in which every line in the cache is updated to memory. Writeback has more traffic during invalidation than write-through. Also, the processor whose cache has the latest value needs to be tracked. This is an additional overhead that write-through does not have.		In a writeback, the cache is updated with a write but memory is not. Because of this, memory can contain stale values. When a block is being replace in the cache, the memory will be updated accordingly. This policy causes more stalls than write-through policy above. When an invalidation needs to occur, the memory might not have the most up to date values. Thus, a ''cache flush'' operation occurs in which every line in the cache is updated to memory. Writeback has more traffic during invalidation than write-through. Also, the processor whose cache has the latest value needs to be tracked. This is an additional overhead that write-through does not have.

Aupreti: /* See More */

2012-03-06T03:29:59Z

← Older revision		Revision as of 03:29, 6 March 2012
Line 346:		Line 346:

	6.Cache coherence : https://parasol.tamu.edu/~rwerger/Courses/654/cachecoherence1.pdf		6.Cache coherence : https://parasol.tamu.edu/~rwerger/Courses/654/cachecoherence1.pdf

			7.Fundamentals of Parallel Computer Architecture by Yan Sohilin Chapter 3:Shared memory parallel programming

Pasokan: /* Comparing Different Cache-Buffering systems */

2012-03-06T03:29:35Z

Comparing Different Cache-Buffering systems

← Older revision		Revision as of 03:29, 6 March 2012
Line 93:		Line 93:

	<u>Write-Through with Buffering</u>(WTB): a write-through cache with no-allocate policy with a FIFO queue write buffer		<u>Write-Through with Buffering</u>(WTB): a write-through cache with no-allocate policy with a FIFO queue write buffer
	[[Image:benchmarks.png\|frame\|Table 1: Benchmarks used for comparison]]		[[Image:benchmarks.png\|frame\|Table 1: Benchmarks used for comparison<ref name="wrpol"/>]]
	<u>Write-Through with WriteBack Write Buffer</u>(WTWB): a write through cache with no-allocate policy with a writeback write buffer		<u>Write-Through with WriteBack Write Buffer</u>(WTWB): a write through cache with no-allocate policy with a writeback write buffer

Pasokan: /* Software Coherency through Write Policies */

2012-03-06T03:28:28Z

Software Coherency through Write Policies

← Older revision		Revision as of 03:28, 6 March 2012
Line 49:		Line 49:
	==Software Coherency through Write Policies==		==Software Coherency through Write Policies==

	===Write-Through<ref name="toussi">http://en.wikipedia.org/wiki/Cache_(computing)</ref>===		===Write-Through<ref name="toussi">http://en.wikipedia.org/wiki/Cache_(computing)</ref><ref name="wrpol">http://ieeexplore.ieee.org.prox.lib.ncsu.edu/stamp/stamp.jsp?tp=&arnumber=236636&tag=1</ref>===
	{\|class="wikitable1" style="float: right;"		{\|class="wikitable1" style="float: right;"
	\|-		\|-
Line 57:		Line 57:
	In a write-through cache, the memory is updated as the cache is updated with a write. This type of update allows invalidation of cache lines to be done with no stalls because the memory already has all the updated values. However, this causes more traffic because memory is being updated every time there is a change.		In a write-through cache, the memory is updated as the cache is updated with a write. This type of update allows invalidation of cache lines to be done with no stalls because the memory already has all the updated values. However, this causes more traffic because memory is being updated every time there is a change.

	===Writeback<ref name="toussi"/>===		===Writeback<ref name="toussi"/><ref name="wrpol"/>===
	In a writeback, the cache is updated with a write but memory is not. Because of this, memory can contain stale values. When a block is being replace in the cache, the memory will be updated accordingly. This policy causes more stalls than write-through policy above. When an invalidation needs to occur, the memory might not have the most up to date values. Thus, a ''cache flush'' operation occurs in which every line in the cache is updated to memory. Writeback has more traffic during invalidation than write-through. Also, the processor whose cache has the latest value needs to be tracked. This is an additional overhead that write-through does not have.		In a writeback, the cache is updated with a write but memory is not. Because of this, memory can contain stale values. When a block is being replace in the cache, the memory will be updated accordingly. This policy causes more stalls than write-through policy above. When an invalidation needs to occur, the memory might not have the most up to date values. Thus, a ''cache flush'' operation occurs in which every line in the cache is updated to memory. Writeback has more traffic during invalidation than write-through. Also, the processor whose cache has the latest value needs to be tracked. This is an additional overhead that write-through does not have.

Line 69:		Line 69:

	===Implementation with Write Buffer===		===Implementation with Write Buffer===
	====Write-Through Cache====		====Write-Through Cache<ref name="wrpol"/>====
	With a write-through cache, the write buffer will hold several lines to be updated into memory allowing the processor to continue without having to wait for the writes to complete.		With a write-through cache, the write buffer will hold several lines to be updated into memory allowing the processor to continue without having to wait for the writes to complete.

Line 76:		Line 76:
	#Another method is for the write buffer to be a small write-back cache. It will act as a cache in that when a write occurs, it will check the address tag. If the tag matches, the data is put in that tag's line and a modified flag bit will be set high. If there is not tag match, a new line will be allocated or an old line will be replaced. The old line that is to be replaced will be updated to memory first. Memory will also be updated in the case of a buffer flush. This design is called ''writeback write buffer''.		#Another method is for the write buffer to be a small write-back cache. It will act as a cache in that when a write occurs, it will check the address tag. If the tag matches, the data is put in that tag's line and a modified flag bit will be set high. If there is not tag match, a new line will be allocated or an old line will be replaced. The old line that is to be replaced will be updated to memory first. Memory will also be updated in the case of a buffer flush. This design is called ''writeback write buffer''.

	=====Writeback Write Buffer=====		=====Writeback Write Buffer<ref name="wrpol"/>=====
	''The writeback write buffer actually reduces the stalls and traffic faced by a multiprocessors compared to a uniprocessor. The FIFO queue style write buffer has the same amount of write traffic as a uniprocessor and thus does not have control to prevent stalls in the case of memory being slow. Writeback write buffer is also easier to implement than the FIFO queue style.''		''The writeback write buffer actually reduces the stalls and traffic faced by a multiprocessors compared to a uniprocessor. The FIFO queue style write buffer has the same amount of write traffic as a uniprocessor and thus does not have control to prevent stalls in the case of memory being slow. Writeback write buffer is also easier to implement than the FIFO queue style.''

Line 88:		Line 88:


	===Comparing Different Cache-Buffering systems===		===Comparing Different Cache-Buffering systems<ref name="wrpol"/>===

	<u>Write-Through with No Buffering</u> (WTNB): a write through cache with no-allocate policy with no write buffer		<u>Write-Through with No Buffering</u> (WTNB): a write through cache with no-allocate policy with no write buffer
Line 104:		Line 104:

	====Hit Ratios====		====Hit Ratios====
	[[Image:hitratio.png\|frame\|Table 2: Hit Ratio Comparison]]		[[Image:hitratio.png\|frame\|Table 2: Hit Ratio Comparison<ref name="wrpol"/>]]
	The cache hit ratio does not depend on whether the cache is write-through or write back. This is because these policies don't affect what data is in the cache, they affect when the data is written to memory. However, whether a cache is write-allocate or no-allocate affects the hit ratio.		The cache hit ratio does not depend on whether the cache is write-through or write back. This is because these policies don't affect what data is in the cache, they affect when the data is written to memory. However, whether a cache is write-allocate or no-allocate affects the hit ratio.

	Of the 5 configurations mentioned above, WTAWB and WB have a write-allocate policy. WTNB, WTB, and WTWB have a no-allocate policy. The use of a write-allocate policy increases the write and read hit ratios. The increase in write hit ratios benefits the writeback caches because it signifies it reduces the need to fetch data from memory because of misses. Increase in read hit benefits both writeback and write-through caches. It did not make a difference whether the caches used a fetch or no fetch policy. The fetch policy only makes a difference if a write miss is followed by a read to that same line. This does not occur often and thus did not make much of a difference. Table 2 shows the difference in hit ratios for write-allocate and no-allocate policies.		Of the 5 configurations mentioned above, WTAWB and WB have a write-allocate policy. WTNB, WTB, and WTWB have a no-allocate policy. The use of a write-allocate policy increases the write and read hit ratios. The increase in write hit ratios benefits the writeback caches because it signifies it reduces the need to fetch data from memory because of misses. Increase in read hit benefits both writeback and write-through caches. It did not make a difference whether the caches used a fetch or no fetch policy. The fetch policy only makes a difference if a write miss is followed by a read to that same line. This does not occur often and thus did not make much of a difference. Table 2 shows the difference in hit ratios for write-allocate and no-allocate policies.
	[[Image:memlat.png\|thumb\|600px\|Figure 3. Memory Latency Comparison: (left) Fast Access System , (right) Slow Access System]]		[[Image:memlat.png\|thumb\|600px\|Figure 3. Memory Latency Comparison: (left) Fast Access System , (right) Slow Access System<ref name="wrpol"/>]]

	====Memory Latency====		====Memory Latency====
Line 116:		Line 116:

	Slow Access System: The results are similar for most configurations. However, WTB has a much higher latency now due to increase in stalls from the slow access system. Still, WTAWB outperforms the other configurations as shown again in Figure 3.		Slow Access System: The results are similar for most configurations. However, WTB has a much higher latency now due to increase in stalls from the slow access system. Still, WTAWB outperforms the other configurations as shown again in Figure 3.
	[[Image:exec.png\|thumb\|600px\|Figure 4. Execution Time Comparison: (left) Fast Access System , (right) Slow Access System]]		[[Image:exec.png\|thumb\|600px\|Figure 4. Execution Time Comparison: (left) Fast Access System , (right) Slow Access System<ref name="wrpol"/>]]

	====Execution Time====		====Execution Time====

Pasokan: /* Software Coherency through Write Policies */

2012-03-06T03:25:14Z

Software Coherency through Write Policies

← Older revision		Revision as of 03:25, 6 March 2012
Line 49:		Line 49:
	==Software Coherency through Write Policies==		==Software Coherency through Write Policies==

	===Write-Through===		===Write-Through<ref name="toussi">http://en.wikipedia.org/wiki/Cache_(computing)</ref>===
	{\|class="wikitable1" style="float: right;"		{\|class="wikitable1" style="float: right;"
	\|-		\|-
Line 57:		Line 57:
	In a write-through cache, the memory is updated as the cache is updated with a write. This type of update allows invalidation of cache lines to be done with no stalls because the memory already has all the updated values. However, this causes more traffic because memory is being updated every time there is a change.		In a write-through cache, the memory is updated as the cache is updated with a write. This type of update allows invalidation of cache lines to be done with no stalls because the memory already has all the updated values. However, this causes more traffic because memory is being updated every time there is a change.

	===Writeback===		===Writeback<ref name="toussi"/>===
	In a writeback, the cache is updated with a write but memory is not. Because of this, memory can contain stale values. When a block is being replace in the cache, the memory will be updated accordingly. This policy causes more stalls than write-through policy above. When an invalidation needs to occur, the memory might not have the most up to date values. Thus, a ''cache flush'' operation occurs in which every line in the cache is updated to memory. Writeback has more traffic during invalidation than write-through. Also, the processor whose cache has the latest value needs to be tracked. This is an additional overhead that write-through does not have.		In a writeback, the cache is updated with a write but memory is not. Because of this, memory can contain stale values. When a block is being replace in the cache, the memory will be updated accordingly. This policy causes more stalls than write-through policy above. When an invalidation needs to occur, the memory might not have the most up to date values. Thus, a ''cache flush'' operation occurs in which every line in the cache is updated to memory. Writeback has more traffic during invalidation than write-through. Also, the processor whose cache has the latest value needs to be tracked. This is an additional overhead that write-through does not have.

Pasokan: /* Partial Block Invalidation Coherence Mechanismhttp://en.wikipedia.org/wiki/Cache_(computing) */

2012-03-06T03:24:45Z

Partial Block Invalidation Coherence Mechanismhttp://en.wikipedia.org/wiki/Cache_(computing)

← Older revision		Revision as of 03:24, 6 March 2012
Line 302:		Line 302:
	There are three types of executions studied: SC, TSO, RMO. SC and RMO are two extremes. TSO is what is most applicable to our study. The figure shows that when we add a SSB to a TSO execution, all capacity stalls are eliminated and we get results similar to that of an RMO.		There are three types of executions studied: SC, TSO, RMO. SC and RMO are two extremes. TSO is what is most applicable to our study. The figure shows that when we add a SSB to a TSO execution, all capacity stalls are eliminated and we get results similar to that of an RMO.

	===Partial Block Invalidation Coherence Mechanism<ref name="toussi"~~>http:~~/~~/en.wikipedia.org/wiki/Cache_(computing)</ref~~>===		===Partial Block Invalidation Coherence Mechanism<ref name="toussi"/>===

	====Partially valid write-back mechanism====		====Partially valid write-back mechanism====