4 ms·

I'm very interested in this space! I've been hacking on some open-source libraries around these ideas: rsdict [1], a SIMD-accelerated rank/select bitmap data st

I'm very interested in this space! I've been hacking on some open-source libraries around these ideas: rsdict [1], a SIMD-accelerated rank/select bitmap data structure, and arbolito [2], a SIMD-accelerated tiny trie. For rsdict, the main idea is to use `pshufb` to implement querying a lookup table on a vector of integers and then use `psadbw` to horizontally sum the vector. The arbolito code is a lot less fleshed out, but the main idea is to take a small trie and encode it into SIMD vectors. Laying out the nodes into a linear order, we'd have one vector that maintains a parent pointer (4 bits for 16 node trees in 128-bit vectors) and another vector with the incoming edge label. Then, following the Teddy algorithm[3] (very similar to the Hillis/Stele state transition ideas too!), we can implement traversing the tree as a state machine, where each node in the trie has a bitmask, and the state transition is a parallel bitshift + shuffle of parent state to children states + bitwise AND. We can even reduce the circuit depth of this algorithm to `O(log depth)` by using successive squaring of the transition, like Hillis/Steele describe too. I've put it on the backburner, but my main goal for arbolito would be to find a way to stitch together these "tiny tries" into a general purpose trie adaptively and get query performance competitive with a hashmap for integer keys. The ART paper[4] does similar stuff but without the SIMD tricks. [1] https://github.com/sujayakar/rsdict https://github.com/sujayakar/rsdict [2] https://github.com/sujayakar/arbolito https://github.com/sujayakar/arbolito [3] https://github.com/jneem/teddy#teddy-1 https://github.com/jneem/teddy#teddy-1 [4] https://db.in.tum.de/~leis/papers/ART.pdf https://db.in.tum.de/~leis/papers/ART.pdf

dragontamer 6y ago
Cool stuff! I'll give it a lookover later. A few years ago, I wrote AESRAND (https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand). I managed to get some well-known programmers to look into it, and their advice helped me write some pretty neat SIMD-tricks. EX: I SIMD-implemented a 32-bit integer -> floating point [0.0, 1.0] operator, to convert the bitstream into floats. As well as integer-based nearly bias-free division / modulus free conversion into [0, WhateverInt] (such as D20 rolls). For 16-bit, 32-bit, and 64-bit integers (with less bias the more bits you supplied). Unfortunately, I ran out of time and some work-related stuff came up. So I never really finished the experiments. ---------- My current home project is bump-allocator + semi-space garbage collection in SIMD for GPUs. As far as I can tell, both bump-allocation and semi-space garbage collection are easily SIMDified in an obvious manner. And since cudamalloc is fully synchronous, I wanted a more scalable, parallel solution to the GPU memory allocation problem.
- sujayakar 6y ago
  Very cool! Independent of the cool use of `aesenc` and `aesdec`, the features for skipping ahead in the random stream and forking a separate stream are awesome. > My current home project is bump-allocator + semi-space garbage collection in SIMD for GPUs. As far as I can tell, both bump-allocation and semi-space garbage collection are easily SIMDified in an obvious manner. And since cudamalloc is fully synchronous, I wanted a more scalable, parallel solution to the GPU memory allocation problem. This is a great idea. I wonder if we could speed up LuaJIT even more by SIMD accelerating the GC's mark and/or sweep phases... If you're interested in more work in this area, a former coworker wrote a neat SPMD implementation of librsync [1]. And, if you haven't seen it, the talk on SwissTable [2] (Google's SIMD accelerated hash table) is excellent. [1] https://github.com/dropbox/fast_rsync https://github.com/dropbox/fast_rsync [2] https://www.youtube.com/watch?v=ncHmEUmJZf4 https://www.youtube.com/watch?v=ncHmEUmJZf4
  - dragontamer 6y ago
    > Very cool! Independent of the cool use of `aesenc` and `aesdec`, the features for skipping ahead in the random stream and forking a separate stream are awesome. Ah yeah, those features... I forgot about them until you mentioned them, lol. I was thinking about 4x (512-bits per iteration) with enc(enc), enc(dec), dec(enc), and dec(dec) as the four 128-bit results (going from 256-bits per iteration to 512-bits per iteration, with only 3-more instructions). I don't think I ever tested that... But honestly, the thing that really made me stop playing with AESRAND was discovering multiply-bitreverse-multiply random number generators (still unpublished... just sitting in a directory in my home computer). Bit-reverse is single-cycle on GPUs (NVidia and AMD), and perfectly fixes the "multiplication only randomizes the top bits" problem. Bit-reverse is unimplemented on x86 for some reason, but bswap64() is good enough. Since bswap64() and multiply64-bit are both implemented really fast on x86-64-bit, a multiply-bswap64-multiply generator probably is fastest for typical x86 code (since there are penalties for going between x86 64-bit registers and AVX 256-bit registers). --------- The key is that multiplying by an odd number (bottom-bit == 1) results in a fully invertible (aka: no information loss) operation. So multiply-bitreverse-multiply is a 1-to-1 bijection in the 64-bit integer space: all 64-bit integers have a singular, UNIQUE multiply-bitreverse-multiply analog. (with multiply-bitreverse-multiply(0) == 0 being the one edge case where things don't really workout. An XOR or ADD instruction might fix that problem...). --------- > This is a great idea. I wonder if we could speed up LuaJIT even more by SIMD accelerating the GC's mark and/or sweep phases... Mark and Sweep looks hard to SIMD-accelerate in my opinion. At least, harder than a bump-allocator. I'm not entirely sure how a SIMD-accelerated traversal of the heap is even supposed to look like (aka: simd-malloc() looks pretty hard). If all allocs are prefix-sum'd across the SIMD-units (ex: malloc ({1, 4, 5, 1, 2, 3, 20, 10}) == return (memory + {0, 1, 5, 10, 11, 13, 14, 34, 44})... for a bump-allocator like strategy... its clear to me that such a mark/sweep allocator would have fragmentation issues. But I guess it would work... Semispace collectors innately fix the fragmentation problem. So prefix-sum(size+header) allocators are just simple and obvious. -------- On the "free" side of Mark/sweep... I think the Mark-and-sweep itself can be implemented in GPU-SIMD thanks to easy gather/scatter on GPUs. However, because gather/scatter is missing (scatter is missing from AVX2), or slow (AVX512 doesn't seem to implement a very efficient vgather or vscatter), I'm not sure if SIMD on CPU-based Mark/Sweep would be a big advantage. ------------ Yup yup. Semispace GC or bust, IMO anyway for the SIMD-world. Maybe mark-compact (since mark-compact would also fix the fragmentation issue). The mark-phase is just breadth-first-search, which seems like a doable SIMD-pattern with the right data-structure (breadth-first is easier to parallelize than depth-first)

dragontamer 6y ago

Cool stuff! I'll give it a lookover later. A few years ago, I wrote AESRAND (https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand). I managed to get some well-known programmers to look into it, and their advice helped me write some pretty neat SIMD-tricks. EX: I SIMD-implemented a 32-bit integer -> floating point [0.0, 1.0] operator, to convert the bitstream into floats. As well as integer-based nearly bias-free division / modulus free conversion into [0, WhateverInt] (such as D20 rolls). For 16-bit, 32-bit, and 64-bit integers (with less bias the more bits you supplied). Unfortunately, I ran out of time and some work-related stuff came up. So I never really finished the experiments. ---------- My current home project is bump-allocator + semi-space garbage collection in SIMD for GPUs. As far as I can tell, both bump-allocation and semi-space garbage collection are easily SIMDified in an obvious manner. And since cudamalloc is fully synchronous, I wanted a more scalable, parallel solution to the GPU memory allocation problem.

sujayakar 6y ago
Very cool! Independent of the cool use of `aesenc` and `aesdec`, the features for skipping ahead in the random stream and forking a separate stream are awesome. > My current home project is bump-allocator + semi-space garbage collection in SIMD for GPUs. As far as I can tell, both bump-allocation and semi-space garbage collection are easily SIMDified in an obvious manner. And since cudamalloc is fully synchronous, I wanted a more scalable, parallel solution to the GPU memory allocation problem. This is a great idea. I wonder if we could speed up LuaJIT even more by SIMD accelerating the GC's mark and/or sweep phases... If you're interested in more work in this area, a former coworker wrote a neat SPMD implementation of librsync [1]. And, if you haven't seen it, the talk on SwissTable [2] (Google's SIMD accelerated hash table) is excellent. [1] https://github.com/dropbox/fast_rsync https://github.com/dropbox/fast_rsync [2] https://www.youtube.com/watch?v=ncHmEUmJZf4 https://www.youtube.com/watch?v=ncHmEUmJZf4
- dragontamer 6y ago
  > Very cool! Independent of the cool use of `aesenc` and `aesdec`, the features for skipping ahead in the random stream and forking a separate stream are awesome. Ah yeah, those features... I forgot about them until you mentioned them, lol. I was thinking about 4x (512-bits per iteration) with enc(enc), enc(dec), dec(enc), and dec(dec) as the four 128-bit results (going from 256-bits per iteration to 512-bits per iteration, with only 3-more instructions). I don't think I ever tested that... But honestly, the thing that really made me stop playing with AESRAND was discovering multiply-bitreverse-multiply random number generators (still unpublished... just sitting in a directory in my home computer). Bit-reverse is single-cycle on GPUs (NVidia and AMD), and perfectly fixes the "multiplication only randomizes the top bits" problem. Bit-reverse is unimplemented on x86 for some reason, but bswap64() is good enough. Since bswap64() and multiply64-bit are both implemented really fast on x86-64-bit, a multiply-bswap64-multiply generator probably is fastest for typical x86 code (since there are penalties for going between x86 64-bit registers and AVX 256-bit registers). --------- The key is that multiplying by an odd number (bottom-bit == 1) results in a fully invertible (aka: no information loss) operation. So multiply-bitreverse-multiply is a 1-to-1 bijection in the 64-bit integer space: all 64-bit integers have a singular, UNIQUE multiply-bitreverse-multiply analog. (with multiply-bitreverse-multiply(0) == 0 being the one edge case where things don't really workout. An XOR or ADD instruction might fix that problem...). --------- > This is a great idea. I wonder if we could speed up LuaJIT even more by SIMD accelerating the GC's mark and/or sweep phases... Mark and Sweep looks hard to SIMD-accelerate in my opinion. At least, harder than a bump-allocator. I'm not entirely sure how a SIMD-accelerated traversal of the heap is even supposed to look like (aka: simd-malloc() looks pretty hard). If all allocs are prefix-sum'd across the SIMD-units (ex: malloc ({1, 4, 5, 1, 2, 3, 20, 10}) == return (memory + {0, 1, 5, 10, 11, 13, 14, 34, 44})... for a bump-allocator like strategy... its clear to me that such a mark/sweep allocator would have fragmentation issues. But I guess it would work... Semispace collectors innately fix the fragmentation problem. So prefix-sum(size+header) allocators are just simple and obvious. -------- On the "free" side of Mark/sweep... I think the Mark-and-sweep itself can be implemented in GPU-SIMD thanks to easy gather/scatter on GPUs. However, because gather/scatter is missing (scatter is missing from AVX2), or slow (AVX512 doesn't seem to implement a very efficient vgather or vscatter), I'm not sure if SIMD on CPU-based Mark/Sweep would be a big advantage. ------------ Yup yup. Semispace GC or bust, IMO anyway for the SIMD-world. Maybe mark-compact (since mark-compact would also fix the fragmentation issue). The mark-phase is just breadth-first-search, which seems like a doable SIMD-pattern with the right data-structure (breadth-first is easier to parallelize than depth-first)