8 ms·

And then your CPU does it again! After all that work, your compiler outputs a totally ordered stream of instructions; then the CPU tries to figure out data dep

by chubot 11y ago

And then your CPU does it again! After all that work, your compiler outputs a totally ordered stream of instructions; then the CPU tries to figure out data dependencies in hardware and execute instructions out of order and in parallel. It seems as though C-like imperative languages and x86 are baked in forever... but the world is actually parallel.

willtim 11y ago
Excellent point!
marssaxman 11y ago
I've recently been thinking that we are looking at a situation analogous to the one Ben Franklin was in when he identified the two types of electrical charge as "positive" or "negative" pressure in the "electrical fluid" - he took a guess, which happened to be wrong, and ever since we have been stuck describing a surplus of electrons as "negative" and a deficit as "positive". This is no obstacle for the experienced but will remain an eternal hangup for beginners. By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.
- masak 11y ago
  Or maybe we needed to scale to some point with the Turing model for the Church model to assert itself and prove its merits in comparison. It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.
  - marssaxman 11y ago
    That certainly makes sense. I'm just looking ahead over the next couple of centuries and imagining generations of young programmers stumbling over all these ancient vestiges of mutable state and synchronous, batch-driven control flow which will probably still be littered around the roots of our computing systems long after the dominant paradigm has shifted. You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway. We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention. Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done. On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.
- chubot 11y ago
  I don't really agree... One reason is that computing models don't say anything useful about I/O, which we need in real computers. Turing machines have a straightforward extension to incorporate I/O -- execute it as a side effect at a given step. In contrast, the Church model doesn't really have any notion of time, so it's not clear how to reason about I/O. What evaluation order is used? In terms of computation, they're of course equivalent, so you can execute the Church model on the Turing-like machines (or more specifically a Von Neumann architecture). So maybe that was the right "choice" (if there ever was one). There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market. Closer to the ground, there is a pattern of "throwing away information at interfaces" in computing. Interfaces like x86, C, Unix, etc. get solidified by evolutionary forces. The cost of that modularity is global inefficiency. Another good example of that is the Java code gen architecture. People say "static types in Java code let you generated better code!" Well, no. The Java compiler throws out all the type information, generating Java byte code, which is dynamically typed. Then the JIT takes the byte code and has to re-infer all the type invariants to generate machine code.
  - dang 11y ago
    > There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market. My understanding is that the dataflow architectures didn't fare well for technical reasons. The instruction-level parallelism they worked with turned out to be too fine-grained, i.e. the cost of scheduling was greater than the win of parallelism for many programs, especially normal sequential programs that still need to be fast. This led to research in coarse-grained dataflow, but it doesn't seem that much has come of that. https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Literature/DataFlowProgrammingLanguages.pdf https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Lit...
trsohmers 11y ago
Unless you have a VLIW based architecture and the compiler takes care of the dependencies and hazard checking in software... then you are able to have dramatically simpler hardware (reducing area and power), along with faster performance! Wait another month and a half and I'll be getting around to writing my blog post in support of VLIW, and why previous attempts have failed miserably.
- catnaroek 11y ago
  Maybe this is a gross over-simplification, but isn't the tl;dr that VLIW architectures require significantly smarter compiler backends, and compiler writers were having none of that?
  - trsohmers 11y ago
    Very overly simplified, but yes. Thankfully my team will be showing the significantly smarter compiler in the coming months. It is primarily for our own architecture that is both VLIW and requires full software management of the memory, but a lot of the techniques we have developed can improve compilers in a general sense. We have also built all of our work within/around LLVM, so our optimizations that occur on the LLVMIR can potentially be applied to other backends, and our backend optimizations make very performant VLIW scheduling actually real.
    - wolf550e 11y ago
      I thought of Mill Computing, but I see from your profile that it's a competitor. Your thing seems less radical. What do you think of the Mill?
      - trsohmers 11y ago
        I've talked with the Mill folks, and while I find their architecture intellectually/academically interesting, I just don't think that stack machines will ever take off. We've stuck to the tried and true von Neumann, while dramatically increasing memory bandwidth within a core, throughout a chip, and when connecting multiple chips, along with enforcing strict determinism at a hardware level, which is why our compilers work. We have one ACM paper published that is intentionally vague, but describes at a high level our scratchpad (software managed) memory techniques... we'll be talking the specifics of our full toolchain later this summer when we have a full public unveiling of the architecture. Another problem with Mill is that they have been around for a little over 10 years, and have not released anything publicly (though have given a number of very detailed talks). They have had a lot of trouble getting their design into FPGAs, and even more trouble with having working compilers. When I started REX, I believed in getting it into silicon as fast as possible, as that is the point when people would take us seriously. We closed funding in July of 2015, and are taping out our first silicon next month... While many have called us crazy (and we will be giving real information on why we are not that crazy), I definitely don't want to be called vaporware.
nickpsecurity 11y ago
And then the CPU itself is a bunch of wires running in parallel with careful synchronization to pretend to be a serial or barely parallel (multicore) machine. ;)

by chubot 11y ago

willtim 11y ago

Excellent point!

marssaxman 11y ago

I've recently been thinking that we are looking at a situation analogous to the one Ben Franklin was in when he identified the two types of electrical charge as "positive" or "negative" pressure in the "electrical fluid" - he took a guess, which happened to be wrong, and ever since we have been stuck describing a surplus of electrons as "negative" and a deficit as "positive". This is no obstacle for the experienced but will remain an eternal hangup for beginners. By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.

masak 11y ago
Or maybe we needed to scale to some point with the Turing model for the Church model to assert itself and prove its merits in comparison. It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.
- marssaxman 11y ago
  That certainly makes sense. I'm just looking ahead over the next couple of centuries and imagining generations of young programmers stumbling over all these ancient vestiges of mutable state and synchronous, batch-driven control flow which will probably still be littered around the roots of our computing systems long after the dominant paradigm has shifted. You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway. We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention. Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done. On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.
chubot 11y ago
I don't really agree... One reason is that computing models don't say anything useful about I/O, which we need in real computers. Turing machines have a straightforward extension to incorporate I/O -- execute it as a side effect at a given step. In contrast, the Church model doesn't really have any notion of time, so it's not clear how to reason about I/O. What evaluation order is used? In terms of computation, they're of course equivalent, so you can execute the Church model on the Turing-like machines (or more specifically a Von Neumann architecture). So maybe that was the right "choice" (if there ever was one). There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market. Closer to the ground, there is a pattern of "throwing away information at interfaces" in computing. Interfaces like x86, C, Unix, etc. get solidified by evolutionary forces. The cost of that modularity is global inefficiency. Another good example of that is the Java code gen architecture. People say "static types in Java code let you generated better code!" Well, no. The Java compiler throws out all the type information, generating Java byte code, which is dynamically typed. Then the JIT takes the byte code and has to re-infer all the type invariants to generate machine code.
- dang 11y ago
  > There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market. My understanding is that the dataflow architectures didn't fare well for technical reasons. The instruction-level parallelism they worked with turned out to be too fine-grained, i.e. the cost of scheduling was greater than the win of parallelism for many programs, especially normal sequential programs that still need to be fast. This led to research in coarse-grained dataflow, but it doesn't seem that much has come of that. https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Literature/DataFlowProgrammingLanguages.pdf https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Lit...

trsohmers 11y ago

Unless you have a VLIW based architecture and the compiler takes care of the dependencies and hazard checking in software... then you are able to have dramatically simpler hardware (reducing area and power), along with faster performance! Wait another month and a half and I'll be getting around to writing my blog post in support of VLIW, and why previous attempts have failed miserably.

catnaroek 11y ago
Maybe this is a gross over-simplification, but isn't the tl;dr that VLIW architectures require significantly smarter compiler backends, and compiler writers were having none of that?
- trsohmers 11y ago
  Very overly simplified, but yes. Thankfully my team will be showing the significantly smarter compiler in the coming months. It is primarily for our own architecture that is both VLIW and requires full software management of the memory, but a lot of the techniques we have developed can improve compilers in a general sense. We have also built all of our work within/around LLVM, so our optimizations that occur on the LLVMIR can potentially be applied to other backends, and our backend optimizations make very performant VLIW scheduling actually real.
  - wolf550e 11y ago
    I thought of Mill Computing, but I see from your profile that it's a competitor. Your thing seems less radical. What do you think of the Mill?
    - trsohmers 11y ago
      I've talked with the Mill folks, and while I find their architecture intellectually/academically interesting, I just don't think that stack machines will ever take off. We've stuck to the tried and true von Neumann, while dramatically increasing memory bandwidth within a core, throughout a chip, and when connecting multiple chips, along with enforcing strict determinism at a hardware level, which is why our compilers work. We have one ACM paper published that is intentionally vague, but describes at a high level our scratchpad (software managed) memory techniques... we'll be talking the specifics of our full toolchain later this summer when we have a full public unveiling of the architecture. Another problem with Mill is that they have been around for a little over 10 years, and have not released anything publicly (though have given a number of very detailed talks). They have had a lot of trouble getting their design into FPGAs, and even more trouble with having working compilers. When I started REX, I believed in getting it into silicon as fast as possible, as that is the point when people would take us seriously. We closed funding in July of 2015, and are taping out our first silicon next month... While many have called us crazy (and we will be giving real information on why we are not that crazy), I definitely don't want to be called vaporware.

nickpsecurity 11y ago

And then the CPU itself is a bunch of wires running in parallel with careful synchronization to pretend to be a serial or barely parallel (multicore) machine. ;)