Реализация LZW алгоритма сжатия с использованием возможностей современных GPU

Формат TIFF характеризуется большими объемами получаемых файлов (например, изображение формата A4 в цветовой модели CMYK с разрешением 300 dpi, обычно применяемым для высококачественной печати, имеет объем порядка 40 Мбайт). Поэтому он используется преимущественно при вводе информации со сканеров и в электронных версиях печатных изданий.



2. Возможности использования современных GPU

Появление современного GPU для вычисления общего назначения обеспечило платформу, чтобы написать заявления, которые могут управлять на сотнях маленьких ядер. CUDA (Вычисляют Объединенную Архитектуру Устройства) является выполнением NVIDIA этой параллельной архитектуры на их GPU и предоставляет ПЧЕЛУ программистам, чтобы разработать параллельные приложения, используя язык программирования. CUDA обеспечивает абстракцию программного обеспечения для аппаратных средств, названных блоками, которые являются группой нити, которые могут разделить память. Эти блоки назначены на многие скалярные процессоры, которым доступны аппаратные средства. Восемь скалярных процессоров составляют мультипроцессор, и различные модели GPU содержат отличающееся количество мультипроцессора.

Сжатие - важная и полезная техника, которая может быть медленной на текущих центральных процессорах.

Первым алгоритмом сжатия, было сжатие изображения JPEG. Большие файлы обычно будут требовать некоторые формы вытекания данных и от GPU, JPEG требует только несколько копий памяти и от устройств, уменьшая необходимую полосу пропускания памяти GPU и наверху.

Графический процессор (англ. Graphics processing unit, GPU) -- отдельное устройство персонального компьютера или игровой приставки, выполняющее графический рендеринг. Современные графические процессоры очень эффективно обрабатывают и отображают компьютерную графику, благодаря специализированной конвейерной архитектуре они намного эффективнее в обработке графической информации, чем типичный центральный процессор.

Графический процессор в современных видеоадаптерах применяется в качестве ускорителя трёхмерной графики, однако его можно использовать в некоторых случаях и для вычислений (GPGPU). Отличительными особенностями по сравнению с ЦП являются:

· архитектура, максимально нацеленная на увеличение скорости расчёта текстур и сложных графических объектов;

· ограниченный набор команд.

Примером может служить чип R520 от ATI или G70 от nVidia.

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

Методы: Решение поставленной задачи основано на разработке специфических программ-шейдеров. Для эффективного использования особенностей архитектуры графического процессора необходимо обеспечить значительный параллелизм вычислений. В процессе выполнения проекта мы ориентируемся на продукты компании NVIDIA: новые семейства графических процессоров - g80 и g92; среду разработки CUDA SDK (www.nvidia.com). Используя фундаментальный алгоритм сжатия данных и возможность его распараллеливания, можно разработать новый алгоритм, более производительный и требующий меньшего количества ресурсов для исполнения. В качестве базового алгоритма был выбран алгоритм сжатия данных LZW (Lempel/Ziv/Welch). Последовательный характер этого алгоритма и структур данных, использованных в нем, позволяет разбить входной поток данных на несколько независимо друг от друга обрабатывающихся потоков. Результаты: Предлагаемый подход имеет ряд преимуществ: 1) почти полная разгрузка центрального процессора; 2) графический процессор является устройством изначально ориентированным на сложные арифметические операции; 3) конвейерная обработка данных, организованная в графическом процессоре, позволяет производить параллельную обработку больших массивов данных. Слабым местом такого подхода является интерфейс между центральным и графическим процессорами, так как значительное время тратится на пересылку данных между этими устройствами. Однако, этот недостаток носит условный характер, так как: 1) ведется разработка и внедрение оборудования, имеющего большую пропускную способность интерфейса графического процессора; 2) оптимизация шейдеров программистами может практически свести на нет падение производительности при пересылке данных. В отношении реализации алгоритма LZW на графическом процессоре следует отметить, что незначительное увеличение результирующего файла по сравнению с классическим алгоритмом LZW компенсируется гораздо большей скоростью вычислений и практически полным освобождением центрального процессора от вычислительной нагрузки. Преимущества данного подхода определяют перспективность разработки алгоритмов сжатия для графических процессоров.

2.1 Алгоритм

Шаги алгоритма должны быть выполнены в последовательной манере, потому что операции в каждом блоке зависят от продукции предыдущего блока. Сжатие начинается, загружая несжатое изображение в форме 24-битового изображения битового массива с 8-битовой краснотой, зелёной и синие ценности для каждого пиксела. Изображение загружено в главную память, и Jpeglib выполняет операции на блоках из 8x8 пикселя под названием MCU (минимальные закодированные единицы). Первый шаг после погрузки изображения должен преобразовать ценности RGB к YCC (luma, синяя насыщенность цвета, красная насыщенность цвета). Это просто ряд линейных операций на трех ценностях RGB для каждого пиксела по изображению. Цель преобразование должна отделить яркость (luma) изображения от отдельных цветов.

2.2 Исполнительные точки отсчёта

Ускорение выполнения

Центральный процессор только последовательная версия 1.00

GPU Spectral Floor Calc & PCM Window 0.23

GPU PCM Окно только 0.56

GPU PCM Окно только, memcpy удалил 1.17

GPU Spectral Floor Calc & PCM Windows &

MDCT для петель 0.79

GPU PCM Windows & MDCT для петель 0.93

GPU PCM 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-битные варианты программы работают хорошо и на маленьких файлах.

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

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

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

И, наконец, можно брать вырабатываемые LZW-методом коды и пропускать их через адаптирующийся кодирующий фильтр Хаффмана. Это дает несколько большую степень сжатия, но стоимость такой работы более высока, также как и время обработки.

Приведенная программа была написана и тестирована на MS-DOS машине и успешно скомпилирована и выполнена с использованием обычного компилятора "C". Она должна работать на любой машине, поддерживающей 16-битный целые и 32-битные длинные целые языка "C".

Реализация компиляторов "C" для MS-DOS обычно создает сложности при использовании массивов больших, чем 64К байт, не позволяя использовать 15- или 16-битные коды в программе. На машинах с другими процессорами, таких как VAX, эти сложности преодолеваются, и облегчается использование кодов большей длины.

Отметим, что перевод этого кода на язык ассемблера любой машины, поддерживающей 16- и 32-битную математику, не встретит затруднений и позволит улучшить некоторые характеристики.

Различие между обычным LZW и LZW для GIF заключаются в наличии двух дополнительных специальных кодов и переменном размере сжатия.

Учитывая архитектуру сегодняшних систем, возможно, продолжить повторно проектировать библиотеку Vorbis, чтобы взять дальнейшее преимущество доступного GPU. Однако, осуществление перенесения, вовлеченное в преобразование всех частей этот алгоритм в формат, который является более способствующим векторной обработке, является трудоёмким, утомительным, трудным к отладьте и вовлекает удаление многих интуитивных элементов, достижимых арифметикой указателя.

Совместное управление алгоритмом между системным центральным процессором и доступным GPU - эффективный метод для исполнительного усовершенствования, когда соответствующие силы этих двух наборов микросхем сохранены в памяти.



Список используемой литературы

1. Ватолин Д.С., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002.

2. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC.- М.:Унитех, 1992.

3. Семенюк В. В. Экономное кодирование дискретной информации. - СПб.: СПбГИТМО (ТУ), 2001.

4. http://library.mephi.ru/data/scientific-sessions/2001/13/2146.html

5. http://algolist.manual.ru/compress/standard/lzw.php



Приложение

/*Демонстрационная программа для LZW-алгоритма сжатия/распаковки данных.*/

/* Mark R. Nelson*/

#include <stdio.h>

#define BITS 12 /* Установка длины кода равной 12, 13 */

#define HASHING_SHIFT BITS-8 /* или 14 битам. */

#define MAX_VALUE (1 << BITS) -1/* Отметим, что на MS-DOS-машине при */

#define MAX_CODE MAX_VALUE - 1 /* длине кода 14 бит необходимо компилировать, используя large-модель. */

#if BITS == 14

#define TABLE_SIZE 18041 /* Размер таблицы строк должен быть */

#endif /* простым числом, несколько большим, */

#if BITS == 13 /* чем 2**BITS. */

#define TABLE_SIZE 9029

#endif

#if BITS <= 12

#define TABLE_SIZE 5021

#endif

void *malloc();

/* Это массив для значений кодов */

int *code_value;

/* Этот массив содержит префиксы кодов */

unsigned int *prefix_code;

/* Этот массив содержит добавочные символы */

unsigned char *append_character;

/* Этот массив содержит декодируемые строки */

unsigned char decode_stack[4000];

/*Эта программа получает имя файла из командной строки. Она упаковывает файл, посылая выходной поток в файл test.lzw. Затем распаковывает test.lzw в test.out. Test.out должен быть точной копией исходного файла.*/

main(int argc, char *argv[])

{

FILE *input_file;

FILE *output_file;

FILE *lzw_file;

char input_file_name[81];

/*Эти три буфера необходимы на стадии упаковки.*/

code_value=malloc(TABLE_SIZE*sizeof(unsigned int));

prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));

append_character=malloc(TABLE_SIZE*sizeof(unsigned char));

if (code_value==NULL || prefix_code==NULL || append_character==NULL)

{

printf("Fatal error allocating table space!\n");

exit();

}

/*Получить имя файла, открыть его и открыть выходной lzw-файл.*/

if (argc>1)

strcpy(input_file_name,argv[1]);

else

{

printf("Input file name? ");

scanf("%s",input_file_name);

}

input_file=fopen(input_file_name,"rb");

lzw_file=fopen("test.lzw","wb");

if (input_file==NULL || lzw_file==NULL)

{

printf("Fatal error opening files.\n");

exit();

};

/*Сжатие файла.*/

compress(input_file,lzw_file);

fclose(input_file);

fclose(lzw_file);

free(code_value);

/*Сейчас открыть файлы для распаковки.*/

lzw_file=fopen("test.lzw","rb");

output_file=fopen("test.out","wb");

if (lzw_file==NULL || output_file==NULL)

{

printf("Fatal error opening files.\n");

exit();

};

/*Распаковка файла.*/

expand(lzw_file,output_file);

fclose(lzw_file);

fclose(output_file);

free(prefix_code);

free(append_character);

}

/*Процедура сжатия.*/

compress(FILE *input,FILE *output)

{

unsigned int next_code;

unsigned int character;

unsigned int string_code;

unsigned int index;

int i;

next_code=256; /* Next_code - следующий доступный код строки */

for (i=0;i<TABLE_SIZE;i++)/*Очистка таблицы строк перед стартом */

code_value[i]=-1;

i=0;

printf("Compressing...\n");

string_code=getc(input); /* Get the first code*/

/*Основной цикл. Он выполняется до тех пор, пока возможно чтение входного потока. Отметим, что он прекращает заполнение таблицы строк после того, как все возможные коды были использованы.*/

while ((character=getc(input)) != (unsigned)EOF)

{

if (++i==1000) /* Печатает * через каждые 1000 */

{ /* чтений входных символов (для */

i=0; /* умиротворения зрителя). */

printf("*");

}

/* Смотрит, есть ли строка */

index=find_match(string_code,character);

if (code_value[index] != -1) /* в таблице. Если есть, */

string_code=code_value[index];/* получает значение кода*/

else /* Если нет, добавляет ее */

{ /* в таблицу. */

if (next_code <= MAX_CODE)

{

code_value[index]=next_code++;

prefix_code[index]=string_code;

append_character[index]=character;

}

output_code(output,string_code);/*Когда обнаруживается, что*/

string_code=character; /*строки нет в таблице, */

} /*выводится последняя строка*/

} /*перед добавлением новой */

/*

** End of the main loop.

*/

output_code(output,string_code); /* Вывод последнего кода */

output_code(output,MAX_VALUE); /* Вывод признака конца потока */

output_code(output,0); /* Очистка буфера вывода */

printf("\n");

}

/*Процедура хэширования. Она пытается найти сопоставление для строки префикс+символ в таблице строк. Если найдено, возвращается индекс. Если нет, то возвращается первый доступный индекс.*/

find_match(int hash_prefix,unsigned int hash_character)

{

int index;

int offset;

index = (hash_character << HASHING_SHIFT) ^ hash_prefix;

if (index == 0)

offset = 1;

else

offset = TABLE_SIZE - index;

while (1)

{

if (code_value[index] == -1)

return(index);

if (prefix_code[index]==hash_prefix

&&append_character[index]==hash_character)

return(index);

index -= offset;

if (index < 0)

index += TABLE_SIZE;

}

}

/*Процедура распаковки. Она читает файл LZW-формата и распаковывает его в выходной файл.*/

expand(FILE *input,FILE *output)

{

unsigned int next_code;

unsigned int new_code;

unsigned int old_code;

int character;

int counter;

unsigned char *string;

char *decode_string(unsigned char *buffer,unsigned int code);

next_code=256; /* Следующий доступный код. */

counter=0; /* Используется при выводе на экран.*/

printf("Expanding...\n");

old_code=input_code(input);/*Читается первый код, инициализируется*/

character=old_code; /* переменная character и посылается первый */

putc(old_code,output); /* код в выходной файл. */

/*Основной цикл распаковки. Читаются коды из LZW-файла до тех пор, пока не встретится специальный код, указывающий на конец данных.*/

while ((new_code=input_code(input)) != (MAX_VALUE))

{

if (++counter==1000) { counter=0; printf("*"); }

/*

** Проверка кода для специального случая

** STRING+CHARACTER+STRING+CHARACTER+

** STRING, когда генерируется неопределенный код.

** Это заставляет его декодировать последний код,

** добавив CHARACTER в конец декод. строки.

*/

if (new_code>=next_code)

{

*decode_stack=character;

string=decode_string(decode_stack+1,old_code);

}

/*Иначе декодируется новый код.*/

else

string=decode_string(decode_stack,new_code);

/*Выводится декодируемая строка в обратном порядке.*/

character=*string;

while (string >= decode_stack)

putc(*string--,output);

/*Наконец, если возможно, добавляется новый код в таблицу строк.*/

if (next_code <= MAX_CODE)

{

prefix_code[next_code]=old_code;

append_character[next_code]=character;

next_code++;

}

old_code=new_code;

}

printf("\n");

}

/*Процедура простого декодирования строки из таблицы строк, сохраняющая результат в буфер. Этот буфер потом может быть выведен в обратном порядке программой распаковки.*/

char *decode_string(unsigned char *buffer,unsigned int code)

{

int i;

i=0;

while (code > 255)

{

*buffer++ = append_character[code];

code=prefix_code[code];

if (i++>=4094)

{

printf("Fatal error during code expansion.\n");

exit();

}

}

*buffer=code;

return(buffer);

}

/*Следующие две процедуры управляют вводом/выводом кодов переменной длины. Они для ясности написаны чрезвычайно простыми и не очень эффективны.*/

input_code(FILE *input)

{

unsigned int return_value;

static int input_bit_count=0;

static unsigned long input_bit_buffer=0L;

while (input_bit_count <= 24)

{

input_bit_buffer|=(unsigned long)getc(input)<<(24-input_bit_count);

input_bit_count += 8;

}

return_value=input_bit_buffer >> (32-BITS);

input_bit_buffer <<= BITS;

input_bit_count -= BITS;

return(return_value);

}

output_code(FILE *output,unsigned int code)

{

static int output_bit_count=0;

static unsigned long output_bit_buffer=0L;

output_bit_buffer|=(unsigned long)code<<(32-BITS-output_bit_count);

output_bit_count += BITS;

while (output_bit_count >= 8)

{

putc(output_bit_buffer >> 24,output);

output_bit_buffer <<= 8;

output_bit_count -= 8;

}

Размещено на Allbest.ru