Équipe ICPS - Informatique et Calcul Parallèle Scientifique

Nested Loop Recognition

From Équipe ICPS - Informatique et Calcul Parallèle Scientifique
Revision as of 12:24, 16 September 2013 by Genaud (talk | contribs) (Created page with "Nested loop recognition (NLR) is an algorithm that transforms a series of values into a loop nest. The technique is described in our paper Prediction and trace compression of ...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Nested loop recognition (NLR) is an algorithm that transforms a series of values into a loop nest. The technique is described in our paper Prediction and trace compression of data access addresses through nested loop recognition.

The software is freely available upon request. Please send an email to Alain Ketterlin for request.

Below is an example run of the tool on a simple trace. More complex data formats are handled (tuples, symbols, etc.), and various output options can be customized. The basic algorithm can also be used as a library.


<pre style="color: #d3d3d3; background-color: #000000;"><span style="color: #d3d3d3; background-color: #000000;">alain@durian$ head fir2dim.trace</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530832</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530832</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530833</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530883</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530883</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530884</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530934</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530934</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530935</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">530832</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">alain@durian$ wc fir2dim.trace</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> 90000 90000 630000 fir2dim.trace</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">alain@durian$ ./nlr -k 100 < fir2dim.trace </span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">for </span><span style="color: #cd0000; background-color: #000000;">i0</span><span style="color: #d3d3d3; background-color: #000000;"> = 0 to 0x63</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> for </span><span style="color: #00cd00; background-color: #000000;">i1</span><span style="color: #d3d3d3; background-color: #000000;"> = 0 to 0x31</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> for </span><span style="color: #0000ee; background-color: #000000;">i2</span><span style="color: #d3d3d3; background-color: #000000;"> = 0 to 0x2</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> val 0x81990 + 51*</span><span style="color: #cd0000; background-color: #000000;">i0</span><span style="color: #d3d3d3; background-color: #000000;"> + 1*</span><span style="color: #00cd00; background-color: #000000;">i1</span><span style="color: #d3d3d3; background-color: #000000;"> + 51*</span><span style="color: #0000ee; background-color: #000000;">i2</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> val 0x81990 + 51*</span><span style="color: #cd0000; background-color: #000000;">i0</span><span style="color: #d3d3d3; background-color: #000000;"> + 1*</span><span style="color: #00cd00; background-color: #000000;">i1</span><span style="color: #d3d3d3; background-color: #000000;"> + 51*</span><span style="color: #0000ee; background-color: #000000;">i2</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> val 0x81991 + 51*</span><span style="color: #cd0000; background-color: #000000;">i0</span><span style="color: #d3d3d3; background-color: #000000;"> + 1*</span><span style="color: #00cd00; background-color: #000000;">i1</span><span style="color: #d3d3d3; background-color: #000000;"> + 51*</span><span style="color: #0000ee; background-color: #000000;">i2</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> for </span><span style="color: #0000ee; background-color: #000000;">i2</span><span style="color: #d3d3d3; background-color: #000000;"> = 0 to 0x2</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> val 0x81990 + 51*</span><span style="color: #cd0000; background-color: #000000;">i0</span><span style="color: #d3d3d3; background-color: #000000;"> + 1*</span><span style="color: #00cd00; background-color: #000000;">i1</span><span style="color: #d3d3d3; background-color: #000000;"> + 51*</span><span style="color: #0000ee; background-color: #000000;">i2</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> val 0x81991 + 51*</span><span style="color: #cd0000; background-color: #000000;">i0</span><span style="color: #d3d3d3; background-color: #000000;"> + 1*</span><span style="color: #00cd00; background-color: #000000;">i1</span><span style="color: #d3d3d3; background-color: #000000;"> + 51*</span><span style="color: #0000ee; background-color: #000000;">i2</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;"> val 0x81991 + 51*</span><span style="color: #cd0000; background-color: #000000;">i0</span><span style="color: #d3d3d3; background-color: #000000;"> + 1*</span><span style="color: #00cd00; background-color: #000000;">i1</span><span style="color: #d3d3d3; background-color: #000000;"> + 51*</span><span style="color: #0000ee; background-color: #000000;">i2</span><span style="color: #d3d3d3; background-color: #000000;"> </span><span style="color: #d3d3d3; background-color: #000000;">alain@durian$ </span><span style="color: #d3d3d3; background-color: #000000;"> </span></pre>

Retrieved from "https://icps.icube.unistra.fr/index.php?title=Nested_Loop_Recognition&oldid=41"