|
#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". -->
| 