Difference between revisions of "Nested Loop Recognition"
Jump to navigation
Jump to search
(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 ...") |
|||
| Line 5: | Line 5: | ||
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. | 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;"> | <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;"> | ||
| Line 33: | Line 30: | ||
</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><span style="color: #d3d3d3; background-color: #000000;">alain@durian$ </span><span style="color: #d3d3d3; background-color: #000000;"> | ||
| − | </span></pre | + | </span> |
| − | + | </pre> | |
Revision as of 12:25, 16 September 2013
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.
<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>