Можно ли добиться декодирования Хаффмана в GPU?

У нас есть база данных, закодированная с кодировкой Хаффмана. Целью здесь является копирование на графическом процессоре с соответствующим декодером; затем на графическом процессоре, декодировать базу данных и делать вещи в этой декодированной базе данных без копирования ее на CPU.

Я далек от специалиста Хаффмана, но немногие, кого я знаю, показывают, что это, по-видимому, алгоритм, основанный на контрольных структурах. С основным алгоритмом я боюсь, что будет много сериализованных операций.

Мои 2 вопроса:

Знаете ли вы, существует ли какая-либо эффективная версия GPU для кодирования Хаффмана.
Если нет, вы думаете, что существует алгоритм Хаффмана, который адаптируется к GPU (т.е. с меньшими структурами управления). Или, может быть, вы знаете (и вы могли бы предоставить ссылку), что эффективное декодирование Хаффмана не может быть эффективным на GPU.

Я вижу другие ограничения, но они не критичны: - GPU не может быть очень эффективным для обработки дерева: двоичное дерево может храниться в классическом массиве - рабочая нагрузка может быть трудно сбалансировать: мы увидим после

Ответ 1

Проблема с кодировкой Хаффмана заключается в том, что вы не можете перемотки вперед. т.е.: вы должны декодировать по частям, линейно.

Как таковой, он не идеален для parallelism.

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

Ответ 2

Я удивлен очевидным консенсусом в отношении того, что Хаффман на графическом процессоре невозможно.

Я обращаюсь к афоризму: "Если это произойдет, это должно быть возможно". (по-разному приписываются Агате Кристи, Альберту Эйнштейну и т.д.)

Так как SuperXero делает Huffman на GPU, я полагаю, это должно быть возможно.

Сбой процессора huffman быстрее после первого выполнения? (SuperXero)

Google: дефрагментация hubman GPU

Ответ 3

Да, вы можете делать декодирование huffman параллельно, и поэтому вы можете получить преимущества в GPU - при условии, что память не является проблемой.

В следующем обсуждении я расскажу о дереве хаффмана и выходе huffman - вывод - это сжатые символы, которые нужно искать в дереве huffman, который нужно декодировать.

Алгоритм huffman требует, чтобы у вас было дерево huffman для декодирования - это дерево может быть большим. Вы можете обойти это, используя небольшое дерево хаффмана, которое подходит для локальной памяти в графическом процессоре, но это повлияет на эффективность сжатия алгоритма. Например. вы можете ограничить дерево лучшими 2 ^ n узлами столько, сколько позволяют ваши процессоры gpu. (например, использовать дерево ограничено, чтобы сказать 1024 узла.

Если вы не ограничиваете дерево huffman таким, что вы можете поместить одну копию в локальное хранилище на каждом gpu, тогда вы действительно не получите parallelism, который вы ожидаете, потому что все процессоры gpu будут заблокированы для доступа к памяти все чтение то же общее дерево.

Вывод huffman символов упаковывается в переменное количество бит. Нет никакого способа, если вы начнете посередине вывода, чтобы узнать, находитесь ли вы на символе boudary. Но вы можете создать свои собственные границы. Например, в выводе вы можете просто заставить выравнивание символов каждые x слов выравниваться по слову. Затем вы знаете, что вы можете начать декодирование на любом кратном x слова на выходе и отправить этот блок на обработку графического процессора node вместе с соответствующим деревом.

Вам не нужно использовать только одно дерево, но одно дерево на блок может быть слишком велико. То есть, если у вас есть одно дерево на блок, вы сильно сократите эффективность сжатия, если блоки будут небольшими.

Итак, вы можете попробовать посмотреть на сходство блоков и закодировать аналогичные блоки с одним и тем же деревом и сохранить индекс дерева для каждого блока. Например. вы можете иметь 10000 блоков на выходе, но всего 50 1024 - node деревьев. Затем вы отправляете один блок и одно дерево для каждой обработки графического процессора node для параллельного декодирования.

Ключ к быстрому выполнению заключается в том, что каждая обработка графического процессора node работает только в локальной памяти.