SSE3 и SSE4

Оптимизация под набор команд SSE3 и SSE4 не дала вообще никакого прироста производительности. Все три варианты выполняются за стабильно одинаковое количество тактов. А скалярная версия под FPU чуть-учть быстрее.

То ли я чего не так делаю, то ли все дело в процессоре... Но в общем пока я пришел к выводу, что оптимизация операций с плавающей точкой на основе SSE не дает особого выигрыша в производительности. Лучше оптимизировать скалярный код.

Наверное, гораздо больший выигрыш можно получить при выполнении операций с целыми числами в режиме SIMD. Такой вариант я пока не проверял, потому что сильнее всего загружает процессор при выполнении сжатия именно вейвлет-преобразование, которое требует операций с плавающей точкой.

Еще можно попробовать использовать команды SSE для вычислений в скалярном режиме. Возможно, это даст какой-то выигрыш.

SSE

Начал пытаться оптимизировать под SSE wavelet-преобразование.

Чисто теоретически система команд SIMD позволяет одновременно выполнить сразу несколько команд (4 в случае SSE). Правда, за это приходится платить тем, что данные для таких команд надо подготовить. Ситуации, когда данные расположены не подряд в памяти, не так уж редки. В наборе команд SSE1 (самой первой версии), специальных инструкций для таких случаев я не обнаружил.

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

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

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

Для выполнения вейвлет-преобразования необходимо выполнить векторное произведение. Если его написать тупо, вот так например:

result := 0;
for i := 0 to 3 do
  result := result+v1[i]*v2[i]

то особо параллельного выполнения команд здесь не будет. А вот если переписать в таком виде

result := v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2]+v1[3]*v2[3]

то тут есть где разгуляться современному процессору.

Ну так вот. Такой код при включенной оптимизации работает лишь чуть медленнее варианта на  ассемблере под SSE1. Это показалось мне подозрительным и я переписал исходный скалярный код с паскаля на ассемблер. Вуаля: это код работает чуть быстрее, чем SSE1.

Хотя, может это просто мой процессор дешевый и модуль SSE у него не быстрый? Еще одна тема вызывает у меня удивление: это набор команд SSE. Наверное, я чего-то не понимаю, но мне они показались чрезвычайно неудобными.

Теперь продолжу эксперименты с более новыми версиями SSE, там в версии 4 есть даже вариант, который, собственно, считает векторное произведение. Может, это существенно ускорит работу SIMD.

Wavelet и музыка

В прошлом посте проанализировал маленький фрагмент человеческого голоса, чуть больше одной секунды.

Сейчас добрался и до музыки, спектральный и динамический диапазон которой часто бывает существенно выше чисто голосовых записей. Выбрал небольшой фрагмент порядка 4 секунд и проанализировал его:

Все оказалось именно так, как я и думал. Степень сжатия таких музыкальный фрагментов существенно ниже, чем у голоса. Но, тем не менее можно ожидать порядка 6-х кратного сжатия. С учетом того, что обычно во всем музыкальном произведении все же не всегда используется весь диапазон, то в среднем можно ожидать сжатие в районе 10-12 раз. Что, на мой взгляд, весьма неплохо.

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

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

Когда-нибудь доберусь и попробую сделать простенькую реализацию сжатия файлов.

Wavelet и голос

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

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

Из-за того, что на одной диаграмме представлены результаты фактически двух экспериментов, она получилось слегка перегруженной. Поэтому объясню подробней. Я исследовал степень потенциального сжатия звуковых данных в зависимости от порядка вейвлета. Поэтому по оси Х откладываются именно эти данные.

По левой оси отложено % коэффициентов прямого вейвлет-преобразования, которые по абсолютной величине меньше 1/256 и 1/16. При оценки степени сжатия я исхожу из того, что первые данные можно в принципе вообще отбросить, а вторые достаточно сильно сжать. Исходя их эти предположений я рассчитываю теоретический предельный уровень сжатия, данные по которому привязаны к правой оси. Таким образом по левой оси 4 графика (по два на каждый эксперимент) и на правой два (по одному на каждый эксперимент).

Выводы

Исходя из представленных данных можно сделать следующие выводы:

1. Вполне ожидаемый. По достижении определенного порядка вейвлет-преоборазования его дальнейшее увеличение не ведет к повышению степени сжатия. Для голосовых данных насыщение наступает в районе 18-20 порядка, для зашумленных чуть позже. Это связано как с тем, что вейвлет-преобразование осуществляется многократно, так и с тем, что зависимости более высокого порядка отсутствуют в исходных данных. Но в музыкальных данных такие зависимости могут быть.
2. Даже без учета психоакустических особенностей слуха можно с помощью вейвлет-преобразования можно добиться результатов, сравнимых с преобразованием Фурье, а возможно, и несколько лучше.
3. Однако отсутствие учета психоакустических особенностей может привести и к существенным искажениям данных, что сделает прослушивание такого звука малоприятным.

Что дальше

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

Звук

Интересно, насколько сильно можно сжать звук с помощью вейвлет-преобразования?

Мои собственные попытки в 2004 году оказались не очень удачные в этом плане. MPEG audio, используя психоакустические особенности восприятия звука человеком, достигает примерно 10-кратного сжатия звука, которое практически не заметно на слух (для большинства, за исключением меломанов и профессионалов).

С ходу в русскоязычном интернете я не нашел каких-либо значимых работ в этом направлении. Но сильно не усердствовал, так как мне интересна проблема само по себе, вне контекста других работ в этом направлении.

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

Основой сжатия MPEG audio является  преобразование Фурье, базисом которого как раз и являются синусоидальные функции. В то время как базисом вейвлет-преобразования Добеши являются полиномы.

В принципе, я слышал и о существовании вейвлет-преобразования на основе синусов, но не встречал упоминание о его дискретной форме.

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

1. Во сколько улучшится степень сжатия при использовании вейвлетов более высоких порядков?
2. Каков оптимальный порядок вейвлетов для осуществления сжатия звука с учетом достижения оптимальной производительности преобразования?
3. Можно ли достичь или даже превысить коэффициент сжатия, достигнутый MPEG audio, при сравнимых показателях качества сжатия?

Обновление

Выложил очередное обновление программок. Сделал немножко более "человеколюбивый" интерфейс.

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

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

Но это когда-нибудь потом... )