SIMD Support in GHC

Implementation

SSE instruction support is now in GHC HEAD. It requires using the LLVM back end. Instructions for building GHC along with modified vector and DPH libraries that support SSE instructions are available on github.

Publications

2017

  1. Mainland, G., Leshchinskiy, R. and Peyton Jones, S. 2017. Exploiting Vector Instructions with Generalized Stream Fusion. Communications of the ACM. 60, 5 (Apr. 2017), 83–91. Abstract 
    DOI  PDF  BibTeX

    Ideally, a program written as a composition of concise, self-contained components should perform as well as the equivalent hand-written version where the functionality of what was many components has been manually combined into a monolithic implementation. That is, programmers should not have to sacrifice code clarity or good software engineering practices to obtain performance—we want compositionality without a performance penalty. This work shows how to attain this goal for high-level Haskell in the domain of sequence-processing functions, which includes applications such as array processing. Prior work on stream fusion shows how to automatically transform some high-level sequence-processing functions into efficient implementations. It has been used to great effect in Haskell libraries for manipulating byte arrays, Unicode text, and unboxed vectors. However some operations, like vector append, do not perform well within the stream fusion framework. Others, like SIMD computation using the SSE and AVX instructions available on modern x86 chips, do not seem to fit in the stream fusion framework at all. We describe generalized stream fusion, which solves these issues through a careful choice of stream representation. Benchmarks show that high-level Haskell code written using our compiler and libraries can produce code that is faster than both compiler- and hand-vectorized C.

    @article{mainland17exploiting,
      title = {Exploiting Vector Instructions with Generalized Stream Fusion},
      author = {Mainland, Geoffrey and Leshchinskiy, Roman and Peyton Jones, Simon},
      year = {2017},
      month = apr,
      journal = {Communications of the ACM},
      volume = {60},
      number = {5},
      pages = {83--91},
      issn = {0001-0782},
      doi = {10.1145/3060597}
    }
    

2013

  1. Mainland, G., Leshchinskiy, R. and Peyton Jones, S. 2013. Exploiting Vector Instructions with Generalized Stream Fusion. Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming (Boston, MA, Sep. 2013), 37–48. Abstract 
    DOI  PDF  BibTeX

    Stream fusion is a powerful technique for automatically transforming high-level sequence-processing functions into efficient implementations. It has been used to great effect in Haskell libraries for manipulating byte arrays, Unicode text, and unboxed vectors. However, some operations, like vector append, still do not perform well within the standard stream fusion framework. Others, like SIMD computation using the SSE and AVX instructions available on modern x86 chips, do not seem to fit in the framework at all. In this paper we introduce generalized stream fusion, which solves these issues. The key insight is to bundle together multiple stream representations, each tuned for a particular class of stream consumer. We also describe a stream representation suited for efficient computation with SSE instructions. Our ideas are implemented in modified versions of the GHC compiler and vector library. Benchmarks show that high-level Haskell code written using our compiler and libraries can produce code that is faster than both compiler- and hand-vectorized C.

    @inproceedings{mainland13exploiting,
      title = {Exploiting Vector Instructions with Generalized Stream Fusion},
      booktitle = {Proceedings of the 18th {{ACM SIGPLAN International Conference}} on {{Functional Programming}}},
      author = {Mainland, Geoffrey and Leshchinskiy, Roman and Peyton Jones, Simon},
      year = {2013},
      month = sep,
      pages = {37--48},
      address = {{Boston, MA}},
      doi = {10.1145/2500365.2500601},
      acceptrate = {30},
      citations = {36},
      isbn = {978-1-4503-2326-0}
    }