#shader #gpu #gpgpu #computation-theory
#шейдер #графический процессор #gpgpu #теория вычислений
Вопрос:
Я понимаю, что полные графические процессоры — это гиганты вычислений, включая каждый шаг вычисления и память. Итак, очевидно, что графический процессор может вычислять все, что мы хотим — это Turing complete.
Мой вопрос касается одного шейдера на разных графических процессорах («Потоковый процессор» / «Ядро CUDA»):
Завершено ли оно по Тьюрингу?
Могу ли я (теоретически) вычислить произвольную функцию над произвольными входными данными с помощью одного шейдера?
Я пытаюсь понять, в каком «масштабе» вычислительных шейдеров живут.
Комментарии:
1. Если в языке есть if и goto, он является завершенным по Тьюрингу. Скорее всего, все современные поколения поддержки шейдеров тривиально завершены по тьюрингу.
Ответ №1:
Вы имели в виду shader как программу, используемую для вычисления затенения?
В wiki talk я нашел:
(…) Модели шейдеров 1.x и 2.0 действительно не являются завершенными по Тьюрингу, поскольку им не хватает возможности обобщенной итерации (у них есть некоторые ограниченные циклические конструкции, но это эффективно развертывается во время компиляции, поэтому количество итераций должно быть постоянным).
Модель шейдеров 3.0, которая используется в новейшем оборудовании ПК и на Xbox 360, обладает полностью общими возможностями циклирования и является Turing завершенной в теоретическом смысле. Однако это довольно хорошо подчеркивает разницу между теорией и практикой! Когда люди утверждают, что устройство завершено по Тьюрингу, на самом деле они имеют в виду «если бы у этого было бесконечное время и бесконечная память, оно было бы завершено по Тьюрингу». Модель шейдеров 3.0 по-прежнему крайне ограничена в пространстве регистров и количестве команд программы, поэтому она довольно сильно терпит неудачу при выполнении любого реального теста.
Обратите внимание, что даже шейдер 1.x может стать завершенным по Тьюрингу, если вы разрешите несколько проходов операций рендеринга. Например, тривиально реализовать Game of Life, используя повторяющиеся операции рендеринга в текстуру. В этом случае входные и выходные текстуры предоставляют большой объем дискового пространства, а повторяющиеся вызовы рендеринга заполняют недостающие итерационные конструкции. Однако это обман, потому что выполнение вызовов рендеринга зависит от процессора!
в качестве примера языков, не полных по Тьюрингу: Страница Википедии о шейдерах, не полных по Тьюрингу
Обычно это зависит от языка шейдеров (и ваших требований к завершению по Тьюрингу), но я думаю, что самые последние языки шейдеров можно назвать завершенными по Тьюрингу (если мы игнорируем любые ограничения конечной памяти), потому что они могут выполнять цикл и читать / записывать переменные.
Редактировать:
Если я неправильно понял ваш вопрос, и вы имеете в виду шейдер как шейдерный процессор (например, ядро Cuda), то я думаю, что одноядерный процессор не следует рассматривать в категории завершенного или незавершенного по Тьюрингу. Графический процессор построен не только на ядрах. Отвечая на ваш вопрос, вы можете запрограммировать графический процессор с любым количеством ядер cuda для «вычисления произвольной функции по произвольным входным данным».
Комментарии:
1. Да, я спрашивал об одном исполнительном модуле в современном графическом процессоре. Если я предоставлю ему всю необходимую оперативную память (скажем, 2G), сможет ли одна скомпилированная программа для этого шейдера вычислить произвольную функцию (в пределах требований mem)?
2. Графический процессор, использующий одно ядро, дает вам те же «возможности Turing», что и многоядерный графический процессор. Графический процессор построен не только на ядрах. Ядро Cuda является лишь частью многопроцессорного модуля straming, и для запуска GPU требуется больше ресурсов, чем для этого. Для выполнения вашей программы на графическом процессоре вам нужен компьютер с работающим графическим процессором, а не только его часть. Я думаю, что вам следует рассмотреть язык, на котором ваша программа написана как завершенная по Тьюрингу или нет.