CSC/ECE 506 Spring 2014/3a ns - Revision history

Admin at 18:19, 26 April 2014

2014-04-26T18:19:56Z

← Older revision		Revision as of 18:19, 26 April 2014
Line 16:		Line 16:
	When using any parallel programming model, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization]<ref>Rahman, M.M.; , "Process synchronization in multiprocessor and multi-core processor," Informatics, Electronics & Vision (ICIEV), 2012 International Conference on , vol., no., pp.554-559, 18-19 May 2012</ref> is needed to guarantee accuracy of the overall program. The following situations highlight the necessity of synchronization<ref>http://people.csail.mit.edu/rinard/paper/cpande99.pdf</ref>.		When using any parallel programming model, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization]<ref>Rahman, M.M.; , "Process synchronization in multiprocessor and multi-core processor," Informatics, Electronics & Vision (ICIEV), 2012 International Conference on , vol., no., pp.554-559, 18-19 May 2012</ref> is needed to guarantee accuracy of the overall program. The following situations highlight the necessity of synchronization<ref>http://people.csail.mit.edu/rinard/paper/cpande99.pdf</ref>.

	~~Case1~~: A scenario in which the code following a parallelized loop requires that all of the parallel [http://en.wikipedia.org/wiki/Process_(computer_science) processes] be completed before advancing.		Case 1: A scenario in which the code following a parallelized loop requires that all of the parallel [http://en.wikipedia.org/wiki/Process_(computer_science) processes] be completed before advancing.

	~~Case2~~: A scenario in which a code segment in the middle of a parallelized section needs to be executed sequentially (critical section), to ensure program correctness.		Case 2: A scenario in which a code segment in the middle of a parallelized section needs to be executed sequentially (critical section), to ensure program correctness.

	~~Case3~~: A scenario in which multiple processes must update a global variable in such a way that one process does not overwrite the updates of a different process.		Case 3: A scenario in which multiple processes must update a global variable in such a way that one process does not overwrite the updates of a different process.

	=== Synchronization Mechanisms ===		=== Synchronization Mechanisms ===

Admin: Fixed some of the punctuation mistkakes

2014-04-26T18:19:27Z

Fixed some of the punctuation mistkakes

← Older revision		Revision as of 18:19, 26 April 2014
Line 14:		Line 14:
	-----------------------		-----------------------

	When using any parallel programming ~~models~~, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization]<ref>Rahman, M.M.; , "Process synchronization in multiprocessor and multi-core processor," Informatics, Electronics & Vision (ICIEV), 2012 International Conference on , vol., no., pp.554-559, 18-19 May 2012</ref> is needed to guarantee accuracy of the overall program. The following situations highlight the necessity of synchronization<ref>http://people.csail.mit.edu/rinard/paper/cpande99.pdf</ref>.		When using any parallel programming model, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization]<ref>Rahman, M.M.; , "Process synchronization in multiprocessor and multi-core processor," Informatics, Electronics & Vision (ICIEV), 2012 International Conference on , vol., no., pp.554-559, 18-19 May 2012</ref> is needed to guarantee accuracy of the overall program. The following situations highlight the necessity of synchronization<ref>http://people.csail.mit.edu/rinard/paper/cpande99.pdf</ref>.

	Case1: A scenario in which the code following a parallelized loop requires that all of the parallel [http://en.wikipedia.org/wiki/Process_(computer_science) processes] be completed before advancing.		Case1: A scenario in which the code following a parallelized loop requires that all of the parallel [http://en.wikipedia.org/wiki/Process_(computer_science) processes] be completed before advancing.
Line 26:		Line 26:
	Let us now briefly understand the various [http://en.wikipedia.org/wiki/Synchronization_(computer_science)#Thread_or_process_synchronization process/thread synchronization mechanisms] that helps in achieving correct program execution order.		Let us now briefly understand the various [http://en.wikipedia.org/wiki/Synchronization_(computer_science)#Thread_or_process_synchronization process/thread synchronization mechanisms] that helps in achieving correct program execution order.

	'''Semaphore''' : [https://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore] is a variable that helps in controlling the access to a common resource in a parallel programming model. Not only do they arbitrate, but also help in avoiding race conditions. Semaphores keep only the count of the resource availability.		'''Semaphore''': [https://en.wikipedia.org/wiki/Semaphore_(programming) Semaphore] is a variable that helps in controlling the access to a common resource in a parallel programming model. Not only do they arbitrate, but also help in avoiding race conditions. Semaphores keep only the count of the resource availability.

	'''Mutex / Lock''' :[https://en.wikipedia.org/wiki/Mutex Mutex] refers to Mutual Exclusion. It helps avoiding concurrency issues like race conditions by ensuring that no two concurrently executed processes access a critical section at the same time. Though Mutexes are essentially the same as Semaphores, the fundamental differences between them are as follows [http://en.wikipedia.org/wiki/Semaphore_(programming)#Semaphores_vs._mutexes]:		'''Mutex / Lock''': [https://en.wikipedia.org/wiki/Mutex Mutex] refers to Mutual Exclusion. It helps avoiding concurrency issues like race conditions by ensuring that no two concurrently executed processes access a critical section at the same time. Though Mutexes are essentially the same as Semaphores, the fundamental differences between them are as follows [http://en.wikipedia.org/wiki/Semaphore_(programming)#Semaphores_vs._mutexes]:

	1. Mutexes allow exclusive process access to a resource. Semaphores allow any process to access a resource. Thus the element of ownership in mutex ensures that only the process that has locked the mutex can unlock it. However, in case of Semaphores, the process locking and unlocking the semaphore can be different.		1. Mutexes allow exclusive process access to a resource. Semaphores allow any process to access a resource. Thus the element of ownership in mutex ensures that only the process that has locked the mutex can unlock it. However, in case of Semaphores, the process locking and unlocking the semaphore can be different.
Line 89:		Line 89:
	Return Value: sem_post() returns 0 on success; on error, the value of the semaphore is left unchanged, -1 is returned, and errno is set to indicate the error.		Return Value: sem_post() returns 0 on success; on error, the value of the semaphore is left unchanged, -1 is returned, and errno is set to indicate the error.

	===='''~~Pseudo Code~~'''====		===='''Pseudocode'''====

	<code>		<code>
Line 162:		Line 162:
	Return Value: The functions return a zero on success; otherwise, an error number is returned to indicate the error.		Return Value: The functions return a zero on success; otherwise, an error number is returned to indicate the error.

	====='''~~Pseudo code~~'''=====		====='''Pseudocode'''=====
	<code>		<code>
	pthread_mutex_t *mutex,		pthread_mutex_t *mutex,
Line 399:		Line 399:
	Return Value: Upon successful completion, the functions returns zero; otherwise, an error number is returned to indicate the error.		Return Value: Upon successful completion, the functions returns zero; otherwise, an error number is returned to indicate the error.

	====='''~~Pseudo code~~'''=====		====='''Pseudocode'''=====
	<code>		<code>
	pthread_barrier_t *barrier;		pthread_barrier_t *barrier;
Line 440:		Line 440:
	"sum" can be protected using various synchronization mechanisms like semaphores, mutexes and condition variables. They are illustrated as follows.		"sum" can be protected using various synchronization mechanisms like semaphores, mutexes and condition variables. They are illustrated as follows.

	'''Semaphore ~~Pseudo Code~~'''		'''Semaphore Pseudocode'''

	sem_t * sem;		sem_t * sem;
Line 454:		Line 454:
	Even though semaphore achieves the objective of protecting the critical section, mutex provides additional security by preventing accidental deletion of locks. This property is due to the exclusive ownership property associated with mutex variables where only the locked mutex can unlock the critical section.		Even though semaphore achieves the objective of protecting the critical section, mutex provides additional security by preventing accidental deletion of locks. This property is due to the exclusive ownership property associated with mutex variables where only the locked mutex can unlock the critical section.

	'''Mutex ~~Pseudo Code~~'''		'''Mutex Pseudocode'''

	pthread_mutext * mut_id;		pthread_mutext * mut_id;
Line 468:		Line 468:
	Suppose in the above example the thread has to wait for some other arbitrary process to complete in the critical section, then conditional variable synchronization can be used. Here the mutex will wait until a condition variable is satisfied. The setting of a condition variable is controlled by other another thread. This is illustrated as follows.		Suppose in the above example the thread has to wait for some other arbitrary process to complete in the critical section, then conditional variable synchronization can be used. Here the mutex will wait until a condition variable is satisfied. The setting of a condition variable is controlled by other another thread. This is illustrated as follows.

	'''Conditional Variable ~~Pseudo Code~~'''		'''Conditional Variable Pseudocode'''

	//thread 1: main thread		//thread 1: main thread
Line 500:		Line 500:
	In the above example, minimum of "a" can be calculated only after the computations for "a" is complete. The Barrier implementation for the above code segment is shown below:		In the above example, minimum of "a" can be calculated only after the computations for "a" is complete. The Barrier implementation for the above code segment is shown below:

	'''Barrier ~~Pseudo Code~~'''		'''Barrier Pseudocode'''

	pthread_barrier_t* bar;		pthread_barrier_t* bar;
Line 524:		Line 524:
	S1 does not have any inter loop dependencies. However, S2 is dependent on S1, and S2 has inter loop dependencies. Thus we can parallelize S1 without any synchronization. However, we need synchronization mechanisms for S2. The above code can be parallelized using semaphores and mutexes. The advantages of using mutex over semaphore is the same as mentioned before in DOALL parallelism. They are illustrated as follows.		S1 does not have any inter loop dependencies. However, S2 is dependent on S1, and S2 has inter loop dependencies. Thus we can parallelize S1 without any synchronization. However, we need synchronization mechanisms for S2. The above code can be parallelized using semaphores and mutexes. The advantages of using mutex over semaphore is the same as mentioned before in DOALL parallelism. They are illustrated as follows.

	'''Semaphore ~~Pseudo Code~~'''		'''Semaphore Pseudocode'''

	sem_t * sem; /* a vector of semaphores used to keep track of each loop */		sem_t * sem; /* a vector of semaphores used to keep track of each loop */
Line 536:		Line 536:
	}		}

	'''Mutex ~~Pseudo Code~~'''		'''Mutex Pseudocode'''

	pthread_mutext * mut_id;// a vector of semaphores of length N is used		pthread_mutext * mut_id;// a vector of semaphores of length N is used
Line 562:		Line 562:
	The above code can be parallelized using semaphores and mutexes. They are illustrated as follows.		The above code can be parallelized using semaphores and mutexes. They are illustrated as follows.

	'''Semaphore ~~Pseudo Code~~'''		'''Semaphore Pseudodode'''

	sem_t * sem;		sem_t * sem;
Line 580:		Line 580:
	}		}

	'''Mutex ~~Pseudo Code~~'''		'''Mutex Pseudocode'''

	pthread_mutex_t * mut_id;		pthread_mutex_t * mut_id;

Nkrishn: /* DOPIPE Parallelism */

2014-03-03T19:56:21Z

DOPIPE Parallelism

← Older revision		Revision as of 19:56, 3 March 2014
Line 559:		Line 559:
	}		}

	S1 has inter loop dependencies. S2 depends on S1 even though S2 does not have loop dependencies. Hence S2 can be executed only after S1 is executed in ~~one~~ loop. This necessitates the use of synchronization mechanisms.		S1 has inter loop dependencies. S2 depends on S1 even though S2 does not have loop dependencies. Hence S2 can be executed only after S1 is executed in each loop. This necessitates the use of synchronization mechanisms.
	The above code can be parallelized using semaphores and ~~mutex~~. They are illustrated as follows.		The above code can be parallelized using semaphores and mutexes. They are illustrated as follows.

	'''Semaphore Pseudo Code'''		'''Semaphore Pseudo Code'''

Nkrishn: /* DOACROSS Parallelism */

2014-03-03T19:54:40Z

DOACROSS Parallelism

← Older revision		Revision as of 19:54, 3 March 2014
Line 522:		Line 522:
	}		}

	S1 does not have any loop dependencies. However, S2 is dependent on S1, and S2 is loop ~~dependent~~. Thus we can parallelize S1 without any synchronization. However, we need synchronization mechanisms for S2. The above code can be parallelized using semaphores and ~~mutex~~. The advantages of using mutex over semaphore is the same as mentioned before in DOALL parallelism. They are illustrated as follows.		S1 does not have any inter loop dependencies. However, S2 is dependent on S1, and S2 has inter loop dependencies. Thus we can parallelize S1 without any synchronization. However, we need synchronization mechanisms for S2. The above code can be parallelized using semaphores and mutexes. The advantages of using mutex over semaphore is the same as mentioned before in DOALL parallelism. They are illustrated as follows.

	'''Semaphore Pseudo Code'''		'''Semaphore Pseudo Code'''

Nkrishn: /* DOACROSS Parallelism */

2014-03-03T19:52:22Z

DOACROSS Parallelism

← Older revision		Revision as of 19:52, 3 March 2014
Line 522:		Line 522:
	}		}

	S1 do not have any loop dependencies. However, S2 is dependent on S1, and S2 is loop dependent. Thus we can parallelize S1 without any synchronization. However, we need synchronization mechanisms for S2. The above code can be parallelized using semaphores and mutex. The advantages of using mutex over semaphore is the same as mentioned before in DOALL parallelism. They are illustrated as follows.		S1 does not have any loop dependencies. However, S2 is dependent on S1, and S2 is loop dependent. Thus we can parallelize S1 without any synchronization. However, we need synchronization mechanisms for S2. The above code can be parallelized using semaphores and mutex. The advantages of using mutex over semaphore is the same as mentioned before in DOALL parallelism. They are illustrated as follows.

	'''Semaphore Pseudo Code'''		'''Semaphore Pseudo Code'''

Nkrishn: /* DOALL Parallelism */

2014-03-03T19:51:08Z

DOALL Parallelism

← Older revision		Revision as of 19:51, 3 March 2014
Line 489:		Line 489:
	pthread_mutex_unlock ( mut_id ); /* exit mutex*/		pthread_mutex_unlock ( mut_id ); /* exit mutex*/
	}		}


	The previous example does not mandate barrier synchronization, as the purpose was to avoid shared memory read contention. The purpose of barrier synchronization is to address the case when one needs to complete all parallel tasks until a common point before proceeding. Consider the following code, amenable to DOALL parallelism, slightly modified for illustrating barrier synchronization.		The previous example does not mandate barrier synchronization, as the purpose was to avoid shared memory read contention. The purpose of barrier synchronization is to address the case when one needs to complete all parallel tasks until a common point before proceeding. Consider the following code, amenable to DOALL parallelism, slightly modified for illustrating barrier synchronization.

Nkrishn: /* DOALL Parallelism */

2014-03-03T19:49:08Z

DOALL Parallelism

← Older revision		Revision as of 19:49, 3 March 2014
Line 437:		Line 437:
	}		}

	There are no dependencies ~~between~~ S1 and S2 ~~inside the loop~~, but we can see that "sum" is a critical variable.		There are no loop dependencies for S1 and S2, but we can see that "sum" is a critical variable.
	"sum" can be protected using various synchronization mechanisms like semaphores, mutexes and condition variables. They are illustrated as follows.		"sum" can be protected using various synchronization mechanisms like semaphores, mutexes and condition variables. They are illustrated as follows.

Nkrishn: /* Necessity */

2014-03-03T19:41:35Z

Necessity

← Older revision		Revision as of 19:41, 3 March 2014
Line 18:		Line 18:
	Case1: A scenario in which the code following a parallelized loop requires that all of the parallel [http://en.wikipedia.org/wiki/Process_(computer_science) processes] be completed before advancing.		Case1: A scenario in which the code following a parallelized loop requires that all of the parallel [http://en.wikipedia.org/wiki/Process_(computer_science) processes] be completed before advancing.

	Case2: A scenario in which a code segment in the middle of parallelized section needs to be executed sequentially (critical section), to ensure program correctness.		Case2: A scenario in which a code segment in the middle of a parallelized section needs to be executed sequentially (critical section), to ensure program correctness.

	Case3: A scenario in which multiple processes must update a global variable in such a way that one process does not overwrite the updates of a different process.		Case3: A scenario in which multiple processes must update a global variable in such a way that one process does not overwrite the updates of a different process.

Nkrishn: /* DOPIPE Parallelism */

2014-03-03T19:39:49Z

DOPIPE Parallelism

← Older revision		Revision as of 19:39, 3 March 2014
Line 560:		Line 560:
	}		}

			S1 has inter loop dependencies. S2 depends on S1 even though S2 does not have loop dependencies. Hence S2 can be executed only after S1 is executed in one loop. This necessitates the use of synchronization mechanisms.
	The above code can be parallelized using semaphores and mutex. They are illustrated as follows.		The above code can be parallelized using semaphores and mutex. They are illustrated as follows.

Nkrishn: /* DOACROSS Parallelism */

2014-03-03T19:33:05Z

DOACROSS Parallelism

← Older revision		Revision as of 19:33, 3 March 2014
Line 523:		Line 523:
	}		}

	S1 do not have any loop dependencies. However, S2 is dependent on S1 and S2 is loop dependent. Thus we can parallelize S1 without any ~~synchonoization~~. However, we need synchronization mechanisms for S2. The above code can be parallelized using semaphores and mutex. They are illustrated as follows.		S1 do not have any loop dependencies. However, S2 is dependent on S1, and S2 is loop dependent. Thus we can parallelize S1 without any synchronization. However, we need synchronization mechanisms for S2. The above code can be parallelized using semaphores and mutex. The advantages of using mutex over semaphore is the same as mentioned before in DOALL parallelism. They are illustrated as follows.

	'''Semaphore Pseudo Code'''		'''Semaphore Pseudo Code'''