3 ms·

> It would be interesting to see any Haskell implementations that are competitive. I suspect that the very first thing you will do when trying to get performanc

by dons 15y ago

> It would be interesting to see any Haskell implementations that are competitive. I suspect that the very first thing you will do when trying to get performance is to ditch the functional paradigm and start writing code in an assembly-level monad. Or teach the compiler about the algebra of arrays and matrices, so it can do the things to the code, that we'd write by hand. E.g. * http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp2011-sub.pdf http://www.cse.unsw.edu.au/~benl/papers/stencil/stencil-icfp... * http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.pdf http://www.cse.unsw.edu.au/~benl/papers/repa/repa-icfp2010.p... * http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf http://www.cse.unsw.edu.au/~dons/papers/stream-fusion.pdf * http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf http://www.cse.unsw.edu.au/~chak/papers/acc-cuda.pdf In all these cases arrays codes are written in a function style, accompanied with special purpose optimizations and/or code generators (in the case of GPU code), layered over an imperative arrays primitive layer, using a memory effects monad.

jedbrown 15y ago
This is a worthwhile research topic, but it doesn't really answer my question. From the first paper you cite: The single threaded Handwritten C version is about 45% faster than our best Haskell result, which is achieved with 3 threads. Meanwhile, there is no performance model so we don't know how good the C version is. The paper doesn't even report a simple fraction of FPU or bandwidth peak. It is not using SSE instructions so it cannot possibly be better than 50% of FPU peak (the limit is actually lower because this kernel is/should be bandwidth limited). As for parallelism, I'll quote Bill Gropp [1] The easiest way to make software scalable is to make it sequentially inefficient. [1] http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&ots=TJCM7dzUgl&dq=gropp%20exploiting%20existing%20software%20in%20libraries&lr&pg=PA21#v=onepage&q=gropp%20exploiting%20existing%20software%20in%20libraries&f=false http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&#...
- dons 15y ago
  Oh, I'm certainly not arguing that you're going to beat hand tuned straightline code. I'm just pointing out that dropping into assembly isn't the only possibly path.
  - jedbrown 15y ago
    If you're not within 10% for these kernels, chances are that memory is being used differently. This gets to a further matter which I think is perhaps the greatest failure of current multi/many-core programming paradigms: assuming a flat memory model. Efficient parallel computation has much less to do with computation than with data movement. Recent and future architectures have deeply hierarchical memory systems so any paradigm that does not expose the location of physical pages (within some appropriate abstraction) will have a hard time delivering consistent, understandable performance. Performance should not vary an order of magnitude based on whether memory was faulted (allocation is irrelevant) using a batch of threads with different affinity than those that access it later. But this is the current state of affairs. I would very much like to see a paradigm where a memory distribution (roughly a high-level representation of the mapping to physical memory) was a first-class concept. Suppose that new memory could be allocated or remapped to have certain compatibility relative to the mapping of another block. Then you could associate tasks with certain coupling between two distributions.
    - rayiner 15y ago
      > If you're not within 10% for these kernels, chances are that memory is being used differently More likely imperfect strictness analysis, etc. Haskell is a pure functional lazy language, after all. Getting within 65% of C's performance on a tight numeric kernel is heroic.
      - jedbrown 15y ago
        Different strictness analysis results in using memory differently. Note that some of Don's references are embedding a DSL that gives a high-level interface to very low-level code (e.g. CUDA) specific to this problem. They should have control over strictness.

by dons 15y ago

jedbrown 15y ago

This is a worthwhile research topic, but it doesn't really answer my question. From the first paper you cite: The single threaded Handwritten C version is about 45% faster than our best Haskell result, which is achieved with 3 threads. Meanwhile, there is no performance model so we don't know how good the C version is. The paper doesn't even report a simple fraction of FPU or bandwidth peak. It is not using SSE instructions so it cannot possibly be better than 50% of FPU peak (the limit is actually lower because this kernel is/should be bandwidth limited). As for parallelism, I'll quote Bill Gropp [1] The easiest way to make software scalable is to make it sequentially inefficient. [1] http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&ots=TJCM7dzUgl&dq=gropp%20exploiting%20existing%20software%20in%20libraries&lr&pg=PA21#v=onepage&q=gropp%20exploiting%20existing%20software%20in%20libraries&f=false http://books.google.com/books?id=2Da5OcnjPSgC&lpg=PA21&#...

dons 15y ago
Oh, I'm certainly not arguing that you're going to beat hand tuned straightline code. I'm just pointing out that dropping into assembly isn't the only possibly path.
- jedbrown 15y ago
  If you're not within 10% for these kernels, chances are that memory is being used differently. This gets to a further matter which I think is perhaps the greatest failure of current multi/many-core programming paradigms: assuming a flat memory model. Efficient parallel computation has much less to do with computation than with data movement. Recent and future architectures have deeply hierarchical memory systems so any paradigm that does not expose the location of physical pages (within some appropriate abstraction) will have a hard time delivering consistent, understandable performance. Performance should not vary an order of magnitude based on whether memory was faulted (allocation is irrelevant) using a batch of threads with different affinity than those that access it later. But this is the current state of affairs. I would very much like to see a paradigm where a memory distribution (roughly a high-level representation of the mapping to physical memory) was a first-class concept. Suppose that new memory could be allocated or remapped to have certain compatibility relative to the mapping of another block. Then you could associate tasks with certain coupling between two distributions.
  - rayiner 15y ago
    > If you're not within 10% for these kernels, chances are that memory is being used differently More likely imperfect strictness analysis, etc. Haskell is a pure functional lazy language, after all. Getting within 65% of C's performance on a tight numeric kernel is heroic.
    - jedbrown 15y ago
      Different strictness analysis results in using memory differently. Note that some of Don's references are embedding a DSL that gives a high-level interface to very low-level code (e.g. CUDA) specific to this problem. They should have control over strictness.