CSC/ECE 506 Spring 2010/Ch 9/Synchronization: Difference between revisions
No edit summary |
|||
| Line 4: | Line 4: | ||
Hardware implementations for synchronization traditionally include locks, barriers, and mutual exclusion. These types of hardware synchronizations use a method called busy-waiting, or spinning which prevents threads from continuing to execute. Spinning simply means that a thread continuously checks if it is okay to continue (no other useful work is accomplished by the thread). In the case for a lock, multiple threads are competing for access to the lock. Only one thread is allowed to access the critical code protected by the lock at a time. For barriers, multiple threads reach the barrier at different times and no thread can continue until all threads have reached the barrier. Spinning is implemented in hardware through mutexes or semaphores, which prevent multiple processes from being accessed at the same time. Atomic instructions, which are support by the processor Instruction Set Architecture(ISA), are typically used for hardware synchronization mechanism. Examples of these hardware synchronization mechanisms include: Test-and-Set, Fetch-and-Increment, Test-and-Test-and-Set. Below are descriptions of these atomic instructions: | Hardware implementations for synchronization traditionally include locks, barriers, and mutual exclusion. These types of hardware synchronizations use a method called busy-waiting, or spinning which prevents threads from continuing to execute. Spinning simply means that a thread continuously checks if it is okay to continue (no other useful work is accomplished by the thread). In the case for a lock, multiple threads are competing for access to the lock. Only one thread is allowed to access the critical code protected by the lock at a time. For barriers, multiple threads reach the barrier at different times and no thread can continue until all threads have reached the barrier. Spinning is implemented in hardware through mutexes or semaphores, which prevent multiple processes from being accessed at the same time. Atomic instructions, which are support by the processor Instruction Set Architecture(ISA), are typically used for hardware synchronization mechanism. Examples of these hardware synchronization mechanisms include: Test-and-Set, Fetch-and-Increment, Test-and-Test-and-Set. Below are descriptions of these atomic instructions: | ||
===Software Implementations=== | |||
The software implementations discussed are specifically used in Networks of Workstations (NOWs). Using explicit messages, synchronization can be implemented using software. | |||
==Mutual Exclusion== | |||
Test-and-Set Rx, M: Read the value stored in memory location M, test the value against a constant, and if they match, write the value in register Rx to memory location M. | Test-and-Set Rx, M: Read the value stored in memory location M, test the value against a constant, and if they match, write the value in register Rx to memory location M. | ||
| Line 19: | Line 23: | ||
unlock: st &lockvar, #0 //lockvar = 0 | unlock: st &lockvar, #0 //lockvar = 0 | ||
ret //return to caller | ret //return to caller | ||
==Overhead== | ==Overhead== | ||
Revision as of 15:45, 12 April 2010
Hardware Support For Synchronization
Hardware Implementations
Hardware implementations for synchronization traditionally include locks, barriers, and mutual exclusion. These types of hardware synchronizations use a method called busy-waiting, or spinning which prevents threads from continuing to execute. Spinning simply means that a thread continuously checks if it is okay to continue (no other useful work is accomplished by the thread). In the case for a lock, multiple threads are competing for access to the lock. Only one thread is allowed to access the critical code protected by the lock at a time. For barriers, multiple threads reach the barrier at different times and no thread can continue until all threads have reached the barrier. Spinning is implemented in hardware through mutexes or semaphores, which prevent multiple processes from being accessed at the same time. Atomic instructions, which are support by the processor Instruction Set Architecture(ISA), are typically used for hardware synchronization mechanism. Examples of these hardware synchronization mechanisms include: Test-and-Set, Fetch-and-Increment, Test-and-Test-and-Set. Below are descriptions of these atomic instructions:
Software Implementations
The software implementations discussed are specifically used in Networks of Workstations (NOWs). Using explicit messages, synchronization can be implemented using software.
Mutual Exclusion
Test-and-Set Rx, M: Read the value stored in memory location M, test the value against a constant, and if they match, write the value in register Rx to memory location M.
Fetch-and-Increment M: Read the value stored in memory location M, increment it, and then store the new value to the memory location.
Test-and-Test-and-Set: This is the the same as Test-and-Set, except that there is an extra testing phase. Only when the atomic Test-and-set instruction has a good chance of succeeding, the atomic instruction is executed. See example code below:
lock: ld R1, &lockvar // R1 = lockvar
bnz R1, lock // jump to lock if R1 != 0
t&s R1, &lockvar // test-and-set atomic instruction
// R1=lockvar; if(R1 == 0) lockvar=1
bnz R1, lcok //jump to lock if R1 != 0
ret //return to caller
unlock: st &lockvar, #0 //lockvar = 0
ret //return to caller
Overhead
Improved Hardware Primitives
Barriers
Reference
1. http://www-inst.eecs.berkeley.edu/~n252/su06/CS252Midterm_Hermoso.pdf
2. ftp://ftp.cs.wisc.edu/wwt/ics96_synch.pdf
3. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf
6. http://software.intel.com/en-us/articles/use-non-blocking-locks-when-possible/