3 ms·
Freaking 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 th
by dragontamer 5y ago
Freaking 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?