My first thought when seeing this stack problem was that it might be possible to use the techniques presented in "Internally Deterministic Parallel Algorithms C

My first thought when seeing this stack problem was that it might be possible to use the techniques presented in "Internally Deterministic Parallel Algorithms Can Be Fast"[1]. The idea is that the algorithm runs on the prefix of the input in two steps: In the first step it will figure out which items can be processed in parallel (e.g. those that don't depend on any earlier input) and in the second step it will actually calculate it. Both steps are done in parallel. There's also a slide deck[2] which explains it quite well. I'm not quite sure how it would work on this problem, but it might be interesting to look into. [1]: https://www.cs.cmu.edu/~guyb/papers/BFGS12.pdf https://www.cs.cmu.edu/~guyb/papers/BFGS12.pdf [2]: http://www.cs.cmu.edu/~blelloch/papers/spaapodc17.pdf http://www.cs.cmu.edu/~blelloch/papers/spaapodc17.pdf