CSC/ECE 506 Fall 2007/wiki2 helperThreads - Revision history

Lreddy at 17:38, 28 November 2007

2007-11-28T17:38:04Z

← Older revision		Revision as of 17:38, 28 November 2007
Line 1:		Line 1:
	''A helper thread is a thread that does some of the work of the main thread in advance of the main thread so that the main thread can work more quickly. The Olukotun text only scratches the surface on all the different ways that helper threads can be used. Survey these ways, making sure to include the Slipstream approach developed at NCSU.''		'''''A helper thread is a thread that does some of the work of the main thread in advance of the main thread so that the main thread can work more quickly. The Olukotun text only scratches the surface on all the different ways that helper threads can be used. Survey these ways, making sure to include the Slipstream approach developed at NCSU.'''''

	'''What is a helper thread?'''		'''What is a helper thread?'''

Lreddy at 17:37, 28 November 2007

2007-11-28T17:37:44Z

← Older revision		Revision as of 17:37, 28 November 2007
Line 1:		Line 1:
	A helper thread is a thread that does some of the work of the main thread in advance of the main thread so that the main thread can work more quickly. The Olukotun text only scratches the surface on all the different ways that helper threads can be used. Survey these ways, making sure to include the Slipstream approach developed at NCSU.		''A helper thread is a thread that does some of the work of the main thread in advance of the main thread so that the main thread can work more quickly. The Olukotun text only scratches the surface on all the different ways that helper threads can be used. Survey these ways, making sure to include the Slipstream approach developed at NCSU.''

	'''What is a helper thread?'''		'''What is a helper thread?'''

Lreddy at 17:35, 28 November 2007

2007-11-28T17:35:16Z

← Older revision		Revision as of 17:35, 28 November 2007
Line 71:		Line 71:
	3)http://www.research.ibm.com/journal/rd/502/shetty.html		3)http://www.research.ibm.com/journal/rd/502/shetty.html

	4)www.tinker.ncsu.edu/ericro/research/slipstream.htm		4)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

Lreddy at 17:34, 28 November 2007

2007-11-28T17:34:51Z

← Older revision		Revision as of 17:34, 28 November 2007
Line 62:		Line 62:

	Only certain types of single threaded programs can be sped up with these techniques. Most integer applications have regular data access patterns and hence there will be only few misses to eliminate. The applications with larger memory footprints are easily parellelisable and hence doesn't run on a single main thread. Most floating point applications the data access patterns are fairly regular and hence can be prefetched easily using hardware or software prefetch mechanisms. Hence the range of programs that can be accelerated using helper threads is fairly limited.		Only certain types of single threaded programs can be sped up with these techniques. Most integer applications have regular data access patterns and hence there will be only few misses to eliminate. The applications with larger memory footprints are easily parellelisable and hence doesn't run on a single main thread. Most floating point applications the data access patterns are fairly regular and hence can be prefetched easily using hardware or software prefetch mechanisms. Hence the range of programs that can be accelerated using helper threads is fairly limited.

			'''References'''

			1)ChipMultiprocessor Architecture:Techniques to Improve Throughput and Latency by Kunle Olukotun, Lance Hammond, and James Laudon

			2)Slipstream Execution Mode for CMP-Based Multiprocessors by Khaled Z. Ibrahim, Gregory T. Byrd, and Eric Rotenberg

			3)http://www.research.ibm.com/journal/rd/502/shetty.html

			4)www.tinker.ncsu.edu/ericro/research/slipstream.htm

Lreddy at 17:27, 28 November 2007

2007-11-28T17:27:59Z

← Older revision		Revision as of 17:27, 28 November 2007
Line 61:		Line 61:
	A very tight synchronisation is needed between the main thread and the helper threads in oder to keep them the proper distance ahead of main thread. If the helper threads are too far ahead, then they will cause cache thrashing by prefetching data and then replaing it with subsequent prefetches beofre the main thread can even use it. If they are not far enough ahead, they might not be able to prefetch cache lines in time.		A very tight synchronisation is needed between the main thread and the helper threads in oder to keep them the proper distance ahead of main thread. If the helper threads are too far ahead, then they will cause cache thrashing by prefetching data and then replaing it with subsequent prefetches beofre the main thread can even use it. If they are not far enough ahead, they might not be able to prefetch cache lines in time.

	Only certain types of single threaded programs can be sped up with these techniques. Most integer applications have regular data access patterns and hence there will be only few misses to eliminate. The applications with larger memory footprints are easily parellelisable and hence doesn't run on a single main thread. I floating point applications the data access patterns are fairly regular and hence can be prefetched easily using hardware or software prefetch mechanisms. Hence the range of programs that can be accelerated using helper threads is fairly limited.		Only certain types of single threaded programs can be sped up with these techniques. Most integer applications have regular data access patterns and hence there will be only few misses to eliminate. The applications with larger memory footprints are easily parellelisable and hence doesn't run on a single main thread. Most floating point applications the data access patterns are fairly regular and hence can be prefetched easily using hardware or software prefetch mechanisms. Hence the range of programs that can be accelerated using helper threads is fairly limited.

Lreddy at 17:27, 28 November 2007

2007-11-28T17:27:22Z

← Older revision		Revision as of 17:27, 28 November 2007
Line 41:		Line 41:
	thread approach completely decouples bug monitoring from appication execution and the filtering mechanism reduces		thread approach completely decouples bug monitoring from appication execution and the filtering mechanism reduces
	bug - check frequency. Conseqently, HeapMon achieves a very low performance overhead.		bug - check frequency. Conseqently, HeapMon achieves a very low performance overhead.

	~~'''Fault tolerance'''~~

	~~The helper thread is a subset of main program. This partial redundancy can be used for detecting and recovering~~
	~~from transient hardware faults.~~

	'''Slipstream approach for helper threads:'''		'''Slipstream approach for helper threads:'''

Lreddy at 17:25, 28 November 2007

2007-11-28T17:25:20Z

← Older revision		Revision as of 17:25, 28 November 2007
Line 57:		Line 57:

	Synchronization between an R-stream and its corresponding A-stream is required for two reasons.First, an A-stream that has taken a completely wrong control path and is generating useless data access predictions has to be corrcted. Second, limit how far the A-stream gets ahead, so that its prefetches are not issued so early that the prefetched lines are often replaced or invalidated in the L2 cache before the R-stream uses them. A single semaphore is required between each Astream/		Synchronization between an R-stream and its corresponding A-stream is required for two reasons.First, an A-stream that has taken a completely wrong control path and is generating useless data access predictions has to be corrcted. Second, limit how far the A-stream gets ahead, so that its prefetches are not issued so early that the prefetched lines are often replaced or invalidated in the L2 cache before the R-stream uses them. A single semaphore is required between each Astream/
	R-stream pair to control their synchronization. It can be a shared hardware register, but any shared location that supports an atomic read-modify-write operation is sufficient. Using this semaphore, the following are controlled		R-stream pair to control their synchronization. It can be a shared hardware register, but any shared location that supports an atomic read-modify-write operation is sufficient. Using this semaphore, the following are controlled<br/>
	(a) how many synchronization events the A-stream can skip without waiting for the Rstream		(a) how many synchronization events the A-stream can skip without waiting for the Rstream<br/>
	(b) whether the synchronization is local (involving only the companion R-stream) or global (involving all R-streams). The initial value of the semaphore indicates how many sessions the A-stream may proceed ahead of the Rstream.		(b) whether the synchronization is local (involving only the companion R-stream) or global (involving all R-streams). The initial value of the semaphore indicates how many sessions the A-stream may proceed ahead of the Rstream. <br/>
	This can be viewed as creating an initial pool of tokens that are consumed as the A-stream enters a new session. When there are no tokens, the Astream may not proceed. The R-stream issues tokens by incrementing the semaphore counter.Once the A thread gets the semaphore, A threads advances and gets past the R thread.		This can be viewed as creating an initial pool of tokens that are consumed as the A-stream enters a new session. When there are no tokens, the Astream may not proceed. The R-stream issues tokens by incrementing the semaphore counter.Once the A thread gets the semaphore, A threads advances and gets past the R thread.

Lreddy at 17:24, 28 November 2007

2007-11-28T17:24:15Z

← Older revision		Revision as of 17:24, 28 November 2007
Line 20:		Line 20:

	'''Prefetching of Data:'''		'''Prefetching of Data:'''

	Since helper threads run ahead of main thread, they can predict the which data in memory is needed in		Since helper threads run ahead of main thread, they can predict the which data in memory is needed in
	future by the main thread.they prefetch the data required by the main thread. The helper thread prefetches		future by the main thread.they prefetch the data required by the main thread. The helper thread prefetches
Line 27:		Line 28:

	'''Memory Bug Reduction:'''		'''Memory Bug Reduction:'''

	Memory related bugs such as reads from unitialised memory, read or writes using dangling pointers or		Memory related bugs such as reads from unitialised memory, read or writes using dangling pointers or
	memory leaks are difficult to detect by code inspection because they may invoive different code fragments		memory leaks are difficult to detect by code inspection because they may invoive different code fragments
Line 41:		Line 43:

	'''Fault tolerance'''		'''Fault tolerance'''

	The helper thread is a subset of main program. This partial redundancy can be used for detecting and recovering		The helper thread is a subset of main program. This partial redundancy can be used for detecting and recovering
	from transient hardware faults.		from transient hardware faults.

Lreddy at 17:23, 28 November 2007

2007-11-28T17:23:01Z

← Older revision		Revision as of 17:23, 28 November 2007
Line 11:		Line 11:
	'''Uses of helper threads'''		'''Uses of helper threads'''

	'''Predicting branch at early stages'''		'''Predicting branch at early stages:'''

	Helper threads are made up of program copies of the main thread stripped of all unessential parts		Helper threads are made up of program copies of the main thread stripped of all unessential parts
Line 19:		Line 19:
	mispredictions which may occur when branch predictions are used.		mispredictions which may occur when branch predictions are used.

	'''Prefetching of Data'''		'''Prefetching of Data:'''
	Since helper threads run ahead of main thread, they can predict the which data in memory is needed in		Since helper threads run ahead of main thread, they can predict the which data in memory is needed in
	future by the main thread.they prefetch the data required by the main thread. The helper thread prefetches		future by the main thread.they prefetch the data required by the main thread. The helper thread prefetches
Line 26:		Line 26:
	memory latency is reduced, the execution of main thread speeds up.		memory latency is reduced, the execution of main thread speeds up.

	'''Memory Bug Reduction'''		'''Memory Bug Reduction:'''
	Memory related bugs such as reads from unitialised memory, read or writes using dangling pointers or		Memory related bugs such as reads from unitialised memory, read or writes using dangling pointers or
	memory leaks are difficult to detect by code inspection because they may invoive different code fragments		memory leaks are difficult to detect by code inspection because they may invoive different code fragments
Line 44:		Line 44:
	from transient hardware faults.		from transient hardware faults.

	'''Slipstream approach for helper threads'''		'''Slipstream approach for helper threads:'''

	Slipstream approach is developed at North Carolina State University.		Slipstream approach is developed at North Carolina State University.
Line 59:		Line 59:
	This can be viewed as creating an initial pool of tokens that are consumed as the A-stream enters a new session. When there are no tokens, the Astream may not proceed. The R-stream issues tokens by incrementing the semaphore counter.Once the A thread gets the semaphore, A threads advances and gets past the R thread.		This can be viewed as creating an initial pool of tokens that are consumed as the A-stream enters a new session. When there are no tokens, the Astream may not proceed. The R-stream issues tokens by incrementing the semaphore counter.Once the A thread gets the semaphore, A threads advances and gets past the R thread.

	'''Disadvantages of helper threads'''		'''Disadvantages of helper threads:'''

	A very tight synchronisation is needed between the main thread and the helper threads in oder to keep them the proper distance ahead of main thread. If the helper threads are too far ahead, then they will cause cache thrashing by prefetching data and then replaing it with subsequent prefetches beofre the main thread can even use it. If they are not far enough ahead, they might not be able to prefetch cache lines in time.		A very tight synchronisation is needed between the main thread and the helper threads in oder to keep them the proper distance ahead of main thread. If the helper threads are too far ahead, then they will cause cache thrashing by prefetching data and then replaing it with subsequent prefetches beofre the main thread can even use it. If they are not far enough ahead, they might not be able to prefetch cache lines in time.

	Only certain types of single threaded programs can be sped up with these techniques. Most integer applications have regular data access patterns and hence there will be only few misses to eliminate. The applications with larger memory footprints are easily parellelisable and hence doesn't run on a single main thread. I floating point applications the data access patterns are fairly regular and hence can be prefetched easily using hardware or software prefetch mechanisms. Hence the range of programs that can be accelerated using helper threads is fairly limited.		Only certain types of single threaded programs can be sped up with these techniques. Most integer applications have regular data access patterns and hence there will be only few misses to eliminate. The applications with larger memory footprints are easily parellelisable and hence doesn't run on a single main thread. I floating point applications the data access patterns are fairly regular and hence can be prefetched easily using hardware or software prefetch mechanisms. Hence the range of programs that can be accelerated using helper threads is fairly limited.

Lreddy at 17:22, 28 November 2007

2007-11-28T17:22:10Z

← Older revision		Revision as of 17:22, 28 November 2007
Line 1:		Line 1:
	A helper thread is a thread that does some of the work of the main thread in advance of the main thread so that the main thread can work more quickly. The Olukotun text only scratches the surface on all the different ways that helper threads can be used. Survey these ways, making sure to include the Slipstream approach developed at NCSU.		A helper thread is a thread that does some of the work of the main thread in advance of the main thread so that the main thread can work more quickly. The Olukotun text only scratches the surface on all the different ways that helper threads can be used. Survey these ways, making sure to include the Slipstream approach developed at NCSU.

	What is a helper thread?		'''What is a helper thread?'''

	The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are		The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
Line 9:		Line 9:
	effort to accelerate its performance.		effort to accelerate its performance.

	Uses of helper threads		'''Uses of helper threads'''

	Predicting branch at early stages		'''Predicting branch at early stages'''

	Helper threads are made up of program copies of the main thread stripped of all unessential parts		Helper threads are made up of program copies of the main thread stripped of all unessential parts
Line 19:		Line 19:
	mispredictions which may occur when branch predictions are used.		mispredictions which may occur when branch predictions are used.

	Prefetching of Data		'''Prefetching of Data'''
	Since helper threads run ahead of main thread, they can predict the which data in memory is needed in		Since helper threads run ahead of main thread, they can predict the which data in memory is needed in
	future by the main thread.they prefetch the data required by the main thread. The helper thread prefetches		future by the main thread.they prefetch the data required by the main thread. The helper thread prefetches
Line 26:		Line 26:
	memory latency is reduced, the execution of main thread speeds up.		memory latency is reduced, the execution of main thread speeds up.

	Memory Bug Reduction:		'''Memory Bug Reduction'''
	Memory related bugs such as reads from unitialised memory, read or writes using dangling pointers or		Memory related bugs such as reads from unitialised memory, read or writes using dangling pointers or
	memory leaks are difficult to detect by code inspection because they may invoive different code fragments		memory leaks are difficult to detect by code inspection because they may invoive different code fragments
Line 40:		Line 40:
	bug - check frequency. Conseqently, HeapMon achieves a very low performance overhead.		bug - check frequency. Conseqently, HeapMon achieves a very low performance overhead.

	Fault tolerance:		'''Fault tolerance'''
	The helper thread is a subset of main program. This partial redundancy can be used for detecting and recovering		The helper thread is a subset of main program. This partial redundancy can be used for detecting and recovering
	from transient hardware faults.		from transient hardware faults.

	Slipstream approach for helper threads:		'''Slipstream approach for helper threads'''

	Slipstream approach is developed at North Carolina State University.		Slipstream approach is developed at North Carolina State University.
Line 59:		Line 59:
	This can be viewed as creating an initial pool of tokens that are consumed as the A-stream enters a new session. When there are no tokens, the Astream may not proceed. The R-stream issues tokens by incrementing the semaphore counter.Once the A thread gets the semaphore, A threads advances and gets past the R thread.		This can be viewed as creating an initial pool of tokens that are consumed as the A-stream enters a new session. When there are no tokens, the Astream may not proceed. The R-stream issues tokens by incrementing the semaphore counter.Once the A thread gets the semaphore, A threads advances and gets past the R thread.

	Disadvantages of helper threads:		'''Disadvantages of helper threads'''

	A very tight synchronisation is needed between the main thread and the helper threads in oder to keep them the proper distance ahead of main thread. If the helper threads are too far ahead, then they will cause cache thrashing by prefetching data and then replaing it with subsequent prefetches beofre the main thread can even use it. If they are not far enough ahead, they might not be able to prefetch cache lines in time.		A very tight synchronisation is needed between the main thread and the helper threads in oder to keep them the proper distance ahead of main thread. If the helper threads are too far ahead, then they will cause cache thrashing by prefetching data and then replaing it with subsequent prefetches beofre the main thread can even use it. If they are not far enough ahead, they might not be able to prefetch cache lines in time.

	Only certain types of single threaded programs can be sped up with these techniques. Most integer applications have regular data access patterns and hence there will be only few misses to eliminate. The applications with larger memory footprints are easily parellelisable and hence doesn't run on a single main thread. I floating point applications the data access patterns are fairly regular and hence can be prefetched easily using hardware or software prefetch mechanisms. Hence the range of programs that can be accelerated using helper threads is fairly limited.		Only certain types of single threaded programs can be sped up with these techniques. Most integer applications have regular data access patterns and hence there will be only few misses to eliminate. The applications with larger memory footprints are easily parellelisable and hence doesn't run on a single main thread. I floating point applications the data access patterns are fairly regular and hence can be prefetched easily using hardware or software prefetch mechanisms. Hence the range of programs that can be accelerated using helper threads is fairly limited.