可以计算Shader算法的时间复杂度吗？

Question

我目前正在参加一个算法分析 class，我们被分配了小组作业。教授要求我们选择计算机科学中的某个领域，选择一种算法并证明渐近极限（至少O（N））。

所以我和我的同事选择了做一个计算机图形算法，更具体地说是一个光照体积算法。

但是算法分析书上分析的代码都是跑在CPU上的。 OpenGL 生成的代码在 GPU 上运行，不能保证线性度，因为它是由其他几个 CPUs 运行并行组成的。

该行为会影响计算吗？有人可以帮我弄清楚从哪里开始吗？

这段代码摘自GPU Gems 3： Volumetric Light Scattering as a Post-Process.

float4 main(float2 texCoord : TEXCOORD0) : COLOR0  
{  
  // Calculate vector from pixel to light source in screen space.  
   half2 deltaTexCoord = (texCoord - ScreenLightPos.xy);  
  // Divide by number of samples and scale by control factor.  
  deltaTexCoord *= 1.0f / NUM_SAMPLES * Density;  
  // Store initial sample.  
   half3 color = tex2D(frameSampler, texCoord);  
  // Set up illumination decay factor.  
   half illuminationDecay = 1.0f;  
  // Evaluate summation from Equation 3 NUM_SAMPLES iterations.  
   for (int i = 0; i < NUM_SAMPLES; i++)  
  {  
    // Step sample location along ray.  
    texCoord -= deltaTexCoord;  
    // Retrieve sample at new location.  
   half3 sample = tex2D(frameSampler, texCoord);  
    // Apply sample attenuation scale/decay factors.  
    sample *= illuminationDecay * Weight;  
    // Accumulate combined color.  
    color += sample;  
    // Update exponential decay factor.  
    illuminationDecay *= Decay;  
  }  
  // Output final color with a further scale control factor.  
   return float4( color * Exposure, 1);  
}

我认为渐近极限是样本的函数。还需要考虑的是生成着色器所需的 4 个物理方程。在此先感谢所有社区的帮助！

Answer 1

算法的复杂度不会随着处理元素的数量而改变（对于有限数量的处理器）。多项式时间算法是多项式时间，无论是在 CPU 还是 GPU 上。换句话说，n² 与 (n/320)² 没有区别，因为 "n" 接近无穷大。

算法的复杂度没有改变； 执行时间确实如此。但很多复杂性都是如此。快速排序和合并排序具有相同的 nLog(n) 复杂度，但实际上快速排序平均更快。

渐近极限并不是性能的最终结果。

Answer 2

所有代码行都意味着执行时间恒定（它们并不意味着循环或递归调用或类似的东西）。但是，循环内的行被执行了 NUM_SAMPLES 次。因此，一次着色器调用的执行时间将为：

O(NumSamples)

由于此着色器每个像素执行一次，因此总执行时间将为：

O(NumSamples * ResolutionX * ResolutionY)

记住 Nicol Bolas 是对的，算法的复杂度没有改变，如果在 CPU 上执行也是一样的，但是硬件相关的问题会更慢.

在更深入的分析中，您可以分析每个 GPU 内核的使用情况和 CPU 的加速，但在这个简单的代码中...这并不重要，因为使用情况可能非常接近到 100%。无论如何，要对此进行分析，您需要了解 GPU 硬件架构和一般算法成本。

Answer 3

uniform float exposure;
uniform float decay;
uniform float density;
uniform float weight;
uniform vec2 lightPositionOnScreen;
uniform sampler2D myTexture;
const int NUM_SAMPLES = 100 ;
void main()
{   
C1  vec2 deltaTextCoord=vec2(gl_TexCoord[0].st-lightPositionOnScreen.xy);                          
C2      vec2 textCoo = gl_TexCoord[0].st;                                                                         
C3      deltaTextCoord *= 1.0 /  float(NUM_SAMPLES) * density;                                        
C4      float illuminationDecay = 1.0;                                                                                 
n       for(int i=0; i < NUM_SAMPLES ; i++)     {                                          
C5              textCoo -= deltaTextCoord;                                                    
C6          vec4 sample = texture2D(myTexture, textCoo );                        
C7                     sample *= illuminationDecay * weight;                                   
C8              gl_FragColor += sample;                                                      
C9              illuminationDecay *= decay;                                                    
                                                }
C10                 gl_FragColor *= exposure;  
}

f(n) =∑_(i=0)^n〖(C_5+ C_6+ C_7+ C_8+ C_9)〗 + C_1 + C_2 + C_3 + C_4 + C_10

(C_5+ C_6+ C_7+ C_8+ C_9 )=K_1

(C_1 + C_2 + C_3 + C_4 + C_10)=K_2

因此： f(n)= Cp* K_1*n+ K_2

作为Cp像素数。

这是 f(n)= θ(n) for each pixel.

@dv1729 评论对大学作业的开发过程很有帮助。

这证明计算机图形算法分析可能非常具有欺骗性，因为我们都知道这种 post 处理在硬件上有多难，但是查看代码向我们展示了一个渐近极限，它确实非常低的。这里的常量可能非常高，基于物理的体积光散射背后的深奥数学可能会被忽视。

可以计算Shader算法的时间复杂度吗？

It`s possible to calculate time complexity of Shader algorithm?

opengl

algorithm

graphics

computer-science

time-complexity