Программирование массивно-параллельных архитектур без API на примере параллельного алгоритма построения дерева

В работе предлагается подход к программированию параллельных архитектур без использования интерфейсов параллельного программирования (API) и параллельных директив для различных приложений численного моделирования и компьютерной графики. Основная цель этого подхода — разрешение фундаментального противоречия между кросс-платформенностью и аппаратным ускорением при разработке высокопроизводительных программ. Это противоречие разрешается путём автоматизации процесса разработки: алгоритмическое описание на С++, лишённое каких-бы то ни было специфичных параллельных конструкций, автоматически транслируется в реализацию того же самого алгоритма и генерируется реализация на некотором существующем API программирования параллельных архитектур (C++ транслируется в SPIR-V для GPU, и в векторные инструкции для CPU). Далее, при необходимости добавления специфического аппаратного ускорения программист может заместить отдельные части сгенерированного кода при помощи замены ядер и замещения виртуальных функций в сгенерированном коде. Такое замещение позволяет перегенерировать код и не потерять изменения, сделанные пользователем под конкретную аппаратную платформу. Разработанная система работает как белый ящик, позволяя программисту читать и отлаживать сгенерированный код также, как если бы этот код был написан вручную. Это позволяет нам легко отличать ошибки транслятора от ошибок пользователя и, кроме того, не создаёт зависимости в проектах от разработанной системы. Применение разработанной технологии рассматривается на примере одной из самых сложных и неудобных для GPU задач — параллельные алгоритмы построения деревьев.