CSC/ECE 506 Spring 2013/4a aj - Revision history

Aeveret at 04:21, 15 February 2013

2013-02-15T04:21:00Z

← Older revision		Revision as of 04:21, 15 February 2013
Line 102:		Line 102:
	* Lack of knowledge of loop sizes		* Lack of knowledge of loop sizes
	* Conditional statements that can only be analyzed at runtime		* Conditional statements that can only be analyzed at runtime
			* Pointer-linked data structures pose challenges
	==Examples==		==Examples==
	===Power FORTRAN Analyzer===		===Power FORTRAN Analyzer===

Aeveret at 04:16, 15 February 2013

2013-02-15T04:16:35Z

← Older revision		Revision as of 04:16, 15 February 2013
Line 92:		Line 92:

	===Speculation===		===Speculation===
	~~Under this paradigm a compiler will aggressively identify opportunities for parallelism~~, and ~~some of these opportunities will be unsafe~~.		Thread-level speculation refers to an environment where execution threads operate speculatively, performing potentially unsafe operations, and temporarily buffering the state they generate in a buffer or cache.<ref>http://iacoma.cs.uiuc.edu/iacoma-papers/encyclopedia_tls.pdf</ref> At some later point, it is determined whether the operations were correct or not, and if not then the thread is killed and may restart. Otherwise, the changes are committed and perhaps performance improvements that were non-obvious have taken place.
	<ref>http://iacoma.cs.uiuc.edu/iacoma-papers/encyclopedia_tls.pdf</ref>

	==Limitations==		==Limitations==
Line 99:		Line 98:
	===Limitations===		===Limitations===
	* Tradeoff of program size and execution speed		* Tradeoff of program size and execution speed
			* Inability to rewrite inefficient algorithms
			* Tradeoff between ensuring serialization and exploiting non-obvious parallelism
			* Lack of knowledge of loop sizes
			* Conditional statements that can only be analyzed at runtime
	==Examples==		==Examples==
	===Power FORTRAN Analyzer===		===Power FORTRAN Analyzer===
Line 147:		Line 149:
	-paralell, automatic parallelization		-paralell, automatic parallelization
	[http://www.multicore-challenge.org/resources/FMCCII_Tutorial_Pabst.pdf]		[http://www.multicore-challenge.org/resources/FMCCII_Tutorial_Pabst.pdf]
			===Gnu Compiler Collection (GCC)===
			GCC supports instruction-level parallelism, vectorization, OpenMP, and a Message Passing Interface.
			<ref>http://www.redhat.com/f/summitfiles/presentation/May31/Developer%20Tools/Novillo_ParallelProgGCC.pdf</ref>
	=='''References'''==		=='''References'''==
	<references/>		<references/>

Aeveret: /* Parallelization Techniques in Compilershttp://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdfhttp://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf */

2013-02-14T23:16:01Z

Parallelization Techniques in Compilershttp://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdfhttp://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf

← Older revision		Revision as of 23:16, 14 February 2013
Line 90:		Line 90:
	===Profile Driven===		===Profile Driven===
	Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.		Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.

			===Speculation===
			Under this paradigm a compiler will aggressively identify opportunities for parallelism, and some of these opportunities will be unsafe.
			<ref>http://iacoma.cs.uiuc.edu/iacoma-papers/encyclopedia_tls.pdf</ref>

	==Limitations==		==Limitations==

Aeveret: /* Limitations */

2013-02-14T22:50:07Z

Limitations

← Older revision		Revision as of 22:50, 14 February 2013
Line 94:		Line 94:
	Luke Scharf, of the National Center for Supercomputing Applications, describes well the limitations of automatic parallelization when he wrote of the problem of parallelization in general, "we usually solve this problem by putting a smart scientist in a room with a smart parallel programmer and providing them a whiteboard and a pot of coffee. Until a compiler can do what these people do, the utility of automatic parallelization is very limited." Compilers are thus limited by the amount and the type of information that is made available to them. Yan Solihin provides a great example of this when describing the ocean current problem in which each loop iteration in the code dependent upon previous iterations. He explains that the code introduces these dependencies, but they are not relevant to solving the problem. At this stage he describes that each point simply takes into account their neighbor and creates a result. Therefore, he discerns that the grid points can be separated by red-black partitioning where each neighbor is a different color, and each partition is assigned to a processor. This is something the compiler will probably never accomplish. Another limitation of compilers is that they must produce results that match results that can be computed serially. When there is a risk that the parallel code will not return the same values as a serial implementation, the compiler must err on the side of caution and fail to parallelize that aspect. [http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization]		Luke Scharf, of the National Center for Supercomputing Applications, describes well the limitations of automatic parallelization when he wrote of the problem of parallelization in general, "we usually solve this problem by putting a smart scientist in a room with a smart parallel programmer and providing them a whiteboard and a pot of coffee. Until a compiler can do what these people do, the utility of automatic parallelization is very limited." Compilers are thus limited by the amount and the type of information that is made available to them. Yan Solihin provides a great example of this when describing the ocean current problem in which each loop iteration in the code dependent upon previous iterations. He explains that the code introduces these dependencies, but they are not relevant to solving the problem. At this stage he describes that each point simply takes into account their neighbor and creates a result. Therefore, he discerns that the grid points can be separated by red-black partitioning where each neighbor is a different color, and each partition is assigned to a processor. This is something the compiler will probably never accomplish. Another limitation of compilers is that they must produce results that match results that can be computed serially. When there is a risk that the parallel code will not return the same values as a serial implementation, the compiler must err on the side of caution and fail to parallelize that aspect. [http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization]
	===Limitations===		===Limitations===
	+Tradeoff of program size and execution speed		* Tradeoff of program size and execution speed

	==Examples==		==Examples==

Aeveret: /* Limitations */

2013-02-14T22:49:21Z

Limitations

← Older revision		Revision as of 22:49, 14 February 2013
Line 93:		Line 93:
	==Limitations==		==Limitations==
	Luke Scharf, of the National Center for Supercomputing Applications, describes well the limitations of automatic parallelization when he wrote of the problem of parallelization in general, "we usually solve this problem by putting a smart scientist in a room with a smart parallel programmer and providing them a whiteboard and a pot of coffee. Until a compiler can do what these people do, the utility of automatic parallelization is very limited." Compilers are thus limited by the amount and the type of information that is made available to them. Yan Solihin provides a great example of this when describing the ocean current problem in which each loop iteration in the code dependent upon previous iterations. He explains that the code introduces these dependencies, but they are not relevant to solving the problem. At this stage he describes that each point simply takes into account their neighbor and creates a result. Therefore, he discerns that the grid points can be separated by red-black partitioning where each neighbor is a different color, and each partition is assigned to a processor. This is something the compiler will probably never accomplish. Another limitation of compilers is that they must produce results that match results that can be computed serially. When there is a risk that the parallel code will not return the same values as a serial implementation, the compiler must err on the side of caution and fail to parallelize that aspect. [http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization]		Luke Scharf, of the National Center for Supercomputing Applications, describes well the limitations of automatic parallelization when he wrote of the problem of parallelization in general, "we usually solve this problem by putting a smart scientist in a room with a smart parallel programmer and providing them a whiteboard and a pot of coffee. Until a compiler can do what these people do, the utility of automatic parallelization is very limited." Compilers are thus limited by the amount and the type of information that is made available to them. Yan Solihin provides a great example of this when describing the ocean current problem in which each loop iteration in the code dependent upon previous iterations. He explains that the code introduces these dependencies, but they are not relevant to solving the problem. At this stage he describes that each point simply takes into account their neighbor and creates a result. Therefore, he discerns that the grid points can be separated by red-black partitioning where each neighbor is a different color, and each partition is assigned to a processor. This is something the compiler will probably never accomplish. Another limitation of compilers is that they must produce results that match results that can be computed serially. When there is a risk that the parallel code will not return the same values as a serial implementation, the compiler must err on the side of caution and fail to parallelize that aspect. [http://www.ncsa.illinois.edu/extremeideas/site/on_the_limits_of_automatic_parallelization]
	===~~Fine-grained Parallelism~~===		===Limitations===
	~~blah blah blah~~		+Tradeoff of program size and execution speed
	~~===Course-grained Parallelism===~~
	~~blah blah blah~~
	==Examples==		==Examples==
	===Power FORTRAN Analyzer===		===Power FORTRAN Analyzer===

Aeveret: /* Algorithm/Task-level/Functional Parallelism */

2013-02-14T22:42:06Z

Algorithm/Task-level/Functional Parallelism

← Older revision		Revision as of 22:42, 14 February 2013
Line 60:		Line 60:
	</code>		</code>
	</pre>		</pre>
	~~Parallelism~~ was identified by determining that the order of the operations was not important. Therefore, the operations could be conducted in parallel.		In the above case, parallelism was identified by determining that the order of the operations was not important. Therefore, the operations could be conducted in parallel. A figure of two processing elements working on different routines is depicted to the right.

	==Parallelization Techniques in Compilers<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref><ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>==		==Parallelization Techniques in Compilers<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref><ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>==

Jrcrawfo: /* Parallelization Techniques in Compilershttp://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdfhttp://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf */

2013-02-14T22:24:50Z

Parallelization Techniques in Compilershttp://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdfhttp://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf

← Older revision		Revision as of 22:24, 14 February 2013
Line 65:		Line 65:
	Automated parallelization can take place at compile time where the compiler will perform different kinds of analysis in order to determine what can be parallelized. There are many ways to perform this analysis, including scalar analysis, array analysis, and commutativity analysis. By using different types of analysis, the compiler can find different ways that it is possible to parallelize a program. With the growing need for parallel and distributed computing environments, it is often up to the compiler to determine ways in which a users' program can be parallelized. Giving the traditional software developer who hasn't been trained in parallelization technniques a way to automatically parallelize their programs by using a compiler to parallelize their program is advantageous. However, this has proved to be a very difficult task, given that the compiler knows nothing about the program besides the code that it is given. By using different types of analysis like scalar, array, and commutativity analyses, compilers can make an attempt at making a parallelizable program.		Automated parallelization can take place at compile time where the compiler will perform different kinds of analysis in order to determine what can be parallelized. There are many ways to perform this analysis, including scalar analysis, array analysis, and commutativity analysis. By using different types of analysis, the compiler can find different ways that it is possible to parallelize a program. With the growing need for parallel and distributed computing environments, it is often up to the compiler to determine ways in which a users' program can be parallelized. Giving the traditional software developer who hasn't been trained in parallelization technniques a way to automatically parallelize their programs by using a compiler to parallelize their program is advantageous. However, this has proved to be a very difficult task, given that the compiler knows nothing about the program besides the code that it is given. By using different types of analysis like scalar, array, and commutativity analyses, compilers can make an attempt at making a parallelizable program.

	===Scalar and Array Analysis~~<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>~~===		===Scalar and Array Analysis===
	[[Image:Array_analysis.gif\|thumb\|right\|300px\|Visual of array data-flow analysis <ref>https://computing.llnl.gov/tutorials/parallel_comp/images/array_proc2.gif</ref>]]		[[Image:Array_analysis.gif\|thumb\|right\|300px\|Visual of array data-flow analysis <ref>https://computing.llnl.gov/tutorials/parallel_comp/images/array_proc2.gif</ref>]]

Line 74:		Line 74:
	Although these types of analysis are powerful, there are limitations. The most significant limitation is that it cannot support some subsets of the C programming language, which includes pointers. These types of compiler analyses cannot handle pointers since at compile-time it is impossible to determine if a dynamic pointer will contain data objects that are parallelizable. So, this kind of analysis is limited to loop parallelization where a data access pattern is known.		Although these types of analysis are powerful, there are limitations. The most significant limitation is that it cannot support some subsets of the C programming language, which includes pointers. These types of compiler analyses cannot handle pointers since at compile-time it is impossible to determine if a dynamic pointer will contain data objects that are parallelizable. So, this kind of analysis is limited to loop parallelization where a data access pattern is known.

	===Commutativity Analysis~~<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>~~===		===Commutativity Analysis===
	Unlike scalar and array analysis, commutativity analysis can be used with language more more advanced feature sets, including pointers. "This is a technique that is, 'designed to automatically recognize and exploit commuting operations'". Using the [http://en.wikipedia.org/wiki/Commutative_property commutativity property] in mathematics, the compiler can find ways to automatically parallelize a program. This property is true if two operands, or operations, can be calculated in any order and still produce the same result. In order to test commutativity of an operation, the following conditions are followed:		Unlike scalar and array analysis, commutativity analysis can be used with language more more advanced feature sets, including pointers. "This is a technique that is, 'designed to automatically recognize and exploit commuting operations'". Using the [http://en.wikipedia.org/wiki/Commutative_property commutativity property] in mathematics, the compiler can find ways to automatically parallelize a program. This property is true if two operands, or operations, can be calculated in any order and still produce the same result. In order to test commutativity of an operation, the following conditions are followed:

Line 83:		Line 83:
	In summary, if two operations in a program execute the same method with the same receiver object and the same parameters, then the operation are considered identical by the commutativity property. <ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>		In summary, if two operations in a program execute the same method with the same receiver object and the same parameters, then the operation are considered identical by the commutativity property. <ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>

	===Polytope Method~~<ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>~~===		===Polytope Method===
	[[Image:Polytope.png\|thumb\|right\|200px\|Lattice <ref>http://en.wikipedia.org/wiki/Polyhedral_model</ref>]]		[[Image:Polytope.png\|thumb\|right\|200px\|Lattice <ref>http://en.wikipedia.org/wiki/Polyhedral_model</ref>]]

	The [http://en.wikipedia.org/wiki/Polyhedral_model Polytope Model], or polyhedral transformation, is another method based on static analysis that attempt to parallelize code by transforming the source code. It represent the source code as a polyhedron and performs affine transformations to transform the code into more efficient code, but still equivalent to the source code. However, like other static analysis methods, dynamic pointers cause problems when performing these kinds of analysis.		The [http://en.wikipedia.org/wiki/Polyhedral_model Polytope Model], or polyhedral transformation, is another method based on static analysis that attempt to parallelize code by transforming the source code. It represent the source code as a polyhedron and performs affine transformations to transform the code into more efficient code, but still equivalent to the source code. However, like other static analysis methods, dynamic pointers cause problems when performing these kinds of analysis.

	===Profile Driven~~<ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>~~===		===Profile Driven===
	Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.		Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.

Jrcrawfo: /* Parallelization Techniques in Compilershttp://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdfhttp://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf */

2013-02-14T22:24:13Z

Parallelization Techniques in Compilershttp://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdfhttp://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf

← Older revision		Revision as of 22:24, 14 February 2013
Line 65:		Line 65:
	Automated parallelization can take place at compile time where the compiler will perform different kinds of analysis in order to determine what can be parallelized. There are many ways to perform this analysis, including scalar analysis, array analysis, and commutativity analysis. By using different types of analysis, the compiler can find different ways that it is possible to parallelize a program. With the growing need for parallel and distributed computing environments, it is often up to the compiler to determine ways in which a users' program can be parallelized. Giving the traditional software developer who hasn't been trained in parallelization technniques a way to automatically parallelize their programs by using a compiler to parallelize their program is advantageous. However, this has proved to be a very difficult task, given that the compiler knows nothing about the program besides the code that it is given. By using different types of analysis like scalar, array, and commutativity analyses, compilers can make an attempt at making a parallelizable program.		Automated parallelization can take place at compile time where the compiler will perform different kinds of analysis in order to determine what can be parallelized. There are many ways to perform this analysis, including scalar analysis, array analysis, and commutativity analysis. By using different types of analysis, the compiler can find different ways that it is possible to parallelize a program. With the growing need for parallel and distributed computing environments, it is often up to the compiler to determine ways in which a users' program can be parallelized. Giving the traditional software developer who hasn't been trained in parallelization technniques a way to automatically parallelize their programs by using a compiler to parallelize their program is advantageous. However, this has proved to be a very difficult task, given that the compiler knows nothing about the program besides the code that it is given. By using different types of analysis like scalar, array, and commutativity analyses, compilers can make an attempt at making a parallelizable program.

	===Scalar and Array Analysis===		===Scalar and Array Analysis<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>===
	[[Image:Array_analysis.gif\|thumb\|right\|300px\|Visual of array data-flow analysis <ref>https://computing.llnl.gov/tutorials/parallel_comp/images/array_proc2.gif</ref>]]		[[Image:Array_analysis.gif\|thumb\|right\|300px\|Visual of array data-flow analysis <ref>https://computing.llnl.gov/tutorials/parallel_comp/images/array_proc2.gif</ref>]]

Line 74:		Line 74:
	Although these types of analysis are powerful, there are limitations. The most significant limitation is that it cannot support some subsets of the C programming language, which includes pointers. These types of compiler analyses cannot handle pointers since at compile-time it is impossible to determine if a dynamic pointer will contain data objects that are parallelizable. So, this kind of analysis is limited to loop parallelization where a data access pattern is known.		Although these types of analysis are powerful, there are limitations. The most significant limitation is that it cannot support some subsets of the C programming language, which includes pointers. These types of compiler analyses cannot handle pointers since at compile-time it is impossible to determine if a dynamic pointer will contain data objects that are parallelizable. So, this kind of analysis is limited to loop parallelization where a data access pattern is known.

	===Commutativity Analysis===		===Commutativity Analysis<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>===
	Unlike scalar and array analysis, commutativity analysis can be used with language more more advanced feature sets, including pointers. "This is a technique that is, 'designed to automatically recognize and exploit commuting operations'". Using the [http://en.wikipedia.org/wiki/Commutative_property commutativity property] in mathematics, the compiler can find ways to automatically parallelize a program. This property is true if two operands, or operations, can be calculated in any order and still produce the same result. In order to test commutativity of an operation, the following conditions are followed:		Unlike scalar and array analysis, commutativity analysis can be used with language more more advanced feature sets, including pointers. "This is a technique that is, 'designed to automatically recognize and exploit commuting operations'". Using the [http://en.wikipedia.org/wiki/Commutative_property commutativity property] in mathematics, the compiler can find ways to automatically parallelize a program. This property is true if two operands, or operations, can be calculated in any order and still produce the same result. In order to test commutativity of an operation, the following conditions are followed:

Line 83:		Line 83:
	In summary, if two operations in a program execute the same method with the same receiver object and the same parameters, then the operation are considered identical by the commutativity property. <ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>		In summary, if two operations in a program execute the same method with the same receiver object and the same parameters, then the operation are considered identical by the commutativity property. <ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>

	===Polytope Method===		===Polytope Method<ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>===
	[[Image:Polytope.png\|thumb\|right\|200px\|Lattice <ref>http://en.wikipedia.org/wiki/Polyhedral_model</ref>]]		[[Image:Polytope.png\|thumb\|right\|200px\|Lattice <ref>http://en.wikipedia.org/wiki/Polyhedral_model</ref>]]

	The [http://en.wikipedia.org/wiki/Polyhedral_model Polytope Model], or polyhedral transformation, is another method based on static analysis that attempt to parallelize code by transforming the source code. It represent the source code as a polyhedron and performs affine transformations to transform the code into more efficient code, but still equivalent to the source code. However, like other static analysis methods, dynamic pointers cause problems when performing these kinds of analysis.		The [http://en.wikipedia.org/wiki/Polyhedral_model Polytope Model], or polyhedral transformation, is another method based on static analysis that attempt to parallelize code by transforming the source code. It represent the source code as a polyhedron and performs affine transformations to transform the code into more efficient code, but still equivalent to the source code. However, like other static analysis methods, dynamic pointers cause problems when performing these kinds of analysis.

	===Profile Driven===		===Profile Driven<ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>===
	Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.		Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.

Jrcrawfo: /* Parallelization Techniques in Compilershttp://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf */

2013-02-14T22:23:23Z

Parallelization Techniques in Compilershttp://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf

← Older revision		Revision as of 22:23, 14 February 2013
Line 62:		Line 62:
	Parallelism was identified by determining that the order of the operations was not important. Therefore, the operations could be conducted in parallel.		Parallelism was identified by determining that the order of the operations was not important. Therefore, the operations could be conducted in parallel.

	==Parallelization Techniques in Compilers<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref>==		==Parallelization Techniques in Compilers<ref>http://www.csc.villanova.edu/~tway/publications/DiPasquale_Masplas05_Paper5.pdf</ref><ref>http://www.eecs.berkeley.edu/~chiayuan/cs262a/cs262a_parallel.pdf</ref>==
	Automated parallelization can take place at compile time where the compiler will perform different kinds of analysis in order to determine what can be parallelized. There are many ways to perform this analysis, including scalar analysis, array analysis, and commutativity analysis. By using different types of analysis, the compiler can find different ways that it is possible to parallelize a program. With the growing need for parallel and distributed computing environments, it is often up to the compiler to determine ways in which a users' program can be parallelized. Giving the traditional software developer who hasn't been trained in parallelization technniques a way to automatically parallelize their programs by using a compiler to parallelize their program is advantageous. However, this has proved to be a very difficult task, given that the compiler knows nothing about the program besides the code that it is given. By using different types of analysis like scalar, array, and commutativity analyses, compilers can make an attempt at making a parallelizable program.		Automated parallelization can take place at compile time where the compiler will perform different kinds of analysis in order to determine what can be parallelized. There are many ways to perform this analysis, including scalar analysis, array analysis, and commutativity analysis. By using different types of analysis, the compiler can find different ways that it is possible to parallelize a program. With the growing need for parallel and distributed computing environments, it is often up to the compiler to determine ways in which a users' program can be parallelized. Giving the traditional software developer who hasn't been trained in parallelization technniques a way to automatically parallelize their programs by using a compiler to parallelize their program is advantageous. However, this has proved to be a very difficult task, given that the compiler knows nothing about the program besides the code that it is given. By using different types of analysis like scalar, array, and commutativity analyses, compilers can make an attempt at making a parallelizable program.

Jrcrawfo: /* Profile Driven */

2013-02-14T22:22:26Z

Profile Driven

← Older revision		Revision as of 22:22, 14 February 2013
Line 89:		Line 89:

	===Profile Driven===		===Profile Driven===
	Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized~~. Continue..~~.		Profile driven parallelization is one of the more popular ways to automatically "hot spots" in the programs code that could be parallelized. The program is first ran serially and then a profile is created that includes memory accesses, places where a lot of time is spent processing code, etc. The compiler can then go back and look at the results and pick out the "hot spots" where it thinks it can be parallelized. This is a fairly simple static implementation of parallelizing a program, however, profile driven parallelization often is found to generate many false positives in what it thinks can be parallelized.

	==Limitations==		==Limitations==