Difference between revisions of "Nested Loop Recognition"
Jump to navigation
Jump to search
| 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:red"> |
| − | </span><span style="color: #d3d3d3; background-color: #000000;">530832</span><span style="color: #d3d3d3; background-color: #000000;"> | + | Le texte est '''préformaté''' |
| − | </span><span style="color: #d3d3d3; background-color: #000000;">530832</span><span style="color: #d3d3d3; background-color: #000000;"> | + | avec un style et |
| − | </span><span style="color: #d3d3d3; background-color: #000000;">530833</span><span style="color: #d3d3d3; background-color: #000000;"> | + | la ''syntaxe wiki'' '''''ne peut pas''''' être appliquée. |
| − | </span><span style="color: #d3d3d3; background-color: #000000;">530883</span><span style="color: #d3d3d3; background-color: #000000;"> | + | </pre> |
| − | </span><span style="color: #d3d3d3; background-color: #000000;">530883</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;"> | ||
| + | </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;">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;"> | ||
| Line 16: | Line 26: | ||
</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;">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;">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;">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;"> 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;">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: #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: #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;"> 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;"> | ||
Revision as of 12:29, 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.
Le texte est '''préformaté''' avec un style et la ''syntaxe wiki'' '''''ne peut pas''''' être appliquée.
<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>