Irregular algorithm

Request review at WP:AFC

Irregular Algorithm

Category: Computer Science

To be linked from: [[1]].

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, 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., 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