Chapter 4b CSC/ECE 506 Spring 2011 / ch4b - Revision history

Dbharga at 19:43, 24 April 2011

2011-04-24T19:43:53Z

← Older revision		Revision as of 19:43, 24 April 2011
Line 154:		Line 154:


	==Load Balancing ==		=Load Balancing =


Line 167:		Line 167:


	==Gang Scheduling==		=Gang Scheduling=

Dbharga: /* References */

2011-04-24T19:41:23Z

References

← Older revision		Revision as of 19:41, 24 April 2011
Line 181:		Line 181:


	##Culler David E., Singh Jaswinder pal, Gupta Anoop 2000. Parallel Computer Architecture a Hardware / Software approach. Morgan Kaufmann Publishers, CA, USA.		Culler David E., Singh Jaswinder pal, Gupta Anoop 2000. Parallel Computer Architecture a Hardware / Software approach. Morgan Kaufmann Publishers, CA, USA.

			Solhini Yan 2009. Fundamentals of Parallel Computer Architecture Multichip and Multicore systems. Student edition, Solihin Publishing and Consulting LLC, USA.

			Hwang Kai 1993. Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGraw-Hill, Inc. USA.

	~~##Solhini Yan 2009~~. ~~Fundamentals of Parallel~~ Computer Architecture ~~Multichip~~ and ~~Multicore systems~~. ~~Student edition~~, ~~Solihin Publishing and Consulting LLC~~, ~~USA~~.		Flynn Micheal J. 1995. Computer Architecture : Pipelined and Parallel Processor Design. Jones and Barlette Publishers, Inc. London, UK.

			Patterson David A., Hannessy John L. 1995. Computer Architecture A Quantitative Approach. 2^nd^ Ed., Morgan Kaufmann Publishers, CA, USA.

			Sima Deszo, Fountain Terence, Kacsuk Peter, 1997. Advanced Computer Architecture A Design Space Approach. Addison Wesley Longman, Essex, England.

	~~##Hwang Kai~~ 1993. ~~Advanced~~ Computer Architecture~~: Parallelism, Scalability~~, ~~Programmability. McGraw~~-~~Hill,~~ Inc. USA.		Stone Harold S., 1993. High-Performance Computer Architecture. 3^rd^ Ed., Addison-Wesley Publishing Company Inc., MA, USA.

			Abd-El-Barr Mostafa, El-Rewini Hesham, 2005. Advanced Computer Architecture and Parallel Processing. John Wiley & Sons, Inc. Hoboken, New Jersey, USA.

	~~##Flynn Micheal J~~. ~~1995~~. Computer Architecture ~~: Pipelined and~~ Parallel ~~Processor Design~~. ~~Jones and Barlette Publishers~~, Inc. ~~London, UK~~.		Briggs Faye A., Hwang Kai, 1984. Computer Architecture And Parallel Processing. McGraw-Hill, Inc. USA.

			Wilkinson Barry, 1996. Computer Architecture Design and Performance. 2^nd^ Ed., Prentice Hall Europe, Englewood Cliffs, NJ.

	~~##Patterson David A~~.~~, Hannessy John L. 1995~~. Computer ~~Architecture A Quantitative Approach. 2^nd^ Ed~~., ~~Morgan Kaufmann Publishers, CA~~, USA.		Shiva Sajjan G. 1996. Pipelined and Parallel Computer Architectures. HarperCollins, NY, USA.

			Sinapova Lydia, Operating Systems: Multiprocessor and Real-Time Scheduling. [http://faculty.simpson.edu/lydia.sinapova/www/cmsc335/cmsc335-01/CH10-RT.htm [Load\|http://faculty.simpson.edu/lydia.sinapova/www/cmsc335/cmsc335-01/CH10-RT.htm%20%5C%20Load]

	~~##Sima Deszo, Fountain Terence~~, ~~Kacsuk Peter~~, ~~1997~~. ~~Advanced Computer Architecture A Design Space Approach~~. ~~Addison Wesley Longman~~, ~~Essex~~, ~~England~~.		Squillante Mark S., Wang Fang , Papaefthymio Marios. An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments. Yale University, New Haven, CT.

			Gang Scheduling, Timesharing on Parallel Computers, SC98, November 1998 (a summary)[http://www.llnl.gov/asci/pse_trilab/sc98.summary.html]
	~~##Stone Harold S., 1993. High-Performance Computer Architecture. 3^rd^ Ed., Addison-Wesley Publishing Company Inc., MA, USA.~~


	~~##Abd-El-Barr Mostafa, El-Rewini Hesham, 2005. Advanced Computer Architecture and Parallel Processing. John Wiley & Sons, Inc. Hoboken, New Jersey, USA.~~


	~~##Briggs Faye A., Hwang Kai, 1984. Computer Architecture And Parallel Processing. McGraw-Hill, Inc. USA.~~


	~~##Wilkinson Barry, 1996. Computer Architecture Design and Performance. 2^nd^ Ed., Prentice Hall Europe, Englewood Cliffs, NJ.~~


	~~Shiva Sajjan G. 1996. Pipelined and Parallel Computer Architectures. HarperCollins, NY, USA.~~


	Sinapova Lydia, Operating Systems: Multiprocessor and Real-Time Scheduling. [http://faculty.simpson.edu/lydia.sinapova/www/cmsc335/cmsc335-01/CH10-RT.htm#Load\|http://faculty.simpson.edu/lydia.sinapova/www/cmsc335/cmsc335-01/CH10-RT.htm%20%5C%20Load]


	~~Squillante Mark S., Wang Fang , Papaefthymio Marios. An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments. Yale University, New Haven, CT.~~


	Gang Scheduling, Timesharing on Parallel Computers, SC98, November 1998 (a summary)[http://www.llnl.gov/asci/pse_trilab/sc98.summary.html]

	Intel ISN, 2010. Granularity and Parallel Performance. [http://www.codeproject.com/Members/Intel-ISN]		Intel ISN, 2010. Granularity and Parallel Performance. [http://www.codeproject.com/Members/Intel-ISN]

			Ding-Kai Chen, et al. The Impact of Synchronization and Granularity on Parallel Systems”, _Proceedings of the 17th Annual International Symposium on Computer Architecture 1990_, Seattle, Washington, USA.
	Ding-Kai Chen, et al. The Impact of Synchronization and Granularity on Parallel Systems”, _Proceedings of the 17th Annual International Symposium on Computer Architecture 1990_, Seattle, Washington, USA.

Dbharga: /* References */

2011-04-24T19:40:05Z

References

← Older revision		Revision as of 19:40, 24 April 2011
Line 181:		Line 181:


	##Culler David E., Singh Jaswinder pal, Gupta Anoop 2000. Parallel Computer Architecture a Hardware / Software approach. Morgan Kaufmann Publishers, CA, USA.		##Culler David E., Singh Jaswinder pal, Gupta Anoop 2000. Parallel Computer Architecture a Hardware / Software approach. Morgan Kaufmann Publishers, CA, USA.



	##Solhini Yan 2009. Fundamentals of Parallel Computer Architecture Multichip and Multicore systems. Student edition, Solihin Publishing and Consulting LLC, USA.		##Solhini Yan 2009. Fundamentals of Parallel Computer Architecture Multichip and Multicore systems. Student edition, Solihin Publishing and Consulting LLC, USA.



	##Hwang Kai 1993. Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGraw-Hill, Inc. USA.		##Hwang Kai 1993. Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGraw-Hill, Inc. USA.

Dbharga at 19:39, 24 April 2011

2011-04-24T19:39:32Z

← Older revision		Revision as of 19:39, 24 April 2011
Line 181:		Line 181:


	Culler David E., Singh Jaswinder pal, Gupta Anoop 2000. Parallel Computer Architecture a Hardware / Software approach. Morgan Kaufmann Publishers, CA, USA.		##Culler David E., Singh Jaswinder pal, Gupta Anoop 2000. Parallel Computer Architecture a Hardware / Software approach. Morgan Kaufmann Publishers, CA, USA.



	Solhini Yan 2009. Fundamentals of Parallel Computer Architecture Multichip and Multicore systems. Student edition, Solihin Publishing and Consulting LLC, USA.		##Solhini Yan 2009. Fundamentals of Parallel Computer Architecture Multichip and Multicore systems. Student edition, Solihin Publishing and Consulting LLC, USA.



	Hwang Kai 1993. Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGraw-Hill, Inc. USA.		##Hwang Kai 1993. Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGraw-Hill, Inc. USA.


	Flynn Micheal J. 1995. Computer Architecture : Pipelined and Parallel Processor Design. Jones and Barlette Publishers, Inc. London, UK.		##Flynn Micheal J. 1995. Computer Architecture : Pipelined and Parallel Processor Design. Jones and Barlette Publishers, Inc. London, UK.


	Patterson David A., Hannessy John L. 1995. Computer Architecture A Quantitative Approach. 2^nd^ Ed., Morgan Kaufmann Publishers, CA, USA.		##Patterson David A., Hannessy John L. 1995. Computer Architecture A Quantitative Approach. 2^nd^ Ed., Morgan Kaufmann Publishers, CA, USA.


	Sima Deszo, Fountain Terence, Kacsuk Peter, 1997. Advanced Computer Architecture A Design Space Approach. Addison Wesley Longman, Essex, England.		##Sima Deszo, Fountain Terence, Kacsuk Peter, 1997. Advanced Computer Architecture A Design Space Approach. Addison Wesley Longman, Essex, England.


	Stone Harold S., 1993. High-Performance Computer Architecture. 3^rd^ Ed., Addison-Wesley Publishing Company Inc., MA, USA.		##Stone Harold S., 1993. High-Performance Computer Architecture. 3^rd^ Ed., Addison-Wesley Publishing Company Inc., MA, USA.


	Abd-El-Barr Mostafa, El-Rewini Hesham, 2005. Advanced Computer Architecture and Parallel Processing. John Wiley & Sons, Inc. Hoboken, New Jersey, USA.		##Abd-El-Barr Mostafa, El-Rewini Hesham, 2005. Advanced Computer Architecture and Parallel Processing. John Wiley & Sons, Inc. Hoboken, New Jersey, USA.


	Briggs Faye A., Hwang Kai, 1984. Computer Architecture And Parallel Processing. McGraw-Hill, Inc. USA.		##Briggs Faye A., Hwang Kai, 1984. Computer Architecture And Parallel Processing. McGraw-Hill, Inc. USA.


	Wilkinson Barry, 1996. Computer Architecture Design and Performance. 2^nd^ Ed., Prentice Hall Europe, Englewood Cliffs, NJ.		##Wilkinson Barry, 1996. Computer Architecture Design and Performance. 2^nd^ Ed., Prentice Hall Europe, Englewood Cliffs, NJ.

Dbharga at 19:36, 24 April 2011

2011-04-24T19:36:59Z

Dbharga at 19:36, 24 April 2011

2011-04-24T19:36:14Z

Show changes

Dbharga at 19:31, 24 April 2011

2011-04-24T19:31:09Z

← Older revision		Revision as of 19:31, 24 April 2011
Line 9:		Line 9:
	== Index ==		== Index ==

	~~'''~~ Introduction~~'''~~		# Introduction
	## Parallel Thread Granularity		# Parallel Thread Granularity
	## Instruction Level Parallelism:		## Instruction Level Parallelism:
	## Loop Level Parallelism		## Loop Level Parallelism
Line 20:		Line 20:
	# Gang Scheduling		# Gang Scheduling

	\\

	\\

	Introduction		= Introduction =

	\\

	The granularity of parallel threads depends quite closely on the architecture. For attaining good parallel performance it is important to use the right granularity. Granularity can be defined as the amount of work done by a task, between communications with other tasks. Granularity of parallel threads is achieved at the expense of communication overhead, load balance and extra work to be done by threads. If granularity is too fine, then performance can suffer from communication overhead. If granularity is too coarse, then performance can suffer from load imbalance. If granularity is too fine, the overhead of creating and communicating with threads is too great. There is a middle ground where communication overhead is reduced. The goal of design should to determine the right granularity for parallel tasks, while avoiding load imbalance and communication overhead to achieve the best performance.		The granularity of parallel threads depends quite closely on the architecture. For attaining good parallel performance it is important to use the right granularity. Granularity can be defined as the amount of work done by a task, between communications with other tasks. Granularity of parallel threads is achieved at the expense of communication overhead, load balance and extra work to be done by threads. If granularity is too fine, then performance can suffer from communication overhead. If granularity is too coarse, then performance can suffer from load imbalance. If granularity is too fine, the overhead of creating and communicating with threads is too great. There is a middle ground where communication overhead is reduced. The goal of design should to determine the right granularity for parallel tasks, while avoiding load imbalance and communication overhead to achieve the best performance.
Line 32:		Line 28:
	Granularity is calculated in terms of computation time and communication time, or in terms of coarse, medium or fine granularity.		Granularity is calculated in terms of computation time and communication time, or in terms of coarse, medium or fine granularity.

	\\

	Granularity = Computation Time / Communication Time		Granularity = Computation Time / Communication Time

	\\

	This ratio is a measure of how much overhead is produced per unit of computation. A large granularity implies that the communication overhead is insignificant compared to computation time while a low ratio implies that the communication overhead dominates computation time, that which results in poor performance. Message-passing multiprocessors usually employ medium/coarse granularity. Fine granularity is used in dataflow systems. With coarse granularity, each process contains a large number of sequential instructions and takes a substantial time to execute. In fine granularity, a process might consist of a few instructions or just one instruction. As the granularity is reduced, the process communication overhead generally increases. It is particularly desirable to reduce the communication overhead because of the significant time for communication. The tendency to obtain maximum performance is to resort to finest possible granularity, which leads to highest degree of parallelism. But maximum parallelism should not lead to increasing overhead.		This ratio is a measure of how much overhead is produced per unit of computation. A large granularity implies that the communication overhead is insignificant compared to computation time while a low ratio implies that the communication overhead dominates computation time, that which results in poor performance. Message-passing multiprocessors usually employ medium/coarse granularity. Fine granularity is used in dataflow systems. With coarse granularity, each process contains a large number of sequential instructions and takes a substantial time to execute. In fine granularity, a process might consist of a few instructions or just one instruction. As the granularity is reduced, the process communication overhead generally increases. It is particularly desirable to reduce the communication overhead because of the significant time for communication. The tendency to obtain maximum performance is to resort to finest possible granularity, which leads to highest degree of parallelism. But maximum parallelism should not lead to increasing overhead.

	\\

	In message passing systems overhead can be reduced by mapping several processes onto one processor and switching from one process to another when a processes held up by message passing. The disadvantage of static assignment is that load sharing will be unclear before program is actually executed. Code and data have to be physically transferred to the local memory of each node prior to execution, and this transfer can cause a significant amount of overhead. Similarly results need to be transferred from the nodes to the host system. Clearly, the computation to be performed needs to be reasonably long to lessen the loading overhead.		In message passing systems overhead can be reduced by mapping several processes onto one processor and switching from one process to another when a processes held up by message passing. The disadvantage of static assignment is that load sharing will be unclear before program is actually executed. Code and data have to be physically transferred to the local memory of each node prior to execution, and this transfer can cause a significant amount of overhead. Similarly results need to be transferred from the nodes to the host system. Clearly, the computation to be performed needs to be reasonably long to lessen the loading overhead.

	\\

	Parallel Thread Granularity
			=Parallel Thread Granularity=

	\\		\\

Dbharga at 19:29, 24 April 2011

2011-04-24T19:29:53Z

← Older revision		Revision as of 19:29, 24 April 2011
Line 10:		Line 10:

	''' Introduction'''		''' Introduction'''
	Parallel Thread Granularity		## Parallel Thread Granularity
	## Instruction Level Parallelism:		## Instruction Level Parallelism:
	## Loop Level Parallelism		## Loop Level Parallelism

Dbharga at 19:29, 24 April 2011

2011-04-24T19:29:22Z

@@ Line 1: / Line 1: @@
 == Chapter 4b CSC/ECE 506 Spring 2011 / ch4b ==
 As a book on computer architecture, the text does not go into a great deal of detail on parallel programming techniques. Many of the topics that are mentioned in Chapter 4 can be explored in greater depth. The granularity of parallel threads depends quite closely on the architecture. The granularity of synchronization is a topic that has been studied for many years. There are times when, due to the overhead of locking, it does not make sense to invoke a lock, but rather, just to wait in a loop until a specific predicate is satisfied. This can be considered in more detail, but be sure not to overlap the discussion of lock implementations in Chapter 9 of Solihin.
@@ Line 21: / Line 6: @@
 The textbook considers scheduling and load balancing in somewhat greater detail, but much more can be said. For example, one might consider when [gang scheduling|http://en.wikipedia.org/wiki/Gang_scheduling] is useful; this depends on the overhead of communication and task management. The same is true of load balancing; discuss the tradeoff between static and dynamic scheduling, and different approaches to dynamic scheduling.
-\\
+== Index  ==
-# Introduction
+''' Introduction'''
-# Parallel Thread Granularity
+ Parallel Thread Granularity
 ## Instruction Level Parallelism:
 ## Loop Level Parallelism

Dbharga at 19:27, 24 April 2011

2011-04-24T19:27:57Z

← Older revision		Revision as of 19:27, 24 April 2011
Line 1:		Line 1:

	== Chapter 4b CSC/ECE 506 Spring 2011 / ch4b ==		== Chapter 4b CSC/ECE 506 Spring 2011 / ch4b ==

← Older revision		Revision as of 19:36, 24 April 2011
Line 181:		Line 181:


	# Culler David E., Singh Jaswinder pal, Gupta Anoop 2000. Parallel Computer Architecture a Hardware / Software approach. Morgan Kaufmann Publishers, CA, USA.		Culler David E., Singh Jaswinder pal, Gupta Anoop 2000. Parallel Computer Architecture a Hardware / Software approach. Morgan Kaufmann Publishers, CA, USA.



	# Solhini Yan 2009. Fundamentals of Parallel Computer Architecture Multichip and Multicore systems. Student edition, Solihin Publishing and Consulting LLC, USA.		Solhini Yan 2009. Fundamentals of Parallel Computer Architecture Multichip and Multicore systems. Student edition, Solihin Publishing and Consulting LLC, USA.



	# Hwang Kai 1993. Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGraw-Hill, Inc. USA.		Hwang Kai 1993. Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGraw-Hill, Inc. USA.


	# Flynn Micheal J. 1995. Computer Architecture : Pipelined and Parallel Processor Design. Jones and Barlette Publishers, Inc. London, UK.		Flynn Micheal J. 1995. Computer Architecture : Pipelined and Parallel Processor Design. Jones and Barlette Publishers, Inc. London, UK.


	# Patterson David A., Hannessy John L. 1995. Computer Architecture A Quantitative Approach. 2^nd^ Ed., Morgan Kaufmann Publishers, CA, USA.		Patterson David A., Hannessy John L. 1995. Computer Architecture A Quantitative Approach. 2^nd^ Ed., Morgan Kaufmann Publishers, CA, USA.


	# Sima Deszo, Fountain Terence, Kacsuk Peter, 1997. Advanced Computer Architecture A Design Space Approach. Addison Wesley Longman, Essex, England.		Sima Deszo, Fountain Terence, Kacsuk Peter, 1997. Advanced Computer Architecture A Design Space Approach. Addison Wesley Longman, Essex, England.


	# Stone Harold S., 1993. High-Performance Computer Architecture. 3^rd^ Ed., Addison-Wesley Publishing Company Inc., MA, USA.		Stone Harold S., 1993. High-Performance Computer Architecture. 3^rd^ Ed., Addison-Wesley Publishing Company Inc., MA, USA.


	# Abd-El-Barr Mostafa, El-Rewini Hesham, 2005. Advanced Computer Architecture and Parallel Processing. John Wiley & Sons, Inc. Hoboken, New Jersey, USA.		Abd-El-Barr Mostafa, El-Rewini Hesham, 2005. Advanced Computer Architecture and Parallel Processing. John Wiley & Sons, Inc. Hoboken, New Jersey, USA.


	# Briggs Faye A., Hwang Kai, 1984. Computer Architecture And Parallel Processing. McGraw-Hill, Inc. USA.		Briggs Faye A., Hwang Kai, 1984. Computer Architecture And Parallel Processing. McGraw-Hill, Inc. USA.


	# Wilkinson Barry, 1996. Computer Architecture Design and Performance. 2^nd^ Ed., Prentice Hall Europe, Englewood Cliffs, NJ.		Wilkinson Barry, 1996. Computer Architecture Design and Performance. 2^nd^ Ed., Prentice Hall Europe, Englewood Cliffs, NJ.


	# Shiva Sajjan G. 1996. Pipelined and Parallel Computer Architectures. HarperCollins, NY, USA.		Shiva Sajjan G. 1996. Pipelined and Parallel Computer Architectures. HarperCollins, NY, USA.


	# Sinapova Lydia, Operating Systems: Multiprocessor and Real-Time Scheduling. [http://faculty.simpson.edu/lydia.sinapova/www/cmsc335/cmsc335-01/CH10-RT.htm#Load\|http://faculty.simpson.edu/lydia.sinapova/www/cmsc335/cmsc335-01/CH10-RT.htm%20%5C%20Load]		Sinapova Lydia, Operating Systems: Multiprocessor and Real-Time Scheduling. [http://faculty.simpson.edu/lydia.sinapova/www/cmsc335/cmsc335-01/CH10-RT.htm#Load\|http://faculty.simpson.edu/lydia.sinapova/www/cmsc335/cmsc335-01/CH10-RT.htm%20%5C%20Load]


	# Squillante Mark S., Wang Fang , Papaefthymio Marios. An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments. Yale University, New Haven, CT.		Squillante Mark S., Wang Fang , Papaefthymio Marios. An Analysis of Gang Scheduling for Multiprogrammed Parallel Computing Environments. Yale University, New Haven, CT.


	# Gang Scheduling, Timesharing on Parallel Computers, SC98, November 1998 (a summary)[http://www.llnl.gov/asci/pse_trilab/sc98.summary.html]		Gang Scheduling, Timesharing on Parallel Computers, SC98, November 1998 (a summary)[http://www.llnl.gov/asci/pse_trilab/sc98.summary.html]

	#Intel ISN, 2010. Granularity and Parallel Performance. [http://www.codeproject.com/Members/Intel-ISN]		Intel ISN, 2010. Granularity and Parallel Performance. [http://www.codeproject.com/Members/Intel-ISN]


	# Ding-Kai Chen, et al. The Impact of Synchronization and Granularity on Parallel Systems”, _Proceedings of the 17th Annual International Symposium on Computer Architecture 1990_, Seattle, Washington, USA.		Ding-Kai Chen, et al. The Impact of Synchronization and Granularity on Parallel Systems”, _Proceedings of the 17th Annual International Symposium on Computer Architecture 1990_, Seattle, Washington, USA.