4 ms·
CRCs are inherently non-parallelizable No. CRC is a bitwise linear function over XOR (+). Digesting a message ABCD, crc(ABCD), is simply the expression crc(c
by colanderman 12y ago
CRCs are inherently non-parallelizable
No.
CRC is a bitwise linear function over XOR (+). Digesting a message ABCD, crc(ABCD), is simply the expression crc(crc(crc(crc(A) + B) + C) + D). To parallelize, this can be rearranged (via distributivity of CRC of XOR) as crc(crc(crc(crc(A) + B))) + crc(crc(C) + D). This is simply the CRC of the second half, XORed with the CRC of the first half passed through the function crc(crc(_)) (crc^2), which is itself linear and can be precomputed just like CRC is.
This extends to arbitrary block sizes and/or arbitrary strides through the message. So e.g. you can have four threads compute the CRCs of separate 64-byte (cache-line-sized) blocks within 256-byte chunks, separating each block within a thread using crc^192, offset the results as appropriate with crc^64^k, and then combine them with XOR.
(Protip: these fun properties are exactly what make CRCs a TERRIBLE choice for cryptography!)
- seiji 12y agoyou can have four threads compute You could. You could also have a billion threads. But the article is talking about single-core instruction level parallelism where normal tricks like loop unrolling won't work.
- colanderman 12y agoRegardless of what the post is about, its lede is demonstrably incorrect. Speeding up CRC is great, but "we have to because we can't parallelize it" is a false reason. Anyway the tricks I outlined would probably help even on a single core, since it allows you to pipeline fetches to the CRC table. (If the table is sitting in L2 you've got ~10 cycles latency between successive CRCs. That's enough downtime to run a second CRC in parallel.)