2 ms·
Are you sure about that? The original SIMD-papers in the 1980s show how to compile a Regex into a highly-parallel state machine and then "reduced" (aka: Scan /
by dragontamer 6y ago
Are you sure about that?
The original SIMD-papers in the 1980s show how to compile a Regex into a highly-parallel state machine and then "reduced" (aka: Scan / Prefix-operation: https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum).
A huge amount of operations, such as XML-whitespace removal (aka: SIMD Steam Compacting), Regular Expressions, and more, have been proven ~30 to 40 years ago to benefit from SIMD compute. Yet such libraries don't exist today yet.
SIMD compute is highly niche, and clearly today's population is overly focused on deep-learning... without even seeing the easy opportunities of XML parsing or simple regex yet. Further: additional opportunities are being discovered in O(n^2) operations: such as inner-join operations on your typical database.
Citations.
* For Regular Expressions: Read the 1986 paper "DATA PARALLEL ALGORITHMS". Its an easy read. Hillis / Steele are great writers. They even have the "impossible Linked List" parallelism figured out in there (granted: the nodes are located in such a way that the SIMD-computer can work with the nodes. But... if you had a memory-allocator that worked with their linked-list format, you could very well implement their pointer-jumping approach to SIMD-linked list traversal)
* For whitespace folding / removal, see http://www.cse.chalmers.se/~uffe/streamcompaction.pdf http://www.cse.chalmers.se/~uffe/streamcompaction.pdf. They don't cite it as XML-whitespace removal, but it seems pretty obvious to me that it could be used for parallel whitespace removal in O(lg(n)) steps.
* Database SIMD: http://www.cs.columbia.edu/~kar/pubsk/simd.pdf http://www.cs.columbia.edu/~kar/pubsk/simd.pdf . Various operations have been proven to be better on SIMD, including "mass binary search" (one binary search cannot be parallelized. But if you have 5000-binary searches operating in parallel, its HIGHLY efficient to execute all 5000 in a weird parallel manner, far faster than you might originally imagine).
----------
SIMD-cuckoo hashing, SIMD-skip lists, etc. etc. There's so many data-structures that haven't really been fleshed out on SIMD yet outside of research settings. They have been proven easy to implement and simple / clean to understand. They're just not widely known yet.
- my123 6y agohttps://github.com/simdjson/simdjson https://github.com/simdjson/simdjson as an example that fits in the "outside-of-a-conventional-SIMD-workload" mold.
- skybrian 6y agoIt seems like there are a wide variety of ways to serialize and deserialize data, their performance sometimes varies by orders of magnitude, and the slow code persists because it doesn’t matter enough to optimize compared to other virtues like convenience and maintainability. The key seems to be figuring out how to get good (not the best) performance when you mostly care about other things? Machine learning itself seems like an example of throwing hardware at problems to try to improve the state of the art, to the point where it becomes so expensive that they have to think about performance more.
- dragontamer 6y agoSIMD-compute is a totally different model of compute than what most programmers are familiar with. That's the biggest problem. If you write optimal SIMD-code, no one else in your team will understand it. Since we have so much compute these days (to the point where O(n^2) scanf parsers are all over the place), its become increasingly obvious that few modern programmers care about performance at all. Nonetheless, the more and more I study SIMD-compute, the more I realize that these expert programmers have figured out a ton of good and fast solutions to a wide-variety of problems... decades ago and then somehow forgotten until recently. Seriously: that Data Parallel Algorithms paper is just WTF to me. Linked list traversal (scan-reduced sum from a linked list in SIMD-parallel), Regular Expressions and more. -------- Then I look at the GPU-graphics guys, and they're doing like BVH tree traversal in parallel so that their raytracers work. Its like "Yeah, Raytracing is clearly a parallel operation cause GPUs can do it". So I look it up and wtf? Its not easy. Someone really thought things through. Its non-obvious how they managed to get a recursive / sequential operation to operate in highly parallel SIMD operations while avoiding branch divergence issues. Really: think about it: Raytracing is effectively: If(ray hit object) recursively bounce ray. How the hell did they make that parallel? A combination of stream-compaction and very intelligent data-structures, as well as a set of new SIMD-assembly instructions to cover some obscure cases. There's some really intelligent stuff going on in the SIMD-compute world, that clearly applies beyond just the machine-learning crowd.
- sujayakar 6y agoI'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 agoCool 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.
- lmm 6y ago> A huge amount of operations, such as XML-whitespace removal (aka: SIMD Steam Compacting), Regular Expressions, and more, have been proven ~30 to 40 years ago to benefit from SIMD compute. Yet such libraries don't exist today yet. That's exactly why I don't believe it's ever going to happen. If these things could actually be useful in practice, surely someone would have done it already.