CSC/ECE 506 Spring 2014/4a ad - Revision history

Admin: /* Array analysis */

2014-04-26T19:50:50Z

Array analysis

← Older revision		Revision as of 19:50, 26 April 2014
Line 98:		Line 98:

	===Array analysis ===		===Array analysis ===
	<p>Array analysis is used in conjunction with the scalar analysis. It uses the method of privatization which works on array data to find privatizable arrays. Access to the array is analyzed to determine an equation of access into the array, then, if possible, that array can be privatized. Specifically this is called array ~~data flow~~ analysis.</p>		<p>Array analysis is used in conjunction with the scalar analysis. It uses the method of privatization which works on array data to find privatizable arrays. Access to the array is analyzed to determine an equation of access into the array, then, if possible, that array can be privatized. Specifically this is called array dataflow analysis.</p>
	<p>Consider the loop below~~, it~~ has a data dependence and thus cannot be privatized.</p>		<p>Consider the loop below. It has a data dependence and thus cannot be privatized.</p>
	<pre>		<pre>
	for i = 0; i < x.length; ++i) {		for i = 0; i < x.length; ++i) {

Admin: /* Scalar Analysis */

2014-04-26T19:49:25Z

Scalar Analysis

← Older revision		Revision as of 19:49, 26 April 2014
Line 95:		Line 95:
	}		}
	</pre>		</pre>
	<p>Here the array is accessed in standard ~~liner~~ fashion, but by a function of two variables. So this cannot be parallelized by scalar analysis.</p>		<p>Here the array is accessed in standard linear fashion, but by a function of two variables. So this cannot be parallelized by scalar analysis.</p>

	===Array analysis ===		===Array analysis ===

Admin: /* Scalar Analysis */

2014-04-26T19:47:32Z

Scalar Analysis

← Older revision		Revision as of 19:47, 26 April 2014
Line 82:		Line 82:

	===Scalar Analysis ===		===Scalar Analysis ===
	<p>'Scalar Analysis', 'Array Analysis' and 'Commutativity Analysis' techniques primarily focus on the back end of the compiler to generate the primary output that can be parallelized. These techniques deal with parallelization with specific system in mind.Scalar analysis and array analysis are two techniques often used in conjunction. Because of the nature of the analyses, they are used in imperative languages like FORTRAN and C.</p>		<p>'Scalar Analysis', 'Array Analysis' and 'Commutativity Analysis' techniques primarily focus on the back end of the compiler to generate the primary output that can be parallelized. These techniques deal with parallelization with specific system in mind. Scalar analysis and array analysis are two techniques often used in conjunction. Because of the nature of the analyses, they are used in imperative languages like FORTRAN and C.</p>

	<p>In the scalar analysis a program is broken down to analyze use of scalar variable and the dependencies that they have. Scalar analysis identify the loop carried dependencies. When the memory location is written in one iteration of a loop and it is accessed (read or write) in a different iteration, there is a loop carried dependence. In addition, scalar analysis determines if parallelization may be enabled by privatization or by reduction transformations. There is a slight variation in regular scalar analysis, that is known as scalar symbolic analysis and it is used to check the dependencies on array elements.</P>		<p>In the scalar analysis a program is broken down to analyze use of scalar variable and the dependencies that they have. Scalar analysis identify the loop carried dependencies. When the memory location is written in one iteration of a loop and it is accessed (read or write) in a different iteration, there is a loop carried dependence. In addition, scalar analysis determines if parallelization may be enabled by privatization or by reduction transformations. There is a slight variation in regular scalar analysis, that is known as scalar symbolic analysis and it is used to check the dependencies on array elements.</P>

	<p>''Limitations of Scalar Analysis:'' This analysis is applicable only to specific forms of program constructs. For example, if an array is accessed in a linear form via an equation that acts as if the array were multidimensional , then this form of analysis cannot parallelize the code. </P>		<p>''Limitations of Scalar Analysis'': This analysis is applicable only to specific forms of program constructs. For example, if an array is accessed in a linear form via an equation that acts as if the array were multidimensional , then this form of analysis cannot parallelize the code. </P>

	<p>Consider the loop below:</p>		<p>Consider the loop below:</p>

Admin: /* Pipelined multithreading */

2014-04-26T19:46:32Z

Pipelined multithreading

← Older revision		Revision as of 19:46, 26 April 2014
Line 55:		Line 55:
	Example:		Example:
	<pre>		<pre>
	for(i=1;i<=n;i++){		for (i=1;i<=n;i++){
	x[i] = x[i-1] + y[i];		x[i] = x[i-1] + y[i];
	z[i] = z[i] + x[i];		z[i] = z[i] + x[i];
Line 62:		Line 62:
	</pre>		</pre>

	<p>The compiler can split the above loop into two loops(each can be executed on a different processor) and embed special instructions to forward output of one processor to another.</p>		<p>The compiler can split the above loop into two loops (each can be executed on a different processor) and embed special instructions to forward output of one processor to another.</p>

	<pre>		<pre>
	Loop 1:		Loop 1:
	for(i=1;i<=n;i++){		for (i=1;i<=n;i++){
	x[i] = x[i-1] + y[i];		x[i] = x[i-1] + y[i];
	send(x[i]);		send(x[i]);
Line 72:		Line 72:

	Loop 2:		Loop 2:
	for(i=1;i<=n;i++){		for (i=1;i<=n;i++){
	receive(x[i]);		receive(x[i]);
	z[i] = z[i] + x[i];		z[i] = z[i] + x[i];
Line 80:		Line 80:

	<p>So loop 1 can be run on one processor and the result sent to the second processor which executes loop 2.</p>		<p>So loop 1 can be run on one processor and the result sent to the second processor which executes loop 2.</p>



	===Scalar Analysis ===		===Scalar Analysis ===

Admin: /* Cyclic multithreading */

2014-04-26T19:45:47Z

Cyclic multithreading

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

	=== Cyclic multithreading ===		=== Cyclic multithreading ===
	<p>A parallelizing compiler using cyclic multithreading tries to split a loop in a such a way that each iteration of a loop can be executed concurrently on a different processor.Before actually parallelizing the code, the compiler does two passes analyzing the following in each pass the code respectively.</p>		<p>A parallelizing compiler using cyclic multithreading tries to split a loop in a such a way that each iteration of a loop can be executed concurrently on a different processor. Before actually parallelizing the code, the compiler does two passes analyzing the following in each pass the code respectively.</p>

	*'''How safe is it to parallelize the loop?'''		*'''How safe is it to parallelize the loop?'''
Line 39:		Line 39:
	</pre>		</pre>

	<p>The above for loop cannot be auto-parallelized because z[i] depends on the previous iteration value z[i-1].But it doesn’t mean that it cannot be parallelized. The above loop is equal to the following</p>		<p>The above for loop cannot be auto-parallelized because z[i] depends on the previous iteration value z[i-1]. But it doesn’t mean that it cannot be parallelized. The above loop is equal to the following</p>

	<pre>		<pre>

Admin: /* Introduction */

2014-04-26T19:41:25Z

Introduction

← Older revision		Revision as of 19:41, 26 April 2014
Line 4:		Line 4:

	== Introduction ==		== Introduction ==
	<p>With increasing transistor densities, multi-core computing systems are being touted as the most popular means of delivering performance ~~unless~~ the application is parallelized efficiently, one cannot realize the potential of multi core environment.[[Image:fig03.png\|1000px\|thumb\|right\|Multi core system]]It is a challenge to efficiently parallelize sequential programs without any errors. It is widely accepted that manual parallelization of code, by expert programmers, leads to the most streamlined parallel implementation. But it is also a costly and time consuming process. If one can parallelize the compiler technology itself while ensuring the formal correctness of the resulting parallel code, time-to-market and cost can be greatly reduced.		<p>With increasing transistor densities, multi-core computing systems are being touted as the most popular means of delivering performance. Unless the application is parallelized efficiently, one cannot realize the potential of multi core environment.[[Image:fig03.png\|1000px\|thumb\|right\|Multi core system]]It is a challenge to efficiently parallelize sequential programs without any errors. It is widely accepted that manual parallelization of code, by expert programmers, leads to the most streamlined parallel implementation. But it is also a costly and time consuming process. If one can parallelize the compiler technology itself while ensuring the formal correctness of the resulting parallel code, time-to-market and cost can be greatly reduced.
	</p>		</p>

Dskarkha: /* MIPSpro APO Compiler */

2014-03-03T19:32:01Z

MIPSpro APO Compiler

← Older revision		Revision as of 19:32, 3 March 2014
Line 174:		Line 174:
	=== MIPSpro APO Compiler ===		=== MIPSpro APO Compiler ===

	<p> The MIPSpro APO integrates automatic parallelization using interprocedural analysis (IPA) with other compiler optimizations such as ~~and~~ loop nest optimization (LNO).		<p> The MIPSpro APO integrates automatic parallelization using interprocedural analysis (IPA) with other compiler optimizations such as loop nest optimization (LNO).
	It supports C++ and has improved runtime and compile-time performance.</p>		It supports C++ and has improved runtime and compile-time performance.</p>

Dskarkha: /* MIPSpro APO Compiler */

2014-03-03T18:55:18Z

MIPSpro APO Compiler

← Older revision		Revision as of 18:55, 3 March 2014
Line 174:		Line 174:
	=== MIPSpro APO Compiler ===		=== MIPSpro APO Compiler ===

	<p> The ~~auto-parallelizing compilers integrate~~ automatic parallelization~~, provided by the MIPSpro APO,~~ with other compiler optimizations, such as ~~interprocedural analysis (IPA)~~ and loop nest optimization (LNO). ~~</p>~~		<p> The MIPSpro APO integrates automatic parallelization using interprocedural analysis (IPA) with other compiler optimizations such as and loop nest optimization (LNO).
	~~<p>The MIPSpro APO integrates automatic parallelization and optimization technique. it~~ supports C++ and has improved runtime and compile-time performance.</p>		It supports C++ and has improved runtime and compile-time performance.</p>

	=== SUIF Compiler ===		=== SUIF Compiler ===

Dskarkha: /* MIPSpro APO Compiler */

2014-03-03T18:48:01Z

MIPSpro APO Compiler

← Older revision		Revision as of 18:48, 3 March 2014
Line 174:		Line 174:
	=== MIPSpro APO Compiler ===		=== MIPSpro APO Compiler ===

	<p> The auto-parallelizing compilers integrate automatic parallelization, provided by the MIPSpro APO, with other compiler optimizations, such as interprocedural analysis (IPA) and loop nest optimization (LNO). ~~[[Image:MPRSpro_autoparallelization.jpg\|200px\|thumb\|left\|MIPSpro APO Compiler ]]~~ </p>		<p> The auto-parallelizing compilers integrate automatic parallelization, provided by the MIPSpro APO, with other compiler optimizations, such as interprocedural analysis (IPA) and loop nest optimization (LNO). </p>
	<p>The MIPSpro APO integrates automatic parallelization and optimization technique. it supports C++ and has improved runtime and compile-time performance.</p>		<p>The MIPSpro APO integrates automatic parallelization and optimization technique. it supports C++ and has improved runtime and compile-time performance.</p>


	=== SUIF Compiler ===		=== SUIF Compiler ===

Dskarkha: /* Examples of Auto Parallel Compilers */

2014-03-03T18:00:53Z

Examples of Auto Parallel Compilers

← Older revision		Revision as of 18:00, 3 March 2014
Line 177:		Line 177:
	<p>The MIPSpro APO integrates automatic parallelization and optimization technique. it supports C++ and has improved runtime and compile-time performance.</p>		<p>The MIPSpro APO integrates automatic parallelization and optimization technique. it supports C++ and has improved runtime and compile-time performance.</p>

	~~<p>~~
	=== SUIF Compiler ===		=== SUIF Compiler ===
	<p>SUIF (Stanford University Intermediate Format) is a free infrastructure designed to support collaborative research in optimizing and parallelizing compilers.[11]</p>		<p>SUIF (Stanford University Intermediate Format) is a free infrastructure designed to support collaborative research in optimizing and parallelizing compilers.[11]</p>