I just read "Frighteningly Ambitious Startup Ideas" in detail. Do not
regard the following as an actual start-up idea but as a sketch, if
you will, of the massive R&D project that would actually constitute
a Sufficiently Smart Compiler for the problem of parallelization.
Start with a compiler that computes an effect system on an "ordinary" language, because, automatically, we can't force programmers to move to a new language to use our Sufficiently Smart Compiler. This means that it tracks the read, write, alloc, free, throw, and call behavior of every expression/statement it compiles, aggregating them across compound statements. So far, we're just extending the work of some researchers here.
(Industry has spent billions avoiding having to actually use better languages and better operating systems -- "web services", for example, are largely an attempt to shoehorn application programming into a universal document viewer rather than just use 9P2000/Styx for mounting an application directory across the network. So we can use ideas from the research world, but not actually make anyone else adopt them.)
You use the effect system to form a dependency graph over expressions/statements. This graph has expressions as vertices and data dependencies as arrows; forming it out of effect-system data gives you better information to build the graph out of than conventional data-flow analysis (which is, IIRC, intraprocedural). "Data dependency" of X on Y just means X comes later than Y in sequential execution and both have at least one effect on the same region. This remains in the standard realm of optimizations, pretty much.
Now, here comes the magic. Every node/expression at the same height of that directed-acyclic graph depends not a wink on the others at its height. Each "level" of the graph can be completely parallelized, and its results regathered and execution serialized only when it's time to move on to the next level of the graph. Our compiler is now somewhat smart. I also recommend employing a deterministic-parallel-execution framework/library to cover our asses.
Here's the tricky bit: which nodes of that graph are worth parallelizing? Spawning threads, even green threads, is expensive. We need to figure out what expressions/statements are computationally expensive enough to be worth forking now and joining later. I've never heard of a compiler that will do Big-O complexity analysis for the programmer, at least not without dependent types (static analysis dependent upon and capable of predicting dynamic (run-time) values). We could use hand-written annotations/pragmas to determine what's expensive, but then we're putting effort back on our user instead of acting like a magic genie that solves all their problems without their having to think. Again, we could use a genetic algorithm to decide where to parallelize, but that's obtrusive to the user (spending expensive developer time) instead of transparent (spending cheap computer time).
And, of course, none of this gets us around the problem that much/most actual code in non-functional languages is written in an effectful, inherently-sequential style when it could otherwise be stateless/pure and embarrassingly parallel. All we've built is a compiler capable of spotting the good parallelization opportunities and taking them without outside human direction. We already had to build two kinds of compiler magic, one based on the other, and then employ either some new form of static performance/complexity analysis, some funky heuristics, or even a genetic algorithm to figure out where to allocate our resources.
The sufficiently smart compiler can exist, but it carries such a horrific analytical burden that it would rarely, if ever, get around to the actual business of generating code. And then you'd have to turn it into an actual business treating software as a product ("selling smells")! Or you could build it as a research project, in which case you're likely to spend the rest of your life on the damn thing from having to "pivot" for grant funding every so often.
Start with a compiler that computes an effect system on an "ordinary" language, because, automatically, we can't force programmers to move to a new language to use our Sufficiently Smart Compiler. This means that it tracks the read, write, alloc, free, throw, and call behavior of every expression/statement it compiles, aggregating them across compound statements. So far, we're just extending the work of some researchers here.
(Industry has spent billions avoiding having to actually use better languages and better operating systems -- "web services", for example, are largely an attempt to shoehorn application programming into a universal document viewer rather than just use 9P2000/Styx for mounting an application directory across the network. So we can use ideas from the research world, but not actually make anyone else adopt them.)
You use the effect system to form a dependency graph over expressions/statements. This graph has expressions as vertices and data dependencies as arrows; forming it out of effect-system data gives you better information to build the graph out of than conventional data-flow analysis (which is, IIRC, intraprocedural). "Data dependency" of X on Y just means X comes later than Y in sequential execution and both have at least one effect on the same region. This remains in the standard realm of optimizations, pretty much.
Now, here comes the magic. Every node/expression at the same height of that directed-acyclic graph depends not a wink on the others at its height. Each "level" of the graph can be completely parallelized, and its results regathered and execution serialized only when it's time to move on to the next level of the graph. Our compiler is now somewhat smart. I also recommend employing a deterministic-parallel-execution framework/library to cover our asses.
Here's the tricky bit: which nodes of that graph are worth parallelizing? Spawning threads, even green threads, is expensive. We need to figure out what expressions/statements are computationally expensive enough to be worth forking now and joining later. I've never heard of a compiler that will do Big-O complexity analysis for the programmer, at least not without dependent types (static analysis dependent upon and capable of predicting dynamic (run-time) values). We could use hand-written annotations/pragmas to determine what's expensive, but then we're putting effort back on our user instead of acting like a magic genie that solves all their problems without their having to think. Again, we could use a genetic algorithm to decide where to parallelize, but that's obtrusive to the user (spending expensive developer time) instead of transparent (spending cheap computer time).
And, of course, none of this gets us around the problem that much/most actual code in non-functional languages is written in an effectful, inherently-sequential style when it could otherwise be stateless/pure and embarrassingly parallel. All we've built is a compiler capable of spotting the good parallelization opportunities and taking them without outside human direction. We already had to build two kinds of compiler magic, one based on the other, and then employ either some new form of static performance/complexity analysis, some funky heuristics, or even a genetic algorithm to figure out where to allocate our resources.
The sufficiently smart compiler can exist, but it carries such a horrific analytical burden that it would rarely, if ever, get around to the actual business of generating code. And then you'd have to turn it into an actual business treating software as a product ("selling smells")! Or you could build it as a research project, in which case you're likely to spend the rest of your life on the damn thing from having to "pivot" for grant funding every so often.
0 commentaires:
Enregistrer un commentaire