Я выложил на Github новый проект A Simple GPU Hash Table.
Это простая хэш-таблица для GPU, способная обрабатывать в секунду сотни миллионов вставок. На моём ноутбуке с NVIDIA GTX 1060 код вставляет 64 миллиона случайно сгенерированных пар ключ-значение примерно за 210 мс и удаляет 32 миллиона пар примерно за 64 мс.
То есть скорость на ноутбуке составляет примерно 300 млн вставок/сек и 500 млн удалений/сек.
Таблица написана на CUDA, хотя ту же методику можно применить к HLSL или GLSL. У реализации есть несколько ограничений, обеспечивающих высокую производительность на видеокарте:
- Обрабатываются только 32-битные ключи и такие же значения.
- Хэш-таблица имеет фиксированный размер.
- И этот размер должен быть равен двум в степени.
Для ключей и значений нужно зарезервировать простой разграничивающий маркер (в приведённом коде это 0xffffffff).
Читать полностью »