/Materials Ср, 28.06.2017, 22:22

Сайт методики довузовского обучения программированию
и проектной деятельности в информатике


Главная страница, Контакты, RSS
 
> Меню сайта

> Разделы новостей
Семинар [37]
Семинар по системному и прикладному программированию
Etc [14]
Разное
Конференция [16]
Открытая конференция исследовательских и проектных работ

> Архив новостей

> Партнеры

> Поиск

> Статистика

Главная » 2010 » Февраль » 28 » Cudaffman: Алгоритм сжатия по Хаффману с использованием NVIDIA CUDA
Cudaffman: Алгоритм сжатия по Хаффману с использованием NVIDIA CUDA
Владимир Янушковский
10 класс


Автор: Владимир Янушковский, 10 класс, error0x0@ya.ru

Преподаватель: И. Р. Дединский, mail@ded32.net.ru

Идея. В ходе выполнения домашней работы по курсу "Алгоритмы и структуры данных" по разработке архиватора, основанного на алгоритме Хаффмана, возникла идея ускорить процедуру сжатия, перенеся основную её часть (кодировку) на видеокарту, распределив обработку данных между несколькими потоками с помощью технологии NVIDIA CUDA. Программный этюд Cudaffman  – попытка реализации этой идеи.

Работа была выполнена под впечатлением семинаров по CUDA, проводящихся на факультете ВМиК МГУ, проводящихся А.В. Боресковым и А.Харламовым.

Способ распараллеливания. Было принято решение разбить исходный файл на части (pieces) постоянного размера (16 Кб исходной информации) и при сжатии подгружать по несколько частей, параллельно запускать для них процедуру архивации (kernel) и записывать их в архив.

Формат архива. В начале архива находится 4-байтная сигнатура с номером версии алгоритма, затем 1 Кб информации, необходимой для восстановления дерева Хаффмана (256 целых чисел  – частот символов). Далее следуют куски (pieces) зашифрованной информации, в начале каждого  – длина куска и количество значащих бит в последнем байте.

Архитектура программы. Основу программы составляет класс CudaffmanCompressor, который содержит методы сжатия (compress) и "разжатия" (декомпрессии, decompress) файлов. Оба эти метода работают в соответствии с выбранным алгоритмом, то есть подгружают несколько частей, а затем вызывают функцию ядра для каждой из этих частей. Расмотрим ядро алгоритма сжатия. Оно представлено CUDA-функцией CudaffmanCompressorKernel и её обёрткой – CudaffmanCompressorKernelCall. Также имеются аналогичные функции CudaffmanCompressorKernelCPU и CudaffmanCompressorKernelCPUCall, которые практически совпадают с предыдущими, но выполняются на ЦП. Класс CudaffmanCompressor позволяет включить или отключить использование CUDA. При этом он просто вместо одной обёртки вызывает другую. Декомпрессия устроена абсолютно аналогично. Программа реализована на языке С++ в среде программирования MS Visual Studio 2008.

Метод тестирования. Программе был предоставлен текстовый файл размером 93 Мб, который она успешно сжала до 47 Мб и успешно разжала. При этом при помощи функций QueryPerformance* измерялось время работы Call-функции. Ниже приведены усредненные результаты тестирования (взяты первые 5 блоков по 512 частей):

Время работыCUDA (compress)CPU (compress)CUDA (decompress)CPU (decompress)
Абсолютное, мс463.25 ± 1.7620.75  ± 2.2308.25 ± 7.9455.25 ± 0.5
Относительное, %75%100%68%100%

Дальнейшие планы. Отладка программы (т.к. пока присутствуют некоторые баги), поиск оптимального разбиения потоков на блоки, оптимизация распараллеливания алгоритма.

Материалы: Исходные тексты программы


Категория: Семинар | Просмотров: 2712 | Добавил: ded32
> Инструменты

Orphus


> О рекламе на сайте

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


> Загрузить

> Основные материалы

> Примеры проектов



Copyright (c) И.Р. Дединский, 2006-2017
Никакая часть материалов данного сайта или его подразделов не может быть прямо или косвенно процитирована или упомянута без действующей активной ссылки на данный сайт
...

Хостинг от uCoz

MasterHost Orphus