[Grizzly 0]

Стоит задача выбора алгоритма для реализации на цифровом сигнальном процессоре. В первом 3500 умножений и 64 сравнения, еще около 5000 сложений. Во втором умножений порядка 500, 5400 сложений и 2100 сравнений. То есть операций умножения и сложения меньше, а вот сравнений больше в 30 с лишним раз. Суммарное число операций при этом немного меньше, чем в первом. Насколько я понимаю, все эти операции выполняются за такт, но при выполнении условных операций будет останавливаться конвейер. Эти сравнения нужны для выбора максимального элемента из 16 штук в массиве, таких массивов много.

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

[jcxz 184]

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

С чего Вы взяли?

Насколько я помню ассемблер C55xx там есть команда "нахождение максимального/минимального из двух".

Выполнялась за такт (ну если конечно не было каких-то stall-ов).

Важнее знать - можно-ли совместить умножения со сложениями. Тогда их можно выполнить за одну MAC.

[Grizzly 0]

С чего Вы взяли?

Спасибо за ответ. Почему-то казалось, что сравнение будет приводить к такому. Неправ.

 

По поводу совместных умножений и сложений - в первом алгоритме умножаются матрицы 6х8 на вектора 8х1, вычисляются евклидовы расстояния. Значит, можно объединить.

Получилось, что около 3500 MAC + 64 сравнения ~ 3500

Во втором алгоритме тоже евклидовы расстояния, а далее итерационно происходят суммирования и сравнения: 512 MAC + 4900 сложений и 2100 сравнений ~ 7500

[jcxz 184]

Получилось, что около 3500 MAC + 64 сравнения ~ 3500

Во втором алгоритме тоже евклидовы расстояния, а далее итерационно происходят суммирования и сравнения: 512 MAC + 4900 сложений и 2100 сравнений ~ 7500

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

Попробуйте реализовать оба этих способа и посмотреть что получится.

[Grizzly 0]

Всё сильно зависит от процессора и компилятора. DSP это не ARM

Как раз до этого только под ARM программировал.

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

[sigmaN 0]

И еще наивная реализация на Си будет существенно отличаться по скорости с продуманной реализацией на asm. Где как раз вы и сможете применить все эти редкие инструкции с максимальным эффектом.

Компиляторы конечно умнеют, а последний раз я с DSP имел дело лет 7 назад, но всё-же тогда FIR фильтр реализованный на Си проигрывал asm реализации во много раз(больше 2х).

[bve 1]

Как уже говорилось,многое зависит от самого сигнальника, а также от Вашего понимания термина "сравнение"!

Если это выбор минимального/максимального, а также клиппирование, то, например, у ADSP21xxx есть специальные

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

переход к другому участку кода - а это уже потери....

 

 

[Grizzly 0]

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

P.S. У меня цепочка сравнений из 15 штук для поиска максимума в массиве из 16 элементов. Так что это выбор максимума.