SAT appears to be rather impervious to statistical methods because it is very non-linear and non-local (besides, of course, being NP-complete). Flip one single literal anywhere and poof!, your formula mght go from SAT to UNSAT, or vice versa, or you might enable a ton of simplifications, etc. So it might be very hard to train a network on such a riotous state space.
Additionally, in practice SAT solvers are also supposed to provide witnesses (i.e., a satisfying assignment or an unsatisfiability core) to back their verdicts, and that may be an ever taller order for ML.
Since all of these combinatorial optimization problems are, in full generality, are as difficult as possible in the complexity theoretic sense, there is little prospect of AI/ML helping to solve these problems in general. (?)
But people hope that some subclass of "real-life" instances of one of these optimization problems has enough structure that AI/ML may be able to learn useful heuristics for it. (This is not my field. This is just my take-away from reading some AI/ML-for-CO papers.)
Seems kind of clear to me we’re driving towards as little statefulness as possible, compressed symbolic logic, that’s able to compute as many states as possible. Less resource use on RAM and storage as available chip cycles continues to grow
Human biology is a min/max engine, evolved for years to “enough” food, shelter… and we see daily there is not static state to reality. Our social behavior to try and preserve state is some cognitive dissonant “War is Peace.” insanity
Math is a compressed form of communication. “Add two apples to the set of all apples” is literally more glyphs than the same statement in usual math syntax. Paper and written literacy was hard to come by back in the day, but verbal literacy was cheap and ubiquitous.
The economy is built on physical statistical measures. Such a framework to keep TP and food on shelves is the minimal state needed to keep people from rioting. Economy has nothing to do with historical story and political memes at this point.
We could look further into computing in other substrates, like mycelia. Biochemically shape structure to represent certain states.
Computing is a concept not coupled to contemporary ignorant business machines. We made a social monolith around computing by propping up big tech
One thing is that you can think of static analysis as building facts about the program. You can for example start by assuming nothing and then adding facts about the program. And you need to iteratively propagate these facts from one line of code to the next. But you can also start by assuming the universe and removing facts from this universe.
Some classes of program analysis are safe to stop early. For example, if I have a static analysis that tries to find the target of virtual calls (also known as a devirtualization), you can stop early after a time out. Not finding the target just implies a missed optimization.
There are some other classes of program analysis that are not safe until the algorithm finishes. For example, if you have to prove that two variables do not alias each other, you cannot stop until you have all possible points-to sets and verify that for each of those two variables, their points-to sets do not overlap.
So, given the above restriction, the first class (early termination) is perhaps more desirable and throwing more compute time would yield a better approximation. For the second one, it wouldn't.
Another thing to keep in mind is that most of these data flow frameworks are not easily parallelized. The only paper I've read (but I haven't kept up with these avenue of research) that implemented a control flow analysis in the GPU is the following:
* Prabhu, Tarun, et al. "EigenCFA: Accelerating flow analysis with GPUs." ACM SIGPLAN Notices 46.1 (2011): 511-522.
I'm sure people are working on it. (I should mention that there are some program analyses written in Datalog and Datalog can be parallelized, but I think this is a processor based parallelization and not a GPU one).
The third thing is that when you say whether we are limited by algorithms or compute, I think it is important to note that it is impossible to find all possible facts *precisely* about a program without running it. There is some relation between static program analysis and the halting problem. We want to be able to guarantee termination of our static program analysis and some facts are just unobtainable without running. However, there is not just static program analyses, but also dynamic program analyses which can analyze a program as it is running. An example of a dynamic program analysis can be value profiling. Imagine that you have a conditional and for 99% of the time, the conditional is false. With a virtual machine, you can add some instrumentation to find out the probability distribution of this conditional and then generate code without this condition, optimize the code, and only if the condition is false then run a less optimized version of the code with an additional penalty. Some virtual machines already do this for types and values. Type profiling and value profiling.
One last thing, when you say a meaningful performance boost, it depends on your code. If your code can be folded away completely at compile time, then yes, we could just generate the solution at compile time and that's it. But if it doesn't or parts of it cannot be folded away / the facts cannot be used to optimize the code, then no matter how much you search, you cannot optimize it statically.
Compilers are awesome :)
As an addendum, it might be desirable in the future to have a repository of analyzed code. Compilers right now are re-analyzing code on every single compile and not sharing their results across the web. It is a fantasy of mine to have a repository that maps some code with equivalent representations and every time one does a local compile it explores a new area and adds it to the repository. Essentially, each time you compile the code, it explores new potential optimizations and all of them get stored online.
yes, this is obviously what you want. there shouldn't be a notion of 'running' the compiler; it should simply be a persistent process. importantly, there are two issues, which are orthogonal but both critically important: iterativity—that is, produce an acceptable result immediately, but then continue to refine it—and incrementality—that is, when making a small change to the code, take advantage of information learned about the previous version.
there is this recent paper on incrementality https://arxiv.org/pdf/2104.01270.pdf, though it has some caveats (e.g. it does not handle iterativity at all, so there is only so far it can go; can do much better)—but it is interesting non-technically because the authors work for amazon, so perhaps some of this is headed for industry
> it might be desirable in the future to have a repository of analyzed code.
We did a code verifier back end for a small app store. Were mostly MScs + some Phd consulting.
The world is indeed waiting for a CloudOptimizingCompiler (CoCo?!) - there are so many possibilities for shared compute, library caching, and machine learning.
modern AI is just vector multipication. any AI chip is just 10,000s of very simple cores which can do vector float operations and little else. this also entails clever trade offs of shared cache and internal bandwidth.
(as a thought experiment, consider a naive million by million matrix multipication. this will take a single cpu about 1 year! how do we reduce this to 1s ?)
Nowadays AI chips are specialized in not just vector multiplication but matrix multiplication. Just as moving from scalar math to vectors brings savings in control and routing logic, moving from vector to matrix does the same. Taking a result from a floating point unit and moving it to a big, multi-ported register file and then reading it out again to feed into another floating point unit is often a much bigger draw of power than the multiplication or addition itself and to the extent you can minimize that by feeding the results of one operation direction into the processing structures for the next you've got a big win.
As someone with a lot of interest in but no fluency with chip design, or the dividing and conquering of math within silicon, for that matter, how would you multiply a 1m² matrix?
Each "unit of work" in matrix multiplication is not dependent on any other unit of work. Stuff as many cores as you can into a chip, and then simply feed in all your vectors at the same time.
A million element square matrix is a lot of data. To process that in a second is much more bandwidth than a single socket can support, so you'll need many sockets too.
No modern high-performance motor that needs speed control uses electric power directly from a battery or the mains: it always goes through an electronic controller of some kind, which uses transistors to generate the necessary waveforms at the required voltage. Whether the motor itself is a permanent magnet motor or an inductance motor doesn't really matter; they each have strengths and weaknesses, but they both need electronic controllers.
Is there a pathway to replace these with recycled plastic something?
would love for this to come fr9m OceanCleanup plastics somehow