CSC/ECE 506 Spring 2011/ch9 ms

Synchronization

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

Hardware vs. Operating System Synchronization

Synchronizations are characterized by three parts: acquire, wait, and release. Both hardware and operating system synchronization rely on atomic instructions for acquire and release, but the implementations for the wait portion of a synchronization can vary. Hardware implementations usually use busy-waiting, where a process repeatedly tests a variable waiting for it to change. The operating system can wait using blocking, where the process suspends itself until woken up by another process.

Blocking has the advantage of freeing up the processor for use by other processes, but requires operating system functions to work and thus has a lot of overhead. Busy-waiting has much less overhead, but uses processor and cache resources while waiting. Because of these tradeoffs, it is usually better to use busy-waiting for short wait periods, and blocking for long wait periods.^[1]

Lock Implementations

Locks are an important concept when programming for multiprocessor systems. The purpose of a lock is to protect the code inside the lock, known as a critical section. It must be certain that while some thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. While thread X has entered 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

To evaluate lock performance, we can use these four criteria:

• 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?^[2]

Acquisition Latency

We want a low acquisition latency, especially for applications that repeatedly acquire and release locks. Over the run time of a program, the acquisition latency compounded many times could have a large performance affect. However, low acquisition latency has to be balanced against other factors when implementing a lock.^[1]

Traffic

Traffic is an important consideration when evaluating lock performance. If acquiring lock causes a lot of bus traffic, it will not scale well as the number of threads increases. Eventually the bus will become choked.^[1]

Fairness

In general, threads should acquire a lock in them same order that the locks were requested. If this does not happen, as the number of threads increases so does the chance that a thread will become starved.^[1]

Storage

The amount of storage needed per lock should be small enough such that it scales to a large number of threads without any problems. If a large amount of storage is required, then multiple threads could cause locks to consume too much memory.^[1]

Performance Comparison

Two common lock implementations are test&set and test and test&set. In terms of performance, both have a low storage cost (scalable) and are not fair. Test&set has a low acquisition latency but is not scalable due do high bus traffic when there is a lot of contention for the lock. Test-and-test&set has a higher acquisition latency but scales better because it generates less bus traffic. The next figure shows performance comparisons for these two lock implementations.^[1]

Performance comparison of test&set and test-and-test&set (spin on read)^[3]

Improving performance

Optimizing software can improve the performance of locks. For instance, inserting a delay between a processor noticing a release and then trying to acquire a lock can reduce contention and bus traffic, and increase the performance of the locks. TCP-like back off algorithms can be used to adjust this delay depending on the number of threads contending for the lock.^[3]

Another way to improve performance is to insert a delay between memory references so as to limit the bandwidth (traffic) each processor can use for spinning.^[3]

One way to guarantee fairness is to queue lock attempts in shared memory so that they happen in order.^[3]

Atomic Instructions

Since a multiprocessor system cannot disable interrupts as an effective method to execute code atomically, there must be hardware support for atomic operations.^[4]

The ability 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 (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.^[5]

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.^[6]

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.^[4]

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.^[4]

Barrier Implementations

In many ways, barriers are simpler than locks. A barrier is simply 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

To evaluate lock performance, we can use these two criteria:

• Latency - The time required to enter and exit a barrier.
• Traffic - Communications overhead required by the barrier.^[2]

Latency

Ideally the latency of a barrier should be small, but for barriers that don't scale well latency can increase as the number of threads increases.^[1]

Traffic

Low traffic is also good, as we do not want excess buss traffic to prevent scalability.^[1]

Performance Comparison

Performance Comparison of Barrier Implementations^[2]

Criteria	Sense Reversal Centralized Barrier	Combining Tree Barrier	Barrier Network (Hardware)
Latency	O(1)	O(log p)	O(log p)
Traffic	O(p2)	O(p)	moved to a separate network

Additive Schwarz Preconditioned Conjugate Gradient (ASPCG) kernel on Altix System - This 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.^[7]

EPCC Microbenchmark - This 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.^[7]

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.

^[8]

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.

^[8]

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 loser thread is allowed to set the flag and move to higher level and compete to lose with the loser 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.

^[8]

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.

^[9]

References

1. David Culler, J.P. Singh and Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann. August 1998.
2. Yan Solihin. Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Books. August 2009.
3. Thomas E. Anderson. The Performance of Spin Lock Alternatives for Shared-memory Multiprocessors. http://www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/anderson-spinlock.pdf
4. http://www.statemaster.com/encyclopedia/Lock-(computer-science)
5. http://faydoc.tripod.com/cpu/cmpxchg.htm
6. http://www.cs.duke.edu/courses/fall09/cps110/slides/threads3.ppt
7. Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf
8. Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf
9. http://www.cs.brown.edu/courses/cs176/barrier.ppt