Irregular algorithm
This redirect was tagged by HasteurBot, because it may meet Wikipedia's criteria for speedy deletion as either a page in the draftspace, a declined/unsubmitted userspace Articles for Creation page, or a draft in either namespace with no content except the placeholder article wizard text that has not been edited (excluding bot edits) in over six months. See CSD G13.
If this redirect does not meet the criteria for speedy deletion, please remove this notice. This draft was nominated by HasteurBot on December 30, 2013. If you plan to improve this draft, simply and remove the It MAY qualify to be deleted per WP:CSD#G13 as the edit before that occurred on December 26, 2012 (12.45 years ago). {{Db-afc}}, {{Db-draft}}, or {{Db-g13}} code.Administrators: check links, talk, history (last), and logs before deletion, as this page was tagged by a bot. This page was last edited by HasteurBot (contribs | logs) at 12:03, 30 December 2013 (UTC) (11 years ago) |
 | This article, Irregular algorithm, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Preload talk Inform author |
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, 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