Я читал, что кодирование Хаффмана не работает на GPU, но в этом документе утверждается иначе

Question

Я читал в нескольких местах, что построение кодера Хаффмана в GPU не очень эффективно, потому что алгоритм последовательный. Но эта статья предлагает возможную реализацию и утверждает, что она работает быстрее, чем CPU http://tesla.rcub.bg.ac.rs/~taucet/docs/papers/PAVLE-AnaBalevic09.pdf.

Пожалуйста, советуйте, если результаты статьи неверны

Answer 1

Это выглядит как интересный подход, но я просто предложу одну оговорку: очень мало информации о базовой реализации ЦП, но, скорее всего, она однопоточная и, возможно, не особенно оптимизирована. Люди хотят, чтобы их оптимизированная реализация выглядела настолько хорошо, насколько это возможно, поэтому они склонны использовать посредственные базовые показатели, чтобы обеспечить впечатляющий коэффициент ускорения. Из всего, что мы знаем, может случиться так, что надлежащим образом оптимизированная многопоточная реализация на ЦП может соответствовать производительности GPGPU, и в этом случае реализация GPGPU не будет столь впечатляющей. Прежде чем вкладывать большие усилия в реализацию GPGPU, я хотел бы сначала исчерпать все возможности оптимизации ЦП (возможно, даже используя параллельный алгоритм, как описано в статье, возможно, использовать SIMD, многопоточность и т. Д.), Поскольку реализация ЦП, которая удовлетворение ваших требований к производительности будет гораздо более портативным и полезным, чем решение, связанное с конкретной архитектурой графического процессора.

Answer 2

Вы правы - алгоритм Хаффмана последовательный, хотя и не является узким местом для высокоскоростного кодирования. Пожалуйста, посмотрите на следующую сессию GTC 2012 . Это реальное решение, а не просто пример.

Вы можете найти там некоторые тесты для CPU и GPU, касающиеся кодирования и декодирования Хаффмана. Кодирование Хаффмана на GPU намного быстрее, чем на CPU. Декодирование JPEG на GPU может быть намного медленнее по сравнению с CPU только в том случае, если в изображении JPEG нет маркеров перезапуска.

Если вам нужен Хаффман не для JPEG, то следует использовать двухпроходный алгоритм. На первом проходе можно собирать статистику и выполнять кодирование на втором проходе. Оба прохода могут выполняться параллельно, поэтому лучше использовать графический процессор вместо центрального процессора.

Есть много газет, в которых говорится, что GPU не подходит для Хаффмана. Это просто означает, что было много попыток решить проблему. Идея решения довольно проста: используйте кодирование Хаффмана для небольших порций данных и попробуйте обрабатывать их параллельно.