сравнить-и-обменять: для выбранных двух позиций в массиве производится сравнение элементов, и, если они нарушают порядок сортировки, происходит их обмен. В GPU, как мы помним, определение новых значений массива выполняется независимо, поэтому каждое сравнение приходится делать дважды. Но и это еще не все. Выбор позиций для очередной операции сравнить-и-обменять в быстрых последовательных алгоритмах зависит от результата сравнения в предыдущих операциях. К счастью, в теории параллельных вычислений уже разработана тема сортирующих сетей, которую можно адаптировать для GPU. Количество операций, выполняемых параллельным алгоритмом, больше, чем у лучших последовательных алгоритмов, и их отношение растет с ростом массива. Тем не менее, благодаря своей мощи, современные GPU не уступают в скорости сортировки, хотя о существенном ускорении речь пока не идет.
Остальные алгоритмы конвертируются как-то аналогично или строятся на основе приведенных. Труднее всего GPU даются сложные структуры данных: списки и деревья, особенно их модификация. Поверьте (а если не хотите верить – пройдитесь по ссылкам сами), что придумано множество других любопытных способов переноса, казалось бы, неподходящих расчетов на GPU, включая, например, работу с разреженными матрицами. Но они уже выходят за рамки популярной статьи.
Заметьте, что в последних трех примерах достижение результата на GPU потребовало использования большего объема памяти, чем понадобилось бы на машине классической архитектуры. Добавьте к этому более высокую производительность GPU, выливающуюся в потенциальную способность перемалывать бОльшие объемы данных, и вы поймете, почему размер видеопамяти так высоко ценится среди расчетчиков. В этом вопросе проступает болезненное расхождение с другими пользователями, которые твердо знают, что для компьютерных игр памяти на графической плате много не надо.
Если говорить о ближайшем будущем самих чипов, то здесь все замечательно. Год за годом GPU прибавляют в скорости работы куда быстрее, чем CPU, увеличивая и без того немалый отрыв. Поколения графических чипов тоже сменяются куда чаще. Даже для непрофессионального использования уже некоторое время предлагается устанавливать в компьютер две видеокарты (технологии SLI или Crossfire). Можно будет использовать вторую плату исключительно как сопроцессор для расчетов, полностью освободив ее от обработки графики. Радужные перспективы GPGPU способны поблекнуть только из-за недостаточной программной поддержки.
Неспособность центрального процессора в одиночку справляться с возникающими вычислительными задачами – секрет Полишинеля. Раньше всего это стало очевидно в машинной графике. В результате за прошедшие годы сформировался стандартный современный графический сопроцессор GPU. Сейчас речь заходит о создании других аппаратных акселераторов, в том числе и для игровых целей [Например, скоро вы можете столкнуться с невозможностью запустить игру без еще одного, на сей раз физического процессора:www.ageia.com/products/physx.html]. Но под каждое приложение свою «железку» не выпустишь, куда как интереснее увидеть нераскрытые возможности GPU, находящегося внутри почти каждого персонального компьютера.
Самое чудное во всей этой истории то, что GPU – а по сути суперкомпьютер на чипе – стал массовым продуктом не благодаря целенаправленной и продуманной стратегии ученых мужей, а скорее случайно – как побочное явление индустрии развлечений.
Одно дело – лицезреть графики ускорения на страницах чужих статей, и совсем другое – убедиться в этом самостоятельно. Не случайно ведь пользуются широкой популярностью такие тесты, как 3DMark и Doom 3. Ничего подобного им по удобству и авторитетности в области вычислений на GPU пока не существует. Можно упомянуть разве что пакет GPUBench из Стэнфордского университета, но он предназначен для сравнения GPU только между собой и содержит лишь синтетические тесты вроде скорости выполнения одной инструкции, повторенной многократно. Более того, далеко не каждую найденную программу для GPU вообще удается запустить из-за ориентации ее авторов на конкретного производителя[Если вы читали статью сначала, то легко угадаете какого. К сожалению, неполная совместимость GPU еще не изжита окончательно] графических чипов. Поэтому я решил подойти к проблеме творчески и предложить самодельный набор тестов [Исходные тексты и исполняемые файлы http://jorik.sourceforge.net], а заодно убедить вас, что работа с GPU не так уж и сложна, как может показаться.
Тест 1. Решается динамическая задача распространения звуковых волн в двухмерном пространстве (см. рис.) при помощи простейшей разностной схемы на сетке 1536x1536. Как уже было сказано, такого рода задачи идеально подходят для GPU. Результат неудивителен – GPU может справиться с заданием в десять с лишним раз быстрее (табл. 1).
Примечательно другое. Во-первых, расстановка плат по производительности в играх и в неграфических приложениях может сильно отличаться. Во-вторых, на бюджетной плате ATI Radeon 9600 установлена такая же обычная память, что и на многих системных платах: 200 МГц DDR SDRAM 128 бит (аналог двухканального режима). Оказывается, огромное ускорение может быть получено даже без быстрой и дорогой графической памяти топовых моделей!
Тест 2. Любопытно также рассмотреть другую крайность – «неудобную» для GPU задачу. Производится сортировка массива из 16 млн. действительных чисел. Здесь CPU выполняет алгоритм быстрой сортировки (STL quick sort), GPU – параллельной битонической сортировки (см. выше). В результате разного количества операций в алгоритмах быстрая видеокарта лишь приближается к центральному процессору (табл. 2).
Тест 3. Исследуется скорость копирования многомегабайтной текстуры, где каждый пиксел содержит четыре 32-битных действительных числа, из системной памяти в видеопамять и обратно. Эта скорость важна, потому что она определяет, какие задачи имеет смысл доверять GPU. Если задача проста, то преимущество GPU может быть нивелировано временем передачи данных к нему. Поэтому выгода получается только на крупных задачах, обсчет которых занимает гораздо больше времени, нежели пересылка данных. Результаты[Их достоверность перепроверялась пакетом GPUBench, скорость для платы nVidia близка к данным презентации 'Interactive Geometric Computations using Graphics Processors'] теста оказались просто обескураживающими (табл. 3).
Эти скорости не только ниже 4 Гбит/с шины PCI-Express, но, пожалуй, и самых первых версий AGP. Хочется надеяться, результаты столь низки оттого, что современным играм не приходится часто выполнять копирование больших текстур, особенно описанного формата, и мы имеем дело всего лишь с временной недоработкой драйверов.
До проведения тестирования предполагалось, что использующие GPU программы практически не будут загружать центральный процессор. Действительность оказалась не такой радужной. Нагрузка была очень высокой, доходя до 100%, так что даже окошки по экрану перетаскивались с трудом. Эффект наблюдался и для DirectX-, и для OpenGL-приложений. И еще нельзя не отметить, что плата ATI при большей сетке в первом тесте и при некоторых других обстоятельствах приводила к синему экрану смерти – это уж совсем никуда не годится.
ТЕМА НОМЕРА: По ту сторону треугольников
Приблизительно так можно перевести с английского «Beyond Triangles» – название последней главы замечательной книги «GPU Gems». Она одной из первых рассказала массовому читателю о возможности использовать графический процессор для чего-то большего, нежели рендеринг составленных из треугольников моделей. Тогда это были главным образом научные расчеты: динамика жидкостей, визуализация результатов объемного сканирования, расчет стереограмм и т. д. Однако за прошедшие несколько лет ситуация радикально изменилась: на GPU были перенесены все классические алгоритмы и разработан целый ряд новых, максимально использующих преимущества, даваемые архитектурой современных видеокарт. Техника GPGPU[General-Purpose Computation on GPUs, вычисления общего назначения на графических процессорах] становится по-настоящему general-purpose, универсальной, подходящей для решения практически любых задач. Мне, как большому энтузиасту этой области
