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

Question

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

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

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

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

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

Answer 1

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

Как таковой, он не идеален для параллелизма.

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

Answer 2

Да, вы можете выполнять параллельное декодирование Хаффмана и получить преимущества в графическом процессоре - при условии, что память не является проблемой.

Для обсуждения ниже я расскажу о дереве Хаффмана и Хаффманеoutput - выходные данные - это сжатые символы, которые необходимо найти в дереве Хаффмана для декодирования.

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

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

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

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

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

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

Answer 3

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

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

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

Сжатие процессора Хаффмана быстрее после первого выполнения? (SuperXero)

Google: декомпрессия Хаффмана с помощью графического процессора