3 ms·
Or maybe, the problem isn't as hard as you think it is. Look, I started programming in GPUs a year or two ago. I've begun to "think in parallel", and now I'm b
by dragontamer 5y ago
Or maybe, the problem isn't as hard as you think it is.
Look, I started programming in GPUs a year or two ago. I've begun to "think in parallel", and now I'm beginning to see all sorts of efficient patterns all over the place.
The actual CPU-architects have known about kogge-stone carry-lookahead longer than I have. I'm still a newbie to this mindset of parallel computations... but I enjoy reading the papers on PDEP / PEXT / other parallel structures these CPU designers are doing (and these structures have gross implications to how GPU code should be structured).
But I've had enough practice with Kogge-stone / Carry-lookahead / Prefix-sum / scan pattern (yeah, its __all__ the same parallelism), and this pattern has been well published since the 1970s. I have to assume that engineers know about this stuff.
Instruction length decoding is very clearly a kogge-stone pattern / prefix sum / scan problem to me. Now, I'm not a chip architect and maybe there's some weird fanout / chip level thing going on that my ignorance is keeping me out of... but... based on my understanding of parallel systems + very, very common patterns well known to that community, I'd expect that chip-designers would just Kogge-stone their way out of this decoding problem.
-------
Like, I'm coming in from the reverse here. I suddenly realized that chip-designers have incredibly active minds about the layout and structure of parallel computing mechanisms, and have now taken an interest in studying some CPU-level parallelism techniques to apply to my GPU code.
The CPU-designers are way ahead of us in "parallel thinking". I'm a visitor to their subject, they do this stuff for breakfast every day. They have to see the Kogge-stone solution to the decoding problem. If not, they've thought of something better.
- dragontamer 5y agoFreaking downvotes. What ever happened to actually discussing the technicals here on Hacker News? I'll help ya out. Kogge-Stone is the paper from March 1972 that states that ANY recurrence relation "x_i = f(b_i, g(a_i, x_i-1))" can be parallelized, as long as f and g satisfy distributive and associative-like properties, "executing in time proportional to log2(n)" (aka: O(log2(n)), but this paper was probably before O-notation was popular). The if the Kogge-Stone algorithm is executed sequentially, time is proportional to n. https://ntrl.ntis.gov/NTRL/dashboard/searchResults/titleDetail/PB212080.xhtml https://ntrl.ntis.gov/NTRL/dashboard/searchResults/titleDeta... As you can see, Kogge-Stone can efficiently parallelize (aka: execute O(log2(N)) depth, O(N) total-work) a wide variety of recurrence relationships that initially seem sequential. ----------- GPU programmers know this pattern as prefix-sum. In CPU-architecture books, its called Kogge-Stone. ---------- Maybe this will help? Lets say "1" is "this byte is a start-of-instruction" and "0" is "this is not the start-of-instruction". For example: "1 0 0 1 0 1 1 0" would contain instructions at i_0, i_3, i_5, and i_6. Now prefix_sum(1 0 0 1 0 1 1 0) == (1, 1, 1, 2, 2, 3, 4, 4) f = 1 0 0 1 0 1 1 0 g = 1 1 1 2 2 3 4 4 idx = 0 1 2 3 4 5 6 7 So lets say we have 4-parallel decoders. Decoder #1 gets index 0, 1, 2. Decoder#2 gets byte 3 and 4. Decoder#3 gets byte 5, decoder #4 gets byte 6 and 7. See how that works? Just Kogge-Stone it up. ----------' I assert that "f" itself can also be computed using Kogge Stone, but maybe splitting it up like this is easier? Or will I also have to prove "f" for yall to see it?