Требования к задачам и "методология"


Требования к задачам для их эффективного решения

Современные ГПУ являются достаточно универсальным инструментом, так что с их помощью можно решать практически любые вычислительные задачи. Однако далеко не все задачи можно решать эффективно. Для того, чтобы задача могла быть эффективно решена на ГПУ, она должна удовлетворять ряду свойств, которые вытекают из особенностей архитектуры:

  • Высокая вычислительная мощность. Объем вычислений должен значительно превышать объем необходимых данных, в противном случае вычисления на ГПУ не покроют даже накладных расходов на пересылку входных данных и результатов.
  • Большой размер вычисляемого массива. Запуск прохода - достаточно дорогая операция, более того, при малом размере массива не будет достаточного числа потоков для покрытия расходов на чтение из памяти.
  • Возможность независимого вычисления целевых элементов на каждом из проходов. Это требование напрямую вытекает из отсутствия возможностей синхронизации.
  • Массивы данных, используемые при вычислении, должны целиком помещаться в видеоОЗУ. Это сразу следует из медленного обмена между ОЗУ и видеоОЗУ.

Потоковое программирование

Термин "потоковое программирование" часто используется при программировании ГПУ, хотя сам метод может применяться и на обычных архитектурах. Свое начало он берет от конвейера в ОС UNIX и устроен аналогично. Подход предполагает организацию алгоритма в виде набора ядер - относительно небольших операций, обрабатывающих элементы данных. Ядра обмениваются данными при помощи потоков, состоящих из элементов данных. На каждом шаге работы ядро берет по одному элементу данных из каждого своего входного потока, выполняет их обработку и выдает один или несколько элементов данных в выходной поток. Как правило, ядро не имеет внутреннего состояния, т.е. различные элементы данных обрабатываются независимо.

На рисунке приведен алгоритм извлечения карт глубины из стереоизображения, представленный в виде набора ядер и потоков.

К программированию ГПУ потоковое программирование стало применяться с первыми работами по ОВГПУ. Шейдеры тогда были маленькими (не более 32 команд), и в них можно было выполнить только очень небольшой объем работ. Для реализации больших алгоритмов их требовалось сначала разделить на ядра. Каждое ядро затем реализовывалось в виде отдельного шейдера, а в качестве потоков данных использовались текстуры ГПУ. Такой подход позволял реализовать сложные алгоритмы обработки даже на старых ГПУ, возможности программирования которых были существенно ограниченными.

С расширением возможностей программирования ГПУ подход сохранился, однако ядра стали более сложными. Следует заметить, что потоковое программирование - это лишь подход, он не предполагает определенной технологии программирования. Сами ядра могут быть реализованы на шейдерном языке, специализированной низкоуровневой технологии или языке потокового программирования. Примером такого языка является Brook.

Методология решения задач на ГПУ

  1. Создание программы для центрального процессора для решения задачи. Можно использовать любые известные языки программирования - C/C++, C#, Java, FORTRAN и т.д.
  2. Выделение вычислительно интенсивных участков программы (ядер). Для этого можно использовать профилировщик, понимание структуры программы, а также любые другие соображения.
  3. Определение оправданности переноса конкретных ядер на ГПУ. Для этого можно использовать приведенные выше требования к программам, которые могут быть эффективно реализованы на ГПУ. В ряде случаев выполнение этих требований очевидно. Некоторые ядра (например, умножение матриц) уже реализованы на ГПУ. Если выполняются не все требования, можно попытаться перестроить ядро. Например, если данные не помещаются в видеоОЗУ целиком, можно попытаться разбить их на части. Как правило, потребуется создание прототипа ядра для ГПУ для оценки эффективности решения задачи.
  4. Рефакторинг исходной программы. Каждое ядро, перенесение которого на ГПУ оправдано, выделяется в отдельную функцию. Сама функция реорганизуется таким образом, чтобы в ней не было побочных эффектов, а также массивов, разделяемых с другими частями программы. Во избежание лишних пересылок может понадобиться перенос на ГПУ не только самого ядра, но и смежного кода, перенос которого без самого ядра не оправдан.
  5. Выбор технологии программирования ГПУ. Если имеется готовая библиотека, реализующая необходимую функциональность на ГПУ, имеет смысл ей воспользоваться. Сейчас таких библиотек немного, но их начинает появляться все больше. Некоторые замечания по выбору технологии программирования:
    1. Графические технологии программирования следует использовать только в том случае, если эти же технологии используются для написания остальной части приложения. В других случаях лучше выбирать между низкоуровневыми технологиями и потоковыми библиотеками.
    2. Низкоуровневые технологии программирования привязаны к конкретному типу ГПУ. Если планируется поддержка ГПУ различных производителей, придется писать две версии одного и того же ядра. Нужно быть хорошо знакомыми с архитектурой конкретного ГПУ, поскольку все оптимизации возлагаются на программиста. С другой стороны, поскольку все они используют C-подобные языки, их можно использовать для быстрого создания прототипа с дальнейшей оптимизацией. Существуют ограниченные средства отладки.
    3. Потоковые библиотеки. Обладают ограниченной переносимостью, как правило, с потерей эффективности, иногда очень сильной. В зависимости от задачи, могут понадобиться частично различающиеся версии ядер для разных архитектур. Программа пишется в терминах средств метапрограммирования, обычные функции языка, как правило, использоваться не могут. Большинство оптимизаций возлагаются на программиста. Существуют ограниченные средства отладки.
    4. Высокоуровневые языки и технологии программирования. Программа пишется на высокоуровневом языке в понятных пользователю терминах. Система автоматически синхронизирует данные, выбирает формат их представления, выполняет оптимизацию кода и т.д. Основной недостаток - таких подходов пока мало, а те, что существуют (см. C$), находятся в стадии разработки. Кроме того, при использовании таких средств программист лишается непосредственного контроля над использованием аппаратуры.
  6. Реализация ядра на ГПУ при помощи выбранной технологии программирования. Здесь все понятно.
  7. Дальнейшая оптимизация производительности ядра, если она не устраивает.

© Лаборатория Параллельных информационных технологий НИВЦ МГУ
Rambler's Top100