КИХ-фильтр (MMX) Нужно ускорить программу

[andreyasa]

Здравствуйте помогите пожалуйста ускорить программу на Ассемблере. Преподаватель говорит что ее можно ускорить в 4 или 8 раз. Говорит это легко и быстро !!! Преподаватель как только увидел вот эту строчку кода
;Записываем результат
MOV [edi], eax
сразу сказал что остальное даже можно не смотреть. Он говорит что нам надо на вход вектор и на выходе получать вектор. Мы запутались. Ниже для понимая даем краткую информацию.
ОС Windows XP

1. Постановка задачи

Разработать и реализовать программу, осуществляющую фильтрацию большого массива данных методом простого скользящего среднего с использованием возможностей оптимизации, предоставляемых процессорами Intel Pentium MMX.


2. Описание реализуемого КИХ-фильтра

Цифровая фильтрация является одним из наиболее мощных инструментальных средств ЦОС. Цифровые фильтры широко используются в телекоммуникациях, в приложениях адаптивной фильтрации, таких как подавление эха в модемах, подавление шума и распознавание речи. Существует два основных типа цифровых фильтров: фильтры с конечной импульсной характеристикой (КИХ) и фильтры с бесконечной импульсной характеристикой (БИХ). Как следует из терминологии, эта классификация относится к импульсным характеристикам фильтров.
Примером простого КИХ-фильтра является фильтр скользящего среднего (простое прямоугольное окно). Приведем формулу 4-точечного фильтра.




На основе приведенного примера выведем алгоритм работы фильтра:
- первым шагом происходит запоминание первых семи элементов A(0), A(1), A(2), A(3), A(4), A(5), A(6) в регистрах
- эти величины суммируются и затем полученная сумма делятся
на 7.
- начальные значения выходов y(0), y(1), y(2) некорректны.
- конечные значения выходов y(N-3), y(N-2), y(N-1)
некорректны.

Затем алгоритм повторяется для всего набора данных. Следует отметить, что качество фильтрации увеличивается при увеличении числа блоков (количества точек, по которым берется среднее)

3. Описание программы

В программе представлены два варианта реализации КИХ-фильтра: реализация на С++ и ассемблере с использованием MMX команд. Для проведения анализа двух реализаций имеется счетчик времени выполнения фильтрации. Что позволяет судить о эффективности той или иной реализации.
Данные для фильтрации также генерируются в программе. Перед выполнением алгоритма производится нормировка сгенерированных значений.
4. Исходный код программы

1.Реализация на С++

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

void CKurs_MMXDoc::KIX_C()
{
for(int t=3;t<1020;t++)
{
m_dMasSigKIX_C[t] = m_iMasTemp[t-3];
m_dMasSigKIX_C[t] += m_iMasTemp[t-2];
m_dMasSigKIX_C[t] += m_iMasTemp[t-1];
m_dMasSigKIX_C[t] += m_iMasTemp[t];
m_dMasSigKIX_C[t] += m_iMasTemp[t+1];
m_dMasSigKIX_C[t] += m_iMasTemp[t+2];
m_dMasSigKIX_C[t] += m_iMasTemp[t+3];
m_dMasSigKIX_C[t] = m_dMasSigKIX_C[t]/7;
}
}
Время выполнения фильтрации: 0,076 mc

2.Реализация на ассемблере

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

void CKurs_MMXDoc::KIX_MMX(int *p1, int *p2)
{
__asm
{
MOV esi, p1
MOV edi, p2
MOV ecx, 1017
again:
PXOR mm2, mm2

;Считываем 4 элемента в ММХ регистры
MOVQ mm0, [esi]
MOVQ mm1, [esi+8]

;Вычисляем сумму элементов
PADDD mm1, mm0

;Считываем 3 элемента в ММХ регистры
MOVQ mm0, [esi+16]
MOVD mm2, [esi+24]

;Вычисляем сумму элементов
PADDD mm0, mm2
PADDD mm1, mm0

MOVQ mm0, mm1
PSRLQ mm1, 32
PADDD mm1, mm0
;Сумма элементов в регистр EAX
MOVD eax, mm1

;Делим сумму на 7
MOV ebx, 7
CDQ
IDIV ebx

;Записываем результат
MOV [edi], eax

;Переход к следующему элементу
ADD esi, 4
ADD edi, 4

LOOP again

EMMS
}
}
Время выполнения фильтрации: 0,041 mc

[somewhere]

На мой взгляд команда

Код: Выделить всё

MOV [edi], eax

верная, ибо она есть часть формирования вектора. Основная часть алгоритма тоже верная, после прохода LOOP мы и получим исходный вектор. Ускорить в 4 или 8 раз у вас не получиться без изменения самого алгоритма. Если цель все же ускорить вычисления могу предложить изменить сам алгоритм примерно так:
давайте поглядим на проходы этого алгоритма
p2[0] = (p1[0]+p1[1]+p1[2]+p1[3]+p1[4]+p1[5]+p1[6]) / 7
p2[1] = (p1[1]+p1[2]+p1[3]+p1[4]+p1[5]+p1[6]+p1[7]) / 7
Можно заметить, что элементы p1[1] - p1[6] суммируются два раза
По идее эту строчку можно записать так:
S = p1[0]+p1[1]+p1[2]+p1[3]+p1[4]+p1[5]+p1[6]
p2[0] = S / 7
S = S - p1[0] + p1[7]
p2[1] = S / 7
S = S - p1[1] + p1[8]
p2[2] = S / 7
Чувствуете к чему я клоню, вот тогда может и получиться раза в 1,5 - 2. А насчет препода не переживайте, все у вас верно

[somewhere]

Здравствуйте, огромное спасибо, что обратили внимание на мое сообщение по поводу КИХ - фильтра. Дело в том, что по ассемблеру у нас мало было и теории и практики, по этому в ассемблере я не селен. Мой преподаватель нам намекал про ОКМД (одна команда много данных) поэтому предлагаю использовать все восемь регистров MMX mm0—mm7. Вы писали - “Чувствуете к чему я клоню, вот тогда может и получиться раза в 1,5 – 2» т. е мы, получается выигрываем в скорости экономя по две операции сложения за каждый проход, правильно понимаю? Не могли бы вы помочь в реализации данного кода на ассемблере ?
Наверно должно начинаться так
MOVQ mm0, [esi]
MOVQ mm2, [esi+4]
MOVQ mm4, [esi+8]
MOVQ mm6, [esi+12]

MOVQ mm1, [esi+14]
MOVQ mm3, [esi+18]
MOVQ mm5, [esi+22]
MOVQ mm7, [esi+26]

То, на что намекал ваш преподаватель, называет SIMD инструкции к коим и относятся инструкции MMX. Экономия на самом деле составит не 2, а 5 операций сложения. Выигрыш во времени будет сильно зависеть от скорости работы оперативной памяти а не процессора. Посколько раньше мы суммировали 7 ячеек по 32 бита, то и обращений к памяти было тоже 7, а теперь на остальных кроме первого проходах станет всего по две, а возможно и даже по одной. Помочь с реализацией могу, но так как свободного времени сейчас мало, то я сам не знаю когда напишу.

[andreyasa]

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

[somewhere]

Ну что, начнем? Представляю результат теста, который был написан на Дельфи 7, с использованием процедур на ассемблере по фильру КИХ с использованием разных типов алгоритмов - стандартного (Standart) и доработанного мною(Enhanced). Поскольку исходные данные имеют на входе знаковое 32 битовое целое, то разработаны три основные модификации:
1. Используя 32-разрядные регистры
2. Используя FPU
3. Используя технологию SIMD MMX инструкций

Standart algorithm with MMX

Это тот код, который был написан вами, что самое интересное показывает самый низкий результат. Позже я объясню почему.

Enhanced algorithm with MMX

Этот код был доработан мной по вышеописанному методу, как результат 12% прироста скорости. В основном во всех кроме FPU алгоритмах скорость сильно падает из-за использования команды деления idiv. Без этой команды в обоих алгоритмах чистый выигрыш по использованию MMX составил бы около 40%. Команда idiv занимает третью долю процессорного времени на один проход цикла.

Enhanced & Standart algorithm (Integer)

Прирост производительности 28% и 42% соответственно. Код Enhanced отстает по скорости от Standart algorithm (Integer) за счет работы системы предварительной выборки и механизма предсказания ветвлений. За счет того что цепь команд add eax, mem32 работает только с регистром EAX и с одним участком памяти то весь блок памяти будет закеширован, а конвееры возможно смогут распределить действия между разными ALU для подсчета суммы. В Enhanced алгоритме такое происходит но не в полном объеме, за счет частых изменений разных регистров.

Standart & Enhanced algorithm (float)

Вот они, наш чемпион... - единственный и неповторимый FPU, в отличие от своего кровного брата MMX :-) показал отличнейишие результаты, обойдя таких конкурентов как SIMD технологию и CPU!!! Что же происходит здесь??? Да все очень просто, FPU по своему предназначению очень любить делить и умножать, команды сложения целых из памяти выполняются на нем так же быстро как и на CPU, а вот деление выполняется гораздо быстрее. Enhanced алгоритм выполняется как и положено, быстрее примерно на 20-25% так как на команды FPU блок предсказания команд не распространяется, ну а кеширование памяти само собой никто не отменял.

Так вот, вывод:
Технология SIMD MMX существенно проигрывает в операциях с 32-битовыми целыми. В осовном это связано из за малой длины (64-бита) ММХ регистра, в результате за одну операцию обрабатывается всего два элемента, при условии того, что сама инструкция требует больше процессорного времени, чем две аналогичные команды CPU. Все это делает использование ММХ невыгодным в отношении 32-битовых операндов, пользоваться этими инструкциями можно лишь в случае нехватки регистров общего назначения. Однако при использовании 8 и 16-битовых операндов технология дает существенный выигрыш. Для вычислений и работы с данными длиной 32-бита рекомендую использовать более современные наборы инструкций такие как SSE, SSE2, SSE3, ISSE в которых имеются 128 битовые регистры, специально заточенные для пакетной обработки данных с длиной 32-бита и более.

Я не хочу расстраивать вашего препода, но хочу порадовать вас - у вас теперь имеется куча вариантов ускорить вашу программу. Запусковый файл разместить здесь не могу, но я думаю - вы все же мне поверите. Конечно на разных моделях процессора результаты будут отличаться, возможно на P166 или PII ММХ метод всеже обгонит остальные методы... Успехов вам в вашем нелегком труде и с наступающим Новым годом!!!