Реализация эффективных алгоритмов сортировки с использованием OpenCL

Контекст: Реализация многих высокоуровневых эффективных алгоритмов полагается в своей основе на примитивные «строительные» блоки, такие как параллельная редукция, сортировка, слияние, префиксная сумма, и т.д. OpenCL является открытым стандартом для программирования параллельных вычислений. Но в силу кросс-платформенности и меньшей популярности, для данного стандарта отсутствует устойчивая, полноценная, современная реализация озвученных ранее примитивов.

Цель: Реализовать эффективные алгоритмы для параллельной сортировки с использованием OpenCL.

Задачи:

• Исследовать существующие ad-hoc решения
• Изучить и реализовать state of art алгоритмы для параллельной сортировки.
• Внедрить ad-hoc оптимизации в реализованные алгоритмы, снижение числа аллокаций, упаковка данных, снижение количества dispatch вызовов, понижение битности, точности, использование локальной памяти, обобщение типов элементов
• Исследовать производительность реализации на Nvidia, Intel, Amd устройствах, сравнить производительность с reference решениями.
• Внедрить решение в spla проект.
• Оформить как stand-alone библиотеку.

Алгоритмы:

• сортировка
• сортировка ключ-значение
• сортировка участков
• сортировка с произвольными значениями

Публикации:

• Публикация на тематической конференции
• Публикация в журнале open-source разработок

Технологии:

• С++
• OpenCL
• Python
• CMake