Expertiza_Wiki - User contributions [en]

CSC/ECE 506 Fall 2007/wiki4 helperThreads

2007-12-04T01:42:09Z

Lreddy:

'''''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?'''

It has been experienced that enhancing the speed of microprocessors is becoming an increasingly difficult
task. It is because of various reasons of which few are stated below:

1) Typical instruction streams have only limited parallelism. So a superscalar pipeline which can issue more than four instruction per cycle is of little benefit compared to the cost it incurs.

2) As the depth of the pipeline increases, the cost of pipeline flushes during branch mispredictions becomes intolerable.

3) As the speed and number of transistors on chip increase, the power required to drive complex logic circuits at high clock rate also increases beyond tolerable limit.

So, processor manufacturers are switching to a new design paradigm: the chip microprocessors, which is also known as multicore microprocessors or manycore microprocessors. As the name implies, a chip multiprocessor is simply a group of uniprocessors integrated onto the same processor chip so that they may act as a team, filling the area that would have originally been filled with a single large processors with several smaller cores.

The depth of the pipeline of the uniprocessor cores used will be just enough to exploit the limited instruction level parallelism present in programs inorder to keep power utilization low.So to better exploit the potential of chip multiprocessors (CMPs)the applications are divided into semi - independent parts, or threads that can operate simultaneously across the processors within a system.

The simplest way to use parallel threads within a CMP to increase the performance of a single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an effort to accelerate its performance. Helper threads run ahead of main thread because all the instructions that are not absolutely necessary for performing the function that the helper thread is meant for is removed from the program that the helper thread executes. Hence they can accuarately predict branches, start the long latency operations early, prefect the data needed by the main thread etc which are explained in detail below.

The following figure shows the main thread and helper thread in a two core chip multiprocessor.Main thread spawns the helper thread. Helper thread has the instructions that form a subset of the instructions in the main thread. As a result helper thread executes less instructions than the main thread and hence effectively executes ahead of main thread. As a result, it can start a long latency operations early and provide the result to the main thread by the time main thread starts executing that long latency operation.

[[Image:Helper threads.png]]

'''Uses of helper threads'''

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

As mentioned earlier, helper threads are made up of program copies of the main thread stripped of all unessential parts which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs ahead of main thread. Hence helper threads can do computations that are necessary to decide the direction of the branch. As the branch direction is decided using the result of actual computation and not just prediction, the branch predictor will be trained in favour to the actual branch direction taken by the helper thread. So, branch predictions will be more accuarate. This will inturn remove branch mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

Since helper threads run ahead of main thread, they can predict 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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 corrected. 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 A-stream/
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 
(a) how many synchronization events the A-stream can skip without waiting for the R-stream 
(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. 
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 A-stream 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:'''

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 speeded 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

5)A Survey of Helper Threads And Their Implementation by Ahren Studer

6)Design and Implementation of a Compiler Framework for Helper Threading on Multicore Processors http://pact05.ce.ucsc.edu/datacentric.pdf

CSC/ECE 506 Fall 2007/wiki4 2 helperThreads

2007-12-04T01:31:47Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki4 2 helperThreads

2007-12-04T01:28:55Z

Lreddy:

'''''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?'''

It has been experienced that enhancing the speed of microprocessors is becoming an increasingly difficult
task. It is because of various reasons of which few are stated below:

1) Typical instruction streams have only limited parallelism. So a superscalar pipeline which can issue more than four instruction per cycle is of little benefit compared to the cost it incurs.

2) As the depth of the pipeline increases, the cost of pipeline flushes during branch mispredictions becomes intolerable.

3) As the speed and number of transistors on chip increase, the power required to drive complex logic circuits at high clock rate also increases beyond tolerable limit.

So, processor manufacturers are switching to a new design paradigm: the chip microprocessors, which is also known as multicore microprocessors or manycore microprocessors. As the name implies, a chip multiprocessor is simply a group of uniprocessors integrated onto the same processor chip so that they may act as a team, filling the area that would have originally been filled with a single large processors with several smaller cores.

The depth of the pipeline of the uniprocessor cores used will be just enough to exploit the limited instruction level parallelism present in programs inorder to keep power utilization low.So to better exploit the potential of chip multiprocessors (CMPs)the applications are divided into semi - independent parts, or threads that can operate simultaneously across the processors within a system.

The simplest way to use parallel threads within a CMP to increase the performance of a single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an effort to accelerate its performance. Helper threads run ahead of main thread because all the instructions that are not absolutely necessary for performing the function that the helper thread is meant for is removed from the program that the helper thread executes. Hence they can accuarately predict branches, start the long latency operations early, prefect the data needed by the main thread etc which are explained in detail below.

The following figure shows the main thread and helper thread in a two core chip multiprocessor.Main thread spawns the helper thread. Helper thread has the instructions that form a subset of the instructions in the main thread. As a result helper thread executes less instructions than the main thread and hence effectively executes ahead of main thread. As a result, it can start a long latency operations early and provide the result to the main thread by the time main thread starts executing that long latency operation.

[[Image:Helper threads.png]]

'''Uses of helper threads'''

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

As mentioned earlier, helper threads are made up of program copies of the main thread stripped of all unessential parts which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs ahead of main thread. Hence helper threads can do computations that are necessary to decide the direction of the branch. As the branch direction is decided using the result of actual computation and not just prediction, the branch predictor will be trained in favour to the actual branch direction taken by the helper thread. So, branch predictions will be more accuarate. This will inturn remove branch mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 corrected. 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 A-stream/
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 
(a) how many synchronization events the A-stream can skip without waiting for the R-stream 
(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. 
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 A-stream 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:'''

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 speeded 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

5)A Survey of Helper Threads And Their Implementation by Ahren Studer

6)Design and Implementation of a Compiler Framework for Helper Threading on Multicore Processors http://pact05.ce.ucsc.edu/datacentric.pdf

CSC/ECE 506 Fall 2007/wiki4 2 helperThreads

2007-12-04T01:27:50Z

Lreddy:

'''''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?'''

It has been experienced that enhancing the speed of microprocessors is becoming an increasingly difficult
task. It is because of various reasons of which few are stated below:

1) Typical instruction streams have only limited parallelism. So a superscalar pipeline which can issue more than four instruction per cycle is of little benefit compared to the cost it incurs.

2) As the depth of the pipeline increases, the cost of pipeline flushes during branch mispredictions becomes intolerable.

3) As the speed and number of transistors on chip increase, the power required to drive complex logic circuits at high clock rate also increases beyond tolerable limit.

So, processor manufacturers are swicthing to a new design paradigm: the chip microprocessors, which is also known as multicore microprocessors or manycore microprocessors. As the name implies, a chip multiprocessor is simply a group of uniprocessors integrated onto the same processor chip so that they may act as a team, filling the area that would have originally been filled with a single large processors with several smaller cores.

The depth of the pipeline of the uniprocessor cores used will be just enough to exploit the limited instruction level parallelism present in programs inorder to keep power utilization low.So to better exploit the potential of chip multiprocessors (CMPs)the applications are divided into semi - independent parts, or threads that can operate simultaneously across the processors within a system.

The simplest way to use parallel threads within a CMP to increase the performance of a single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an effort to accelerate its performance. Helper threads run ahead of main thread because all the instructions that are not absolutely necessary for performing the function that the helper thread is meant for is removed from the program that the helper thread executes. Hence they can accuarately predict branches, start the long latency operations early, prefect the data needed by the main thread etc which are explained in detail below.

The following figure shows the main thread and helper thread in a two core chip multiprocessor.Main thread spawns the helper thread. Helper thread has the instructions that form a subset of the instructions in the main thread. As a result helper thread executes less instructions than the main thread and hence effectively executes ahead of main thread. As a result, it can start a long latency operations early and provide the result to the main thread by the time main thread starts executing that long latency operation.

[[Image:Helper threads.png]]

'''Uses of helper threads'''

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

As mentioned earlier, helper threads are made up of program copies of the main thread stripped of all unessential parts which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs ahead of main thread. Hence helper threads can do computations that are necessary to decide the direction of the branch. As the branch direction is decided using the result of actual computation and not just prediction, the branch predictor will be trained in favour to the actual branch direction taken by the helper thread. So, branch predictions will be more accuarate. This will inturn remove branch mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 corrected. 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 A-stream/
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 
(a) how many synchronization events the A-stream can skip without waiting for the R-stream 
(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. 
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 A-stream 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:'''

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 speeded 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

5)A Survey of Helper Threads And Their Implementation by Ahren Studer

6)Design and Implementation of a Compiler Framework for Helper Threading on Multicore Processors http://pact05.ce.ucsc.edu/datacentric.pdf

CSC/ECE 506 Fall 2007/wiki4 2 helperThreads

2007-12-04T01:26:59Z

Lreddy:

'''''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?'''

It has been experienced that enhancing the speed of microprocessors is becoming an increasingly difficult
task. It is because of various reasons of which few are stated below:

1) Typical instruction streams have only limited parallelism. So a superscalar pipeline which can issue more than four instruction per cycle is of little benefit compared to the cost it incurs.
2) As the depth of the pipeline increases, the cost of pipeline flushes during branch mispredictions becomes intolerable.
3) As the speed and number of transistors on chip increase, the power required to drive complex logic circuits at high clock rate also increases beyond tolerable limit.

So, processor manufacturers are swicthing to a new design paradigm: the chip microprocessors, which is also known as multicore microprocessors or manycore microprocessors. As the name implies, a chip multiprocessor is simply a group of uniprocessors integrated onto the same processor chip so that they may act as a team, filling the area that would have originally been filled with a single large processors with several smaller cores.

The depth of the pipeline of the uniprocessor cores used will be just enough to exploit the limited instruction level parallelism present in programs inorder to keep power utilization low.So to better exploit the potential of chip multiprocessors (CMPs)the applications are divided into semi - independent parts, or threads that can operate simultaneously across the processors within a system.

The simplest way to use parallel threads within a CMP to increase the performance of a single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an effort to accelerate its performance. Helper threads run ahead of main thread because all the instructions that are not absolutely necessary for performing the function that the helper thread is meant for is removed from the program that the helper thread executes. Hence they can accuarately predict branches, start the long latency operations early, prefect the data needed by the main thread etc which are explained in detail below.

The following figure shows the main thread and helper thread in a two core chip multiprocessor.Main thread spawns the helper thread. Helper thread has the instructions that form a subset of the instructions in the main thread. As a result helper thread executes less instructions than the main thread and hence effectively executes ahead of main thread. As a result, it can start a long latency operations early and provide the result to the main thread by the time main thread starts executing that long latency operation.

[[Image:Helper threads.png]]

'''Uses of helper threads'''

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

As mentioned earlier, helper threads are made up of program copies of the main thread stripped of all unessential parts which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs ahead of main thread. Hence helper threads can do computations that are necessary to decide the direction of the branch. As the branch direction is decided using the result of actual computation and not just prediction, the branch predictor will be trained in favour to the actual branch direction taken by the helper thread. So, branch predictions will be more accuarate. This will inturn remove branch mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 corrected. 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 A-stream/
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 
(a) how many synchronization events the A-stream can skip without waiting for the R-stream 
(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. 
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 A-stream 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:'''

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 speeded 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

5)A Survey of Helper Threads And Their Implementation by Ahren Studer

6)Design and Implementation of a Compiler Framework for Helper Threading on Multicore Processors http://pact05.ce.ucsc.edu/datacentric.pdf

CSC/ECE 506 Fall 2007/wiki4 2 helperThreads

2007-12-03T23:59:36Z

Lreddy:

'''''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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

[[Image:Helper threads.png]]

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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. 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

CSC/ECE 506 Fall 2007/wiki4 2 helperThreads

2007-11-29T00:39:04Z

Lreddy:

'''''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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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. 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

CSC/ECE 506 Fall 2007/wiki2 4 helperThreads

2007-11-29T00:37:14Z

Lreddy:

'''''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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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. 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

CSC/ECE 506 Fall 2007/wiki2 2 helperThreads

2007-11-29T00:35:58Z

Lreddy:

'''''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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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. 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

CSC/ECE 506 Fall 2007/wiki4 helperThreads

2007-11-28T22:42:26Z

Lreddy:

'''''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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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. 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:38:04Z

Lreddy:

'''''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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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. 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:37:44Z

Lreddy:

''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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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. 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:35:16Z

Lreddy:

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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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. 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)http://www.tinker.ncsu.edu/ericro/research/slipstream.htm

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:34:51Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:27:59Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:27:22Z

Lreddy:

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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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

Slipstream approach is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:25:20Z

Lreddy:

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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

'''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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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 
(a) how many synchronization events the A-stream can skip without waiting for 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. 
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:'''

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:24:15Z

Lreddy:

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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''

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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''

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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

'''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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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
(a) how many synchronization events the A-stream can skip without waiting for 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.
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:'''

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:23:01Z

Lreddy:

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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

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

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data:'''
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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction:'''
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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

'''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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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
(a) how many synchronization events the A-stream can skip without waiting for 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.
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:'''

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:22:10Z

Lreddy:

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?'''

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

'''Uses of helper threads'''

'''Predicting branch at early stages'''

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

'''Prefetching of Data'''
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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

'''Memory Bug Reduction'''
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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

'''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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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
(a) how many synchronization events the A-stream can skip without waiting for 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.
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'''

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T17:20:07Z

Lreddy:

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?

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

Uses of helper threads

Predicting branch at early stages

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

Prefetching of Data
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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

Memory Bug Reduction:
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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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
(a) how many synchronization events the A-stream can skip without waiting for 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.
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:

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T16:08:47Z

Lreddy:

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?

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

Uses of helper threads

Predicting branch at early stages

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

Prefetching of Data
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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

Memory Bug Reduction:
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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

Synchronization between an R-stream and its corresponding A-stream is required for two reasons.First, we must correct an A-stream that has taken a completely wrong control path and is generating useless data access predictions. Second, we want to 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. We require a single semaphore between each Astream/
R-stream pair to control their synchronization. For our experiments, we have assumed a shared hardware register, but any shared location that supports an atomic read-modify-write operation is sufficient. Using this semaphore, we control (a) how many synchronization events the A-stream can skip without waiting for the Rstream and (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. This can be viewed as creating an initial pool of tokens that are consumed as the A-stream enters a new session (Figure 3). 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:

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T16:07:12Z

Lreddy:

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?

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

Uses of helper threads

Predicting branch at early stages

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

Prefetching of Data
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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

Memory Bug Reduction:
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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

Synchronization between an R-stream and its corresponding A-stream is required for two reasons.First, we must correct an A-stream that has taken a completely wrong control path and is generating useless data access predictions. Second, we want to 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. We require a single semaphore between each Astream/
R-stream pair to control their synchronization. For our experiments, we have assumed a shared hardware register, but any shared location that supports an atomic read-modify-write operation is sufficient. Using this semaphore, we control (a) how many synchronization events the A-stream can skip without waiting for the Rstream and (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. This can be viewed as creating an initial pool of tokens that are consumed as the A-stream enters a new session (Figure 3). When there are no tokens, the Astream may not proceed. The R-stream issues tokens by incrementing the semaphore counter.

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.

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:54:40Z

Lreddy:

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?

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

Uses of helper threads

Predicting branch at early stages

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

Prefetching of Data
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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

Memory Bug Reduction:
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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

Synchronization between an R-stream and its corresponding A-stream is required for two reasons.First, we must correct an A-stream that has taken a completely wrong control path and is generating useless data access predictions. Second, we want to 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.

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.

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:47:42Z

Lreddy:

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?

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

Uses of helper threads

Predicting branch at early stages

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

Prefetching of Data
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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

Memory Bug Reduction:
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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

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.

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:46:40Z

Lreddy:

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?

The potential of chip multiprocessors (CMPs) can be exploited in a better way if the applications are
divided into semi - independent parts, or threads that can operate simultaneously across the processors
within a system. The simplest way to use parallel threads within a CMP to increase the performance of a
single thread is to have helper threads. A 'helper' thread performs work on behalf of main thread in an
effort to accelerate its performance.

The speculative reduced program is called A-stream (Advanced Stream) and runs ahead of the unreduced program (main thread or Redundant stream).The R-stream exploits the A-stream to get an accurate picture of the future. For example, the A-stream
provides very accurate branch and value predictions. The predictions are more accurate than predictions made by conventional history-based predictors because they are produced by future program computation. The speculative A-stream occasionally (but
infrequently) goes astray. The R-stream serves as a checker of the speculative A-stream and redirects it when needed.

Uses of helper threads

Predicting branch at early stages

Helper threads are made up of program copies of the main thread stripped of all unessential parts
which are not of absolute necessity for the helper thread to achieve it tasks. Hence helper threads runs
ahead of main thread. Hence helper threads run ahead of main thread. Hence helper threads can do
computations that are necessary to decide the direction of the branch. This will inturn remove branch
mispredictions which may occur when branch predictions are used.

Prefetching of Data
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
the data and places it in the nearest cache accessible to the main thread. This avoids most of the L1 cache
misses that would have been encountered by the main thread had if helper thread was not present. As the
memory latency is reduced, the execution of main thread speeds up.

Memory Bug Reduction:
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
and exist in differnt modules or source code files. Compilers are of little help becuase it fails to
disambiguate pointers. Hence, in practice memory bug detection relies on run time checkers that insert
monitor code to the application during testing. In CMPs, the program which detects the memory bugs can run
as a helper thread.

Ex: Heapmon, a memory bug checker monitors application heap space to detect heap memory bugs. The memory
access events in the application thread are automatically forwarded to helper thread using appropriate
hardware mechanisms. Also the redundant and unnecessary memory accessess are filtered out. Hence the helper
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.

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 is developed at North Carolina State University.
Slipstream execution provides a simple means to use a second processor in a CMP to accelerate a single program.Slipstream execution involves running two redundant copies of the program. A significant number of dynamic instructions are speculatively removed from one of the program copies, without sacrificing its ability to make correct forward progress. The second program verifies the forward progress of the first and is also sped up in the process.

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.

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.

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:42:35Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:39:57Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:33:09Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:32:49Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:32:18Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:31:59Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:31:14Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:30:39Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:28:46Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki2 helperThreads

2007-11-28T15:25:44Z

Lreddy:

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:48:10Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===
'''Communicationa and replication are inherently related.To be clear on the relationship of communication and replication, it is important to distinguish several concepts. When a program performs a write, it binds a data value to an address. The data resides in some physical storage element in the machine. A data transfer occurs whenever data in one storage element is transferred into another. This doesnot necessarily change the bindings of the addresses and values. The same data may reside in multiple physical locations as it does in the uniprosessor storage heirarchy, but the one nearest to the processor is the only one that the processor can observe. If it is updated, the other hidden replicas including the actual memory location, must eventually be updated.Copying data binds a new set of addresses to the sane set of values. Generally, this will cause data transfers.Once the copy has been made, the two sets of bindings are completely independent.Hence, Replication is the creation of a local copy of data to help enable parallelism. Replication helps to avoid unnecessary communication. '''

'''Communication occurs when data written from one process is read by another process. This may cause data transfer within the machine, either on the write or the read,or the data transfer may occur for other reasons.Communication may involve establishing a new binding or not doing so, depending on the particular communication abstraction.'''

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 
'''4.Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''
'''5.Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''
'''6.Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

'''In the context of parallel computers, communication and synchonisation between the processors become very important considerations.The communication between the processors that occurs mostly in the form of data transfers between the processors. So, the performance of a parallel computer is modeled considering the follwoing criteria'''

=== 1.Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

'''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.'''

===2.Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===3.Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

''' Frequency of Communication = Number of communications per unit of work '''
''' Communication Time = Overhead + Occupancy + Network Delay '''
''' Overlap = The portion of the communication operation that is performed concurrently with other useful work. '''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:44:22Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===
'''Communicationa and replication are inherently related.To be clear on the relationship of communication and replication, it is important to distinguish several concepts. When a program performs a write, it binds a data value to an address. The data resides in some physical storage element in the machine. A data transfer occurs whenever data in one storage element is transferred into another. This doesnot necessarily change the bindings of the addresses and values. The same data may reside in multiple physical locations as it does in the uniprosessor storage heirarchy, but the one nearest to the processor is the only one that the processor can observe. If it is updated, the other hidden replicas including the actual memory location, must eventually be updated.Copying data binds a new set of addresses to the sane set of values. Generally, this will cause data transfers.Once the copy has been made, the two sets of bindings are completely independent.Hence, Replication is the creation of a local copy of data to help enable parallelism. Replication helps to avoid unnecessary communication. '''

'''Communication occurs when data written from one process is read by another process. This may cause data transfer within the machine, either on the write or the read,or the data transfer may occur for other reasons.Communication may involve establishing a new binding or not doing so, depending on the particular communication abstraction.'''

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 
'''4.Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''
'''5.Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''
'''6.Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

'''In the context of parallel computers, communication and synchonisation between the processors become very important considerations.The communication between the processors that occurs mostly in the form of data transfers between the processors. So, the performance of a parallel computer is modeled considering the follwoing criteria'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

'''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.'''

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

''' Frequency of Communication = Number of communications per unit of work '''
''' Communication Time = Overhead + Occupancy + Network Delay '''
''' Overlap = The portion of the communication operation that is performed concurrently with other useful work. '''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:40:31Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===
'''Communicationa and replication are inherently related.To be clear on the relationship of communication and replication, it is important to distinguish several concepts. When a program performs a write, it binds a data value to an address. The data resides in some physical storage element in the machine. A data transfer occurs whenever data in one storage element is transferred into another. This doesnot necessarily change the bindings of the addresses and values. The same data may reside in multiple physical locations as it does in the uniprosessor storage heirarchy, but the one nearest to the processor is the only one that the processor can observe. If it is updated, the other hidden replicas including the actual memory location, must eventually be updated.Copying data binds a new set of addresses to the sane set of values. Generally, this will cause data transfers.Once the copy has been made, the two sets of bindings are completely independent.Hence, Replication is the creation of a local copy of data to help enable parallelism. Replication helps to avoid unnecessary communication. '''

'''Communication occurs when data written from one process is read by another process. This may cause data transfer within the machine, either on the write or the read,or the data transfer may occur for other reasons.Communication may involve establishing a new binding or not doing so, depending on the particular communication abstraction.'''

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 
'''4.Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''
'''5.Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''
'''6.Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

'''In the context of parallel computers, communication and synchonisation between the processors become very important considerations.The communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

'''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.'''

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

''' Frequency of Communication = Number of communications per unit of work '''
''' Communication Time = Overhead + Occupancy + Network Delay '''
''' Overlap = The portion of the communication operation that is performed concurrently with other useful work. '''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:39:29Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===
'''Communicationa and replication are inherently related.To be clear on the relationship of communication and replication, it is important to distinguish several concepts. When a program performs a write, it binds a data value to an address. The data resides in some physical storage element in the machine. A data transfer occurs whenever data in one storage element is transferred into another. This doesnot necessarily change the bindings of the addresses and values. The same data may reside in multiple physical locations as it does in the uniprosessor storage heirarchy, but the one nearest to the processor is the only one that the processor can observe. If it is updated, the other hidden replicas including the actual memory location, must eventually be updated.Copying data binds a new set of addresses to the sane set of values. Generally, this will cause data transfers.Once the copy has been made, the two sets of bindings are completely independent.Hence, Replication is the creation of a local copy of data to help enable parallelism. Replication helps to avoid unnecessary communication. '''

'''Communication occurs when data written from one process is read by another process. This may cause data transfer within the machine, either on the write or the read,or the data transfer may occur for other reasons.Communication may involve establishing a new binding or not doing so, depending on the particular communication abstraction.'''

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 
'''4.Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''
'''5.Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''
'''6.Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

'''In the context of parallel computers, communication and synchonisation between the processors become very important considerations.The communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

'''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.'''

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

''' Frequency of Communication = Number of communications per unit of work '''
''' Communication Time = Overhead + Occupancy + Network Delay '''
''' Overlap = The portion of the communication operation that is performed concurrently with other useful work. '''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===Terminology:===

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:34:33Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===
'''Communicationa and replication are inherently related.To be clear on the relationship of communication and replication, it is important to distinguish several concepts. When a program performs a write, it binds a data value to an address. The data resides in some physical storage element in the machine. A data transfer occurs whenever data in one storage element is transferred into another. This doesnot necessarily change the bindings of the addresses and values. The same data may reside in multiple physical locations as it does in the uniprosessor storage heirarchy, but the one nearest to the processor is the only one that the processor can observe. If it is updated, the other hidden replicas including the actual memory location, must eventually be updated.Copying data binds a new set of addresses to the sane set of values. Generally, this will cause data transfers.Once the copy has been made, the two sets of bindings are completely independent.Hence, Replication is the creation of a local copy of data to help enable parallelism. Replication helps to avoid unnecessary communication. '''

'''Communication occurs when data written from one process is read by another process. This may cause data transfer within the machine, either on the write or the read,or the data transfer may occur for other reasons.Communication may involve establishing a new binding or not doing so, depending on the particular communication abstraction.'''

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

'''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.'''

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

''' Frequency of Communication = Number of communications per unit of work '''
''' Communication Time = Overhead + Occupancy + Network Delay '''
''' Overlap = The portion of the communication operation that is performed concurrently with other useful work. '''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===Terminology:===

'''Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''

'''Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''

'''Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:32:35Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===
'''Communicationa and replication are inherently related.To be clear on the relationship of communication and replication, it is important to distinguish several concepts. When a program performs a write, it binds a data value to an address. The data resides in some physical storage element in the machine. A data transfer occurs whenever data in one storage element is transferred into another. This doesnot necessarily change the bindings of the addresses and values. The same data may reside in multiple physical locations as it does in the uniprosessor storage heirarchy, but the one nearest to the processor is the only one that the processor can observe. If it is updated, the other hidden replicas including the actual memory location, must eventually be updated.Copying data binds a new set of addresses to the sane set of values. Generally, this will cause data transfers.Once the copy has been made, the two sets of bindings are completely independent.Hence, Replication is the creation of a local copy of data to help enable parallelism. Replication helps to avoid unnecessary communication. '''

'''Communication occurs when data written from one process is read by another process. This may cause data transfer within the machine, either on the write or the read,or the data transfer may occur for other reasons.Communication may involve establishing a new binding or not doing so, depending on the particular communication abstraction.'''

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

'''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.'''

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===Terminology:===

'''Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''

'''Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''

'''Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:31:44Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===
'''Communicationa and replication are inherently related.To be clear on the relationship of communication and replication, it is important to distinguish several concepts. When a program performs a write, it binds a data value to an address. The data resides in some physical storage element in the machine. A data transfer occurs whenever data in one storage element is transferred into another. This doesnot necessarily change the bindings of the addresses and values. The same data may reside in multiple physical locations as it does in the uniprosessor storage heirarchy, but the one nearest to the processor is the only one that the processor can observe. If it is updated, the other hidden replicas including the actual memory location, must eventually be updated.Copying data binds a new set of addresses to the sane set of values. Generally, this will cause data transfers.Once the copy has been made, the two sets of bindings are completely independent.Hence, Replication is the creation of a local copy of data to help enable parallelism. Replication helps to avoid unnecessary communication. '''

Communication occurs when data written from one process is read by another process. This may cause data transfer within the machine, either on the write or the read,or the data transfer may occur for other reasons.Communication may involve establishing a new binding or not doing so, depending on the particular communication abstraction.

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

'''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.'''

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===Terminology:===

'''Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''

'''Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''

'''Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:30:41Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===
'''Communicationa and replication are inherently related.To be clear on the relationship of communication and replication, it is important to distinguish several concepts. When a program performs a write, it binds a data value to an address. The data resides in some physical storage element in the machine. A data transfer occurs whenever data in one storage element is transferred into another. This doesnot necessarily change the bindings of the addresses and values. The same data may reside in multiple physical locations as it does in the uniprosessor storage heirarchy, but the one nearest to the processor is the only one that the processor can observe. If it is updated, the other hidden replicas including the actual memory location, must eventually be updated.Copying data binds a new set of addresses to the sane set of values. Generally, this will cause data transfers.Once the copy has been made, the two sets of bindings are completely independent.Hence, Replication is the creation of a local copy of data to help enable parallelism. Replication helps to avoid unnecessary communication. '''

Communication occurs when data written from one process is read by another process. This may cause data transfer within the machine, either on the write or the read,or the data transfer may occur for other reasons.Communication may involve establishing a new binding or not doing so, depending on the particular communication abstraction.

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===Terminology:===

'''Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''

'''Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''

'''Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T02:06:55Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Communication and Replication ===

'''Communication occurs when data written from one process is read by another process. '''

''' Replication helps to avoid unnecessary communication.''' 

'''Replication is the creation of a local copy of data to help enable parallelism.''' 

'''

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

''This is a very convinient model, and it is used to describe a diverse collection of operations, including messages, memory accesses, bus transactions, and vector operations. For message passing, the start up cost can be thought of as the time for the first bit to get to the destination. For memory operations, it is essentially the access time. For bus transactions, it reflects the bus arbitration and command phases. For any sort of pipelinedoperation, including pipelined instruction processing or vector operations, it is the time to fill the pipeline.

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist. The essential components of this operation can be described by the following simple model. This model is very generic and can be used to explain data transfers in many places in modern, highly pipelined computer systems.:''' 

'''Communication Time = Overhead+Occupancy+Network Delay'''

'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.The key point is that this is time the processor is busy with the communication event; it cannot do other useful work to initiate other communication during this time. Thr ramaining portion of the communication time is considered as network latency; it is the part that can be hidden by other processor operations'''

'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path.The data wol occupy oyher resources, including buffers,switches, and the communication assist. Often the communication assist is the bottleneck that determines the occupancy. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. If there is buffering between the processor and the bottleneck, the processor may be able to issue a burst of transfers at a frequency greater than I/O occupancy; however, once this buffer is full, the processor must slow to the rate set by the occupancy. A new transfer can start only when an older one finishes'''

'''The remaining communication time is lumped into the network dealy,which includes the time for the bit to be routed across the actual network as well as many other factors, such as the time to get through communication assists.

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

'''Frequency of communication depends on many programming factors and many hardware design factors.In particular, hardware may limit the transfer size and thereby determine the minimum number of messages. It may automatically replicate data or migrate it to where it is used. However, a certain amount of communication is inherent to parallel execution since data must be shared and processors must coordinate their work. In general, for a machine to support programs with a high communication frequency, the other parts of the communication cost equation must be small - low overhead, low network delay, and small occupancy.'''

'''The overlap is the portion of the communication coperation that is performed caoncurrently with other useful work, including computation or other communication time. The reduction of the effective cost is possible because much of the communication time involves work done by the components of the system other than the processor such as the communication assist, the bus, the network, or the remote processor or memory.Overlapping communicationw ith oether work is a form of small-scale parallelism, as is the instruction-level parallelism exploited by fast microprocessors.In effect, some available parallelism will be invested to hide the actual cost of communication.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===Terminology:===

'''Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''

'''Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''

'''Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-11T01:16:34Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Replication: ===

'''Replication is the creation of a local copy of data to help enable parallelism.''' 

===Communication: ===

'''Communication occurs when data written from one process is read by another process. Replication helps to avoid unnecessary communication.''' 

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist''' 
'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.'''
'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. '''

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===Terminology:===

'''Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''

'''Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''

'''Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-10T23:39:51Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Replication: ===

'''Replication is the creation of a local copy of data to help enable parallelism.''' 

===Communication: ===

'''Communication occurs when data written from one process is read by another process. Replication helps to avoid unnecessary communication.''' 

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist''' 
'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.'''
'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. '''

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

===BSP Model:===

'''Bulk Synchronization Parallel Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''
 
'''There are other similar variations of BSP like LogP '''

===Terminology:===

'''Saturation Point: In performance of a parallel system there is a point that is reached where the system can not keep up with the load on it. At this point response times will go to infinity. This point is where the load on the system completely utilizes the most scarce resource, often the cpu. '''
'''Scaleability: Often a parallel system is not rated by its speed alone, but instead based on how it performes with varying loads. A system that is scaleable will have a gradual increase in response times untill it reaches saturation. '''
'''Load: The load on a parallel system is the measure of the work/time that is required of the system. It is relative to the number of actions taking place as well as the time between those actions and the complexity of each action. '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-10T23:22:36Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Replication: ===

'''Replication is the creation of a local copy of data to help enable parallelism.''' 

===Communication: ===

'''Communication occurs when data written from one process is read by another process. Replication helps to avoid unnecessary communication.''' 

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist''' 
'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.'''
'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. '''

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

===BSP Model:===

'''Bulk Synchronization Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''

===LogP Model:===

'''L is a maximum on the latency '''
'''o is the overhead of transmission or reception '''
'''g is the minimum time between consectutive messages '''
'''P is the number of processors '''

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-10T23:18:02Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Replication: ===

'''Replication is the creation of a local copy of data to help enable parallelism.''' 

===Communication: ===

'''Communication occurs when data written from one process is read by another process. Replication helps to avoid unnecessary communication.''' 

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist''' 
'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.'''
'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. '''

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

===BSP Model:===

'''Bulk Synchronization Model: '''
'''The BSP model is a series of supersteps. '''
'''A superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''

===LogP Model:===

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf

CSC/ECE 506 Fall 2007/wiki1 1.3.3 1.3.4 chase2007

2007-09-10T23:17:19Z

Lreddy:

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Communication and Replication (section 1.3.3)'''==

===Replication: ===

'''Replication is the creation of a local copy of data to help enable parallelism.''' 

===Communication: ===

'''Communication occurs when data written from one process is read by another process. Replication helps to avoid unnecessary communication.''' 

=='''Introduction to Parallel Computer Architecture ->Fundamental Design Issues -> Performance (section 1.3.4)'''==

===Computer Performance: ===

'''Computer performance is a measure of the output of a computer with with respect to time and resources used.''' 

===Performance metrics:===

'''Following are the important metrics used to measure a computer's performance:'''

'''1.Latency:''' '''The time taken to perform an operation''' 
'''2.Bandwidth:''''''The rate at which the operations are performed''' 
'''3.Cost:''' '''The impact these operations have on the execution time of the program''' 

'''All the above metrics can be used to define a uniprocessor systems where a single CPU operates.'''

'''However, in the context of parallel computers, it becomes difficult to express the performance in above stated metrics. The reason for this is the communication between the processors that occurs mostly in the form of data transfers between the processors. So, to completely define the performace of a parallel computer, the following metrics are also considered.'''

===Data Transfer Time:===
'''It is the time taken for initiation of a data transfer and the time required for actual data transfer. So the Data Transfer Time can be given as:'''

'''Transfer Time (n) = T+(n/B)''' 
'''where''' 
'''n = Amount of Data (in bytes)''' 
'''B = Transfer Rate of the component moving the data (bytes per second)''' 
'''T = Start up cost, a constant''' 

===Overhead and Occupancy:===

'''The data transfer operations are initiated by the processor through communication assist''' 
'''The overhead is the time the processor spends initiating the transfer of data. This may be a fixed cost, if the processor imply has to tell the communication assist to start. The overhead can also be linear with Tranfer time, if the processor has to copy the data into the assist.'''
'''The occupancy is the time it takes for the data to pass through the slowest componant on the communication path. The occupancy limits how frequently communication operations can be initiated.The next data transfer will have to wait untill the critical resource is no longer occupied before it can use the same resource. '''

===Communication Cost:===

'''It is the time that the processor spends in communicating with other processors. It can be given by the following:'''

'''Communication Cost = Frequency of Communication * (Communication Time - Overlap)'''

'''Frequency of Communication = Number of communications per unit of work'''
'''Communication Time = Overhead + Occupancy + Network Delay'''
'''Overlap = The portion of the communication operation that is performed concurrently with other useful work.'''

===BSP Model:===

'''Bulk Synchronization Model: '''
'''The BSP model is a series of supersteps. superstep on a BSP machine is given by W + G*H + L '''
'''W is the maximum possible work for a given processor '''
'''H is the maximum bytes sent or recieved by a processor '''
'''G is the number of available processors '''
'''L is the time required for the barrier synchronization '''

===LogP Model:===

===References:===
'''Parallel Computer Architecture- A Hardware/Software Approach by David E Culler, Jaswinder Pal Singh and Anoop Guptha''' 

http://en.wikipedia.org/wiki/Computer_performance

The BSP Model
http://wwwcs.uni-paderborn.de/fachbereich/AG/agmadh/WWW/bono/paper/nestedbsp/node6.html

LogP: Towards a Realistic Model of Parallel Computation
http://cs315b-wiki.stanford.edu/images/8/8b/Logp.pdf