Использование GPGPU для сжатия данных (Часть I)

Здравствуй, уважаемое хабра-сообщество.

Многие, наверное, уже слышали о вычислениях на GPGPU(видеокартах), на текущий момент существует много реализаций этой техники программирования. Мы остановимся на двух из них — это небезызвестная CUDA от компании Nvidia, и я думаю чуть менее популярный, но также известный фреймворк OpenCL. На хабре уже есть достаточное количество статей, в которых описан основной принцип работы этих технологий, поэтому мы не будем заострять на этом внимание. В статье я хочу поделиться результатами, полученными при использовании GPGPU в сравнении с CPU для сжатия данных.

Предыстория


Мне всегда были интересны параллельные вычисления, поэтому в институте, в качестве научной работы, я выбрал именно это направление. Когда нужно было выбирать тему дипломной работы, начитавшись разных статей о GPGPU и увеличении производительности, решил что тема диплома будет связанна именно с GPGPU. Пробовать я решил на сжатии данных (вы можете сказать, что это не самая лучшая задача для GPGPU), в качестве алгоритма был выбран статический алгоритм Хаффмана для сжатия данных.

Стандартный алгоритм Хаффмана для сжатия данных


Для тех, кто не знаком с алгоритмом, приведу маленький пример его работы.
Рассмотрим алгоритм на примере следующей последовательности символов:
aaaaaaaccaabccbbbb
Шаг 1:
Необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII.
Для нашего примера частота вхождения символов соответственно равна:
a — 9, b — 5, c — 4.
Шаг 2:
После подсчета частоты вхождения каждого символа, необходимо сформировать бинарное дерево, рассмотрим алгоритм построения дерева на примере.
  • Наша последовательность состоит из трех символов, расположим эти символы в порядке убывания их частот: {(a,9), (b,5), (c,4)}.
  • На следующей строке запишем набор, полученный из предыдущего следующим образом:
    -вместо двух последних символов с их частотами запишем новый элемент, у которого вместо названия символа будет запись «Вершина #n», а вместо частоты — сумма частот последних двух элементов предыдущего набора;
    -отсортируем полученный набор по убыванию.
    {(a, 19), («вершина #1», 9)}.
  • Повторяем предыдущий шаг до тех пор, пока набор не будет состоять только из одного элемента: («вершина #last_number», summa_vseh_chastot):
    {(«вершина #2», 28)}

Мы получили бинарное дерево, где корнем является последняя вершина.
Шаг 3:
Используя полученное дерево, мы можем кодировать файл. Для этого выделяем новые последовательности бит для символов, мы двигаемся вверх по узлам дерева и для каждого правого узла добавляем 1, а для левого 0. В нашем примере символы будут закодированы следующим образом:
a — 0, b — 10, c — 11,
отметим что до сжатия согласно таблице ASCII символы имели вид:
a — 01100001, b — 01100010, c — 01100011.
При кодировании заменяем символы на данные последовательности.
Для возможности декодировать файл мы должны сохранить дерево в файл. Декодирование осуществляется путем прохода по дереву от корня к листьям.

Алгоритм сжатия с использование GPGPU


Программа кодирования логически делится на препроцессор (шаг 1,2 алгоритма) и собственно кодирование (шаг 3). Шаг 1,3 алгоритма были вынесены на GPGPU.
Первые два этапа предобработки являются стандартными при реализации метода Хаффмана:
  1. подсчёт частот, с которыми встречаются различные символы алфавита;
  2. упорядочивание массива частот;

Затем необходимо построить дерево Хаффмана (шаг 2). В нашем случае вместо дерева Хаффмана строится дополнительная структура данных которая содержит:
  1. массив кодов символов;
  2. массив длин кодов символов.

Решение использовать эту структуру данных заменяющую стандартное дерево Хаффмана, было принято, поскольку реализовать полноценное дерево на GPGPU не позволяет ни одна из используемых технологий.
Из всех описанных выше шагов предобработки только подсчёт частот символов зависит от размера входных данных. Остальные этапы предобработки являются элементарными шагами.

Результаты


В качестве языка программирования был выбран С#. Для сравнения эффективности были написаны две версии программы для CPU, CPU(Async) — параллельная версия и CPU(Sync) – последовательная, и две версии для GPGPU (OpenCL и CUDA).

Для тестирования использовалось следующее оборудование:
  • процессор(CPU): AMD PHENOM X4 965 Black Edition;
  • видеокарта: MSI GeForce GTS 450.

Для замера скорости работы программ, были выбраны два файла: один размером 200 МБ (210 596 352 байт), второй 603 МБ (633 128 511 байт). Для измерения времени используются класс Stopwatch(), доступный в языке C#. Точность замера времени зависит от частоты процессора и теоретически на используемом компьютере равна 1/36902109016524975 = 3,0e-16.
Замеры производились по десять раз для каждой версии программы и для каждого файла. На рис. 1-4 представлены графики, демонстрирующие среднее время на основании замеров.

Среднее время выполнения программы на файле размером 200 МБ (без записи)
Рисунок 1.
На этом тесте OpenCL и CUDA превосходят по скорости CPU(Sync) в восемь с половиной раз, а CPU(Async) в два с половиной раза.

Среднее время выполнения программы на файле размером 200 МБ (с записью)
Рисунок 2.
На этом тесте OpenCL и CUDA превосходят по скорости CPU(Sync) в четыре с половиной раза, а CPU(Async) в полтора раза.

Среднее время выполнения программы на файле размером 603 МБ (без записи)
Рисунок 3.
На этом тесте OpenCL и CUDA превосходят по скорости CPU(Sync) в восемь раз, а CPU(Async) в два с половиной раза.

Среднее время выполнения программы на файле размером 603 МБ (с записью)
Рисунок 4.
На этом тесте OpenCL и CUDA превосходят по скорости CPU(Sync) в четыре и три раза, а CPU(Async) в один и три раза.

Заключение


CUDA и OpenCL подтвердили свою эффективность при тестировании в сравнении с CPU.
На основании результатов, можно сделать вывод, что для задач, не использующих большое количество математических расчетов время работы программ написанных с использованием OpenCL равно времени работы программ написанных с использованием CUDA. Во второй части статьи, я расскажу о технических аспектах реализации.
Поделиться публикацией

Похожие публикации

Комментарии 25

    0
    Предваряя техническое описание — возможно ли использование OpenCL и CUDA в «больших» архиваторах типа WinRAR или 7zip.
      0
      Думаю, что какую-то часть операций можно вынести на GPGPU, но на текущий момент написать архиватор с полной поддержкой GPGPU, не возможно в силу особенностей этих технологий. Наверное в будущем это и будет возможно.
      0
      Интересно, а на видеокартах AMD каков прирост будет.
      P.S. если будут исходники/бинарники и инструкция по запуску (если там есть подводные камни), могу потестить на ATI Radeon HD 5770.
        0
        Да во второй части я размещу exe-файл, для запуска нужен будет только .Net 4.0. Подводных камней быть не должно, вам только нужно будет установить драйвера с поддержкой OpenCl.
        0
        Интересно было, все-таки посмотреть на результаты сравнения, если бы алгоритм для CPU был бы написан на C++, все-таки это было бы более справедливо.
          +1
          Вы правы, я уже думал об этом, можно лишь отметить, что Cuda и OpenCl также работают из NET. Ну, если взять лучший вариант для CPU, то время у GPGPU все равно лучше. Также я заметил, что GPGPU работает гораздо быстрее, чем происходит запись в файл, процесс записи в файл одна из долгих операций.
            0
            Вы правы, я уже думал об этом, можно лишь отметить, что Cuda и OpenCl также работают из NET

            Я честно говоря не знаю как с CUDA/OpenCL работать из под .Net, но в любом случае код, который исполняется на видеокарте, должен компилироваться напрямую в машинные инструкции, то есть выполнятся не под виртуальной машинной, без автоматической сборки мусора.
            Кстати сама статья по работе с CUDA/OpenCL из .Net была бы интересная, или хотя бы комментарий со ссылками на библиотеки:)
              +3
              Все тоже самое, как и в C/C++, только «хостом» является .Net приложение. Хорошо, в ближайшее время постараюсь написать о .Net и работе с CUDA и OpenCl.
              Я использовал библиотеку CLOO для OpenCl, и CUDA.NET для CUDA.
                0
                Спасибо, будет что на выходных посмотреть.
                  0
                  Насколько я понял, CUDA.NET — это оболочка для CUDA API, при этом функцию обработки данных на видеокарте все равно нужно писать на неуправляемом языке, верно?

                  Было бы интересно посмотреть сравнение времени работы алгоритма на c для параллельной работы на CPU и вашей реализации на CUDA.NET.
                    0
                    Насколько я понял, CUDA.NET — это оболочка для CUDA API

                    Да и CLOO и CUDA.NET это обертки над API.
                    при этом функцию обработки данных на видеокарте все равно нужно писать на неуправляемом языке, верно?

                    Исключительно на неуправляемом языке, мы пишем ядро(kernel) для видеокарты, а вызываем мы его из .Net, при этом как ядро будет компилироваться и работать зависит только от вашего драйвера, по сути, это же ядро мы можем вызвать из C/C++, Matlab, и т.д.(все что может работать с OpenCl и CUDA).
                    Было бы интересно посмотреть сравнение времени работы алгоритма на c для параллельной работы на CPU и вашей реализации на CUDA.NET.

                    Мне тоже было интересно, но времени писать пока нет.
                0
                Может тогда стоит писать на рамдиск, чтобы увидеть реальную производительность?
              +1
              В вашем тесте файлы размером в 200мб и в 600мб. Интересно посмотреть было бы как изменится картина с:
              1. OpenCL выполнялся на карте AMD
              2. Файл выходил за пределы памяти, допустим при памяти в 1гб на видеокарте, он занимал 2,2 гб. Соответствующие тесты провести можно было бы для CPU также.
                +1
                1. OpenCL выполнялся на карте AMD

                В следующей статье я выложу программу, и вы сами сможете протестировать. Так получилось что у всех моих знакомых видеокарты Nvidia. Правда до этого у меня была AMD 4850, но она не поддерживала расширение(OpenCl) cl_khr_byte_addressable_store, поэтому я не мог работать на ней с байтами.
                2. Файл выходил за пределы памяти, допустим при памяти в 1гб на видеокарте, он занимал 2,2 гб. Соответствующие тесты провести можно было бы для CPU также.

                На видеокарту файл подается частями, и теоретически он может быть любого размера.
                0
                Не упираются ли результаты на GPU в скорость чтения/записи винчестера? Судя по цифрам вроде бы не должны, но для чистоты эксперимента хотелось бы уточнить, а вдруг потенциал еще больше.
                  0
                  Да, я думаю, жесткий диск тормозит OpenCl и CUDA. Я специально тестировал сначала с записью в файл, а потом без записи. Например, если сравнить результаты:
                  CPU(Async) без записи 00:01:16.5318999 с записью 01:30.8914603, разница в 14 секунд.
                  OpenCL без записи 00:00:29.4916041 с записью 00:01:09.3714452, разница в 39 секунд.
                  Для CUDA аналогично.
                  Можно увидеть, что для OpenCl и CUDA происходит большой скачек по времени, это связанно с тем, что файл подается порциями и после обработки на видеокарте, файл сначала записывается на диск, а потом запускается следующий кусочек на обработку. Я хотел сделать буффер для обработки и асинхронно записывать в файл, но времени на это не хватило.

                    0
                    может попорбовать потестировать и исключив зависимость от чтения?
                    то есть (освободив кучу памяти) сначала зачитать весь файл в оперативку, а потом уже начать счет.
                  0
                  Исходный код закрыт? Интересно было бы посмотреть… Если нет, не сложно было бы на гитхабе выложить?
                    0
                    Возможно, я выложу код на гитхабе, если выложу, в следующей статье дам ссылку.
                      +1
                      Мы тоже реализовал Хаффмана на GPU. Однако в сравнении участвовала самая быстрая на данный момент реализация на C++ — FastHuffman. Процессор, на котором мы тестировали — i7, реализация GPU работала на Amazon. Прирост где-то около 15-20 процентов, но реализация неоптимальна. А что у вас с декодированием?
                      Наши исходники доступны тут: github.com/Kentzo/phuffman, бранч называется cuda
                        0
                        Интересно:)
                        Вначале я планировал сделать и декодирование, но с ним возникли сложности, а так как времени у меня было не много, пришлось его пока отложить, но кое-какие мысли есть!
                        Однако в сравнении участвовала самая быстрая на данный момент реализация на C++ — FastHuffman.

                        Не поделитесь?
                        Прирост где-то около 15-20 процентов, но реализация неоптимальна.

                        Я не претендую на самую быструю реализацию.
                          0
                          Доступна где-то в сети. Я попозже поищу — дам ссылку. Что касается декодирования, то тут все сложнее и у нас с этим тоже некоторые проблемы. Я предлагаю объединиться и бороться с проблемами декодирования сообща. У меня Хаффман это небольшая часть диссера.
                            0
                            Вот, нашел: www.cipr.rpi.edu/~said/FastAC.html
                            Там еще и адаптивный вариант имеется.
                          +1
                          Не хватает тестов OpenCL на CPU и CPU+GPU вместе.
                            0
                            Не хватает сравнения с оптимизированным 7z на тех же данных.

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

                            Самое читаемое