Шаги, связанные с кодировкой Хаффмана, довольно последовательны. Итак, мне было интересно, как я могу ввести параллелизм при реализации кодировки Хаффмана на любых платформах, поддерживающих параллельную реализацию, таких как графические процессоры, многоядерные процессоры и т. Д.?Есть ли способ распараллеливать реализацию кодировки Хаффмана на аппаратном обеспечении?
На основе быстрого поиска по поиску в поисковых запросах возможно кодирование Хаффмана, и документы датируются десятилетиями назад.
Я не готов ни один из них (просто взял короткий взгляд, чтобы понять уместность).
Вот small blog post on the topic где парень утверждает, что:
хотя параллельно Хаффман декодирование не должно быть трудно, если у нас есть достаточно большое количество процессоров, и мы предполагаем, что время связи между процессорными элементами является очень короткий.
Спасибо. Вы правы, есть несколько способов реализовать декодер Хаффмана параллельно, но вряд ли какая-либо статья говорит о параллельной реализации кодировщика. – beginner
многожильных/несколько процессоров:
Это можно распараллелить кодирование Хаффмана с использованием многоядерных процессоров. Основная идея состоит в том, чтобы просто разделить поток источника на куски, назначить кусок каждому процессору, параллельно закодировать куски в отдельные промежуточные буферы, а затем объединить закодированные результаты от промежуточных буферов (которые будут иметь разную длину) в конечный выходной буфер.
Одним из осложнений является то, что, поскольку кодировка Хаффмана использует коды различной длины бит, каждый фрагмент, скорее всего, не будет кодировать бит поток целых байтов. Это означает, что при конкатенации результатов может потребоваться использование смещения бит для правильного выравнивания вывода одного промежуточного буфера с выходом предыдущего. Например, если буфер A произвел результат 150 байтов и 3 бита в длину, то при копировании буфера B данные должны быть сдвинуты на 3 бита, причем 5 бит байта и 3 бита следующего из промежуточного буфера соединены вместе чтобы каждый байт записывался в выходной буфер.
Обходным путем для этого является использование особенностей выходного формата. Например, если вы являетесь данными изображения кодирования Хаффмана для формата JPEG, вы можете вывести маркер перезапуска JPEG в начале каждого фрагмента, который вы записываете в выходной буфер, чтобы выровнять поток до границы байта. Согласно спецификациям JPEG этот маркер предназначен для параллельного декодирования, но он также упрощает параллельное кодирование.
Многопоточность
Предположим, у вас есть поток источника данных 100Кб и 4 процессоров. Самое простое - просто разбить его на куски по 25 Кб каждый, но это может привести к худшему сценарию, когда первый кусок является последним для завершения кодирования, поэтому все остальные процессоры должны его ждать, потому что второй кусок не может быть записан в выходной буфер до тех пор, пока не будет известна длина первого фрагмента.Чтобы избежать этого, разделите входной поток на более мелкие куски, доводя данные до доступных процессоров по принципу «первым пришел-первым-обслужен», причем каждый процессор записывает содержимое промежуточного буфера в выходной буфер, как только он будет завершен и все более ранние фрагменты завершили кодирование (так, что известен индекс для записи в выходной буфер), а затем назначается следующий доступный фрагмент во входном потоке.
Вам нужно будет синхронизировать доступ к индексу чтения входного буфера и записать индекс выходного буфера, но не синхронизировать доступ к самому выходному буфере. Например, как только процессор завершен, он может (используя синхронизацию потоков) считывать индекс выходного буфера, чтобы знать, с чего начать писать, затем (по-прежнему используя синхронизацию потоков) обновляет индекс, основываясь на размере данных, которые он собирается записать, и затем (больше не используя синхронизацию) начинают писать. Таким образом, один и тот же процессор может сразу записывать в выходной буфер. Аналогичную схему можно использовать для входного буфера.
GPU и аппаратное ускорение
Я не знаю какой-либо простой схемы для использования графических процессоров для кодирования Хаффмана. В общем, графические процессоры очень хороши в операциях, которые читаются с неравномерно расположенных точек памяти и записываются в постоянно разнесенные ячейки памяти, но не наоборот (именно поэтому смещение является настолько сложным, например). Поскольку кодировка Хаффмана является примером последнего, она не очень хорошо подходит для ускорения на основе графического процессора. Однако есть особые аппаратные решения проблемы, например, используемые в аппаратных ускоренных видеокодерах, которые можно найти на многих мобильных телефонах.
Когда вы говорите «в аппаратных средствах», вы имеете в виду дизайн архитектуры системы/чипа/независимо от того, чтобы она была предназначена для запуска Хаффмана параллельно? – Daniel
Ну, я имею в виду проектирование аппаратной архитектуры, включающей параллелизм для реализации кодировки Хаффмана в системе, которая поддерживает параллельную реализацию, такую как GPU, многоядерный процессор и т. Д. В принципе, я хочу ввести параллелизм в архитектуре для кодировки Хаффмана, шаги которой довольно последовательны. – beginner
Я все еще смущен. Вы говорите «на оборудовании» в названии, но «в системе, которая поддерживает параллельную реализацию» в комментарии. Итак, вы спрашиваете о 1) создании параллельной реализации Huffman Encoding на компьютере, уже способном работать параллельно или 2) создании аппаратной архитектуры, специально разработанной для одновременного запуска Huffman? – Daniel