So, theoretically, given unlimited processing power, it should be possible to pass unoptimized SAT solver to a supercompiler, and obtain an optimized version. If this optimized SAT version is polynomial, then P equals NP. In practice, combinatorial explosion makes this screnario likely unprobable.
However, beside the brute force supercompilers, there should exist a set of rules in a form of A <-> B, where A and B are code fragments equivalent in their functionality. Using these rules, it should be possible to perform code transformations with a result similar to supercompilers, but in much less time (especially given a genetic or otherwise weighted algorithm). This method would be also prone to combinatorial explosion, but I think in much less degree, and more controllable than supercompilers. Under assumption that the method is in computationally acceptable range, the question would be how to automatically construct equivalence rules. A few of these rules could be axiomatic in their nature, and might be automatically derived utilizing supercompiler for a start. Once there is a complete axiomatic set of equivalences, we could dismiss the more time consuming supercompiler, and proceed with faster transforming-by-rules method. And again, if we could get any NP-complete algorithm optimized down to polynomial time, then P equals NP. čet, 8. stu 2018. u 17:53 Linas Vepstas <[email protected]> napisao je: > > > On Thu, Nov 8, 2018 at 10:02 AM Ivan Vodišek <[email protected]> wrote: > >> >> >> Once I saw an interesting discussion about a specific brute force >> assembler optimizer. Optimizer was taking an input domain and a short >> piece of code that operates over that domain, pairing it with codomain >> values (complete definition of an arbitrary algorithm). Then it was >> constructing a different combinations of instruction sequences that behave >> exactly as the starting program, but happen to be either smaller, or faster >> than the original code. >> > > This is called a "supercompiler". The earliest experiments were at IBM in > the 1980's; since then some half-dozen or more PhD's were written on it. > The hard part is determining if two different instruction sequences produce > the same output, or not, and for that, it turns out SAT is extremely > effective. They don't show up commercially, for many reasons. One is that > once you discover pairings, they have to be stuck into some database. A > second is that fewer instructions is not the same as lower power (a concern > on cell phones) A third is that the alternative may schedule insn's to > units that are occupied, so, although its fewer insns, it will take more > cycles, waiting for the bubble to drain. This is particularly fun for VLIW > machines. Finally, the top 10 or 20 most important aliases are known, and > the compiler writers have inserted them by hand, into compilers. The > remaining aliases seem not to improve things by more than a few percent, so > the effort does not seem worth it. How do I know this? I worked on a > supercompiler for hexagon for qualcomm. The hexagon was a six-unit/core > VLIW. > > --linas > > > -- > You received this message because you are subscribed to the Google Groups > "opencog" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at https://groups.google.com/group/opencog. > To view this discussion on the web visit > https://groups.google.com/d/msgid/opencog/CAHrUA37fdfNkm3%3D590wRm6uxD7MundKaHwB%2Bv4K7OQJduoY0xA%40mail.gmail.com > <https://groups.google.com/d/msgid/opencog/CAHrUA37fdfNkm3%3D590wRm6uxD7MundKaHwB%2Bv4K7OQJduoY0xA%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "opencog" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/opencog. To view this discussion on the web visit https://groups.google.com/d/msgid/opencog/CAB5%3Dj6U3KVPfu9AqJvdZ-_kydtAh_13ry2smZWJWY19oCxK9Zg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
