Да, вы можете выполнять декодирование Хаффмана параллельно, и поэтому вы можете получить преимущества в графическом процессоре — при условии, что память не является проблемой.
Для дальнейшего обсуждения я расскажу о дереве Хаффмана и выводе Хаффмана — вывод представляет собой сжатые символы, которые нужно искать в дереве Хаффмана для декодирования.
Алгоритм Хаффмана требует, чтобы у вас было дерево Хаффмана для декодирования — это дерево может быть большим. Вы можете обойти это, используя небольшое дерево Хаффмана, которое помещается в локальную память графического процессора, но это повлияет на эффективность сжатия алгоритма. Например. вы можете ограничить дерево лучшими узлами 2 ^ n настолько, насколько позволяют ваши процессоры GPU. (например, используйте дерево, ограниченное, скажем, 1024 узлами.
Если вы не ограничите дерево Хаффмана таким образом, чтобы вы могли поместить одну копию в локальное хранилище на каждом графическом процессоре, вы не получите ожидаемого параллелизма, потому что все процессоры графического процессора будут заблокированы при доступе к памяти, и все они будут читать одно и то же общее дерево.
Хаффман выводит символы, упакованные в переменное количество битов. Если вы начнете с середины вывода, вы не сможете узнать, находитесь ли вы на границе символа. Но вы можете создать свои собственные границы. Например, в выводе вы можете просто принудительно выровнять символы через каждые x слов, чтобы они были выровнены по словам. Тогда вы знаете, что можете начать декодирование любого слова, кратного x в выходных данных, и отправить этот блок на узел обработки графического процессора вместе с соответствующим деревом.
Вам не обязательно использовать только одно дерево, но одно дерево на блок также может быть излишним. То есть, если у вас есть одно дерево на блок, вы сильно сократите эффективность сжатия, если блоки маленькие.
Таким образом, вы можете попробовать посмотреть на сходство блоков и закодировать похожие блоки одним и тем же деревом и сохранить индекс дерева для каждого блока. Например. у вас может быть 10000 блоков на выходе, но всего 50 деревьев с 1024 узлами. Затем вы отправляете один блок и одно дерево на каждый узел обработки GPU для параллельного декодирования.
Ключ к тому, чтобы сделать это быстрым, заключается в том, что каждый узел обработки графического процессора работает только с локальной памятью.
person
Rafael Baptista
schedule
10.10.2012
