Irregular algorithm - Revision history

BD2412: remove errata from redirect page using AWB

2014-09-09T19:03:41Z

remove errata from redirect page using AWB

← Previous revision		Revision as of 19:03, 9 September 2014
Line 1:		Line 1:
	#REDIRECT [[ Automatic parallelization#Difficulties]]		#REDIRECT [[ Automatic parallelization#Difficulties]]

	Irregular Algorithm

	Category: Computer Science

	To be linked from: [[Irregular]].

	An irregular algorithm is characterized by unpredictable data-access and control-access patterns. Unstructured accesses such as those using arbitrary indirection and pointers constitute irregularity in the underlying program.

	The following code exhibits data irregularity.

	integer a[10], b[10], c[10];
	readinput(a);
	for i = 1 to 10 do
	b[i] = c[a[i]];
	end for

	In the above code, the index of array c is unpredictable at compile time and static analysis techniques fail to optimize or parallelize the code because the data accesses are input dependent.

	Similarly, a control-flow irregularity is exhibited by a code that execute parts of a program based on the input values. The following code exhibits control-flow irregularity.

	integer a[10];
	readinput(a);
	if (a[5] < 20) then
	do_one();
	else
	do_two();
	end if

	The above code cannot be optimized unless the values from the array a are known.

	Traditionally, irregular algorithms have been known to be difficult to optimize and parallelize.

	References:

	1. Gudula Rünger, [http://link.springer.com/chapter/10.1007%2F3-540-33541-2_1?LI=true Parallel Programming Models for Irregular Algorithms], in Parallel Algorithms and Cluster Computing vol 52, 2006, pages 3--23, Springer Berlin Heidelberg

	2. Mario Méndez-Lojo et al., [http://dl.acm.org/citation.cfm?id=1693457 Structure-driven optimizations for amorphous data-parallel programs], in ACM SIGPLAN Notices - PPoPP '10
	Volume 45 Issue 5, May 2010, Pages 3-14, ACM New York, NY, USA

	<!-- This will add a notice to the bottom of the page and won't blank it! The new template which says that your draft is waiting for a review will appear at the bottom; simply ignore the old (grey) drafted templates and the old (red) decline templates. A bot will update your article submission. Until then, please don't change anything in this text box and press "Save page". -->

Anne Delong: change to a redirect as per discussion at Wikiproject Computer science

2014-01-01T19:20:42Z

change to a redirect as per discussion at Wikiproject Computer science

← Previous revision		Revision as of 19:20, 1 January 2014
Line 1:		Line 1:
			#REDIRECT [[ Automatic parallelization#Difficulties]]
	{{AFC submission\|d\|reason\|3=Not suitable for wikipedia.\|declinets=20121226063516\|decliner=Pratyya Ghosh\|ts=20121219044629\|u=Rupesh0508\|ns=2}}

	Irregular Algorithm		Irregular Algorithm

Anne Delong: Anne Delong moved page Wikipedia talk:Articles for creation/Irregular algorithm to Irregular algorithm: moving to article space

2014-01-01T19:16:08Z

Anne Delong moved page Wikipedia talk:Articles for creation/Irregular algorithm to Irregular algorithm: moving to article space

← Previous revision	Revision as of 19:16, 1 January 2014
(No difference)

JohnCD: RM G13 tag after restoration

2014-01-01T10:48:24Z

RM G13 tag after restoration

← Previous revision		Revision as of 10:48, 1 January 2014
Line 1:		Line 1:
	{{db-g13\|ts=2012-12-26T06:35:17Z}}
	{{AFC submission\|d\|reason\|3=Not suitable for wikipedia.\|declinets=20121226063516\|decliner=Pratyya Ghosh\|ts=20121219044629\|u=Rupesh0508\|ns=2}}		{{AFC submission\|d\|reason\|3=Not suitable for wikipedia.\|declinets=20121226063516\|decliner=Pratyya Ghosh\|ts=20121219044629\|u=Rupesh0508\|ns=2}}
	Irregular Algorithm		Irregular Algorithm

HasteurBot: User:HasteurBot:Nominating for CSD:G13

2013-12-30T12:03:20Z

User:HasteurBot:Nominating for CSD:G13

← Previous revision		Revision as of 12:03, 30 December 2013
Line 1:		Line 1:
			{{db-g13\|ts=2012-12-26T06:35:17Z}}
	{{AFC submission\|d\|reason\|3=Not suitable for wikipedia.\|declinets=20121226063516\|decliner=Pratyya Ghosh\|ts=20121219044629\|u=Rupesh0508\|ns=2}}		{{AFC submission\|d\|reason\|3=Not suitable for wikipedia.\|declinets=20121226063516\|decliner=Pratyya Ghosh\|ts=20121219044629\|u=Rupesh0508\|ns=2}}
	Irregular Algorithm		Irregular Algorithm

Pratyya Ghosh: Declining submission: see comment therein (AFCH)

2012-12-26T06:35:17Z

Declining submission: see comment therein (AFCH)

← Previous revision		Revision as of 06:35, 26 December 2012
Line 1:		Line 1:
			{{AFC submission\|d\|reason\|3=Not suitable for wikipedia.\|declinets=20121226063516\|decliner=Pratyya Ghosh\|ts=20121219044629\|u=Rupesh0508\|ns=2}}
	== Request review at [[WP:AFC]] ==

	Irregular Algorithm		Irregular Algorithm

	Category: Computer Science		Category: Computer Science

	To be linked from: [[~~http://en.wikipedia.org/wiki/~~Irregular]].		To be linked from: [[Irregular]].

	An irregular algorithm is characterized by unpredictable data-access and control-access patterns. Unstructured accesses such as those using arbitrary indirection and pointers constitute irregularity in the underlying program.		An irregular algorithm is characterized by unpredictable data-access and control-access patterns. Unstructured accesses such as those using arbitrary indirection and pointers constitute irregularity in the underlying program.
Line 41:		Line 40:

	<!-- This will add a notice to the bottom of the page and won't blank it! The new template which says that your draft is waiting for a review will appear at the bottom; simply ignore the old (grey) drafted templates and the old (red) decline templates. A bot will update your article submission. Until then, please don't change anything in this text box and press "Save page". -->		<!-- This will add a notice to the bottom of the page and won't blank it! The new template which says that your draft is waiting for a review will appear at the bottom; simply ignore the old (grey) drafted templates and the old (red) decline templates. A bot will update your article submission. Until then, please don't change anything in this text box and press "Save page". -->
	{{AFC submission\|\|\|ts=20121219044629\|u=Rupesh0508\|ns=2}}

Rupesh0508 at 22:09, 20 December 2012

2012-12-20T22:09:48Z

← Previous revision		Revision as of 22:09, 20 December 2012
Line 5:		Line 5:
	Category: Computer Science		Category: Computer Science

	To be linked from: [[http://en.wikipedia.org/wiki/~~Irregular\|Wikipedia~~ Irregular]].		To be linked from: [[http://en.wikipedia.org/wiki/Irregular]].

	An irregular algorithm is characterized by unpredictable data-access and control-access patterns. Unstructured accesses such as those using arbitrary indirection and pointers constitute irregularity in the underlying program.		An irregular algorithm is characterized by unpredictable data-access and control-access patterns. Unstructured accesses such as those using arbitrary indirection and pointers constitute irregularity in the underlying program.

MatthewVanitas: MatthewVanitas moved page User:Rupesh0508/sandbox to Wikipedia talk:Articles for creation/Irregular algorithm: Preferred location for AfC submissions

2012-12-19T20:48:15Z

MatthewVanitas moved page User:Rupesh0508/sandbox to Wikipedia talk:Articles for creation/Irregular algorithm: Preferred location for AfC submissions

← Previous revision	Revision as of 20:48, 19 December 2012
(No difference)

Rupesh0508: /* Request review at WP:AFC */ new section

2012-12-19T04:46:29Z

Request review at WP:AFC: new section

New page

== Request review at [[WP:AFC]] ==

Irregular Algorithm

Category: Computer Science

To be linked from: [[http://en.wikipedia.org/wiki/Irregular|Wikipedia Irregular]].

An irregular algorithm is characterized by unpredictable data-access and control-access patterns. Unstructured accesses such as those using arbitrary indirection and pointers constitute irregularity in the underlying program.

The following code exhibits data irregularity.

integer a[10], b[10], c[10];
readinput(a);
for i = 1 to 10 do
b[i] = c[a[i]];
end for

In the above code, the index of array c is unpredictable at compile time and static analysis techniques fail to optimize or parallelize the code because the data accesses are input dependent.

Similarly, a control-flow irregularity is exhibited by a code that execute parts of a program based on the input values. The following code exhibits control-flow irregularity.

integer a[10];
readinput(a);
if (a[5] < 20) then
do_one();
else
do_two();
end if

The above code cannot be optimized unless the values from the array a are known.

Traditionally, irregular algorithms have been known to be difficult to optimize and parallelize.

References:

1. Gudula Rünger, [http://link.springer.com/chapter/10.1007%2F3-540-33541-2_1?LI=true Parallel Programming Models for Irregular Algorithms], in Parallel Algorithms and Cluster Computing vol 52, 2006, pages 3--23, Springer Berlin Heidelberg

2. Mario Méndez-Lojo et al., [http://dl.acm.org/citation.cfm?id=1693457 Structure-driven optimizations for amorphous data-parallel programs], in ACM SIGPLAN Notices - PPoPP '10
Volume 45 Issue 5, May 2010, Pages 3-14, ACM New York, NY, USA


{{AFC submission|||ts=20121219044629|u=Rupesh0508|ns=2}}