Irregular algorithm: Difference between revisions
Content deleted Content added
Anne Delong (talk | contribs) change to a redirect as per discussion at Wikiproject Computer science |
m remove errata from redirect page using AWB |
||
| 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". --> |
|||
Latest revision as of 19:03, 9 September 2014
Redirect to: