Difference between revisions of "Locally optimal optimisation of code fragments"
(→The problem with optimal optimisation of code) |
(→The problem with optimal optimisation of code) |
||
| Line 4: | Line 4: | ||
==The problem with optimal optimisation of code== | ==The problem with optimal optimisation of code== | ||
| − | If we assume a code fragment of 4 instructions of 32 bit each and the two input registers to be 32 bit then we have | + | If we assume a code fragment of 4 instructions of 32 bit each and the two input registers to be 32 bit then we have: |
:2<sup>32<sup>4</sup></sup> * 2<sup>32</sup> * 2<sup>32</sup> = 6 277 101 735 386 680 763 835 789 423 207 666 416 102 355 444 464 034 512 896 | :2<sup>32<sup>4</sup></sup> * 2<sup>32</sup> * 2<sup>32</sup> = 6 277 101 735 386 680 763 835 789 423 207 666 416 102 355 444 464 034 512 896 | ||
possible combinations of code and data. This number is so large that there is no hope in using brute force to test all possible combinations or to verify that two different code fragments give the same result for all possible input. | possible combinations of code and data. This number is so large that there is no hope in using brute force to test all possible combinations or to verify that two different code fragments give the same result for all possible input. | ||
| − | Boolean logic is different from arithmetic in that every bit is computed completely independently from the others. So it makes no difference if we use the full 32 bit or just one bit, changing the value of one bit will never affect | + | Boolean logic is different from arithmetic in that every bit is computed completely independently from the others. So it makes no difference if we use the full 32 bit or just one bit, changing the value of one bit will never affect the others. That means we now have: |
:2<sup>32<sup>4</sup></sup> * 2<sup>1</sup> * 2<sup>1</sup> = 1 361 129 467 683 753 853 853 498 429 727 072 845 824 | :2<sup>32<sup>4</sup></sup> * 2<sup>1</sup> * 2<sup>1</sup> = 1 361 129 467 683 753 853 853 498 429 727 072 845 824 | ||
| − | possible combinations of code and data, a huge improvement but still | + | possible combinations of code and data, a huge improvement but still impossibly large. So it is clear that using brute force alone will not work. |
| + | |||
| + | Since we now have reduced the input to two bits then there are just 2<sup>2</sup) = 4 possible input combinations. | ||
| + | '''A''' '''B''' | ||
| + | 0 0 | ||
| + | 0 1 | ||
| + | 1 0 | ||
| + | 1 1 | ||
| + | |||
Revision as of 06:51, 6 September 2013
A 32 bit CPU
The problem with optimal optimisation of code
If we assume a code fragment of 4 instructions of 32 bit each and the two input registers to be 32 bit then we have:
- 2324 * 232 * 232 = 6 277 101 735 386 680 763 835 789 423 207 666 416 102 355 444 464 034 512 896
possible combinations of code and data. This number is so large that there is no hope in using brute force to test all possible combinations or to verify that two different code fragments give the same result for all possible input.
Boolean logic is different from arithmetic in that every bit is computed completely independently from the others. So it makes no difference if we use the full 32 bit or just one bit, changing the value of one bit will never affect the others. That means we now have:
- 2324 * 21 * 21 = 1 361 129 467 683 753 853 853 498 429 727 072 845 824
possible combinations of code and data, a huge improvement but still impossibly large. So it is clear that using brute force alone will not work.
Since we now have reduced the input to two bits then there are just 22</sup) = 4 possible input combinations.
A B 0 0 0 1 1 0 1 1
We assume 32 bit per variable
All bits are completely independent from each other, that means we only have to consider the least significant bit. All other bits will behave the same.
Out of 14 190 004 558 696 programs generated only 64 974 were unique. That means that there must be 64 974 shortest code fragments, one for each function. If we can find a mapping between
1111010011110000 B C A D not or or and not (not ((((not D) or A) or C) and B))
Generate the truth table
A B C D T 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0
Generate the truth table in parallel
A 0000000011111111 B 0000111100001111 C 0011001100110011 D 0101010101010101 T 1111010011110000
v1 |v2 |v3 |v4 | ¬((¬v4||v1||v3)&&v2)
1 | 1 | 1 | 1 | 0 1 | 1 | 1 | 0 | 0 1 | 1 | 0 | 1 | 0 1 | 1 | 0 | 0 | 0 1 | 0 | 1 | 1 | 1 1 | 0 | 1 | 0 | 1 1 | 0 | 0 | 1 | 1 1 | 0 | 0 | 0 | 1 0 | 1 | 1 | 1 | 0 0 | 1 | 1 | 0 | 0 0 | 1 | 0 | 1 | 1 0 | 1 | 0 | 0 | 0 0 | 0 | 1 | 1 | 1 0 | 0 | 1 | 0 | 1 0 | 0 | 0 | 1 | 1 0 | 0 | 0 | 0 | 1
