The recursive scan-then-fan is described in the NVIDIA Technical Report NVR-2008-003 by Sengupta et al. A recursive reduce-then-scan formulation is described by Dotsenko et al. The two-pass reduce-then-scan algorithm is due to Merrill; his paper is extremely valuable reading, both for background and for an overview of negative results – for example, an attempted formulation of Scan modeled on Sklansky’s minimum-depth circuit whose performance was disappointing. The single-pass decoupled look-back algorithm, which underlies the scan primitives in CUB and Thrust, is described by Merrill and Garland in NVIDIA Technical Report NVR-2016-002.
Blelloch, Guy E. Prefix sums and their applications. Tech Rep. CMU-CS-90-190.
Dotsenko, Yuri, Naga K. Govindaraju, Peter-Pike Sloan, Charles Boyd, and John Manferdelli. Fast scan algorithms in graphics processors. In Proceedings of the 22nd Annual International Conference on Supercomputing, ACM, 2008, pp. 205-213.
Merrill, Duane and Andrew Grimshaw. Parallel scan for stream architectures. Technical Report CS2009-14, Department of Computer Science, University of Virginia.
Merrill, Duane and Michael Garland. Single-pass parallel prefix scan with decoupled look-back. NVIDIA Technical Report NVR-2016-002, March 2016.
Harris, Mark, Shubhabrata Sengupta, and John Owens. Parallel prefix sum (scan) with CUDA. In GPU Gems 3, Nguyen, H., (ed.). Addison-Wesley, Aug. 2007.
Harris, Mark and Michael Garland. Optimizing parallel prefix operations for the Fermi architecture. In GPU Computing Gems, Jade Edition, Wen-Mei Hwu, ed. Morgan Kaufmann, Waltham, MA, 2012, pp. 29-38.
Sengupta, Shubhabrata, Mark Harris, ZhangYao Zhang, and John D. Owens. Scan primitives for GPU computing. In Proceedings of the 22nd ACM SIGGRAPH/Eurographics Symposium on Graphics Hardware (San Diego, CA, August 4-5, 2007). D. Fellner and S. Spender, Eds. SIGGRAPH/Eurographics Conference on Graphics Hardware. Eurographics Association, Aire-la-Ville, Switzerland, pp. 97-106.
Sengupta, Shubhabrata, Mark Harris, and Michael Garland. Efficient parallel scan algorithms for GPUs. NVIDIA Technical Report NVR-2008-003, December 2008. http://research.nvidia.com/publication/efficient-parallel-scan-algorithms-gpus
There is a rich literature on circuits to compute parallel prefix sums; besides the Brent-Kung, Sklansky and Kogge-Stone formulations, other examples of scan circuits include Ladner-Fischer and more recent work by Lin and Hsiao. Hinze describes an algebra of scans that can be used to reason about Scan implementations; the details of his work are outside the scope of this book, but his paper is highly recommended reading.
Brent, Richard P. and H.T. Kung, A regular layout for parallel adders, IEEE Transactions on Computers C-31 (1982), 260-264.
Hinze, Ralf. An algebra of scans. In Mathematics of Program Construction, Springer, 2004, pp. 186-210.
Kogge, Peter M. & Harold S. Stone. "A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations". IEEE Transactions on Computers, 1973, C-22, 783-791
Sklansky, J. Conditional sum addition logic. IRE Trans. Electron. Comput. 9, 2 (June 1960), 226-231.