6 ms·

GPUs are much closer to von Neumann machines than to anything people typically deriding the latter have in mind (such as say the Reduceron architecture.) Every

by yosefk 10y ago

GPUs are much closer to von Neumann machines than to anything people typically deriding the latter have in mind (such as say the Reduceron architecture.) Every commercially significant accelerator, GPUs included, has a RAM, often multi-banked to support vectorized random access, it has an imperative programming model, and it runs (often vector) instructions from program memory operating on registers, data is occasionally exchanged between registers and RAM addresses. $100 says this will remain true for the next 20 years. The thing most far away from a von Neumann machine that is commercially significant is the FPGA and it is nothing like what people deriding the von Neumann machines have in mind. It's imperative, has registers and RAM blocks, and it will cause nausea in the typical functional programming supremacist. (Except those that choose to squander its performance potential on implementing a wasteful machine like the Reduceron because graph reduction is just better than an imperative low-level programming model.) Programmers need to be liberated from misconceptions wrt von Neumann machines.

DigitalJack 10y ago
I have to ask, what makes you say this: "and it will cause nausea in the typical functional programming supremacist" with regard to FPGAs?
- _yosefk 10y ago
  Not only are FPGAs as far from the ideal of "computation as reduction" expressed in the paper as they could possibly be, but they're the hardest machine to fit into this sort of a paradigm. The typical CPU will run functional code fairly efficiently if enough work is put into the compiler (to some functional programmers this sounds bad because hardware should make writing functional language compilers easy. People who know about hardware make a different conclusion - that hardware is just fine, as Ken Thompson said, "the PDP-11 is a fine Lisp machine, it's not a language special enough to warrant a specialized machine.") The typical accelerator is a harder target to a general-purpose functional programming language (it's a poor target for a general-purpose imperative language to begin with.) The FPGA, with its explicit management of every imaginable resource, is the worst target for a general-purpose functional programming language. In general, the farther away a commercially significant machine is from the classical von Neumann architecture, the more terrible target it is for functional languages, which never prevented FP aficionados from talking about "the end of Moore's law bringing about the long-awaited demise of the von Neumann machine", a "demise" that largely doesn't happen and where it does, it does not mean what they think it means.
  - nickpsecurity 10y ago
    What about PLA or PAL? Such tech seems closer to functional programming than FPGA's.
  - catnaroek 10y ago
    > to some functional programmers this sounds bad because hardware should make writing functional language compilers easy. People who know about hardware make a different conclusion - that hardware is just fine, as Ken Thompson said, "the PDP-11 is a fine Lisp machine, it's not a language special enough to warrant a specialized machine." Wow, really? C got a lot of things wrong, but the one thing that it got right is its abstract model of the machine. As a functional programmer, rather than specialized hardware, what I want is functional languages designed to target the abstract C machine. (Though maybe I am in a minority.) > The FPGA, with its explicit management of every imaginable resource, is the worst target for a general-purpose functional programming language. Explicit resource management is compatible with functional programming, but it requires a type system capable of undestanding the ephemeral nature of resources, à la Rust.
  - chillingeffect 10y ago
    > The FPGA, with its explicit management of every imaginable resource, is the worst target for a general-purpose functional programming language. That's a great way to put it... but perhaps there's a more suitable FPGA cell for functional programming (than block lookup tables with state)? Maybe something with a local stack, recursion assistance, an iterator? Also, a good deal of the FPGA resource management is focused on optimization... What if the optimization-at-all-costs constraint were relaxed somewhat, or supplanted with meta-information to indicate the completion of a group of cells to allow a message to propagate? With relaxed constraints partial, on-the-fly and self- modifications could become regular features.
    - adwn 10y ago
      > Maybe something with a local stack, recursion assistance, an iterator? [...] supplanted with meta-information to indicate the completion of a group of cells to allow a message to propagate? What you're describing sounds a lot more like many CPU cores connected by a network than like an FPGA. The point of an FPGA is that it gives you very precise and flexible control over things like timing and interconnects. Without that, FPGAs are actually pretty slow and you'd better use a CPU. > With relaxed constraints partial, on-the-fly and self- modifications could become regular features. There's a reason why self-modifying software is restricted to niche use cases: it's hard to reason about. Dynamic partial reconfiguration is slowly becoming a thing in FPGA design, but it's typically used to work around resource limitations.
- adwn 10y ago
  To put it simple, FPGA design (as practiced in nearly 100% of commercial use cases, i.e. with VHDL or Verilog) is iterative programming on steroids – even a sequence of actions requires an explicit mutable state variable. If you need to access external memory (e.g., DDR3 RAM), you have to communicate with a memory controller module. So not only is there no garbage collection, there's not even a malloc! And no recursion. From time to time you'll read statements along the lines of "functional programming languages map really well to FPGA design", allegedly because the logic functions between register stages behave like declarative constructs. Such claims are excellent bullshit detectors, indicating that the person uttering them doesn't have the slightest clue what they're talking about. It's on par with believing that expressions like "a + b * c" make C a functional language.
  - hderms 10y ago
    what are your opinions on http://www.clash-lang.org/ http://www.clash-lang.org/ ? It's different than what you describe because the language is explicitly aware of the fact its running on an FPGA. However, it's seemingly pretty declarative and functional and has an FPGA as a possible target.
    - _yosefk 10y ago
      First impression, could be misinformed, but I'll bite. Since a hardware circuit is a recursive function that takes a state of the hardware and produces a new state, starting from an initial state (and so is the universe where the initial state was supplied by the Big Bang), you can of course express it straightforwardly as a recursive function, which I think is what they sometimes do: blinkerT (leds,mode,cntr) key1R = ((leds',mode',cntr'),leds) where -- clock frequency = 50e6 (50 MHz) -- led update rate = 333e-3 (every 333ms) cnt_max = 16650000 -- 50e6 * 333e-3 cntr' | cntr == cnt_max = 0 | otherwise = cntr + 1 mode' | key1R = not mode | otherwise = mode leds' | cntr == 0 = if mode then complement leds else rotateL leds 1 | otherwise = leds This is VHDL/Verilog spelled in Haskell (real hardware description languages will not make you spell the old state - leds,mode... - and the new state - leds',mode'... explicitly, which gets annoying for 20 state variables. Of course this could be taken care of by a preprocessor or a macro system, my point isn't that it's verbose but that it's VHDL spelled in Haskell, a bit awkwardly and maybe you can do it less awkwardly but the programming model is the same so calling it Haskell is cheating, kinda.) This is definitely not what TFA is about - you don't represent the blinking leds as graph reduction, rather, you generate VHDL from VHDL-like Haskell. This is not to say they aren't doing cool things in this project. If indeed they compile this: fir coeffs x = dotp coeffs (window x) where dotp as bs = sum (zipWith (*) as bs) ...to efficient hardware description code, that's really cool. In general, I think that a sufficiently restricted functional language can compile very nicely to FPGA/hardware (and to DSPs and GPUs etc. etc.) I'm just saying that a general-purpose functional language is better targeted at a CPU, and that a functional language targeting something else is a DSL of sorts.
stcredzero 10y ago
GPUs are much closer to von Neumann machines than to anything people typically deriding the latter have in mind The GPU architecture was developed to enable the application of many von Neumann machines to a particular type of "mildly embarrassing" parallelism. I'm not so sure that we couldn't greatly benefit from going a little further in this direction. Right now, I see a mainstream architecture that does fairly well with read parallelism, with a need for more efficient two-way communication between separate threads. What if we had better hardware support for the things we're trying to do with with the Disruptor that came out of HFT? This would also benefit multiplayer games.
jerf 10y ago
I'm taking the general case of the question, admittedly. I think a lot of the von Neumann detractors think that there's going to be this revolution, where one day they'll wake up and omigosh, stream processors have suddenly taken over the market (or whatever your favorite non-von-Neumann architecture is) and That was the Day that Everything Changed. That's not how it's going to be. It can't be. Too much inertia. And that inertia isn't just a vague mass... it's everything you do now, browsers, video games, everything. It's going to be gradual. No, it is gradual, since it's actually happening now. From that perspective it's not a surprise that GPGPUs are still "mostly von Neumann", and are the first things out of the gate that have become wildly popular. I think it also demonstrates my "familiarity breeds contempt" point fairly well. I remember around the time the PS3 came out, there was a convergence between the Cell hype and what-became-CUDA hype, and I recall a small legion of fanboys running around claiming that in five or ten years, GPUs or Cells would be the dominant form of processor. Which ignores the fact that von Neumann is not all disadvantage; if all we had were non-von-Neumann processors, von Neumann processors would be hailed as a breakthrough when somebody invented them, because wow, look at these workloads they just tear through compared to the competition! Even heavy-duty FP programmers will dip into true imperative programming on certain data sets without shame, using the FP system to confine the side effects but freely using them within that confine. We'll get there. But it'll take time. And as always, initial naive ideas and wild promises will give way to surprising practical problems and performance that wasn't quite as good as we hoped, but may still be advantageous for certain problems. I... think we're vehemently agreeing? On the plus side, once these architectures get proofed, if they're in conventional silicon they'll have very swift access to the very-small-number-of nanometers chip fabrication processes.
- yosefk 10y ago
  I don't think it's inertia. I think RAM is fundamentally very useful, and that's why it's not going away. You want to store data somewhere if you access it more than once, it has to be a large array of cells if it's a lot of data, and accessing data in the array by address seems to me more useful than accessing it by something else (such as by key/content.) Similarly, a file of registers addressable by number is very useful, etc. I don't mind new and original ideas - let's hear new and original ideas, if someone invents a non-round wheel that's better than a round one, great! I do mind a general assumption that wheels are round due to inertia without explaining what if not round wheels we're gonna use once we're past inertia.
SilasX 10y ago
Yeah, I kind of get the impression that all these alternatives are about how to structure programs at a high level; none of them seem to avoid the need to translate it to run on hardware with a von Neumann architecture, nor remove any of the related frictions, nor identify a superior hardware architecture that would avoid the problems.
bogomipz 10y ago
"The thing most far away from a von Neumann machine that is commercially significant is the FPGA and it is nothing like what people deriding the von Neumann machines have in mind." Are you referring to Rudeceron architecture FPGAs here?

by yosefk 10y ago

DigitalJack 10y ago

I have to ask, what makes you say this: "and it will cause nausea in the typical functional programming supremacist" with regard to FPGAs?

_yosefk 10y ago
Not only are FPGAs as far from the ideal of "computation as reduction" expressed in the paper as they could possibly be, but they're the hardest machine to fit into this sort of a paradigm. The typical CPU will run functional code fairly efficiently if enough work is put into the compiler (to some functional programmers this sounds bad because hardware should make writing functional language compilers easy. People who know about hardware make a different conclusion - that hardware is just fine, as Ken Thompson said, "the PDP-11 is a fine Lisp machine, it's not a language special enough to warrant a specialized machine.") The typical accelerator is a harder target to a general-purpose functional programming language (it's a poor target for a general-purpose imperative language to begin with.) The FPGA, with its explicit management of every imaginable resource, is the worst target for a general-purpose functional programming language. In general, the farther away a commercially significant machine is from the classical von Neumann architecture, the more terrible target it is for functional languages, which never prevented FP aficionados from talking about "the end of Moore's law bringing about the long-awaited demise of the von Neumann machine", a "demise" that largely doesn't happen and where it does, it does not mean what they think it means.
- nickpsecurity 10y ago
  What about PLA or PAL? Such tech seems closer to functional programming than FPGA's.
- catnaroek 10y ago
  > to some functional programmers this sounds bad because hardware should make writing functional language compilers easy. People who know about hardware make a different conclusion - that hardware is just fine, as Ken Thompson said, "the PDP-11 is a fine Lisp machine, it's not a language special enough to warrant a specialized machine." Wow, really? C got a lot of things wrong, but the one thing that it got right is its abstract model of the machine. As a functional programmer, rather than specialized hardware, what I want is functional languages designed to target the abstract C machine. (Though maybe I am in a minority.) > The FPGA, with its explicit management of every imaginable resource, is the worst target for a general-purpose functional programming language. Explicit resource management is compatible with functional programming, but it requires a type system capable of undestanding the ephemeral nature of resources, à la Rust.
- chillingeffect 10y ago
  > The FPGA, with its explicit management of every imaginable resource, is the worst target for a general-purpose functional programming language. That's a great way to put it... but perhaps there's a more suitable FPGA cell for functional programming (than block lookup tables with state)? Maybe something with a local stack, recursion assistance, an iterator? Also, a good deal of the FPGA resource management is focused on optimization... What if the optimization-at-all-costs constraint were relaxed somewhat, or supplanted with meta-information to indicate the completion of a group of cells to allow a message to propagate? With relaxed constraints partial, on-the-fly and self- modifications could become regular features.
  - adwn 10y ago
    > Maybe something with a local stack, recursion assistance, an iterator? [...] supplanted with meta-information to indicate the completion of a group of cells to allow a message to propagate? What you're describing sounds a lot more like many CPU cores connected by a network than like an FPGA. The point of an FPGA is that it gives you very precise and flexible control over things like timing and interconnects. Without that, FPGAs are actually pretty slow and you'd better use a CPU. > With relaxed constraints partial, on-the-fly and self- modifications could become regular features. There's a reason why self-modifying software is restricted to niche use cases: it's hard to reason about. Dynamic partial reconfiguration is slowly becoming a thing in FPGA design, but it's typically used to work around resource limitations.
adwn 10y ago
To put it simple, FPGA design (as practiced in nearly 100% of commercial use cases, i.e. with VHDL or Verilog) is iterative programming on steroids – even a sequence of actions requires an explicit mutable state variable. If you need to access external memory (e.g., DDR3 RAM), you have to communicate with a memory controller module. So not only is there no garbage collection, there's not even a malloc! And no recursion. From time to time you'll read statements along the lines of "functional programming languages map really well to FPGA design", allegedly because the logic functions between register stages behave like declarative constructs. Such claims are excellent bullshit detectors, indicating that the person uttering them doesn't have the slightest clue what they're talking about. It's on par with believing that expressions like "a + b * c" make C a functional language.
- hderms 10y ago
  what are your opinions on http://www.clash-lang.org/ http://www.clash-lang.org/ ? It's different than what you describe because the language is explicitly aware of the fact its running on an FPGA. However, it's seemingly pretty declarative and functional and has an FPGA as a possible target.
  - _yosefk 10y ago
    First impression, could be misinformed, but I'll bite. Since a hardware circuit is a recursive function that takes a state of the hardware and produces a new state, starting from an initial state (and so is the universe where the initial state was supplied by the Big Bang), you can of course express it straightforwardly as a recursive function, which I think is what they sometimes do: blinkerT (leds,mode,cntr) key1R = ((leds',mode',cntr'),leds) where -- clock frequency = 50e6 (50 MHz) -- led update rate = 333e-3 (every 333ms) cnt_max = 16650000 -- 50e6 * 333e-3 cntr' | cntr == cnt_max = 0 | otherwise = cntr + 1 mode' | key1R = not mode | otherwise = mode leds' | cntr == 0 = if mode then complement leds else rotateL leds 1 | otherwise = leds This is VHDL/Verilog spelled in Haskell (real hardware description languages will not make you spell the old state - leds,mode... - and the new state - leds',mode'... explicitly, which gets annoying for 20 state variables. Of course this could be taken care of by a preprocessor or a macro system, my point isn't that it's verbose but that it's VHDL spelled in Haskell, a bit awkwardly and maybe you can do it less awkwardly but the programming model is the same so calling it Haskell is cheating, kinda.) This is definitely not what TFA is about - you don't represent the blinking leds as graph reduction, rather, you generate VHDL from VHDL-like Haskell. This is not to say they aren't doing cool things in this project. If indeed they compile this: fir coeffs x = dotp coeffs (window x) where dotp as bs = sum (zipWith (*) as bs) ...to efficient hardware description code, that's really cool. In general, I think that a sufficiently restricted functional language can compile very nicely to FPGA/hardware (and to DSPs and GPUs etc. etc.) I'm just saying that a general-purpose functional language is better targeted at a CPU, and that a functional language targeting something else is a DSL of sorts.

stcredzero 10y ago

GPUs are much closer to von Neumann machines than to anything people typically deriding the latter have in mind The GPU architecture was developed to enable the application of many von Neumann machines to a particular type of "mildly embarrassing" parallelism. I'm not so sure that we couldn't greatly benefit from going a little further in this direction. Right now, I see a mainstream architecture that does fairly well with read parallelism, with a need for more efficient two-way communication between separate threads. What if we had better hardware support for the things we're trying to do with with the Disruptor that came out of HFT? This would also benefit multiplayer games.

jerf 10y ago

I'm taking the general case of the question, admittedly. I think a lot of the von Neumann detractors think that there's going to be this revolution, where one day they'll wake up and omigosh, stream processors have suddenly taken over the market (or whatever your favorite non-von-Neumann architecture is) and That was the Day that Everything Changed. That's not how it's going to be. It can't be. Too much inertia. And that inertia isn't just a vague mass... it's everything you do now, browsers, video games, everything. It's going to be gradual. No, it is gradual, since it's actually happening now. From that perspective it's not a surprise that GPGPUs are still "mostly von Neumann", and are the first things out of the gate that have become wildly popular. I think it also demonstrates my "familiarity breeds contempt" point fairly well. I remember around the time the PS3 came out, there was a convergence between the Cell hype and what-became-CUDA hype, and I recall a small legion of fanboys running around claiming that in five or ten years, GPUs or Cells would be the dominant form of processor. Which ignores the fact that von Neumann is not all disadvantage; if all we had were non-von-Neumann processors, von Neumann processors would be hailed as a breakthrough when somebody invented them, because wow, look at these workloads they just tear through compared to the competition! Even heavy-duty FP programmers will dip into true imperative programming on certain data sets without shame, using the FP system to confine the side effects but freely using them within that confine. We'll get there. But it'll take time. And as always, initial naive ideas and wild promises will give way to surprising practical problems and performance that wasn't quite as good as we hoped, but may still be advantageous for certain problems. I... think we're vehemently agreeing? On the plus side, once these architectures get proofed, if they're in conventional silicon they'll have very swift access to the very-small-number-of nanometers chip fabrication processes.

yosefk 10y ago
I don't think it's inertia. I think RAM is fundamentally very useful, and that's why it's not going away. You want to store data somewhere if you access it more than once, it has to be a large array of cells if it's a lot of data, and accessing data in the array by address seems to me more useful than accessing it by something else (such as by key/content.) Similarly, a file of registers addressable by number is very useful, etc. I don't mind new and original ideas - let's hear new and original ideas, if someone invents a non-round wheel that's better than a round one, great! I do mind a general assumption that wheels are round due to inertia without explaining what if not round wheels we're gonna use once we're past inertia.

SilasX 10y ago

Yeah, I kind of get the impression that all these alternatives are about how to structure programs at a high level; none of them seem to avoid the need to translate it to run on hardware with a von Neumann architecture, nor remove any of the related frictions, nor identify a superior hardware architecture that would avoid the problems.

bogomipz 10y ago

"The thing most far away from a von Neumann machine that is commercially significant is the FPGA and it is nothing like what people deriding the von Neumann machines have in mind." Are you referring to Rudeceron architecture FPGAs here?