CSC/ECE 506 Spring 2010/Ch 9/Synchronization - Revision history

Bsriggan: /* Overhead */

2010-04-20T04:16:03Z

Overhead

← Older revision		Revision as of 04:16, 20 April 2010
Line 33:		Line 33:


	The performance of test-and-set degrades significantly as the number of processors increases. There are two reasons for this performance decrease. First, a thread must contend with other threads in order to release the lock. The second reason is that the requests by the spinning threads trying to access the lock slow the lock holder. The overhead of this approach is very minimal. There is not much overhead associated with test-and-set. This approach is very trivial. It is the easiest to implement, but has the worst performance.		The performance of test-and-set degrades significantly as the number of processors increases. There are two reasons for this performance decrease. First, a thread must contend with other threads in order to release the lock. The second reason is that the requests by the spinning threads trying to access the lock slow the lock holder. The overhead of this approach is very minimal. There is not much overhead associated with test-and-set. This approach is very trivial. It is the easiest to implement, but has the worst performance. (The code below come from the solihin text).

	lock: test-and-set R1, &lockvar //R1 = lockvar		lock: test-and-set R1, &lockvar //R1 = lockvar
Line 46:		Line 46:


	The performance of test-and-test-and-set is slightly better than test-and-set. The downside to test-and-test-and-set performance is that there is a separation between detecting that the lock has been released and trying to acquire the lock. The separation allows multiple threads to see that the lock is free, and then the threads that pass the test attempt a test-and-set instruction to try to acquire the lock. The overhead is about the same as test-and-set. There is still not a significant amount of overhead associated with test-and-test-and-set. Performance is sacrificed when overhead is smaller.		The performance of test-and-test-and-set is slightly better than test-and-set. The downside to test-and-test-and-set performance is that there is a separation between detecting that the lock has been released and trying to acquire the lock. The separation allows multiple threads to see that the lock is free, and then the threads that pass the test attempt a test-and-set instruction to try to acquire the lock. The overhead is about the same as test-and-set. There is still not a significant amount of overhead associated with test-and-test-and-set. Performance is sacrificed when overhead is smaller. (The code below comes from the Solihin text).

	lock: ld R1, &lockvar // R1 = lockvar		lock: ld R1, &lockvar // R1 = lockvar

Bsriggan: /* Test and Test and Set */

2010-04-20T04:13:13Z

Test and Test and Set

← Older revision		Revision as of 04:13, 20 April 2010
Line 48:		Line 48:
	The performance of test-and-test-and-set is slightly better than test-and-set. The downside to test-and-test-and-set performance is that there is a separation between detecting that the lock has been released and trying to acquire the lock. The separation allows multiple threads to see that the lock is free, and then the threads that pass the test attempt a test-and-set instruction to try to acquire the lock. The overhead is about the same as test-and-set. There is still not a significant amount of overhead associated with test-and-test-and-set. Performance is sacrificed when overhead is smaller.		The performance of test-and-test-and-set is slightly better than test-and-set. The downside to test-and-test-and-set performance is that there is a separation between detecting that the lock has been released and trying to acquire the lock. The separation allows multiple threads to see that the lock is free, and then the threads that pass the test attempt a test-and-set instruction to try to acquire the lock. The overhead is about the same as test-and-set. There is still not a significant amount of overhead associated with test-and-test-and-set. Performance is sacrificed when overhead is smaller.

			lock: ld R1, &lockvar // R1 = lockvar
			bnz R1, lock // jump to lock if R1 != 0
			t&s R1, &lockvar // R1 = lockvar
			// if (R1 == 0) lockvar = 1
			bnz R1, lock // jump to lock if R1 != 0
			ret // return to caller

			unlock: st &lockvar #0 // lockvar = 0
			ret // return to caller

	===Ticket Lock===		===Ticket Lock===

Bsriggan: /* Test and Set */

2010-04-20T04:05:11Z

Test and Set

← Older revision		Revision as of 04:05, 20 April 2010
Line 35:		Line 35:
	The performance of test-and-set degrades significantly as the number of processors increases. There are two reasons for this performance decrease. First, a thread must contend with other threads in order to release the lock. The second reason is that the requests by the spinning threads trying to access the lock slow the lock holder. The overhead of this approach is very minimal. There is not much overhead associated with test-and-set. This approach is very trivial. It is the easiest to implement, but has the worst performance.		The performance of test-and-set degrades significantly as the number of processors increases. There are two reasons for this performance decrease. First, a thread must contend with other threads in order to release the lock. The second reason is that the requests by the spinning threads trying to access the lock slow the lock holder. The overhead of this approach is very minimal. There is not much overhead associated with test-and-set. This approach is very trivial. It is the easiest to implement, but has the worst performance.

			lock: test-and-set R1, &lockvar //R1 = lockvar
			//if (R1 == 0) lockvar = 1;
			bnz R1, lock //jump to lock if R1 != 0
			ret //return to caller

			unlock: st &lockvar, #0 // lockvar = 0
			ret // return to caller

	===Test and Test and Set===		===Test and Test and Set===

Bsriggan: /* Overhead */

2010-04-20T04:01:41Z

Overhead

← Older revision		Revision as of 04:01, 20 April 2010
Line 43:		Line 43:

	===Ticket Lock===		===Ticket Lock===


			The overhead for ticket locks is low, however, with contention traffic generated from ticket locks is about the same as test-and-set or test-and-test-and-set. This traffic is due to invalidations from the releasing of the lock. When there is very little contention the ticket lock performs much better than the MCS lock, but when there is high contention MCS locks are better (see MCS lock below).

	typedef struct TIXLOCK {		typedef struct TIXLOCK {
	unsigned long next_tix;		unsigned long next_tix;
Line 66:		Line 70:
	===MCS Lock===		===MCS Lock===


			As mentioned above, under high contention MCS locks have less traffic. This is because MCS locks use multiple flags (oppose to a single counter variable) which eliminates many invalidations and reloads.

	typedef struct qnode {		typedef struct qnode {

Bsriggan: /* MCS Lock */

2010-04-20T03:24:13Z

MCS Lock

← Older revision		Revision as of 03:24, 20 April 2010
Line 71:		Line 71:
	boolean locked; }		boolean locked; }
	qnode_typed;		qnode_typed;

	typedef struct MCSLOCK {		typedef struct MCSLOCK {
	qnode_type *q_ptr; }		qnode_type *q_ptr; }
	mcs_lock_type;		mcs_lock_type;

	void acquire(long lock_addr) {		void acquire(long lock_addr) {
	/* allocated to each lock acquire instance */		/* allocated to each lock acquire instance */

Bsriggan: /* MCS Lock */

2010-04-20T03:23:34Z

MCS Lock

← Older revision		Revision as of 03:23, 20 April 2010
Line 66:		Line 66:
	===MCS Lock===		===MCS Lock===


			typedef struct qnode {
			struct qnode * next;
			boolean locked; }
			qnode_typed;

			typedef struct MCSLOCK {
			qnode_type *q_ptr; }
			mcs_lock_type;

			void acquire(long lock_addr) {
			/* allocated to each lock acquire instance */
			/* and keep permanent until release */
			qnode_type* qnode = allocate_qnode(lock_addr);
			mcs_lock_type* ml = (mcs_lock_type*)lock_addr;
			qnode_type *pred;

			qnode->next = NULL;
			pred = (qnode_type *) fetch_and_store((long)&ml->q_ptr, (long)qnode);

			if(pred!=NULL) {
			qnode->locked = TRUE;
			pred->next = qnode;
			while(qnode->locked);
			}
			}

			void release(long lock_addr) {
			qnode_type* qnode = get_qnode(lock_addr);
			mcs_lock_type* ml = (mcs_lock_type*)lock_addr;

			if (qnode->next == NULL) {
			if (compare_and_swap((long_&ml->q_ptr, (long)qnode, NULL)) return;
			while (qnode->next == NULL);
			}
			qnode->next->locked = FALSE;
			}

	===API Synchronization===		===API Synchronization===

Bsriggan: /* Overhead */

2010-04-20T03:06:53Z

Overhead

← Older revision		Revision as of 03:06, 20 April 2010
Line 43:		Line 43:

	===Ticket Lock===		===Ticket Lock===
			typedef struct TIXLOCK {
			unsigned long next_tix;
			unsinged long whose_turn; }
			tix_lock_type;

			void acquire (long lock_addr) {
			unsigned long my_tix;
			tix_lock_type* L = (tix_lock_type*)lock_addr;

			my_tix = fetch_and_increment((long)&(L->next_tix));
			while(L->whose_turn != my_tix)
			pause(proportional_backoff * (my_tix - L->whose_turn));
			}

			void release(long lock_addr) {
			tix_lock_type* L = (tix_lock_type*)lock_addr;

			L->whose_turn+1;
			}

Bsriggan: /* Overhead */

2010-04-19T16:35:28Z

Overhead

← Older revision		Revision as of 16:35, 19 April 2010
Line 40:		Line 40:

	The performance of test-and-test-and-set is slightly better than test-and-set. The downside to test-and-test-and-set performance is that there is a separation between detecting that the lock has been released and trying to acquire the lock. The separation allows multiple threads to see that the lock is free, and then the threads that pass the test attempt a test-and-set instruction to try to acquire the lock. The overhead is about the same as test-and-set. There is still not a significant amount of overhead associated with test-and-test-and-set. Performance is sacrificed when overhead is smaller.		The performance of test-and-test-and-set is slightly better than test-and-set. The downside to test-and-test-and-set performance is that there is a separation between detecting that the lock has been released and trying to acquire the lock. The separation allows multiple threads to see that the lock is free, and then the threads that pass the test attempt a test-and-set instruction to try to acquire the lock. The overhead is about the same as test-and-set. There is still not a significant amount of overhead associated with test-and-test-and-set. Performance is sacrificed when overhead is smaller.


			===Ticket Lock===


			===MCS Lock===


Line 50:		Line 56:

	[[Image:Graph2.png]]		[[Image:Graph2.png]]


	==Improved Hardware Primitives==		==Improved Hardware Primitives==

Bsriggan: /* Hardware Implementations */

2010-04-19T16:34:37Z

Hardware Implementations

← Older revision		Revision as of 16:34, 19 April 2010
Line 5:		Line 5:


	Hardware implementations for synchronization traditionally include '''locks''', '''barriers''', and '''mutual exclusion'''. Locks are a block code in a parallel program that is meant to be executed by a single processor or thread. Barriers are different types of synchronization that wait for all threads to reach a specific point in the program. And mutual exclusion is the prevention from the concurrent access of shared data. 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 supported by the processor Instruction Set Architecture (ISA), are typically used for the hardware synchronization mechanism. Examples of these hardware synchronization mechanisms include: Test-and-Set, Fetch-and-Increment, Exchange, Compare-and-Swap. These types of synchronizations are used to provide mutual exclusion.		Hardware implementations for synchronization traditionally include '''locks''', '''barriers''', and '''mutual exclusion'''. Locks are a block code in a parallel program that is meant to be executed by a single processor or thread. Barriers are different types of synchronization that wait for all threads to reach a specific point in the program. And mutual exclusion is the prevention from the concurrent access of shared data. 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 supported by the processor Instruction Set Architecture (ISA), are typically used for the hardware synchronization mechanism. Examples of these hardware synchronization mechanisms include: Test-and-Set, Fetch-and-Increment, Exchange, Compare-and-Swap. These types of synchronizations are used to provide mutual exclusion. They are also used in lock implementations, such as '''Test-and-Set''' or '''Test-and-Test-and-Set'''. See examples below.

	===Software Implementations===		===Software Implementations===

Bsriggan: /* Hardware Implementations */

2010-04-19T16:29:59Z

Hardware Implementations

← Older revision		Revision as of 16:29, 19 April 2010
Line 5:		Line 5:


	Hardware implementations for synchronization traditionally include '''locks''', '''barriers''', and '''mutual exclusion'''. Locks are a block code in a parallel program that is meant to be executed by a single processor or thread. Barriers are different types of synchronization that wait for all threads to reach a specific point in the program. And mutual exclusion is the prevention from the concurrent access of shared data. 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 supported by the processor Instruction Set Architecture (ISA), are typically used for the hardware synchronization mechanism. Examples of these hardware synchronization mechanisms include: Test-and-Set, Fetch-and-Increment, ~~Test~~-and-~~Test-and-Set~~. These types of synchronizations are used to provide mutual exclusion.		Hardware implementations for synchronization traditionally include '''locks''', '''barriers''', and '''mutual exclusion'''. Locks are a block code in a parallel program that is meant to be executed by a single processor or thread. Barriers are different types of synchronization that wait for all threads to reach a specific point in the program. And mutual exclusion is the prevention from the concurrent access of shared data. 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 supported by the processor Instruction Set Architecture (ISA), are typically used for the hardware synchronization mechanism. Examples of these hardware synchronization mechanisms include: Test-and-Set, Fetch-and-Increment, Exchange, Compare-and-Swap. These types of synchronizations are used to provide mutual exclusion.

	===Software Implementations===		===Software Implementations===