Автор: Владимир Янушковский, 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.7 | 620.75
± 2.2 | 308.25
± 7.9 | 455.25
± 0.5 | | Относительное, % | 75% | 100% | 68% | 100% |
Дальнейшие планы. Отладка программы (т.к. пока присутствуют некоторые баги), поиск оптимального разбиения потоков на блоки, оптимизация распараллеливания алгоритма. Материалы: Исходные тексты программы
| 
