# Performing multiple summations in one GPU kernel

**URL:** <https://forums.developer.nvidia.com/t/performing-multiple-summations-in-one-gpu-kernel/30485>\
**Category:** CUDA Programming and Performance\
**Created:** [August 17, 2013, 3:32pm UTC](https://forums.developer.nvidia.com/t/performing-multiple-summations-in-one-gpu-kernel/30485 "2013-08-17T15:32:47Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![AstroGPU](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@AstroGPU](https://forums.developer.nvidia.com/u/AstroGPU)\
**Post date:** [August 17, 2013, 3:32pm UTC](https://forums.developer.nvidia.com/t/performing-multiple-summations-in-one-gpu-kernel/30485/1 "2013-08-17T15:32:47Z")

</div>

Hi all,

I’d like to accelerate the following task on a GPU. The problem is one of reduction, however due to its nature, the “usual” trick of saving partial sums on shared memory won’t work.

This is the essence of the task:

```auto
void Task(double *x, double *Output) {
    for (int i = 0; i < 1000000; i++) {
        AuxiliaryNumber = 0;
        for (int k = 0; k < 600; k++) {
            Output[k] += SomeFunction(x[i], AuxiliaryNumber);
            AuxiliaryNumber = OtherFunction(x[i], AuxiliaryNumber);
        }
    }
}

```

The output is 600 numbers in an array, each of them is a sum of one million summands. The order of the loops can’t be switched, because the inner loop has to be executed sequentially. If instead of 600, I had a small number (like 5), then I could define a 2D structure in shared memory, 5xThreadsPerBlock, and have each thread write its partial sum to it, and then finalize the summation. There is simply not enough shared memory (by a long shot) to do this with a size-600 array. Having each thread write its partial sum to global memory also seems a pretty poor option, since this structure will be hundreds of MB in size (depending on the number of threads, of course)… It would fit, but I’m worried about performance.

Any ideas would be greatly appreciated!

---

<div class="post-metadata">

**Author:** ![njuffa](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@njuffa](https://forums.developer.nvidia.com/u/njuffa)\
**Post date:** [August 17, 2013, 4:25pm UTC](https://forums.developer.nvidia.com/t/performing-multiple-summations-in-one-gpu-kernel/30485/2 "2013-08-17T16:25:54Z")

</div>

Why does the inner loop have to be executed sequentially?

---

<div class="post-metadata">

**Author:** ![pasoleatis](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@pasoleatis](https://forums.developer.nvidia.com/u/pasoleatis)\
**Post date:** [August 17, 2013, 5:36pm UTC](https://forums.developer.nvidia.com/t/performing-multiple-summations-in-one-gpu-kernel/30485/3 "2013-08-17T17:36:57Z")

</div>

It appears you could each thread doing one value of i, unless x[i] depends on something else. You can divide the inner loop in smaller parts and do some writes to the global memory.

---

<div class="post-metadata">

**Author:** ![sBc-Random](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@sBc-Random](https://forums.developer.nvidia.com/u/sBc-Random)\
**Post date:** [August 18, 2013, 4:44am UTC](https://forums.developer.nvidia.com/t/performing-multiple-summations-in-one-gpu-kernel/30485/4 "2013-08-18T04:44:09Z")

</div>

Edit: misread problem.

Depends how complex OtherFunction is. If it’s highly complex (and therefore you are compute bound), atomicadds might be the way to go, if it’s very simple (or you could simplify it to something that’s easily repeatable), you should do what pasoleatis said and work on one value of i at a time.  
For example:

OtherFunction(x) { return pow(x,2) }

Then OtherFunction(x, threadIdx) {return pow(x,2\*threadIdx)}

Now the loop is parallelised.

Unfortunately I assume it’s the first version (given that it troubled you enough to post here :P), in which case you will have to resort to atomics most likely.

---

<div class="post-metadata">

**Author:** ![sBc-Random](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@sBc-Random](https://forums.developer.nvidia.com/u/sBc-Random)\
**Post date:** [August 18, 2013, 5:53am UTC](https://forums.developer.nvidia.com/t/performing-multiple-summations-in-one-gpu-kernel/30485/5 "2013-08-18T05:53:27Z")

</div>

Also, If you have a stack of free global memory, you could always store Auxiliary to global

Ie

```auto
void Task(double *x, double *Output, double *Auxiliary(10^6,1)) {
    AuxiliaryNumber = 0;
    for (int k = 0; k < 600; k++) {
    for (int i = 0; i < 1000000; i++) {
    Output[k] += SomeFunction(x[i], AuxiliaryNumber[i]);
    AuxiliaryNumber[i] = OtherFunction(x[i], AuxiliaryNumber[i]);
    }
    }
    }

```

---

<div class="post-metadata">

**Author:** ![AstroGPU](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@AstroGPU](https://forums.developer.nvidia.com/u/AstroGPU)\
**Post date:** [August 19, 2013, 4:01am UTC](https://forums.developer.nvidia.com/t/performing-multiple-summations-in-one-gpu-kernel/30485/6 "2013-08-19T04:01:48Z")

</div>

Thanks! It’s probably best to implement something like sBc-Random’s last suggestion. It seems that the requirement from global memory is pretty small, and it will allow use of shared memory for the reduction algorithm.