Реализация LZW алгоритма сжатия с использованием возможностей современных GPU
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
е семейства графических процессоров - g80 и g92; среду разработки CUDA SDK (www.nvidia.com). Используя фундаментальный алгоритм сжатия данных и возможность его распараллеливания, можно разработать новый алгоритм, более производительный и требующий меньшего количества ресурсов для исполнения. В качестве базового алгоритма был выбран алгоритм сжатия данных LZW (Lempel/Ziv/Welch). Последовательный характер этого алгоритма и структур данных, использованных в нем, позволяет разбить входной поток данных на несколько независимо друг от друга обрабатывающихся потоков. Результаты: Предлагаемый подход имеет ряд преимуществ: 1) почти полная разгрузка центрального процессора; 2) графический процессор является устройством изначально ориентированным на сложные арифметические операции; 3) конвейерная обработка данных, организованная в графическом процессоре, позволяет производить параллельную обработку больших массивов данных. Слабым местом такого подхода является интерфейс между центральным и графическим процессорами, так как значительное время тратится на пересылку данных между этими устройствами. Однако, этот недостаток носит условный характер, так как: 1) ведется разработка и внедрение оборудования, имеющего большую пропускную способность интерфейса графического процессора; 2) оптимизация шейдеров программистами может практически свести на нет падение производительности при пересылке данных. В отношении реализации алгоритма LZW на графическом процессоре следует отметить, что незначительное увеличение результирующего файла по сравнению с классическим алгоритмом LZW компенсируется гораздо большей скоростью вычислений и практически полным освобождением центрального процессора от вычислительной нагрузки. Преимущества данного подхода определяют перспективность разработки алгоритмов сжатия для графических процессоров.
.1 Алгоритм
Шаги алгоритма должны быть выполнены в последовательной манере, потому что операции в каждом блоке зависят от продукции предыдущего блока. Сжатие начинается, загружая несжатое изображение в форме 24-битового изображения битового массива с 8-битовой краснотой, зелёной и синие ценности для каждого пиксела. Изображение загружено в главную память, и Jpeglib выполняет операции на блоках из 8x8 пикселя под названием MCU (минимальные закодированные единицы). Первый шаг после погрузки изображения должен преобразовать ценности RGB к YCC (luma, синяя насыщенность цвета, красная насыщенность цвета). Это просто ряд линейных операций на трех ценностях RGB для каждого пиксела по изображению. Цель преобразование должна отделить яркость (luma) изображения от отдельных цветов.
.2 Исполнительные точки отсчёта
Ускорение выполнения
Центральный процессор только последовательная версия 1.00
GPU Spectral Floor Calc & PCM Window 0.23PCM Окно только 0.56PCM Окно только, memcpy удалил 1.17Spectral Floor Calc & PCM Windows &
MDCT для петель 0.79PCM Windows & MDCT для петель 0.93PCM Windows & MDCT для петель, memcpy
удаленный 1.28
Исполнительные точки отсчета были взяты на базируемой системе Windows, используя NVidia 8800 GTS 512, у которого была полоса пропускания памяти между центральным процессором и пространством GPU 1.5 GB/s. От собранных данных могут быть сделаны несколько выводов. Первое и самое очевидное заключение состоит в том, что спектральное вычисление пола, которое требует верхнего из копирования трех множеств с плавающей запятой к GPU и только вовлекает одно вычисление с плавающей запятой.
Заключение
Достаточно трудно охарактеризовать результативность какой-либо техники сжатия данных. Степень сжатия определяется различными факторами. LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры. По этой причине он работает весьма эффективно, когда встречает английский текст. Уровень сжатия может достигать 50% и выше. Соответственно, сжатие видеоформ и копий экранов показывает еще большие результаты.
Трудности при сжатии файлов данных несколько больше. В зависимости от данных, результат сжатия может быть как хорошим, так и не очень удовлетворительным. В некоторых случаях "сжатый" файл может превосходить по своим размерам исходный текст.
Программа, приведенная в данной работе, является рабочей. Процедуры, организующие входные и выходные потоки, невелики по размерам и легки для понимания, но увеличивают накладные расходы. Вы можете попробовать увеличить скорость программы, совершенно переписав эти процедуры с использованием кодов фиксированной длины, скажем 12 бит.
Одной из проблем является то, что приведенная программа не адаптируется к различной длине файлов. Использование 14- или 15-битных кодов дает лучшую степень сжатия на больших файлах (это объясняется тем, что для них строятся большие таблицы строк), но хуже работает с маленькими файлами. Такие программы, как "ARC", решают эту проблему использованием кодов переменной длины. Например, когда величина next_code находится между 256 и 511, "ARC" читает и выводит 9-битные коды. Когда величина next_code становится настолько большой, что необходимы 10-битные коды, процедуры сжатия и распаковки увеличивают размер кода. Это значит, что 12- и 15-битные варианты программы работают хорошо и на маленьких файлах.
Другой проблемой больших файлов является то, что с увеличением числа прочитанных байтов степень сжатия может начать ухудшаться. Причина проста: так как размер таблицы строк фиксирован, после занесения определенного числа строк и