CSC/ECE 506 Spring 2014/9b vn

Instruction and Previous Work

Changes are made as per the instructions given in https://docs.google.com/a/ncsu.edu/document/d/1Xk0HiD31nKXVxFt3MfNh-SLftvS4mAhlzYPBIuojAEk/edit?pli=1#

Previous Version can be found here: http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2013/9b_sc

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 the software. The most common types of hardware synchronization mechanisms are locks and barriers which are discussed in the further sections.

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 mechanism 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 consequently has a lot of overhead. Busy-waiting has much less overhead but uses the 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.

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] The syntax for the instruction is LOCK CMPXCHG SOURCE DESTINATION. Here, the source has to be a register while the destination can be either Register or Memory. An example of LOCK CMPXCHG is implementation in dis-assembly of Linux kernel's rtc_cmos_read(). The CPU locks needs to be copied and and then updated to a non zero value if the lock is to be applied. But there is a possibility when the value got copied earlier and changed later. This causes a race condition. Hence,it helps in briefing the busy wait loop by preventing race condition. The pseudo code for same is given as below^[10]:

spin: # see if the lock-variable is clear
mov cmos_lock, %eax
test %eax, %eax
jnz spin
# ok, now we try to grab the lock
lock cmpxchg %edx, cmos_lock
# did another CPU grab it first? 
test %eax, %eax
jnz spin

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]. Waiting thread gives up processor so that other threads (e.g. the thread with the lock) can run more quickly. Someone wakes up thread when the lock is free. The separation of ready queue from that of waiting queue fastens the process of execution. In the below example, the lock is given to a waiting thread by the unlock method. The interrupts are enabled only when the thread is placed in waiting queue and disabled once its given the lock.

lock () {
   disable interrupts
   
   if (value == FREE) {
      value = BUSY
   } 
   
   else {
      add thread to queue of threads waiting for
      this lock
      switch to next runnable thread
   }
   
   enable interrupts
}

unlock () {
   disable interrupts
   
   value = FREE
   if (any thread is waiting for this lock) {
      move waiting thread from waiting queue to
      ready queue
      value = BUSY
   }
   
   enable interrupts
} 

But this fails if interrupt happens after thread enable interrupts Lock() adds thread to wait queue Lock() enables interrupts Interrupts causes pre-emption, i.e. switch to another thread. Pre-emption moves thread to ready queue. Now thread is on two queues (wait and ready)! Also, switch is likely to be a critical section Adding thread to wait queue and switching to next thread must be atomic. Solution to this problem is waiting thread leaves interrupts disabled when it calls switch. Next thread to run has the responsibility of re-enabling interrupts before returning to user code. When waiting thread wakes up, it returns from switch with interrupts disabled (from the last thread)^[11]

Performance Evaluation

Lock performance can be evaluated using the below four criteria:^[2]

Acquisition Latency

Acquisition latency can be defined as the time taken to acquire the lock. This factor must be low, 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 can be defined as the bus traffic that is generated by the threads when attempting to acquire the lock. It is an important consideration when evaluating lock performance. If acquiring lock causes excess bus traffic, it will not scale well with the increase in the number of threads. This might lead to the eventual chocking of the bus.^[1]

Fairness

In general, threads should acquire a lock in them same order that the locks were requested. With the increase in the number of threads if this condition is not enforced, some of the threads might get 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 the 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) but are not fair. Test&set has a low acquisition latency but is not scalable due do high bus traffic when there is high contention for the lock. Test-and-test&set has a higher acquisition latency but scales better because it generates less bus traffic. The figure below 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

Performance of locking mechanisms can be improved in the following ways:

1. 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]
2. The term "Spinning" or "Spinlock" refers to a processor waiting in a loop while trying to acquire the lock. One 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]
3. Additionally, fairness can be guaranteed by queuing the lock attempts in shared memory so that they happen in order.^[3]

Avoiding Locks

There are many reasons why a programmer should attempt to write programs in such a way as to avoid locks if possible as there are many problems that can arise with the use of locks. Some of them are discussed below^[4]

One of the most well known issues is deadlock. This can occur when the threads are waiting to acquire the lock, but the lock would never be released. For example, there are two processes A and B and they need two methods (1 and 2) to be grabbed for completion of a task which are shared by both A and B. There is a potential deadlock situation when A grabs 1 and B grabs 2. Since both processes need one other method to reach completion, neither of them change their state. The solution to this problem is to set a condition where in process A can lock method 2 only if it has locked method 1.

Another problem with using locks is that the performance is not optimal, since a lock is often 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]

To avoid locks, lock free programming techniques like compare and swap and sequential consistency can be followed. This pattern typically involves copying a shared variable to a local variable, performing some speculative work, and attempting to publish the changes using CAS^[12]:

void LockFreeQueue::push(Node* newHead)
{
    for (;;)
    {
        // Copy a shared variable (m_Head) to a local.
        Node* oldHead = m_Head;

        // Do some speculative work, not yet visible to other threads.
        newHead->next = oldHead;

        // Next, attempt to publish our changes to the shared variable.
        // If the shared variable hasn't changed, the CAS succeeds and we return.
        // Otherwise, repeat.
        if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead)
           return;
    }
}

The above code basically follows the Read-Write-Update order and makes sure that each thread has its local copy to work on and gets it updated sequentially so that the next thread has the correct value. In case the value is incorrect, the write fails.

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. Some of the popular barrier techniques are listed below

Fuzzy Barrier

Barriers can have a major performance impact because of two properties. Firstly, threads that have reached a barrier are forced to wait for other barriers and as a result are in an idling state. The thread is essentially performing no useful function in this state. Secondly, the execution of the barrier itself may be slow (if implemented in software), due to the fact that they may consist of several instructions that need to execute.

The fuzzy barrier aims to solve both of these issues. To increase the speed of the barrier implementation, fuzzy barriers are implemented in hardware. The other problem is to keep each thread as busy as possible for a majority of the time. This is done by extending the concept of a barrier to include a set of instructions that can be safely executed by the waiting/idling thread. By making this safe barrier region as large as possible we can ensure that almost none of the threads have to completely stall at any particular time. ^[14]

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 scales quadratically with number of processors.

^[8]

A sense-reversing barrier is a more elegant and practical solution to the problem of reusing barriers. A phase’s sense is a Boolean value: true for even-numbered phases and false otherwise. Each SenseBarrier object has a Boolean sense field indicating the sense of the currently executing phase. Each thread keeps its current sense as a thread-local object. Initially the barrier’s sense is the complement of the local sense of all the threads. When a thread calls await(), it checks whether it is the last thread to decrement the counter. If so, it reverses the barrier’s sense and continues. Otherwise, it spins waiting for the balancer’s sense field to change to match its own local sense.^[13]

struct barrier {
   shared int count; 
   // a Fetch&Inc/Dec() object with initial value n 
   // this object supports also read and write
   boolean sense;
   
   // initially FALSE;
   boolean mysense[n];
   // initially, psense[i] = TRUE,
   // for each 1 ≤ i ≤ n.
};

void await(struct barrier *B) { 
   // code for process pi
   int position = Get&Dec(B->count); 
   
   if (position == 1) {
      B->count = n;
      B->sense = B->mysense[i]; 
   }
   
   else {
      while (B->sense!= B->mysense[i]) 
   noop; //No operation
   }
   
   B->mysense[i] = 1-B->mysense[i];
}

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]

Another example in form of pseudo code is given below:

procedure combining_barrier 
 combining_barrier_aux(mynode) // join the barrier 
 sense := not sense // for next barrier 

procedure combining_barrier_aux(nodepointer : ^node) 
 with nodepointer^ do 
 if fetch_and_decrement(&count) = 1 // last to reach this node 
 if parent != nil 
 combining_barrier_aux(parent) 
 count := k // prepare for next barrier
 nodesense := not nodesense // release waiting processors
 repeat until nodesense = sense

Here, each processor starts at a leaf node of the tree and the leaf count value is decreased. The last descendant to reach each node in tree gets to continue further. The processor reaching the root wakes up and retraces its path through tree and unblocks siblings at each node along path.

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]

An example of tournament barrier is given as follows:

void await(boolean mySense) {
 if (top) {
  return;
 } 
 else if (parent != null) {
   while (flag != mySense) {};
   parent.await(mySense);
   partner.flag = mySense;
 }
 else {
   partner.flag = mySense;
   while (flag != mySense) {};
 }

}

Here, the parent variable stores the value i.e. null if not a winner else a winner, and then waits for a partner (represented by flag) and then performs synchronization. Otherwise a natural loser is chosen and partnered with current thread.

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 log(n) rounds all the threads are aware of the status of every other thread running and whether it has reached the barrier. Overall synchronization is achieved by implication from a carefully chosen sequence of pairwise synchronizations.

^[9]

An example of this type of barrier can be found below:

for [s = 0 to stages-1] { 
   ## there will be ceiling(log_2 p) stages
   work out who my out-going partner is at stage s;
   <await (arrive[partner][s] == 0);>
   arrive[partner][s] = 1;
   <await (arrive[myid][s] == 1);>
   arrive[myid][s] = 0;
}

Here, each thread executes the same code, choosing partners for the pairwise synchronizations as a function of its own identifier and the internal iteration. Our own arrive flag is now set by an “in-coming” partner, who is distinct from our “out-going” partner (except when p=2).

Performance Evaluation

To evaluate lock performance, we can use these two criteria:^[2]

Latency

Latency can be defined as the time taken to enter and exit a barrier. Ideally the latency of a barrier should be small, but for barriers that do not scale well, latency can increase as the number of threads increases.^[1]

Traffic

Traffic is the communications overhead required by the barrier. Ideally barrier traffic should be low, as excess traffic limits scalability.^[1]

Performance Comparison

The comparison of the performance of some of the barrier implementations have been tabulated below:

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

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. Retrieved from here
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. https://iwomp.zih.tu-dresden.de/downloads/scalability-Nanjegowda.pdf
8. Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.3867&rep=rep1&type=pdf
9. http://cs.brown.edu/courses/cs176/lectures/lecture13.pptx
10.http://heather.cs.ucdavis.edu/~matloff/50/PLN/lock.pdf
11.http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf
12.Jeff Pershing. (2012, Jun 12). "An Introduction to Lock Free programming". Retreived from here
13.Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kauffman. March 03,1998
14.Rajiv Gupta. The Fuzzy Barrier: A Mechanism for High Speed Synchronization of Processors. 1989.