Expertiza_Wiki - User contributions [en]

CSC/ECE 506 Spring 2010/ch 9

2010-04-28T23:02:27Z

Pwlane:

In addition to a proper cache coherency model, it is also important for a multiprocessor system to provide support at the hardware level for synchronization. The most common types of synchronization are locks and barriers, which are discussed in this chapter.

= Lock Implementations =

Locks are an important concept when programming for multi core systems. The basic concept of a lock is to protect the code inside the lock. That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering. This can be accomplished in a variety of ways of varying complexity and performance.

== Performance Evaluation ==

The Solihin text gives 4 methods to determine the performance of a lock implementation.

*Acquisition Latency - How much time does it take to acquire the lock?

*Traffic - How much bus traffic is generated by threads attempting to acquire the lock?

*Fairness - FIFO vs. Luck

*Storage - How much storage is needed compared to the number of threads?

== Atomic Instructions ==

Since a multiprocessor system cannot disable interupts as an effective method to execute a bit of code atomically, there must be hardware support for atomic operations. [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

Being able to execute an atomic instruction is a requirement for most lock implementations. It is important that when a processor attempts to set a lock either the lock is fully set and the thread is able to enter into the critical section, or the lock is not set, and it appears that none of the instructions required to set the lock have executed.

In the x86 instruction set the opcode CMPXCHG (meaning compare and exchange) can be used in a lock implementation in order to guarantee atomicity. This function works by sending a destination and a source. The accumulator is compared to the destination and if they are equal loaded with the source. If they are NOT equal the accumulator is loaded with the destination value. In order to assure that this is executed atomically the opcode must be issued with the LOCK prefix. This is useful in implementing some locks, such as ticket locks. [http://faydoc.tripod.com/cpu/cmpxchg.htm]

== Hand-off Lock ==

Another type of lock that is not discussed in the text is known as the "Hand-off" lock. In this lock the first thread acquires the lock if no other thread is currently locked (since it is the first thread). When another thread attempts to gain the lock it will see that the lock is in use and adds itself to the queue. Once done this thread can sleep until called by the thread with the lock. Once the thread in the lock is finished, it will pass the lock to the next thread in the queue. [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]

== Avoiding Locks ==

There are many reasons why a programmer should attempt to write programs in such a way as to avoid locks if possible. There are many problems that can arise with the use of locks. [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

One of the must well known issue is deadlock. This can occur when the threads are waiting to acquire the lock, but the lock will never be unlocked. For example if 2 threads are both spinning on a lock that is locked, they will continue to spin forever, as each thread 'thinks' that the other is inside the critical section.

Another problem with using locks is that the performance is not optimal, as often a lock is used when there is only a chance of conflict. This approach to programming yields slower performance than what might be possible with other methods. This also leads to questions of granularity, that is how much of the code should be protected under the critical section. The programmer must decide between many small (fine grain) locks or fewer, more encompassing locks. This decision can greatly effect the performance of the program. Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

= Barrier Implementations =

In many ways, barriers are simpler than locks. A barrier simply is a point in a program where one or more threads must reach before the parallel program is allowed to continue. When using barriers a programmer does not have to be concerned with advanced topics such as fairness, that are required when programming for locks.

== Performance Evaluation ==

The Solihin text gives 2 metrics for which the performance of a barrier implementation should be evaluated.

*Latency - The time required to enter and exit a barrier.

*Traffic - Communications overhead required by the barrier.

== Sense-Reversal Barrier ==

This barrier is a centralized barrier where a single count variable protected by a lock is shared among all the threads. Each thread on reaching the barrier increments its value and waits till the value of variable has reached the number of threads for which barrier was implemented.

Since all the threads are spinning around a single variable the miss rate is scales quadratically with number of processors.

[[Image:Ch9wiki01.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Combining Tree Barrier ==

This barrier is a distributed barrier where group of processors form clusters and updates value of a local variable. The local variable on reaching a value equal to number of threads updating it, proceeds to increment another variable higher in hierarchy in the combining tree. When the variable in the highest level of hierarchy in the combining tree reaches its max value it is considered that all the threads have reached the barrier and synchronization is complete.

Since in this case all the threads are updated local variables in form of smaller groups the miss rate is not as high as sense-reversal barrier.

The diagram below shows the operation of combining tree barrier with threads grouped in two groups. The variables C0 and C1 are local to each group and C2 is the variable that is at higher level of hierarchy in the tree.

[[Image:Ch9wiki02.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Tournament Barrier ==

In tournament barrier the threads are considered to be leaves at the end of a binary tree and each node represents a flag. Two threads compete with each other and the looser thread is allowed to set the flag and move to higher level and compete to loose with the looser thread from other section of binary tree. Thus the thread which completes last is able to set the highest flag in the binary tree. On setting the flag it indicates to all the threads that barrier has been completed and thus synchronization is achieved.

[[Image:Ch9wiki03.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Disseminating Barrier ==

In this barrier each thread maintains a record of the activity of other threads. For every round i with n threads, thread A notifies thread (A + 2i) mod n. Thus after logn rounds all the threads are aware of the status of every other thread running and whether it has reached the barrier.

[[Image:Ch9wiki04.png]]
[http://www.cs.brown.edu/courses/cs176/barrier.ppt]

== Performance Comparison ==

Additive Schwarz Preconditioned Conjugate Gradient (ASPCG) kernal on Altix System

[[Image:Ch9wiki05.png]]

Figure shows the timings of the ASPCG kernel using the different barrier implementations. It can be seen that the blocking barrier does not scale with number of threads as with increase in number of threads the contention increases. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

EPCC Microbenchmark

[[Image:Ch9wiki06.png]]

Figure shows the timings to implement a barrier of the EPCC Microbenchmark using the different barrier implementations. It can be seen that the blocking barrier/centralized blocking barrier does not scale with number of threads as with increase in number of threads the contention increases. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

= References =

* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.
* CMPXCHG - Compare and Exchange [http://faydoc.tripod.com/cpu/cmpxchg.htm]
* Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]
* www.cs.duke.edu/~chase/cps110/slides/threads3.ppt [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
* Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]
* Barrier Synchronization in Java, Carwyn Ball and Mark Bull [http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]
* www.cs.brown.edu/courses/cs176/barrier.ppt [http://www.cs.brown.edu/courses/cs176/barrier.ppt]
* Scalability evaluation of barrier algorithms for OpenMP [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

CSC/ECE 506 Spring 2010/ch 9

2010-04-28T22:57:19Z

Pwlane:

In addition to a proper cache coherency model, it is also important for a multiprocessor system to provide support at the hardware level for synchronization. The most common types of synchronization are locks and barriers, which are discussed in this chapter.

= Lock Implementations =

Locks are an important concept when programming for multi core systems. The basic concept of a lock is to protect the code inside the lock. That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering. This can be accomplished in a variety of ways of varying complexity and performance.

== Performance Evaluation ==

The Solihin text gives 4 methods to determine the performance of a lock implementation.

*Acquisition Latency - How much time does it take to acquire the lock?

*Traffic - How much bus traffic is generated by threads attempting to acquire the lock?

*Fairness - FIFO vs. Luck

*Storage - How much storage is needed compared to the number of threads?

== Atomic Instructions ==

Since a multiprocessor system cannot disable interupts as an effective method to execute a bit of code atomically, there must be hardware support for atomic operations. [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

Being able to execute an atomic instruction is a requirement for most lock implementations. It is important that when a processor attempts to set a lock either the lock is fully set and the thread is able to enter into the critical section, or the lock is not set, and it appears that none of the instructions required to set the lock have executed.

In the x86 instruction set the opcode CMPXCHG (meaning compare and exchange) can be used in a lock implementation in order to guarantee atomicity. This function works by sending a destination and a source. The accumulator is compared to the destination and if they are equal loaded with the source. If they are NOT equal the accumulator is loaded with the destination value. In order to assure that this is executed atomically the opcode must be issued with the LOCK prefix. This is useful in implementing some locks, such as ticket locks. [http://faydoc.tripod.com/cpu/cmpxchg.htm]

== Hand-off Lock ==

Another type of lock that is not discussed in the text is known as the "Hand-off" lock. In this lock the first thread acquires the lock if no other thread is currently locked (since it is the first thread). When another thread attempts to gain the lock it will see that the lock is in use and adds itself to the queue. Once done this thread can sleep until called by the thread with the lock. Once the thread in the lock is finished, it will pass the lock to the next thread in the queue. [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]

== Avoiding Locks ==

There are many reasons why a programmer should attempt to write programs in such a way as to avoid locks if possible. There are many problems that can arise with the use of locks. [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

One of the must well known issue is deadlock. This can occur when the threads are waiting to acquire the lock, but the lock will never be unlocked. For example if 2 threads are both spinning on a lock that is locked, they will continue to spin forever, as each thread 'thinks' that the other is inside the critical section.

Another problem with using locks is that the performance is not optimal, as often a lock is used when there is only a chance of conflict. This approach to programming yields slower performance than what might be possible with other methods. This also leads to questions of granularity, that is how much of the code should be protected under the critical section. The programmer must decide between many small (fine grain) locks or fewer, more encompassing locks. This decision can greatly effect the performance of the program. Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

= Barrier Implementations =

== Sense-Reversal Barrier ==

This barrier is a centralized barrier where a single count variable protected by a lock is shared among all the threads. Each thread on reaching the barrier increments its value and waits till the value of variable has reached the number of threads for which barrier was implemented.

Since all the threads are spinning around a single variable the miss rate is scales quadratically with number of processors.

[[Image:Ch9wiki01.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Combining Tree Barrier ==

This barrier is a distributed barrier where group of processors form clusters and updates value of a local variable. The local variable on reaching a value equal to number of threads updating it, proceeds to increment another variable higher in hierarchy in the combining tree. When the variable in the highest level of hierarchy in the combining tree reaches its max value it is considered that all the threads have reached the barrier and synchronization is complete.

Since in this case all the threads are updated local variables in form of smaller groups the miss rate is not as high as sense-reversal barrier.

The diagram below shows the operation of combining tree barrier with threads grouped in two groups. The variables C0 and C1 are local to each group and C2 is the variable that is at higher level of hierarchy in the tree.

[[Image:Ch9wiki02.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Tournament Barrier ==

In tournament barrier the threads are considered to be leaves at the end of a binary tree and each node represents a flag. Two threads compete with each other and the looser thread is allowed to set the flag and move to higher level and compete to loose with the looser thread from other section of binary tree. Thus the thread which completes last is able to set the highest flag in the binary tree. On setting the flag it indicates to all the threads that barrier has been completed and thus synchronization is achieved.

[[Image:Ch9wiki03.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Disseminating Barrier ==

In this barrier each thread maintains a record of the activity of other threads. For every round i with n threads, thread A notifies thread (A + 2i) mod n. Thus after logn rounds all the threads are aware of the status of every other thread running and whether it has reached the barrier.

[[Image:Ch9wiki04.png]]
[http://www.cs.brown.edu/courses/cs176/barrier.ppt]

== Performance Comparison ==

Additive Schwarz Preconditioned Conjugate Gradient (ASPCG) kernal on Altix System

[[Image:Ch9wiki05.png]]

Figure shows the timings of the ASPCG kernel using the different barrier implementations. It can be seen that the blocking barrier does not scale with number of threads as with increase in number of threads the contention increases. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

EPCC Microbenchmark

[[Image:Ch9wiki06.png]]

Figure shows the timings to implement a barrier of the EPCC Microbenchmark using the different barrier implementations. It can be seen that the blocking barrier/centralized blocking barrier does not scale with number of threads as with increase in number of threads the contention increases. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

= References =

* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.
* CMPXCHG - Compare and Exchange [http://faydoc.tripod.com/cpu/cmpxchg.htm]
* Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]
* www.cs.duke.edu/~chase/cps110/slides/threads3.ppt [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
* Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]
* Barrier Synchronization in Java, Carwyn Ball and Mark Bull [http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]
* www.cs.brown.edu/courses/cs176/barrier.ppt [http://www.cs.brown.edu/courses/cs176/barrier.ppt]
* Scalability evaluation of barrier algorithms for OpenMP [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

CSC/ECE 506 Spring 2010/ch 9

2010-04-26T21:49:33Z

Pwlane:

In addition to a proper cache coherency model, it is also important for a multiprocessor system to provide support at the hardware level for synchronization. The most common types of synchronization are locks and barriers, which are discussed in this chapter.

= Lock Implementations =

Locks are an important concept when programming for multi core systems. The basic concept of a lock is to protect the code inside the lock. That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering. This can be accomplished in a variety of ways of varying complexity and performance.

== Performance Evaluation

The Solihin text gives 4 methods to determine the performance of a lock implementation.

*Acquisition Latency - How much time does it take to acquire the lock?

*Traffic - How much bus traffic is generated by threads attempting to acquire the lock?

*Fairness - FIFO vs. Luck

*Storage - How much storage is needed compared to the number of threads?

== Atomic Instructions ==

Since a multiprocessor system cannot disable interupts as an effective method to execute a bit of code atomically, there must be hardware support for atomic operations. [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

Being able to execute an atomic instruction is a requirement for most lock implementations. It is important that when a processor attempts to set a lock either the lock is fully set and the thread is able to enter into the critical section, or the lock is not set, and it appears that none of the instructions required to set the lock have executed.

In the x86 instruction set the opcode CMPXCHG (meaning compare and exchange) can be used in a lock implementation in order to guarantee atomicity. This function works by sending a destination and a source. The accumulator is compared to the destination and if they are equal loaded with the source. If they are NOT equal the accumulator is loaded with the destination value. In order to assure that this is executed atomically the opcode must be issued with the LOCK prefix. This is useful in implementing some locks, such as ticket locks. [http://faydoc.tripod.com/cpu/cmpxchg.htm]

== Hand-off Lock ==

Another type of lock that is not discussed in the text is known as the "Hand-off" lock. In this lock the first thread acquires the lock if no other thread is currently locked (since it is the first thread). When another thread attempts to gain the lock it will see that the lock is in use and adds itself to the queue. Once done this thread can sleep until called by the thread with the lock. Once the thread in the lock is finished, it will pass the lock to the next thread in the queue. [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]

== Avoiding Locks ==

There are many reasons why a programmer should attempt to write programs in such a way as to avoid locks if possible. There are many problems that can arise with the use of locks. [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

One of the must well known issue is deadlock. This can occur when the threads are waiting to acquire the lock, but the lock will never be unlocked. For example if 2 threads are both spinning on a lock that is locked, they will continue to spin forever, as each thread 'thinks' that the other is inside the critical section.

Another problem with using locks is that the performance is not optimal, as often a lock is used when there is only a chance of conflict. This approach to programming yields slower performance than what might be possible with other methods. This also leads to questions of granularity, that is how much of the code should be protected under the critical section. The programmer must decide between many small (fine grain) locks or fewer, more encompassing locks. This decision can greatly effect the performance of the program. Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

= Barrier Implementations =

== Sense-Reversal Barrier ==

This barrier is a centralized barrier where a single count variable protected by a lock is shared among all the threads. Each thread on reaching the barrier increments its value and waits till the value of variable has reached the number of threads for which barrier was implemented.

Since all the threads are spinning around a single variable the miss rate is scales quadratically with number of processors.

[[Image:Ch9wiki01.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Combining Tree Barrier ==

This barrier is a distributed barrier where group of processors form clusters and updates value of a local variable. The local variable on reaching a value equal to number of threads updating it, proceeds to increment another variable higher in hierarchy in the combining tree. When the variable in the highest level of hierarchy in the combining tree reaches its max value it is considered that all the threads have reached the barrier and synchronization is complete.

Since in this case all the threads are updated local variables in form of smaller groups the miss rate is not as high as sense-reversal barrier.

The diagram below shows the operation of combining tree barrier with threads grouped in two groups. The variables C0 and C1 are local to each group and C2 is the variable that is at higher level of hierarchy in the tree.

[[Image:Ch9wiki02.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Tournament Barrier ==

In tournament barrier the threads are considered to be leaves at the end of a binary tree and each node represents a flag. Two threads compete with each other and the looser thread is allowed to set the flag and move to higher level and compete to loose with the looser thread from other section of binary tree. Thus the thread which completes last is able to set the highest flag in the binary tree. On setting the flag it indicates to all the threads that barrier has been completed and thus synchronization is achieved.

[[Image:Ch9wiki03.png]]
[http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]

== Disseminating Barrier ==

In this barrier each thread maintains a record of the activity of other threads. For every round i with n threads, thread A notifies thread (A + 2i) mod n. Thus after logn rounds all the threads are aware of the status of every other thread running and whether it has reached the barrier.

[[Image:Ch9wiki04.png]]
[http://www.cs.brown.edu/courses/cs176/barrier.ppt]

== Performance Comparison ==

Additive Schwarz Preconditioned Conjugate Gradient (ASPCG) kernal on Altix System

[[Image:Ch9wiki05.png]]

Figure shows the timings of the ASPCG kernel using the different barrier implementations. It can be seen that the blocking barrier does not scale with number of threads as with increase in number of threads the contention increases. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

EPCC Microbenchmark

[[Image:Ch9wiki06.png]]

Figure shows the timings to implement a barrier of the EPCC Microbenchmark using the different barrier implementations. It can be seen that the blocking barrier/centralized blocking barrier does not scale with number of threads as with increase in number of threads the contention increases. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

= References =

* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.
* CMPXCHG - Compare and Exchange [http://faydoc.tripod.com/cpu/cmpxchg.htm]
* Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]
* www.cs.duke.edu/~chase/cps110/slides/threads3.ppt [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
* Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]
* Barrier Synchronization in Java, Carwyn Ball and Mark Bull [http://www.ukhec.ac.uk/publications/reports/synch_java.pdf]
* www.cs.brown.edu/courses/cs176/barrier.ppt [http://www.cs.brown.edu/courses/cs176/barrier.ppt]
* Scalability evaluation of barrier algorithms for OpenMP [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]

File:Ch9wiki06.png

2010-04-26T21:40:04Z

Pwlane:

File:Ch9wiki05.png

2010-04-26T21:39:53Z

Pwlane:

File:Ch9wiki04.png

2010-04-26T21:39:38Z

Pwlane:

File:Ch9wiki03.png

2010-04-26T21:39:25Z

Pwlane:

File:Ch9wiki02.png

2010-04-26T21:39:13Z

Pwlane:

File:Ch9wiki01.png

2010-04-26T21:39:00Z

Pwlane:

CSC/ECE 506 Spring 2010/ch 9

2010-04-26T18:25:10Z

Pwlane:

CSC/ECE 506 Spring 2010/ch 9

2010-04-26T18:24:31Z

Pwlane:

CSC/ECE 506 Spring 2010/ch 9

2010-04-26T18:24:15Z

Pwlane:

CSC/ECE 506 Spring 2010/ch 7 pl/

2010-04-05T20:05:44Z

Pwlane: /* Other Methods */

Shared-memory multiprocessors run into several problems that are more pronounced than their uniprocessor counterparts. The Solihin text used in this course goes into detail on three of these issues, that is cache coherence, memory consistency and synchronization. It is the goal of this wiki supplement to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

{{{
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
}}}

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in its cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example (load A, store A) --> (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

== Open MP ==
The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

== Fence Insertion ==

One method that is commonly used on production shared memory systems and microprocessors it the insertion of fences. These fences can be used by the programmer to force the chip to perform a synchronization, or wait until "all previous memory operations of the processor are guaranteed to have completed" [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790] Fence insertion is a method giving the programmer (or compiler) control over the hardware's default ordering of memory operations (such as sequential consistency, processor consistency, weak ordering, etc). It is important from a performance standpoint that the complier be able to quickly and efficiently insert fences automatically, and the algorithms used for this automatic insertion have a large bearing on performance. [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

=== Instructions used for fence operations ===
*SPARC V8 > store barrier
*SPARC V9 > MEMBAR
*Alpha > memory barrier and write memory barrier
*MIPS / PPC > sync
*Intel x86 > lfence (load) sfence (store)

Taken from [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

== Other Methods ==

There are many other ways to implement synchronization directives as well. This ACM article [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf] discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them. The programmer (or complier) is responsible for knowing which synchronization directives are available on a given architecture and implementing them in an efficient manner.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

* Automatic fence insertion for shared memory multiprocessing [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790 http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

CSC/ECE 506 Spring 2010/ch 7 pl/

2010-04-05T20:04:56Z

Pwlane: /* Fence Insertion */

Shared-memory multiprocessors run into several problems that are more pronounced than their uniprocessor counterparts. The Solihin text used in this course goes into detail on three of these issues, that is cache coherence, memory consistency and synchronization. It is the goal of this wiki supplement to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

{{{
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
}}}

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in its cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example (load A, store A) --> (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

== Open MP ==
The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

== Fence Insertion ==

One method that is commonly used on production shared memory systems and microprocessors it the insertion of fences. These fences can be used by the programmer to force the chip to perform a synchronization, or wait until "all previous memory operations of the processor are guaranteed to have completed" [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790] Fence insertion is a method giving the programmer (or compiler) control over the hardware's default ordering of memory operations (such as sequential consistency, processor consistency, weak ordering, etc). It is important from a performance standpoint that the complier be able to quickly and efficiently insert fences automatically, and the algorithms used for this automatic insertion have a large bearing on performance. [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

=== Instructions used for fence operations ===
*SPARC V8 > store barrier
*SPARC V9 > MEMBAR
*Alpha > memory barrier and write memory barrier
*MIPS / PPC > sync
*Intel x86 > lfence (load) sfence (store)

Taken from [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

== Other Methods ==

There are many other ways to implement synchronization directives as well. The ACM article [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf] discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them. The programmer (or complier) is responsible for knowing which synchronization directives are available on a given architecture and implementing them in an efficient manner.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

* Automatic fence insertion for shared memory multiprocessing [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790 http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

CSC/ECE 506 Spring 2010/ch 7 pl/

2010-04-05T20:01:56Z

Pwlane: /* Other Methods */

Shared-memory multiprocessors run into several problems that are more pronounced than their uniprocessor counterparts. The Solihin text used in this course goes into detail on three of these issues, that is cache coherence, memory consistency and synchronization. It is the goal of this wiki supplement to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

{{{
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
}}}

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in its cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example (load A, store A) --> (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

== Open MP ==
The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

== Fence Insertion ==

One method that is commonly used on production shared memory systems and microprocessors it the insertion of fences. These fences can be used by the programmer to force the chip to perform a synchronization, or wait until "all previous memory operations of the processor are guaranteed to have completed" [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790] Fence insertion is an important go between for the programmer, allowing control over the hardware's default ordering of memory operations. It is important from a performance standpoint that the complier be able to quickly and efficiently insert fences automatically, and the algorithms used for this automatic insertion have a large bearing on performance. [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

=== Instructions used for fence operations ===
*SPARC V8 > store barrier
*SPARC V9 > MEMBAR
*Alpha > memory barrier and write memory barrier
*MIPS / PPC > sync
*Intel x86 > lfence (load) sfence (store)

Taken from [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

== Other Methods ==

There are many other ways to implement synchronization directives as well. The ACM article [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf] discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them. The programmer (or complier) is responsible for knowing which synchronization directives are available on a given architecture and implementing them in an efficient manner.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

* Automatic fence insertion for shared memory multiprocessing [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790 http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

CSC/ECE 506 Spring 2010/ch 7 pl/

2010-04-05T19:59:21Z

Pwlane: /* Synchronization */

Shared-memory multiprocessors run into several problems that are more pronounced than their uniprocessor counterparts. The Solihin text used in this course goes into detail on three of these issues, that is cache coherence, memory consistency and synchronization. It is the goal of this wiki supplement to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

{{{
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
}}}

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in its cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example (load A, store A) --> (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

== Open MP ==
The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

== Fence Insertion ==

One method that is commonly used on production shared memory systems and microprocessors it the insertion of fences. These fences can be used by the programmer to force the chip to perform a synchronization, or wait until "all previous memory operations of the processor are guaranteed to have completed" [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790] Fence insertion is an important go between for the programmer, allowing control over the hardware's default ordering of memory operations. It is important from a performance standpoint that the complier be able to quickly and efficiently insert fences automatically, and the algorithms used for this automatic insertion have a large bearing on performance. [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

=== Instructions used for fence operations ===
*SPARC V8 > store barrier
*SPARC V9 > MEMBAR
*Alpha > memory barrier and write memory barrier
*MIPS / PPC > sync
*Intel x86 > lfence (load) sfence (store)

Taken from [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

== Other Methods ==

There are many other ways to implement synchronization directives as well. The ACM article discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

* Automatic fence insertion for shared memory multiprocessing [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790 http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

CSC/ECE 506 Spring 2010/ch 7 pl/

2010-04-05T19:47:17Z

Pwlane: /* Ordering on a Uniprocessor */

Shared-memory multiprocessors run into several problems that are more pronounced than their uniprocessor counterparts. The Solihin text used in this course goes into detail on three of these issues, that is cache coherence, memory consistency and synchronization. It is the goal of this wiki supplement to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

{{{
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
}}}

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in its cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example (load A, store A) --> (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

There are many other ways to implement synchronization directives as well. The ACM article discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

* Automatic fence insertion for shared memory multiprocessing [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790 http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

CSC/ECE 506 Spring 2010/ch 7 pl/

2010-04-05T19:46:32Z

Pwlane: /* References */

Shared-memory multiprocessors run into several problems that are more pronounced than their uniprocessor counterparts. The Solihin text used in this course goes into detail on three of these issues, that is cache coherence, memory consistency and synchronization. It is the goal of this wiki supplement to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

{{{
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
}}}

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in its cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example (load A, store A) --> (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

There are many other ways to implement synchronization directives as well. The ACM article discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

* Automatic fence insertion for shared memory multiprocessing [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790 http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

CSC/ECE 506 Spring 2010/ch 7 pl/

2010-04-05T19:45:24Z

Pwlane: /* References */

Shared-memory multiprocessors run into several problems that are more pronounced than their uniprocessor counterparts. The Solihin text used in this course goes into detail on three of these issues, that is cache coherence, memory consistency and synchronization. It is the goal of this wiki supplement to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

{{{
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
}}}

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in its cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example (load A, store A) --> (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

There are many other ways to implement synchronization directives as well. The ACM article discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

* Automatic fence insertion for shared memory multiprocessing
[http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

CSC/ECE 506 Spring 2010/ch 7 pl/

2010-03-26T00:15:49Z

Pwlane:

Shared Memory multiprocessors run into several problems that are more pronounced then on their uniprocessors counterparts. The Solihin text used in this course goes into a small amount of detail on three of these issues, that is Cache Coherence, Memory Consistency and Synchronization. It is the goal of this wiki to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has it's own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

{{{
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
}}}

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in it's cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the SAME address. For example (load A, store A) > (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

The Solihin text uses the #pragma omp critical directive in the code given in the cache coherency section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

There are many other ways to implement synchronization directives as well. The ACM article discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

CSC/ECE 506 Spring 2010/ch 4 pl/

2010-03-26T00:15:38Z

Pwlane:

CSC/ECE 506 Spring 2010/ch 4 pl/

2010-03-26T00:13:50Z

Pwlane:

CSC/ECE 506 Spring 2010/ch 4 pl/

2010-03-26T00:01:46Z

Pwlane:

Shared Memory multiprocessors run into several problems that are more pronounced then on their uniprocessors counterparts. The Solihin text used in this course goes into a small amount of detail on three of these issues, that is Cache Coherence, Memory Consistency and Synchronization. It is the goal of this wiki to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has it's own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

[code]
sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;
[/code]

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in it's cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the SAME address. For example (load A, store A) > (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

The Solihin text uses the #pragma omp critical directive in the code given in the cache coherency section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

There are many other ways to implement synchronization directives as well. The ACM article discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]

CSC/ECE 506 Spring 2010/ch 4 pl/

2010-03-26T00:01:00Z

Pwlane:

Shared Memory multiprocessors run into several problems that are more pronounced then on their uniprocessors counterparts. The Solihin text used in this course goes into a small amount of detail on three of these issues, that is Cache Coherence, Memory Consistency and Synchronization. It is the goal of this wiki to discuss these three issues and also what can be done to ensure that instructions are handled in both a timely and efficient manner and in a manner that is consistent with what the programmer might desire.

= Cache Coherence =

This problem arises when each chip in the system has it's own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

sum = 0;
#pragma omp parallel for
for (i=0; i<2; i++) {
#pragma omp critical {
sum = sum + a[i];
}
}
print sum;

The problem that will arise as discussed in the text is that P0 will calculate a value for sum, and store it in it's cache, and since P1 is not aware of the contents of P0's cache, it will read an invalid value for sum from main memory. It will be impossible to obtain the actual value for sum since each processor now believes that it possess the correct value for sum. That is, since they both read the value of sum from main memory to be 0, P0 thinks that the value of sum to be sum + a[0] while P1 thinks the value of sum to be sum + a[1]. It is important to note that placing the summation in a critical section does not fix this problem, since the problem is not that the 2 processors are executing at the same time, but that the main memory is not being updated and that the processors are not aware that the correct value for sum is now present (and only present) in another processors cache.

= Memory Consistency =

Another important issue in multiprocessor systems is the ordering of loads and stores into memory. The Solihin text gives an example of a signal-wait synchronization. In this example, P0 generates a certain piece of data and then signals (by setting a certain memory location to 1) that this data is now ready. P1 is spinning in a while waiting for this data ready flag to become 1, and then it will print the data. It is important that the complier understand what is going on so that the program order is preserved. In C, this can be accomplished by declaring certain variables as volatile.

== Ordering on a Uniprocessor ==

On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

(load A, load B) > (load B, load A)
(store B, store A) > (store A, store B)

These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the SAME address. For example (load A, store A) > (store A, load A) would not be OK.

== Ordering on a Multiprocessor ==

On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

(store A, store B): maintained in order.
(load A, store B): load must be done first, ignoring a younger store in the queue.
(store A, load B): load must be not go ahead of the store, even though the store is to a different address.
(load A, load B): even if the addresses are different, the older load must go first.

= Synchronization =

The Solihin text uses the #pragma omp critical directive in the code given in the cache coherency section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

The problem is that with out special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

There are many other ways to implement synchronization directives as well. The ACM article discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them.

= References =
* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.

* Notes on Memory Consistancy and Cache Coherence [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf]

* Mirko Loghi, Massimo Poncino, Luca Benini, Cache Coherence Tradeoffs in Shared-Memory MPSoCs [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf]