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

Vmarapa: /* Quiz */

2012-04-25T03:32:24Z

Quiz

← Older revision		Revision as of 03:32, 25 April 2012
Line 224:		Line 224:
	2) Which of the following are types of prefetching?		2) Which of the following are types of prefetching?

	a) Sequential.		a) Sequential.
	b) Binding.		b) Binding.
	c) Non-binding.		c) Non-binding.
	d) Release.		d) Release.

	3) What effect does prefetching have on speed of execution?		3) What effect does prefetching have on speed of execution?

	a) Speeds up.		a) Speeds up.
	b) Does not have any effect.		b) Does not have any effect.
	c) Degrades performance.		c) Degrades performance.
	d) Does not speed up always.		d) Does not speed up always.

	4) Which of the following perform better than prefetching under SC?		4) Which of the following perform better than prefetching under SC?

	a) Prefetching with Release Consistency.		a) Prefetching with Release Consistency.
	b) Prefetching with Weak Ordering.		b) Prefetching with Weak Ordering.
	c) Speculative Execution.		c) Speculative Execution.
	d) All of the above give more or less the same performance as prefetching under SC.		d) All of the above give more or less the same performance as prefetching under SC.

	5) Which of the following are true about prefetching?		5) Which of the following are true about prefetching?

	a) The amount of lookahead we do for a prefetch needs to be controlled.		a) The amount of lookahead we do for a prefetch needs to be controlled.
	b) Prefetching in most cases boosts performance.		b) Prefetching in most cases boosts performance.
	c) Prefetching scales considerably well with increasing program size.		c) Prefetching scales considerably well with increasing program size.
	d) None of the above are true.		d) None of the above are true.

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

Vmarapa: /* Quiz */

2012-04-25T03:31:31Z

Quiz

← Older revision		Revision as of 03:31, 25 April 2012
Line 217:		Line 217:
	1) How does SC with prefetching perform?		1) How does SC with prefetching perform?

	a) Very bad.		a) Very bad.
	b) Good for some cases and bad for other cases.		b) Good for some cases and bad for other cases.
	c) Can be adopted widely, has good performance.		c) Can be adopted widely, has good performance.
	d) There are better alternatives available.		d) There are better alternatives available.

	2) Which of the following are types of prefetching?		2) Which of the following are types of prefetching?

Vmarapa: /* Glossary */

2012-04-25T03:30:48Z

Glossary

@@ Line 211: / Line 211: @@
 '''GPU:''' Like the CPU, GPU is a single-chip processor. However, the GPU is used primarily for computing 3D functions.
 == References ==
 <references />

Vmarapa: /* Glossary */

2012-04-25T03:16:05Z

Glossary

← Older revision		Revision as of 03:16, 25 April 2012
Line 200:		Line 200:
	== Glossary ==		== Glossary ==

	Prefetching: In computer architecture, instruction prefetch is a technique used in microprocessors to speed up the execution of a program by reducing wait states. Modern microprocessors are much faster than the memory where the program is kept, meaning that the program's instructions cannot be read fast enough to keep the microprocessor busy. Adding a cache can provide faster access to needed instructions.		'''Prefetching:''' In computer architecture, instruction prefetch is a technique used in microprocessors to speed up the execution of a program by reducing wait states. Modern microprocessors are much faster than the memory where the program is kept, meaning that the program's instructions cannot be read fast enough to keep the microprocessor busy. Adding a cache can provide faster access to needed instructions.

	Branch prediction: In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors are crucial in today's pipelined microprocessors for achieving high performance.		'''Branch prediction:''' In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors are crucial in today's pipelined microprocessors for achieving high performance.

	Speculative execution: Speculative execution in computer systems is doing work, the result of which may not be needed. This performance optimization technique is used in pipelined processors and other systems.		'''Speculative execution:''' Speculative execution in computer systems is doing work, the result of which may not be needed. This performance optimization technique is used in pipelined processors and other systems.

	Pipeline processing: Pipeline processing incorporates the functions of a computer's central processing unit (CPU) on a single integrated circuit, (IC) or at most a few integrated circuits.		'''Pipeline processing:''' Pipeline processing incorporates the functions of a computer's central processing unit (CPU) on a single integrated circuit, (IC) or at most a few integrated circuits.

	Store buffer: The cache controller includes a store buffer to hold data before it is written to the cache		'''Store buffer:''' The cache controller includes a store buffer to hold data before it is written to the cache

	GPU: Like the CPU, GPU is a single-chip processor. However, the GPU is used primarily for computing 3D functions.		'''GPU:''' Like the CPU, GPU is a single-chip processor. However, the GPU is used primarily for computing 3D functions.

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

Vmarapa: /* Glossary */

2012-04-25T03:14:38Z

Glossary

@@ Line 199: / Line 199: @@
 == Glossary ==
 == References ==
 <references />

Vmarapa: /* Illustrative example */

2012-04-25T02:49:45Z

Illustrative example

← Older revision		Revision as of 02:49, 25 April 2012
Line 185:		Line 185:
	[[File:SE_example.png\|600px\|Organization of a load store functional unit]]		[[File:SE_example.png\|600px\|Organization of a load store functional unit]]

	In the above figure, the contents of various buffers are showed along with the cache content for each event that occurs. All three mechanisms which we have discussed will be traced in the example. The [http://en.wikipedia.org/wiki/Instruction_prefetch prefetching reorder] buffer holds the instructions that are fetched and decoded. Tracing through the set of events, initially the loads and prefetches (exclusive mode) are issued for the corresponding stores. In the meantime, while the store buffer is working on the store operations, the speculative load buffer has three loads. The returned value of read D has already been used by the processor. The second event indicates an ownership for B, however it is not immediately completed. Its completion has been reordered and delayed by the reorder buffer. The third event indicates that the value of A arrives and the entries for A are purged from both the speculative-load and reorder buffers. Once the load A completes, the reorder buffer signals the store buffer to allow the store B to complete, and this is a hit because the value is already cached and thus finishes quickly. Store C is next to be served in the reorder buffer and its access is merged with the previous prefetch request for the same location.<ref>[http://www.cs.waikato.ac.nz/timewarp/wengine/papers/gc99_1/ Data and Control Speculative Execution]</ref>		In the above figure, the contents of various buffers are showed along with the cache content for each event that occurs. All three mechanisms which we have discussed will be traced in the example. The [http://en.wikipedia.org/wiki/Instruction_prefetch prefetching reorder] buffer holds the instructions that are fetched and decoded. Tracing through the set of events, initially the loads and prefetches (exclusive mode) are issued for the corresponding stores. In the meantime, while the store buffer is working on the store operations, the [http://www.csl.cornell.edu/courses/ee572/gharachorloo.icpp91.pdf speculative load buffer] has three loads. The returned value of read D has already been used by the processor. The second event indicates an ownership for B, however it is not immediately completed. Its completion has been reordered and delayed by the reorder buffer. The third event indicates that the value of A arrives and the entries for A are purged from both the speculative-load and reorder buffers. Once the load A completes, the reorder buffer signals the store buffer to allow the store B to complete, and this is a hit because the value is already cached and thus finishes quickly. Store C is next to be served in the reorder buffer and its access is merged with the previous prefetch request for the same location.<ref>[http://www.cs.waikato.ac.nz/timewarp/wengine/papers/gc99_1/ Data and Control Speculative Execution]</ref>

	Now to make things interesting, let us assume that there is an invalidation for D. This would cause a mismatch in the value speculated for D and hence the load D and the instructions following it are purged, indicated by event 5. The 6th event shows the correction mechanism by fetching the two instructions again and yet again load D will be a speculative event because store C has not finished. The 7th event shows new value in location D and since it is cached and its value known, E[D] proceeds. The 8th event shows that store C has finished, and since it does not affect D, the speculative value is correct and and is retired from the reorder and speculative-load buffers. The last event signifies the completion of E[D].		Now to make things interesting, let us assume that there is an invalidation for D. This would cause a mismatch in the value speculated for D and hence the load D and the instructions following it are purged, indicated by event 5. The 6th event shows the correction mechanism by fetching the two instructions again and yet again load D will be a speculative event because store C has not finished. The 7th event shows new value in location D and since it is cached and its value known, E[D] proceeds. The 8th event shows that store C has finished, and since it does not affect D, the speculative value is correct and and is retired from the reorder and speculative-load buffers. The last event signifies the completion of E[D].

Vmarapa: /* Illustrative example */

2012-04-25T02:47:53Z

Illustrative example

← Older revision		Revision as of 02:47, 25 April 2012
Line 185:		Line 185:
	[[File:SE_example.png\|600px\|Organization of a load store functional unit]]		[[File:SE_example.png\|600px\|Organization of a load store functional unit]]

	In the above figure, the contents of various buffers are showed along with the cache content for each event that occurs. All three mechanisms which we have discussed will be traced in the example. The [http://en.wikipedia.org/wiki/Instruction_prefetch prefetching]~~reorder~~ buffer holds the instructions that are fetched and decoded. Tracing through the set of events, initially the loads and prefetches (exclusive mode) are issued for the corresponding stores. In the meantime, while the store buffer is working on the store operations, the speculative load buffer has three loads. The returned value of read D has already been used by the processor. The second event indicates an ownership for B, however it is not immediately completed. Its completion has been reordered and delayed by the reorder buffer. The third event indicates that the value of A arrives and the entries for A are purged from both the speculative-load and reorder buffers. Once the load A completes, the reorder buffer signals the store buffer to allow the store B to complete, and this is a hit because the value is already cached and thus finishes quickly. Store C is next to be served in the reorder buffer and its access is merged with the previous prefetch request for the same location.<ref>[http://www.cs.waikato.ac.nz/timewarp/wengine/papers/gc99_1/ Data and Control Speculative Execution]</ref>		In the above figure, the contents of various buffers are showed along with the cache content for each event that occurs. All three mechanisms which we have discussed will be traced in the example. The [http://en.wikipedia.org/wiki/Instruction_prefetch prefetching reorder] buffer holds the instructions that are fetched and decoded. Tracing through the set of events, initially the loads and prefetches (exclusive mode) are issued for the corresponding stores. In the meantime, while the store buffer is working on the store operations, the speculative load buffer has three loads. The returned value of read D has already been used by the processor. The second event indicates an ownership for B, however it is not immediately completed. Its completion has been reordered and delayed by the reorder buffer. The third event indicates that the value of A arrives and the entries for A are purged from both the speculative-load and reorder buffers. Once the load A completes, the reorder buffer signals the store buffer to allow the store B to complete, and this is a hit because the value is already cached and thus finishes quickly. Store C is next to be served in the reorder buffer and its access is merged with the previous prefetch request for the same location.<ref>[http://www.cs.waikato.ac.nz/timewarp/wengine/papers/gc99_1/ Data and Control Speculative Execution]</ref>

	Now to make things interesting, let us assume that there is an invalidation for D. This would cause a mismatch in the value speculated for D and hence the load D and the instructions following it are purged, indicated by event 5. The 6th event shows the correction mechanism by fetching the two instructions again and yet again load D will be a speculative event because store C has not finished. The 7th event shows new value in location D and since it is cached and its value known, E[D] proceeds. The 8th event shows that store C has finished, and since it does not affect D, the speculative value is correct and and is retired from the reorder and speculative-load buffers. The last event signifies the completion of E[D].		Now to make things interesting, let us assume that there is an invalidation for D. This would cause a mismatch in the value speculated for D and hence the load D and the instructions following it are purged, indicated by event 5. The 6th event shows the correction mechanism by fetching the two instructions again and yet again load D will be a speculative event because store C has not finished. The 7th event shows new value in location D and since it is cached and its value known, E[D] proceeds. The 8th event shows that store C has finished, and since it does not affect D, the speculative value is correct and and is retired from the reorder and speculative-load buffers. The last event signifies the completion of E[D].

Vmarapa: /* Illustrative example */

2012-04-25T02:47:27Z

Illustrative example

← Older revision		Revision as of 02:47, 25 April 2012
Line 185:		Line 185:
	[[File:SE_example.png\|600px\|Organization of a load store functional unit]]		[[File:SE_example.png\|600px\|Organization of a load store functional unit]]

	In the above figure, the contents of various buffers are showed along with the cache content for each event that occurs. All three mechanisms which we have discussed will be traced in the example. The reorder buffer holds the instructions that are fetched and decoded. Tracing through the set of events, initially the loads and prefetches (exclusive mode) are issued for the corresponding stores. In the meantime, while the store buffer is working on the store operations, the speculative load buffer has three loads. The returned value of read D has already been used by the processor. The second event indicates an ownership for B, however it is not immediately completed. Its completion has been reordered and delayed by the reorder buffer. The third event indicates that the value of A arrives and the entries for A are purged from both the speculative-load and reorder buffers. Once the load A completes, the reorder buffer signals the store buffer to allow the store B to complete, and this is a hit because the value is already cached and thus finishes quickly. Store C is next to be served in the reorder buffer and its access is merged with the previous prefetch request for the same location.<ref>[http://www.cs.waikato.ac.nz/timewarp/wengine/papers/gc99_1/ Data and Control Speculative Execution]</ref>		In the above figure, the contents of various buffers are showed along with the cache content for each event that occurs. All three mechanisms which we have discussed will be traced in the example. The [http://en.wikipedia.org/wiki/Instruction_prefetch prefetching]reorder buffer holds the instructions that are fetched and decoded. Tracing through the set of events, initially the loads and prefetches (exclusive mode) are issued for the corresponding stores. In the meantime, while the store buffer is working on the store operations, the speculative load buffer has three loads. The returned value of read D has already been used by the processor. The second event indicates an ownership for B, however it is not immediately completed. Its completion has been reordered and delayed by the reorder buffer. The third event indicates that the value of A arrives and the entries for A are purged from both the speculative-load and reorder buffers. Once the load A completes, the reorder buffer signals the store buffer to allow the store B to complete, and this is a hit because the value is already cached and thus finishes quickly. Store C is next to be served in the reorder buffer and its access is merged with the previous prefetch request for the same location.<ref>[http://www.cs.waikato.ac.nz/timewarp/wengine/papers/gc99_1/ Data and Control Speculative Execution]</ref>

	Now to make things interesting, let us assume that there is an invalidation for D. This would cause a mismatch in the value speculated for D and hence the load D and the instructions following it are purged, indicated by event 5. The 6th event shows the correction mechanism by fetching the two instructions again and yet again load D will be a speculative event because store C has not finished. The 7th event shows new value in location D and since it is cached and its value known, E[D] proceeds. The 8th event shows that store C has finished, and since it does not affect D, the speculative value is correct and and is retired from the reorder and speculative-load buffers. The last event signifies the completion of E[D].		Now to make things interesting, let us assume that there is an invalidation for D. This would cause a mismatch in the value speculated for D and hence the load D and the instructions following it are purged, indicated by event 5. The 6th event shows the correction mechanism by fetching the two instructions again and yet again load D will be a speculative event because store C has not finished. The 7th event shows new value in location D and since it is cached and its value known, E[D] proceeds. The 8th event shows that store C has finished, and since it does not affect D, the speculative value is correct and and is retired from the reorder and speculative-load buffers. The last event signifies the completion of E[D].

Vmarapa: /* Future directions and ambitious implementations */

2012-04-25T02:44:29Z

Future directions and ambitious implementations

← Older revision		Revision as of 02:44, 25 April 2012
Line 196:		Line 196:

	To gain significant improvement in terms of performance, there have been a number of memory consistency models proposed. One disadvantage of the relaxed memory consistency models is that they present a more complex programming model to the user. The cost of this added performance benefit, however, is the extra hardware complexity that comes with it. The prefetch technique is simple and can easily be absorbed into the modern multiprocessor architectures while the speculative execution technique is not that easy when compared to the prefetch technique. Things get more complicated when the speculative execution technique is to be incorporated into multiprocessor systems when compared to uniprocessor systems. In the future, we might expect better implementations of the speculative execution technique which will make this transition easy.		To gain significant improvement in terms of performance, there have been a number of memory consistency models proposed. One disadvantage of the relaxed memory consistency models is that they present a more complex programming model to the user. The cost of this added performance benefit, however, is the extra hardware complexity that comes with it. The prefetch technique is simple and can easily be absorbed into the modern multiprocessor architectures while the speculative execution technique is not that easy when compared to the prefetch technique. Things get more complicated when the speculative execution technique is to be incorporated into multiprocessor systems when compared to uniprocessor systems. In the future, we might expect better implementations of the speculative execution technique which will make this transition easy.


			== Glossary ==

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

Mbplautz: Section VI

2012-04-07T03:07:01Z

Section VI

← Older revision		Revision as of 03:07, 7 April 2012
Line 195:		Line 195:
	The paper by Stenstrom <ref>[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=223075&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D223075 A latency-hiding scheme for multiprocessors with buffered multistage networks]</ref> proposes a mechanism for guaranteeing access order at the memory instead of at the processor. Each request contains a processor identification and a sequence number. Consecutive requests from the same processor get consecutive sequence numbers. Each memory module has access to a common data structure called next sequence-number table (NST). The NST contains P entries, one entry per processor. Each entry contains the sequence number of the next request to be performed by the corresponding processor. This allows the mechanism to guarantee that accesses from each processor are kept in program order. Theoretically, this scheme can enhance the performance of sequential consistency. However, the major disadvantage is that caches are not allowed. This can severely hinder the performance when compared to implementations that allow shared locations to be cached.		The paper by Stenstrom <ref>[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=223075&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D223075 A latency-hiding scheme for multiprocessors with buffered multistage networks]</ref> proposes a mechanism for guaranteeing access order at the memory instead of at the processor. Each request contains a processor identification and a sequence number. Consecutive requests from the same processor get consecutive sequence numbers. Each memory module has access to a common data structure called next sequence-number table (NST). The NST contains P entries, one entry per processor. Each entry contains the sequence number of the next request to be performed by the corresponding processor. This allows the mechanism to guarantee that accesses from each processor are kept in program order. Theoretically, this scheme can enhance the performance of sequential consistency. However, the major disadvantage is that caches are not allowed. This can severely hinder the performance when compared to implementations that allow shared locations to be cached.

	To gain significant improvement in terms of performance, there have been a number of memory consistency models proposed. One disadvantage of the relaxed memory consistency models is that they present a more complex programming model to the user. The cost of this added performance benefit is ~~however~~ the extra hardware complexity that comes with it. The prefetch technique is simple and can easily be absorbed into the modern ~~multi processor~~ architectures while the speculative execution technique is not that easy when compared to the prefetch technique. Things get more complicated when the speculative execution technique is to be incorporated into ~~multi processor~~ systems when compared to ~~uni processor~~ systems. In future, we might expect better implementations of the speculative execution technique which will make this transition easy.		To gain significant improvement in terms of performance, there have been a number of memory consistency models proposed. One disadvantage of the relaxed memory consistency models is that they present a more complex programming model to the user. The cost of this added performance benefit, however, is the extra hardware complexity that comes with it. The prefetch technique is simple and can easily be absorbed into the modern multiprocessor architectures while the speculative execution technique is not that easy when compared to the prefetch technique. Things get more complicated when the speculative execution technique is to be incorporated into multiprocessor systems when compared to uniprocessor systems. In the future, we might expect better implementations of the speculative execution technique which will make this transition easy.

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