15 July 2011

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

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

Многие, наверное, уже слышали о вычислениях на 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. Во второй части статьи, я расскажу о технических аспектах реализации.
Tags:openclcudagpgpuсжатие данных
Hubs: High performance
+26
9.2k 35
Comments 25
Top of the last 24 hours