Much Ado about Two: A Pearl on Parallel Prefix Computation
The paper is available via the ACM DL Author-ize feature:
| Author: | J. Voigtländer |
|---|---|
| Published: | In 35th Symposium on Principles of Programming Languages (POPL'08, acceptance rate 35/212), San Francisco, California, Proceedings, volume 43(1) of SIGPLAN Notices, pages 29-35, ACM, January 2008. |
| DOI: | 10.1145/1328897.1328445 |
| BibTeX: | Voi08b.bib |
| Abstract: | This pearl develops a statement about parallel prefix computation in the spirit of Knuth's 0-1-Principle for oblivious sorting algorithms. It turns out that 0-1 is not quite enough here. The perfect hammer for the nails we are going to drive in is relational parametricity. |
| Download: | http://dl.acm.org/authorize?937632 (free) |
| Slides: | Slides of my talk at the conference are here. |