Results 1 to 4 of 4

Thread: Adding up a large array.

  1. #1
    Junior Member
    Join Date
    Jul 2011
    Posts
    5

    Adding up a large array.

    If at the end of a computation I want to add up all the elements in a one-dimensional array A, how would I best go about doing this?

    I figured I could do this in O(log(n)) time, by halving the field repeatedly and doing
    A[i] := A[i] + A[i + n/2]
    for all i.

    Here is the idea (serial) in pseudocode (for simplicity I'm assuming the size of the field is a power of two):

    Code :
    n := n / 2
    while (n > 0) do
      for i = 1 to n do
        A[i] := A[i] + A[i+n]
      end
      n := n / 2
    end

    I want each iteration of the for loop to be done by one work item, however, I am not sure which of the following two approaches would be best or most idiomatic here:

    1. Enqueing the kernel log(n) times with an ever decreasing work size.[/*:m:18gjs991]
    2. Putting the while loop (with log(n) iterations) inside the kernel and having some sort of synchronisation point inside the loop so that the additions don't conflict with each other.[/*:m:18gjs991]

  2. #2
    Senior Member
    Join Date
    Mar 2011
    Location
    Seoul
    Posts
    118

    Re: Adding up a large array.

    NVIDIA has a really good whitepaper on reduction optimizations. Although its for CUDA the concepts directly transfer to OpenCL and AMD has a helpful comparison chart of terms and functions between CUDA and OpenCL.

  3. #3
    Senior Member
    Join Date
    May 2010
    Location
    Toronto, Canada
    Posts
    845

    Re: Adding up a large array.

    As Sean said, what you describe is called a parallel reduction.
    Disclaimer: Employee of Qualcomm Canada. Any opinions expressed here are personal and do not necessarily reflect the views of my employer. LinkedIn profile.

  4. #4
    Junior Member
    Join Date
    Jul 2011
    Posts
    5

    Re: Adding up a large array.

    Thank you for the replies.

    That term was the pointer I needed.

Similar Threads

  1. Help adding large array
    By Rui in forum OpenCL
    Replies: 1
    Last Post: 06-03-2010, 12:35 PM
  2. Help: Adding two arrays
    By Rui in forum OpenCL
    Replies: 1
    Last Post: 03-24-2010, 07:57 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •