<p>Can a GPU do this? Sure. Can it do it fast? Not really, no.</p>
<p>The nature of the algorithm is antagonistic to how a GPU wants to do work. GPUs gain performance through massive parallelism. Your algorithm is inherently single-threaded: no answer can be computed until the prior answer is computed.</p>
<p>Will the processing time of such a single-threaded operation be greater than the cost of a full GPU-&gt;CPU-&gt;GPU synchronization? That depends on how much data you're talking about. That being said, unless the data is being computed <em>by</em> the GPU, the CPU could just hold onto a copy of it and compute the values itself.</p>

CC BY-SA 4.0
2023-06-02T22:32:26.513Z
Thanks Nicol, it is useful to have it confirmed that a GPU can do this. I will look at converting my compute shader to a mesh/primitive shader. I'm convinced the vertex shader can't do this, and the geometry shader is too limited.
Nick
CC BY-SA 4.0
2023-06-02T22:41:21.767Z
It is also useful  to have it confirmed that the algorithm is inherently single-threaded => can't be parallelised. The GPU is very good at calculating the initial data, so I think the fastest way is to do it all on the GPU even though the cumulative sum is not really appropriate for the GPU. I think the cost of a full GPU->CPU->GPU synchronization would need to be less than the difference in processing time between GPU/CPU. Maybe I can investigate this at some point.
Nick
CC BY-SA 4.0
2023-06-02T22:43:25.230Z
"*I will look at converting my compute shader to a mesh/primitive shader.*" ... how would that help?
Nicol Bolas
CC BY-SA 4.0
2023-06-02T22:45:57.373Z
Your answer has helped me clarify the way to go from here. I'm not allowed to vote it up, so I'll just accept it. Thanks again.
Nick
CC BY-SA 4.0
2023-06-02T22:49:51.333Z
I'm not merely calculating the data, I want to plot it too.  Can I send the output of a compute shader into a graphics pipeline without using the CPU?
Nick
CC BY-SA 4.0
2023-06-02T23:13:14.913Z
@Nick: "*without using the CPU*" What does that mean? You can't do anything in the graphics pipeline "without using the CPU". But that doesn't mean that the CPU needs to know [specific details](https://www.khronos.org/opengl/wiki/Indirect_Rendering).
Nicol Bolas
CC BY-SA 4.0
2023-06-03T00:07:02.057Z
I think you mean "Yes! you _can_ send the output of a compute shader into a graphics pipeline without using the CPU.  Here's a link ..."
Nick
CC BY-SA 4.0
2023-06-03T00:08:32.293Z
What I meant was "Like a mesh/primitive shader can send primitives for rasterisation without using the CPU"
Nick
CC BY-SA 4.0
2023-06-03T00:10:52.230Z
@Nick: "*I think you mean "Yes! you can send the output of a compute shader into a graphics pipeline without using the CPU. Here's a link ..."*" But that's not what indirect rendering is. The CPU is being used, as the CPU must execute a call to `glDrawElementsIndirect` in order to perform indirect rendering. The CPU doesn't have to know about the details of how much stuff gets rendered or where exactly it is in the current buffers. But it is still using the CPU in a way that task shaders *do not*.
Nicol Bolas
CC BY-SA 4.0
2023-06-03T15:13:39.320Z
Indirect Rendering is definitely an interesting technique, and would help greatly in implementing a solution to my question, even though the CPU is being used -- Not to transfer data but to call the API.  
I think calling the API should be assumed to be handled by the CPU.  
When I say "without using the CPU" I think its meaning is obvious -- although I don't mean _not at all_ -- I don't feel the need to clarify precisely what it it might, or might not be doing.  
I think it is also obvious that my understanding of all this is incomplete, at best. Thanks for your help
Nick
CC BY-SA 4.0
2023-06-02T20:23:45.320Z
2023-06-02T20:23:45.320Z
Nicol Bolas
<p>I am rewriting this answer because of misunderstandings and a better explanation of the algorithm.</p>
<p>The render pipeline is not well suited for this kind of task. It is better to use compute shaders instead.</p>
<p>The following algorithm is designed to be run as a compute shader.</p>
<p>First, let's start with a simple example:</p>
<p>Suppose we have 50000 values stored in a shader storage buffer object (SSBO1). And let us further assume that all values are <code>1</code>. So figure 1 shows the input data.</p>
<p><a href="https://i.sstatic.net/37ZsO.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/37ZsO.png" alt="Enter image description here" /></a></p>
<p><strong>Figure 1:</strong> 50000 data points, each has the value <code>1</code>.</p>
<p>This algorithm calculates the cumulative sum. For our simple example, the result looks like Figure 2.</p>
<p><a href="https://i.sstatic.net/wMKTM.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wMKTM.png" alt="Insert image description here" /></a></p>
<p><strong>Figure 2:</strong> The final result of the simple example (cumulative sum / discrete integral).</p>
<p>Compute shaders can have different workgroup sizes. In our case, we try to keep the workgroup size as small as possible, with respect to the minimum warp/wave length of 32 (Nvidia) 64 (AMD). Let's assume we are using an AMD graphics card, then our workgroup size is (x = 64, y = 1, z = 1).
The algorithm needs additional SSBOs to store intermediate values. The additional SSBOs will contain the following number of values:</p>
<pre><code>unsigned int workgroupSize = 64;
unsigned int dataCount = 50000;

unsigned int SSBO2_count = static_cast&lt;unsigned int&gt;(ceil(static_cast&lt;float&gt;(inputDataCount) / workgroupSize)); // 782
unsigned int SSBO3_count = static_cast&lt;unsigned int&gt;(ceil(static_cast&lt;float&gt;(SSBO2_count) / workgroupSize)); //13
</code></pre>
<p>The first compute shader will work as follows:
Each invocation will load the global value from SSBO1 (original data) and store the value in shared memory so that other invocations within that workgroup can quickly access that value. Then a <code>barrier</code> is needed to ensure that all data is loaded correctly. Then the first invocation within each workgroup accumulates these values while updating the original SSBO1, and stores the accumulated workgroup result to SSBO2.</p>
<pre><code>#version 430 core
layout (local_size_x = 64, local_size_y = 1, local_size_z = 1) in;

layout(std430, binding = 1) buffer SSBOInput
{
    float values[]; //first execution: 50000 values. Second execution: 782 values
}ssboInput;

layout(std430, binding = 2) buffer SSBOOutput
{
    float values[]; //first execution: 782 values. Second execution 13 values
}ssboOutput;    

shared float loadedValues[64];
uniform int countData;
uniform int writeToOutput;

void main()
{
    loadedValues[gl_LocalInvocationIndex] = 0.0;
    if(gl_GlobalInvocationID.x &lt; countData) //check if inside ssbo1
    {
        loadedValues[gl_LocalInvocationIndex] = ssboInput.values[gl_GlobalInvocationID.x];
    }
    barrier(); //ensure, that all values are loaded to shared memory
    if(gl_LocalInvocationIndex == 0)
    {
        float sum = 0;
        for(int i = 0; i &lt; 64; ++i)
        {
            sum += loadedValues[i];
            if(gl_GlobalInvocationID.x + i &lt; countData)
            {
                ssboInput.values[gl_GlobalInvocationID.x + i] = sum;
            }
        }
        if(writeToOutput == 1)
            ssboOutput.values[gl_WorkGroupID.x] = sum;
    }
}
</code></pre>
<p>Bind SSBO1 to binding location 1 (ssboInput) and SSBO2 to binding location 2 (ssboOutput). The uniforms <code>countData</code> = 50000 and <code>writeToOutput</code> = 1.
After running 782 workgroups, the values will look like Figure 3.</p>
<p><a href="https://i.sstatic.net/S33rn.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/S33rn.png" alt="Insert image description here" /></a></p>
<p><strong>Figure 3:</strong> These are the values stored in SSBO1 after the compute shader is executed.</p>
<p>In our example, the SSBO2 (782 data points) will all store the value <code>64</code>. This is the case because the input values are all <code>1</code>. If we ask for the cumulative value of index (e.g. 200), we only need to calculate the following:</p>
<p><span class="math-container">$$indexMax = floor(200 / 64)-1$$</span>
<span class="math-container">$$CumulativeSum = SSBO1[200] + \sum_{i = 0}^{indexMax}(SSBO2[i])$$</span></p>
<p>If we look at the equation, we will see that the problem is still the same, except that the difference is between 50000 and 782 data points.</p>
<p><strong>So we do the same thing again.</strong>
First, bind SSBO2 to binding slot 1. And bind SSBO3 to binding slot 2.
Change the variable <code>countData</code> to 782. <code>writeToOutput</code> = 1. And run the compute shader with 13 workgroups.</p>
<p><strong>Let's take a look at the SSBO value:</strong>.
SSBO1 is not touched and has the values from figure 3. SSBO2 has changed! The values are accumulated depending on the workgroup size (see Figure 4). SSBO3 is now filled, the values are all <code>4096</code>.</p>
<p>[<img src="https://i.sstatic.net/oqdv7.png" alt="Enter image description here" />]</p>
<p><strong>Figure 4:</strong> These are the values stored in SSBO2 after the second compute shader call.</p>
<p><strong>So we do the same thing again for the last time:</strong> This time it is the last execution of this compute shader. We bind SSBO3 to binding slot 1 and disable <code>writeToOutput</code> = 0. <code>countData</code> = 13. We only need to execute one workgroup.</p>
<p><strong>Final step!</strong></p>
<p>The precalculations are finished. Now we can compute the cumulative sum of the individual values within <span class="math-container">$log_{64}(50000)$</span> steps. The following compute shader stores the cumulative sum in SSBO1.</p>
<pre><code>#version 430 core
layout (local_size_x = 64, local_size_y = 1, local_size_z = 1) in;

layout(std430, binding = 1) buffer SSBO1
{
    float values[]; //50000 values
}ssbo1;

layout(std430, binding = 2) buffer SSBO2
{
    float values[]; //782 values
}ssbo2;   

layout(std430, binding = 3) buffer SSBO3
{
    float values[]; //13 values
}ssbo3;    

uniform int countData;

void main()
{
    if(gl_GlobalInvocationID.x &lt; countData) //check if inside ssbo1
    {
        float sum1 = ssbo1.values[gl_GlobalInvocationID.x];
        int index2 = gl_GlobalInvocationID.x / 64 - 1;
        float sum2 = index2 &gt;= 0 ? ssbo2.values[index2] : 0;
        int index3 = index2 / 64 - 1;
        float sum3 = index3 &gt;= 0 ? ssbo3.values[index3] : 0;

        //store cululative sum
        ssbo1.values[gl_GlobalInvocationID.x] = sum1 + sum2 + sum3;
    }
}
</code></pre>
<p>The cumulative sum is stored in SSBO1 (see Figure 2).</p>
<p>This code has not been tested yet. So there might be some sintax errors in it.... Sorry for that.</p>

CC BY-SA 4.0
2023-06-08T23:44:39.157Z
Thanks @Thomas. your answer does contain useful advice about workgroup sizes, but I don't think it is relevant to my question.  It seems you are simply adding all the data to produce a sum. The Q clearly asks for "a plot of the same data, but each point relative to the previous one".  If I start with 100 points, I want to produce 100 points, each being added on to the previous point (relative instead of absolute).  Thus each summation must wait for previous point to be calculated.
Nick
CC BY-SA 4.0
2023-06-09T09:22:34.203Z
@Nick this is a misunderstanding, the answer gives you the cumulative sum with same size as the input data. The SSBO2 stores the Differenz from one workgroup to the next... To calculate the final result of a point within your data, you only need the sum the values from SSBO2 index 0 till the index of the point of interest + the value from SSBO1. As you can see, the problem is still the same, with a difference in size... SSBO1 has size of 50000 where SSBO2 has a size of 50000 / 64. You can use SSBO3 in the same way as SSBO2 to reduce the values to 50000/64/64... Till it has only 64 values left.
Thomas
CC BY-SA 4.0
2023-06-12T11:19:22.873Z
@Nick I rewrote the answer to make clear how the algorithm works. Please take a look at it :)
Thomas
CC BY-SA 4.0
2023-06-14T23:31:32.117Z
Thanks @Thomas. This is much more understandable, especially with diagrams and equations, and code is a bonus too.  I'm still not clear in my mind how the parallelisation actually happens, though I'm sure this is my failing not yours.  I'm trying to implement this myself, and also my Q needs much improvement, but I am battling the constraints of this site, and my ISP in SE England have made SE unreachable.
Nick
CC BY-SA 4.0
2023-06-15T06:58:18.663Z
@Nick try to understand the algorithm... it is not as complicated as it looks like. The first execution gives you the cumulative sum of the input data with respect to the workgroup size (64). The offset of the cumulated sum of each workgroup is stored to SSBO2. So after the first execution we have broken down the problem from 50000 data points to 782 data points. But these 782 data points need to be cumulative summed as the 50000. So we use the same shader again just with other bindings and store the result to SSBO3. You need $log_{64}(n)$ many SSBOs  to brake down the problem to one workgroup
Thomas
CC BY-SA 4.0
2023-06-15T07:00:16.183Z
You can also only generate one additional SSBO by storing all values of SSBO2, SSBO3... into one SSBO. I'm using multiple SSBOs just to clearify the algorithm. But with an index offset it is possible to store all results to one buffer.
Thomas
CC BY-SA 4.0
2023-06-07T09:19:35.743Z
2023-06-15T07:02:31.640Z
2023-06-15T07:02:31.640Z
Thomas
<p>I have a vertex shader happily producing all the vertices I want for a 2D plot. Now I want to also render a plot of the same data, but each point relative to the previous one, like <a href="https://en.wikipedia.org/wiki/SVG#Design" rel="nofollow noreferrer">SVG</a> <strong>Paths</strong> using <code>l</code> instead of <code>L</code>.</p>
<p>I have tried a geometry shader, but the primitive would have to be a line strip with <em>all</em> the vertices -- 500,000 or more.</p>
<p>I'm pretty sure a vertex shader can't use the output of the previous instance, and computing the sum of 1..n is difficult to parallelise.</p>
<p>The only method I can think of is;</p>
<ol>
<li>Use a compute shader to calculate the data</li>
<li>Calculate cumulative sums with CPU</li>
<li>Send data to vertex shader that does very little</li>
</ol>
<p>Is there a way of doing this with a vertex, geometry or mesh shader? Or with an extension that might help?</p>
<p>It seems to be something basic enough, and useful enough to be included in SVG.</p>
<p>What is the best method to tackle this?</p>

CC BY-SA 4.0
2023-06-01T18:45:00.597Z
Thanks @Yves
By cumulative sum, I mean
    `buff_new[n] =Sum(m=1..n, buff_old[m])`
or
    `buff_new[n] = buff_old[n]  buff_new[n-1]`
which means that calculating `buff_new[n]` needs to wait for `buff_new[n-1]` to be available. Hence, difficult to parallelise.
Nick
CC BY-SA 4.0
2023-06-01T18:47:52.753Z
Nevertheless, it would be useful if the GPU can do this, as I wouldn't need to copy buffer back to CPU, calculate, then send to GPU again.
Nick
CC BY-SA 4.0
2023-06-01T18:51:01.683Z
By best method, I mean "Is it possible to do all this in a shader/on the GPU"?
Nick
CC BY-SA 4.0
2023-06-01T20:01:48.207Z
[order of execution][1] seems to be relevant if binary tree only has one (very deep) branch. Seems to indicate lack of any parallelism :-(  
  
But what I want to do is available in SVG, so I thought there might be a way native to Vulkan.  
  
[1]: https://computergraphics.stackexchange.com/questions/7838/controling-order-of-execution-of-a-compute-shader-on-an-array-of-vertices-dat?rq=1
Nick
<shader><algorithm><vulkan><vector-graphics>
Relative coordinates -- cumulative sum
Nick
# Relative coordinates -- cumulative sum

(Asked by: username_0 on 2023-06-01)

I have a vertex shader happily producing all the vertices I want for a 2D plot. Now I want to also render a plot of the same data, but each point relative to the previous one, like [SVG](https://en.wikipedia.org/wiki/SVG#Design) **Paths** using `l` instead of `L`.

I have tried a geometry shader, but the primitive would have to be a line strip with *all* the vertices -- 500,000 or more.

I'm pretty sure a vertex shader can't use the output of the previous instance, and computing the sum of 1..n is difficult to parallelise.

The only method I can think of is;

1. Use a compute shader to calculate the data
2. Calculate cumulative sums with CPU
3. Send data to vertex shader that does very little

Is there a way of doing this with a vertex, geometry or mesh shader? Or with an extension that might help?

It seems to be something basic enough, and useful enough to be included in SVG.

What is the best method to tackle this?

**Tags:** shader, algorithm, vulkan, vector-graphics

> **Comments:**
> **username_0**: Thanks @Yves By cumulative sum, I mean     `buff_new[n] =Sum(m=1..n, buff_old[m])` or     `buff_new[n] = buff_old[n]  buff_new[n-1]` which means that calculating `buff_new[n]` needs to wait for `buff_new[n-1]` to be available. Hence, difficult to parallelise.  
> **username_0**: Nevertheless, it would be useful if the GPU can do this, as I wouldn't need to copy buffer back to CPU, calculate, then send to GPU again.  
> **username_0**: By best method, I mean "Is it possible to do all this in a shader/on the GPU"?  
> **username_0**: [order of execution][1] seems to be relevant if binary tree only has one (very deep) branch. Seems to indicate lack of any parallelism :-(      But what I want to do is available in SVG, so I thought there might be a way native to Vulkan.      [1]: https://computergraphics.stackexchange.com/questions/7838/controling-order-of-execution-of-a-compute-shader-on-an-array-of-vertices-dat?rq=1  

---

## 2 answers

### Answer by username_1 on 2023-06-02. Score: 0 | Accepted answer

Can a GPU do this? Sure. Can it do it fast? Not really, no.

The nature of the algorithm is antagonistic to how a GPU wants to do work. GPUs gain performance through massive parallelism. Your algorithm is inherently single-threaded: no answer can be computed until the prior answer is computed.

Will the processing time of such a single-threaded operation be greater than the cost of a full GPU->CPU->GPU synchronization? That depends on how much data you're talking about. That being said, unless the data is being computed *by* the GPU, the CPU could just hold onto a copy of it and compute the values itself.

> **Comments:**
> **username_0**: Thanks username_1, it is useful to have it confirmed that a GPU can do this. I will look at converting my compute shader to a mesh/primitive shader. I'm convinced the vertex shader can't do this, and the geometry shader is too limited.  
> **username_0**: It is also useful  to have it confirmed that the algorithm is inherently single-threaded => can't be parallelised. The GPU is very good at calculating the initial data, so I think the fastest way is to do it all on the GPU even though the cumulative sum is not really appropriate for the GPU. I think the cost of a full GPU->CPU->GPU synchronization would need to be less than the difference in processing time between GPU/CPU. Maybe I can investigate this at some point.  
> **username_1**: "*I will look at converting my compute shader to a mesh/primitive shader.*" ... how would that help?  
> **username_0**: Your answer has helped me clarify the way to go from here. I'm not allowed to vote it up, so I'll just accept it. Thanks again.  
> **username_0**: I'm not merely calculating the data, I want to plot it too.  Can I send the output of a compute shader into a graphics pipeline without using the CPU?  
> **username_1**: @username_0: "*without using the CPU*" What does that mean? You can't do anything in the graphics pipeline "without using the CPU". But that doesn't mean that the CPU needs to know [specific details](https://www.khronos.org/opengl/wiki/Indirect_Rendering).  
> **username_0**: I think you mean "Yes! you _can_ send the output of a compute shader into a graphics pipeline without using the CPU.  Here's a link ..."  
> **username_0**: What I meant was "Like a mesh/primitive shader can send primitives for rasterisation without using the CPU"  
> **username_1**: @username_0: "*I think you mean "Yes! you can send the output of a compute shader into a graphics pipeline without using the CPU. Here's a link ..."*" But that's not what indirect rendering is. The CPU is being used, as the CPU must execute a call to `glDrawElementsIndirect` in order to perform indirect rendering. The CPU doesn't have to know about the details of how much stuff gets rendered or where exactly it is in the current buffers. But it is still using the CPU in a way that task shaders *do not*.  
> **username_0**: Indirect Rendering is definitely an interesting technique, and would help greatly in implementing a solution to my question, even though the CPU is being used -- Not to transfer data but to call the API.   I think calling the API should be assumed to be handled by the CPU.   When I say "without using the CPU" I think its meaning is obvious -- although I don't mean _not at all_ -- I don't feel the need to clarify precisely what it it might, or might not be doing.   I think it is also obvious that my understanding of all this is incomplete, at best. Thanks for your help  

---

### Answer by username_2 on 2023-06-07. Score: 2

I am rewriting this answer because of misunderstandings and a better explanation of the algorithm.

The render pipeline is not well suited for this kind of task. It is better to use compute shaders instead.

The following algorithm is designed to be run as a compute shader.

First, let's start with a simple example:

Suppose we have 50000 values stored in a shader storage buffer object (SSBO1). And let us further assume that all values are `1`. So figure 1 shows the input data.

[![Enter image description here](https://i.sstatic.net/37ZsO.png)](https://i.sstatic.net/37ZsO.png)

**Figure 1:** 50000 data points, each has the value `1`.

This algorithm calculates the cumulative sum. For our simple example, the result looks like Figure 2.

[![Insert image description here](https://i.sstatic.net/wMKTM.png)](https://i.sstatic.net/wMKTM.png)

**Figure 2:** The final result of the simple example (cumulative sum / discrete integral).

Compute shaders can have different workgroup sizes. In our case, we try to keep the workgroup size as small as possible, with respect to the minimum warp/wave length of 32 (Nvidia) 64 (AMD). Let's assume we are using an AMD graphics card, then our workgroup size is (x = 64, y = 1, z = 1).
The algorithm needs additional SSBOs to store intermediate values. The additional SSBOs will contain the following number of values:

```
unsigned int workgroupSize = 64;
unsigned int dataCount = 50000;

unsigned int SSBO2_count = static_cast<unsigned int>(ceil(static_cast<float>(inputDataCount) / workgroupSize)); // 782
unsigned int SSBO3_count = static_cast<unsigned int>(ceil(static_cast<float>(SSBO2_count) / workgroupSize)); //13

```

The first compute shader will work as follows:
Each invocation will load the global value from SSBO1 (original data) and store the value in shared memory so that other invocations within that workgroup can quickly access that value. Then a `barrier` is needed to ensure that all data is loaded correctly. Then the first invocation within each workgroup accumulates these values while updating the original SSBO1, and stores the accumulated workgroup result to SSBO2.

```
#version 430 core
layout (local_size_x = 64, local_size_y = 1, local_size_z = 1) in;

layout(std430, binding = 1) buffer SSBOInput
{
    float values[]; //first execution: 50000 values. Second execution: 782 values
}ssboInput;

layout(std430, binding = 2) buffer SSBOOutput
{
    float values[]; //first execution: 782 values. Second execution 13 values
}ssboOutput;    

shared float loadedValues[64];
uniform int countData;
uniform int writeToOutput;

void main()
{
    loadedValues[gl_LocalInvocationIndex] = 0.0;
    if(gl_GlobalInvocationID.x < countData) //check if inside ssbo1
    {
        loadedValues[gl_LocalInvocationIndex] = ssboInput.values[gl_GlobalInvocationID.x];
    }
    barrier(); //ensure, that all values are loaded to shared memory
    if(gl_LocalInvocationIndex == 0)
    {
        float sum = 0;
        for(int i = 0; i < 64; ++i)
        {
            sum += loadedValues[i];
            if(gl_GlobalInvocationID.x + i < countData)
            {
                ssboInput.values[gl_GlobalInvocationID.x + i] = sum;
            }
        }
        if(writeToOutput == 1)
            ssboOutput.values[gl_WorkGroupID.x] = sum;
    }
}

```

Bind SSBO1 to binding location 1 (ssboInput) and SSBO2 to binding location 2 (ssboOutput). The uniforms `countData` = 50000 and `writeToOutput` = 1.
After running 782 workgroups, the values will look like Figure 3.

[![Insert image description here](https://i.sstatic.net/S33rn.png)](https://i.sstatic.net/S33rn.png)

**Figure 3:** These are the values stored in SSBO1 after the compute shader is executed.

In our example, the SSBO2 (782 data points) will all store the value `64`. This is the case because the input values are all `1`. If we ask for the cumulative value of index (e.g. 200), we only need to calculate the following:

$$indexMax = floor(200 / 64)-1$$
$$CumulativeSum = SSBO1[200] + \sum\_{i = 0}^{indexMax}(SSBO2[i])$$

If we look at the equation, we will see that the problem is still the same, except that the difference is between 50000 and 782 data points.

**So we do the same thing again.**
First, bind SSBO2 to binding slot 1. And bind SSBO3 to binding slot 2.
Change the variable `countData` to 782. `writeToOutput` = 1. And run the compute shader with 13 workgroups.

**Let's take a look at the SSBO value:**.
SSBO1 is not touched and has the values from figure 3. SSBO2 has changed! The values are accumulated depending on the workgroup size (see Figure 4). SSBO3 is now filled, the values are all `4096`.

[![Enter image description here](https://i.sstatic.net/oqdv7.png)]

**Figure 4:** These are the values stored in SSBO2 after the second compute shader call.

**So we do the same thing again for the last time:** This time it is the last execution of this compute shader. We bind SSBO3 to binding slot 1 and disable `writeToOutput` = 0. `countData` = 13. We only need to execute one workgroup.

**Final step!**

The precalculations are finished. Now we can compute the cumulative sum of the individual values within $log\_{64}(50000)$ steps. The following compute shader stores the cumulative sum in SSBO1.

```
#version 430 core
layout (local_size_x = 64, local_size_y = 1, local_size_z = 1) in;

layout(std430, binding = 1) buffer SSBO1
{
    float values[]; //50000 values
}ssbo1;

layout(std430, binding = 2) buffer SSBO2
{
    float values[]; //782 values
}ssbo2;   

layout(std430, binding = 3) buffer SSBO3
{
    float values[]; //13 values
}ssbo3;    

uniform int countData;

void main()
{
    if(gl_GlobalInvocationID.x < countData) //check if inside ssbo1
    {
        float sum1 = ssbo1.values[gl_GlobalInvocationID.x];
        int index2 = gl_GlobalInvocationID.x / 64 - 1;
        float sum2 = index2 >= 0 ? ssbo2.values[index2] : 0;
        int index3 = index2 / 64 - 1;
        float sum3 = index3 >= 0 ? ssbo3.values[index3] : 0;

        //store cululative sum
        ssbo1.values[gl_GlobalInvocationID.x] = sum1 + sum2 + sum3;
    }
}

```

The cumulative sum is stored in SSBO1 (see Figure 2).

This code has not been tested yet. So there might be some sintax errors in it.... Sorry for that.

> **Comments:**
> **username_0**: Thanks @username_2. your answer does contain useful advice about workgroup sizes, but I don't think it is relevant to my question.  It seems you are simply adding all the data to produce a sum. The Q clearly asks for "a plot of the same data, but each point relative to the previous one".  If I start with 100 points, I want to produce 100 points, each being added on to the previous point (relative instead of absolute).  Thus each summation must wait for previous point to be calculated.  
> **username_2**: @username_0 this is a misunderstanding, the answer gives you the cumulative sum with same size as the input data. The SSBO2 stores the Differenz from one workgroup to the next... To calculate the final result of a point within your data, you only need the sum the values from SSBO2 index 0 till the index of the point of interest + the value from SSBO1. As you can see, the problem is still the same, with a difference in size... SSBO1 has size of 50000 where SSBO2 has a size of 50000 / 64. You can use SSBO3 in the same way as SSBO2 to reduce the values to 50000/64/64... Till it has only 64 values left.  
> **username_2**: @username_0 I rewrote the answer to make clear how the algorithm works. Please take a look at it :)  
> **username_0**: Thanks @username_2. This is much more understandable, especially with diagrams and equations, and code is a bonus too.  I'm still not clear in my mind how the parallelisation actually happens, though I'm sure this is my failing not yours.  I'm trying to implement this myself, and also my Q needs much improvement, but I am battling the constraints of this site, and my ISP in SE England have made SE unreachable.  
> **username_2**: @username_0 try to understand the algorithm... it is not as complicated as it looks like. The first execution gives you the cumulative sum of the input data with respect to the workgroup size (64). The offset of the cumulated sum of each workgroup is stored to SSBO2. So after the first execution we have broken down the problem from 50000 data points to 782 data points. But these 782 data points need to be cumulative summed as the 50000. So we use the same shader again just with other bindings and store the result to SSBO3. You need $log_{64}(n)$ many SSBOs  to brake down the problem to one workgroup  
> **username_2**: You can also only generate one additional SSBO by storing all values of SSBO2, SSBO3... into one SSBO. I'm using multiple SSBOs just to clearify the algorithm. But with an index offset it is possible to store all results to one buffer.  

---

