Компьютерра - Журнал «Компьютерра» № 13 от 04 апреля 2006 года

Сейчас мы уже знаем, что GPU способен применять одинаковую программу для вычисления значения каждого элемента одного массива, основываясь на данных других массивов. Есть ли алгоритмы, которые формулируются именно таким образом? Оказывается, есть. К этому классу относятся, например, методы фильтрации изображений и часть способов приближенного решения дифференциальных уравнений, отражающих динамические явления физики. Именно такие алгоритмы проще всего переносятся на GPU, и именно на них достигается наибольшее ускорение.

Давайте рассмотрим что-нибудь посложнее. Задача редукции массива заключается в нахождении какой-то скалярной функции его элементов. Это может быть сумма всех чисел массива, или величина максимума, или что-то в том же духе. Поскольку шейдер ограничен в количестве операций, за один проход рендеринга решить задачу решительно невозможно. Применяется следующий способ. Порождается вспомогательная текстура, размерами чаще всего вдвое меньше исходной по обеим осям. Используемый шейдер, заполняя ее, вычисляет функцию только от четырех величин. Затем вспомогательная текстура назначается на вход шейдера, а выходом служит еще вчетверо меньшая текстура. И так до получения текстуры из одного пиксела, которая содержит ответ (рис. 5). Число проходов составляет логарифм от начального размера массива.

Умножить матрицу на вектор при ограничениях Shader Model 2.0 тоже не так-то просто. Одно из определений гласит, что произведение является линейной комбинацией столбцов исходной матрицы, взятых с весами из второго сомножителя. Поступают таким образом. На первом шаге каждый элемент матрицы умножается на соответствующий ему вес — получается вторая матрица. Последующие шаги посвящаются комбинированию столбцов — редукции только по горизонтали.

Еще интереснее дела обстоят с сортировкой массива. Сразу понятно, что в случае с GPU понадобится второй вспомогательный массив из-за невозможности выполнять чтение и запись одновременно с одним массивом. Но на этом сложности не кончаются. Алгоритмы сортировки основываются на операции сравнить-и-обменять: для выбранных двух позиций в массиве производится сравнение элементов, и, если они нарушают порядок сортировки, происходит их обмен. В GPU, как мы помним, определение новых значений массива выполняется независимо, поэтому каждое сравнение приходится делать дважды. Но и это еще не все. Выбор позиций для очередной операции сравнить-и-обменять в быстрых последовательных алгоритмах зависит от результата сравнения в предыдущих операциях. К счастью, в теории параллельных вычислений уже разработана тема сортирующих сетей, которую можно адаптировать для GPU. Количество операций, выполняемых параллельным алгоритмом, больше, чем у лучших последовательных алгоритмов, и их отношение растет с ростом массива. Тем не менее, благодаря своей мощи, современные GPU не уступают в скорости сортировки, хотя о существенном ускорении речь пока не идет.

Остальные алгоритмы конвертируются как-то аналогично или строятся на основе приведенных. Труднее всего GPU даются сложные структуры данных: списки и деревья, особенно их модификация. Поверьте (а если не хотите верить — пройдитесь по ссылкам сами), что придумано множество других любопытных способов переноса, казалось бы, неподходящих расчетов на GPU, включая, например, работу с разреженными матрицами. Но они уже выходят за рамки популярной статьи.

Заметьте, что в последних трех примерах достижение результата на GPU потребовало использования большего объема памяти, чем понадобилось бы на машине классической архитектуры. Добавьте к этому более высокую производительность GPU, выливающуюся в потенциальную способность перемалывать бОльшие объемы данных, и вы поймете, почему размер видеопамяти так высоко ценится среди расчетчиков. В этом вопросе проступает болезненное расхождение с другими пользователями, которые твердо знают, что для компьютерных игр памяти на графической плате много не надо.

Если говорить о ближайшем будущем самих чипов, то здесь все замечательно. Год за годом GPU прибавляют в скорости работы куда быстрее, чем CPU, увеличивая и без того немалый отрыв. Поколения графических чипов тоже сменяются куда чаще. Даже для непрофессионального использования уже некоторое время предлагается устанавливать в компьютер две видеокарты (технологии SLI или Crossfire). Можно будет использовать вторую плату исключительно как сопроцессор для расчетов, полностью освободив ее от обработки графики. Радужные перспективы GPGPU способны поблекнуть только из-за недостаточной программной поддержки.