A Generalized Parallel Prefix Sums Algorithm for Arbitrary Size Arrays

1. Intel Developer Cloud. https://devcloud.intel.com/. Accessed 30 Oct 2022

2. Aananthakrishnan, S., et al.: Piuma: programmable integrated unified memory architecture. arXiv preprint arXiv:2010.06277 (2020)

3. Akl, S.G.: Parallel Computation: Models and Methods. Prentice-Hall, Inc., Hoboken (1997)

   Google Scholar 

4. Bell, N., Garland, M.: Implementing sparse matrix-vector multiplication on throughput-oriented processors. In: Proceedings of the ACM/IEEE Conference on High Performance Computing, SC 2009, November 14–20, 2009, Portland, Oregon, USA. ACM (2009). https://doi.org/10.1145/1654059.1654078

5. Bilgic, B., Horn, B.K.P., Masaki, I.: Efficient integral image computation on the GPU. In: IEEE Intelligent Vehicles Symposium (IV), 2010, La Jolla, CA, USA, June 21–24, 2010, pp. 528–533. IEEE (2010). https://doi.org/10.1109/IVS.2010.5548142

6. Blelloch, G.E.: Scans as primitive parallel operations. IEEE Trans. Comput. 38(11), 1526–1538 (1989). https://doi.org/10.1109/12.42122

   Article  Google Scholar 

7. Blelloch, G.E.: Prefix sums and their applications. Technical report. CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, November 1990

   Google Scholar 

8. Blelloch, G.E., Little, J.J.: Parallel solutions to geometric problems in the scan model of computation. J. Comput. Syst. Sci. 48(1), 90–115 (1994). https://doi.org/10.1016/S0022-0000(05)80023-6

   Article  MathSciNet  MATH  Google Scholar 

9. Chatterjee, S., Blelloch, G.E., Zagha, M.: Scan primitives for vector computers. In: Martin, J.L., Pryor, D.V., Montry, G.R. (eds.) Proceedings Supercomputing ’90, New York, NY, USA, November 12–16, 1990, pp. 666–675. IEEE Computer Society (1990). https://doi.org/10.1109/SUPERC.1990.130084

10. Cole, R., Vishkin, U.: Faster optimal parallel prefix sums and list ranking. Inf. Comput. 81(3), 334–352 (1989). https://doi.org/10.1016/0890-5401(89)90036-9

    Article  MathSciNet  MATH  Google Scholar 

11. Elliott, C.: Generic functional parallel algorithms: scan and FFT. Proc. ACM Program. Lang. 1(ICFP), 7:1–7:25 (2017). https://doi.org/10.1145/3110251

12. Fisher, A.L., Ghuloum, A.M.: Parallelizing complex scans and reductions. In: Sarkar, V., Ryder, B.G., Soffa, M.L. (eds.) Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation (PLDI), Orlando, Florida, USA, June 20–24, 1994, pp. 135–146. ACM (1994). https://doi.org/10.1145/178243.178255

13. Harris, M., Sengupta, S., Owens, J.D.: Chapter 39. parallel prefix sum (scan) with CUDA (2007). https://developer.nvidia.com/gpugems/gpugems3/part-vi-gpu-computing/chapter-39-parallel-prefix-sum-scan-cuda

14. Hillis, W.D., Jr., G.L.S.: Data parallel algorithms. Commun. ACM. 29(12), 1170–1183 (1986). https://doi.org/10.1145/7902.7903

15. Iso/iec 14882:2020(en) programming languages - c++. Standard, International Organization for Standardization, Geneva, Switzerland, December 2020

    Google Scholar 

16. Ladner, R.E., Fischer, M.J.: Parallel prefix computation. J. ACM 27(4), 831–838 (1980). https://doi.org/10.1145/322217.322232

    Article  MathSciNet  MATH  Google Scholar 

17. Lakhotia, K., Petrini, F., Kannan, R., Prasanna, V.K.: Accelerating all reduce with in-network reduction on intel PIUMA. IEEE Micro 42(2), 44–52 (2022)

    Article  Google Scholar 

18. Lakshmivarahan, S., Dhall, S.K.: Parallel Computing Using the Prefix Problem. Oxford University Press, Oxford (1994)

    Google Scholar 

19. Merrill, D., Garland, M., Grimshaw, A.S.: High-performance and scalable GPU graph traversal. ACM Trans. Parallel Comput. 1(2), 14:1–14:30 (2015). https://doi.org/10.1145/2717511

20. Morihata, A.: Lambda calculus with algebraic simplification for reduction parallelisation: extended study. J. Funct. Program. 31, e7 (2021). https://doi.org/10.1017/S0956796821000058

    Article  MathSciNet  MATH  Google Scholar 

21. Reinders, J., Ashbaugh, B., Brodman, J., Kinsner, M., Pennycook, J., Tian, X.: Data Parallel C++: Mastering DPC++ for Programming of Heterogeneous Systems Using C++ and SYCL. Springer Nature, CA (2021). https://doi.org/10.1007/978-1-4842-5574-2

    Book  Google Scholar 

22. Sanders, P., Träff, J.L.: Parallel prefix (scan) algorithms for MPI. In: Mohr, B., Träff, J.L., Worringen, J., Dongarra, J.J. (eds.) Recent Advances in Parallel Virtual Machine and Message Passing Interface, 13th European PVM/MPI User’s Group Meeting, Bonn, Germany, September 17–20, 2006, Proceedings. LNCS, vol. 4192, pp. 49–57. Springer, Cham (2006). https://doi.org/10.1007/11846802_15

23. Satish, N., Harris, M.J., Garland, M.: Designing efficient sorting algorithms for manycore GPUs. In: 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23–29, 2009, pp. 1–10. IEEE (2009). https://doi.org/10.1109/IPDPS.2009.5161005

24. Sengupta, S., Lefohn, A., Owens, J.D.: A work-efficient step-efficient prefix sum algorithm (2006)

    Google Scholar 

25. Sycl 2020 specification (revision 5). Standard, Khronos Group, Beaverton, OR, USA, May 2022

    Google Scholar 

26. Zhang, N.: A novel parallel prefix sum algorithm and its implementation on multi-core platforms. In: 2010 2nd International Conference on Computer Engineering and Technology, vol. 2, pp. V2–66-V2-70. IEEE (2010). https://doi.org/10.1109/ICCET.2010.5485315

27. Zhang, W., Wang, Y., Ross, K.A.: Parallel prefix sum with SIMD. In: Bordawekar, R., Lahiri, T. (eds.) International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures, ADMS@VLDB 2020, Tokyo, Japan, August 31, 2020. pp. 1–11 (2020)

    Google Scholar 

Download references