Results 1 to 1 of 1

Thread: New ASPLOS paper on SIMD FSM's and Huffman decoding

  1. #1
    Member
    Join Date
    Oct 2013
    Location
    Filling a much-needed gap in the literature
    Posts
    350
    Thanks
    177
    Thanked 49 Times in 35 Posts

    New ASPLOS paper on SIMD FSM's and Huffman decoding

    It's "Data Parallel Finite-State Machines" by Mytkowicz, Musavathi, and Schulte

    https://research.microsoft.com/pubs/...-mytkowicz.pdf

    They argue that lots of (most?) FSM's are amenable to substantial (but not huge) speedup with SIMD processing, due to convergences in the state transition network limiting the amount of wasted speculative execution you have to do.

    One of their examples is tokenizing HTML, for which they get a speedup of 2.3.

    They also compare an optimized non-SIMD Huffman decode with a SIMD one, getting single-core speedups of about 2---from 300+ MB/sec to 600+ MB/sec on a Intel 2.67GHz Xeon (X5650). (16x bytes SIMD.)

    I'm not qualified to evaluate this paper, but I thought it looked interesting in terms of both scanning strings and encoding.

  2. Thanks (2):

    Bulat Ziganshin (5th April 2017),thorfdbg (24th April 2014)

Similar Threads

  1. Does someone has access to IEEE? Looking for a paper.
    By Sebastian in forum Data Compression
    Replies: 2
    Last Post: 23rd January 2012, 09:12
  2. BWTS paper
    By willvarfar in forum Data Compression
    Replies: 2
    Last Post: 19th January 2012, 13:06
  3. A paper on GPGPU Huffman
    By m^2 in forum Data Compression
    Replies: 3
    Last Post: 15th July 2011, 02:02
  4. BWTS STATUS OF PAPER
    By biject.bwts in forum Data Compression
    Replies: 20
    Last Post: 4th September 2009, 21:10
  5. Original paper on LZMW
    By encode in forum Forum Archive
    Replies: 3
    Last Post: 9th February 2008, 13:34

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •