GPU着色器Turing是否已完成 [英] Are GPU shaders Turing complete

问题描述

我知道完整的GPU是计算的庞然大物-包括计算的每个步骤和内存.因此，很明显，GPU可以计算出我们想要的任何东西-它已经完成了Turing.

I understand that complete GPUs are behemoths of computing - including every step of calculation, and memory. So obviously a GPU can compute whatever we want - it's Turing complete.

我的问题是关于各种GPU(流处理器"/"CUDA核心")上的单个着色器:
图灵完成了吗?
我(理论上)可以使用单个着色器在任意输入上计算任意函数吗?
我试图了解计算着色器的规模"是什么.

My question is in regard to a single shader on various GPUs ("Stream Processor"/"CUDA Core"):
Is it Turing complete?
Can I (in theory) compute an arbitrary function over arbitrary inputs by using a single shader?
I'm trying to understand at what "scale" of computation shaders live.

推荐答案

您将着色器指的是用于计算着色的程序吗?

Did You mean shader as a program used to compute shading?

在维基谈话中，我发现:

On wiki talk I found:

(...)着色器模型1.x和2.0确实不是图灵完整的，因为 他们缺乏通用的迭代能力(他们确实有一些 有限的循环结构，但这实际上是在 编译时间，因此迭代次数必须是恒定的.)

(...)Shader models 1.x and 2.0 are indeed not Turing complete, because they lack a generalised iteration capability (they do have some limited looping constructs, but this is effectively unrolled at compile time, so the number of iterations must be constant).

Shader模型3.0，可在最新的PC硬件和更高版本中使用 Xbox 360，具有完全常规的循环功能，并且图灵完整 从理论上讲.这很好地突出了区别 在理论与实践之间！当人们声称设备是 图灵完整，实际上，它们的意思是如果有无限的时间， 并且无限存储，那将是图灵完整的".着色器模型3.0 寄存器空间和程序指令仍然非常有限 计数，因此在进行任何现实世界的测试时，它都将严重失败.

Shader model 3.0, which is used in the latest PC hardware and on Xbox 360, has fully general looping abilities and is Turing complete in the theoretical sense. This rather nicely highlights the difference between theory and practice, though! When people claim a device is Turing complete, what they actually mean is "if this had infinite time and infinite storage, it would be Turing complete". Shader model 3.0 is still extremely limited in register space and program instruction count, so it fails rather badly when put to any real world test.

请注意，如果允许的话，甚至着色器1.x也可以成为图灵完整版 渲染操作的多次通过.例如，对于 使用重复的渲染到纹理实现生命游戏 操作.在这种情况下，输入和输出纹理可提供较大的 的存储空间量，重复的渲染调用将填写 缺少的迭代构造.但这是作弊，因为 取决于CPU发出渲染调用！

Note that even shader 1.x can become Turing complete if you allow multiple passes of rendering operations. For instance it is trivial to implement the Game of Life using repeated render-to-texture operations. In this case the input and output textures provide a large amount of storage space, and the repeated render calls fills in for the missing iteration constructs. This is cheating, though, because it is depending on the CPU to issue the render calls!

作为非图灵完整语言的示例: 非图灵完整着色器上的维基百科页面

as an example of non-turing-complete languages: Wikipedia Page on non-turing-complete Shaders

通常它取决于着色器语言(和您的Turing-complete要求)，但是我认为大多数最新的着色器语言可以称为Turing complete(如果我们忽略有限内存的任何限制)，因为它们可以循环并读取/写入变量

Generally it depends on shader language (and Your Turing-complete requirements), but I think that most recent shader languages can be called Turing complete (if we ignore any limitations of finite memory) bacause they can loop and read/write variables.

编辑:

如果我误解了您的问题，并且您将着色器称为着色器处理单元(如Cuda核心)，那么我认为不应将图灵完整或不完整类别视为单个核心. GPU不仅建立在内核上.回答您的问题，您可以使用任意数量的cuda内核对GPU进行编程，以通过任意输入计算任意函数".

If I misunderstood Your question and You mean shader as shader processing unit (like Cuda core) then I think that single core should not be considered in category of Turing complete or not complete. GPU is not only built up on cores. Answering Your question you can program GPU with any number of cuda cores to "compute an arbitrary function over arbitrary inputs".

这篇关于GPU着色器Turing是否已完成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！