[HN Gopher] Efficient parallelization of an ubiquitous sequentia...
___________________________________________________________________
Efficient parallelization of an ubiquitous sequential computation
Author : cs702
Score : 58 points
Date : 2023-12-07 14:26 UTC (8 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| _aavaa_ wrote:
| Interesting. They don't explicitly state it, but it looks like
| the restrictions of a_t and b_t is that while they may vary in
| time, they must have a closed form solution which is independent
| of x.
| cs702 wrote:
| Too early to tell, but this looks like it could both simplify
| implementation and speed-up execution of linear RNNs like RWKV,
| Mamba, retnet, etc.
| jimsimmons wrote:
| They already use closed form summations. That's their whole
| point
| cs702 wrote:
| Yes, but this uses only _two_ plan-vanilla parallel scans,
| shown as a* and b* in the pdf.
|
| In the sample code, that's two calls to PyTorch's built-in
| API.
|
| That looks _very_ efficient to me, almost like it shouldn 't
| be possible. But I tested the sample code[a] and it works.
|
| Not an expert on this, but I don't think I've ever seen
| _that_ before. Have you?
|
| [a] https://github.com/glassroom/heinsen_sequence
| geysersam wrote:
| Unfortunately it doesn't work for matrix valued coefficients.
| Unless I am mistaken?
| namibj wrote:
| The math works (I think, don't really see why it shouldn't);
| the intermediate of the scan is matrix-valued, though.
| geysersam wrote:
| Sure the math works but it's not efficient. Matrix matrix
| multiplication instead of matrix vector multiplication.. and
| then throw an matrix exponential in the mix for good measure.
| randomizedalgs wrote:
| As a super minor grammar point for the author, "ubiquitous" is a
| rare example of a word that starts with a vowel but should be
| proceeded by "a" instead of "an".
| jjtheblunt wrote:
| I think that's got to be a great test for foreign spies!
|
| "ubiquitous" starts with the sound of "you-biquitous" and so
| the suffix -n is a duplicated non-vowel. ("y" is probably a
| vocalic glide, but still not in {a,e,i,o,u}.)
|
| I bet the real rule is some reality about feasibility of
| pronunciation, even though native english speakers see the
| rules explained in terms of spellings.
| loxias wrote:
| > I bet the real rule is some reality about feasibility of
| pronunciation
|
| YUP! Sorry I don't have a good citation handy, but lots of
| English grammar happens as a result of misaligned word
| boundaries. "napron" (from the French naperon) became "an
| apron". Orange (from the Arabic naranj)... "an ewt" became "a
| newt". etc.
| JoshTriplett wrote:
| > I bet the real rule is some reality about feasibility of
| pronunciation, even though native english speakers see the
| rules explained in terms of spellings.
|
| The rule as often given in English classes is to use "an" if
| a word starts with a "vowel _sound_ ", rather than starting
| with a vowel. So, it's "an herb" (since the 'h' is silent in
| (American) English), but "a ubiquitous".
|
| Relatedly, you can infer whether someone likely pronounces
| "URL" by spelling it out (like "you are ell") or as a word
| (like "earl") based on whether they write "a URL" or "an
| URL".
| ithkuil wrote:
| A union
|
| A urinal
|
| ...
| bee_rider wrote:
| It seems like they must require (or maybe I missed something)
| that none of their a's are zero (I guess this would be easy to
| check and avoid). It seem like it would be harder to know
| beforehand that none of the it b*'s are equal to -x_0 and none of
| their b's are equal to the corresponding a*. But maybe this is
| just unlikely enough to not care about.
| leecarraher wrote:
| I wish there were more explanation for why this work. There is a
| proof but a more opinionated description would also help. My
| summary of it is that parallel prefix sum is work efficient for
| computing general recurrences of the form xi = x_i-1 + yi.
| Furthermore, a product of elements can be expressed as a sum by
| taking the sum of the log of elements and exponentiated the
| result. These are two super useful properties, but merging the
| two operations to this general formulation is not clear. Is it
| simply sum the logs, and the addends via prefix sums, and then
| sum those two results? That seems pretty straightforward, so I
| suspect I am missing something that makes the solution less
| obvious and more complexity. Is there some fancy fixed point
| combinator, or solution to a differential equation of the linear
| system for the recurrence equation?
| shwestrick wrote:
| It's worth noting that you can solve these linear recurrences,
| `x(t) = a(t)x(t-1) + b(t)`, using a single parallel prefix sum
| where the elements are the input tuples `(a(t), b(t))`.
|
| The following operator called `combine` works. It's associative
| over these tuples; the final result will be the final value of
| the second component. Altogether, this gives you O(n) work and
| O(log n) span, but using just a single parallel prefix kernel,
| which may be more efficient in practice.
| combine ((a1, b1), (a2, b2)) = (a1 * a2, b1 * a2 + b2)
|
| For example, here's a C++ implementation:
| https://github.com/MPLLang/parallel-ml-bench/blob/main/cpp/l...
| And, here's an implementation in a functional language:
| https://github.com/MPLLang/parallel-ml-bench/blob/main/mpl/b...
|
| I'm pretty sure this generalizes, too, to abstract
| multiplications and additions in any field (at first glance,
| seems like it should but I haven't done the formal proof yet).
|
| Anyway, it would be interesting to compare this against the
| solution in the arxiv paper.
|
| ----
|
| EDIT: ah, good, this is already being discussed here:
| https://github.com/glassroom/heinsen_sequence/issues/1
|
| And, for reference, I learned this algorithm from Guy Blelloch;
| see Sec 1.4.1 of https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf
| cs702 wrote:
| Yes! That's pretty much how I would have thought about this
| with my puny little brain.
|
| But... I'm not sure 1 parallel scan with 2 floating-point mults
| and 1 sum per step is faster than 2 parallel scans with 1 sum
| per step. I don't know which is better in theory or in
| practice. And then, wouldn't we have to think about how to
| sidestep all the numerical issues with the cumulative products?
|
| Or am I missing something?
| leiroigh wrote:
| This is very very well known. Cf
| https://en.wikipedia.org/wiki/Affine_group
|
| I don't see how people should glorify this with the word
| "algorithm". It is a trivial undergrad homework exercise, once
| you give the hint "use parallel reduce / fold / prefixsum".
|
| This may involve more interesting tradeoffs if you deal with
| large or sparse matrices or matrix-free operators.
| dang wrote:
| If you know more than others do, that's great, but instead of
| posting putdowns, please share some of what you know so the
| rest of us can learn.
|
| The trouble with comments like this is that they degrade
| discussion put others down without really teaching us
| anything.
|
| https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor.
| ..
|
| https://news.ycombinator.com/newsguidelines.html
| nalzok wrote:
| Is this equivalent to treating the linear recurrence as a
| convolution and computing it with a Fourier transform? See
| https://www.youtube.com/watch?v=OpJMn8T7Z34&t=840s
| rkp8000 wrote:
| I had the same thought. If a were constant I believe the
| solution would just be a convolution of b_t with an exponential
| filter. I think this is different because a_t depends on time,
| so it's equivalent to convolving b_t with a filter whose
| timescale changes at every timestep, which doesn't seem like
| something that's obviously parallelizable with FT.
___________________________________________________________________
(page generated 2023-12-07 23:00 UTC)