Grizzzly
Feb 18 2017, 17:28
Стоит задача выбора алгоритма для реализации на цифровом сигнальном процессоре. В первом 3500 умножений и 64 сравнения, еще около 5000 сложений. Во втором умножений порядка 500, 5400 сложений и 2100 сравнений. То есть операций умножения и сложения меньше, а вот сравнений больше в 30 с лишним раз. Суммарное число операций при этом немного меньше, чем в первом. Насколько я понимаю, все эти операции выполняются за такт, но при выполнении условных операций будет останавливаться конвейер. Эти сравнения нужны для выбора максимального элемента из 16 штук в массиве, таких массивов много.
Для того чтобы получить максимальное быстродействие, лучше использовать алгоритм с меньшим числом сравнений, но несколько большим суммарным числом операций?
Цитата(Grizzzly @ Feb 18 2017, 23:28)

Насколько я понимаю, все эти операции выполняются за такт, но при выполнении условных операций будет останавливаться конвейер.
С чего Вы взяли?
Насколько я помню ассемблер C55xx там есть команда "нахождение максимального/минимального из двух".
Выполнялась за такт (ну если конечно не было каких-то stall-ов).
Важнее знать - можно-ли совместить умножения со сложениями. Тогда их можно выполнить за одну MAC.
Grizzzly
Feb 18 2017, 22:17
Цитата(jcxz @ Feb 19 2017, 00:48)

С чего Вы взяли?
Спасибо за ответ. Почему-то казалось, что сравнение будет приводить к такому. Неправ.
По поводу совместных умножений и сложений - в первом алгоритме умножаются матрицы 6х8 на вектора 8х1, вычисляются евклидовы расстояния. Значит, можно объединить.
Получилось, что около 3500 MAC + 64 сравнения ~ 3500
Во втором алгоритме тоже евклидовы расстояния, а далее итерационно происходят суммирования и сравнения: 512 MAC + 4900 сложений и 2100 сравнений ~ 7500
Цитата(Grizzzly @ Feb 19 2017, 04:17)

Получилось, что около 3500 MAC + 64 сравнения ~ 3500
Во втором алгоритме тоже евклидовы расстояния, а далее итерационно происходят суммирования и сравнения: 512 MAC + 4900 сложений и 2100 сравнений ~ 7500
Всё сильно зависит от процессора и компилятора. DSP это не ARM, в нём много сложных команд, выполняющих много действий. В каждом DSP свой набор таких команд. И результат реализации заранее не очевиден.
Попробуйте реализовать оба этих способа и посмотреть что получится.
Grizzzly
Feb 19 2017, 08:09
Цитата(jcxz @ Feb 19 2017, 09:30)

Всё сильно зависит от процессора и компилятора. DSP это не ARM
Как раз до этого только под ARM программировал.
Посмотрел на будущее еще SIMD и параллельные MAC операции на C66xx и подобных - это вообще отдельная тема, у каждой модели свои регистры. Пока не реализуешь, даже примерно не поймешь. Спасибо, буду пробовать.
sigmaN
Feb 19 2017, 12:00
И еще наивная реализация на Си будет существенно отличаться по скорости с продуманной реализацией на asm. Где как раз вы и сможете применить все эти редкие инструкции с максимальным эффектом.
Компиляторы конечно умнеют, а последний раз я с DSP имел дело лет 7 назад, но всё-же тогда FIR фильтр реализованный на Си проигрывал asm реализации во много раз(больше 2х).
Как уже говорилось,многое зависит от самого сигнальника, а также от Вашего понимания термина "сравнение"!
Если это выбор минимального/максимального, а также клиппирование, то, например, у ADSP21xxx есть специальные
команды, выполняемые за один такт, а если после сравнения надо сделать несколько операций - то может потребоваться
переход к другому участку кода - а это уже потери....
Grizzzly
Feb 20 2017, 21:31
Ясно. Спасибо. Изначально просто хотелось прикинуть, имея перд глазами таблички с числом операций по алгоритмам, что же будет выгоднее. Теперь осознал, что умозрительно не получится заранее всё учесть.
P.S. У меня цепочка сравнений из 15 штук для поиска максимума в массиве из 16 элементов. Так что это выбор максимума.
Для просмотра полной версии этой страницы, пожалуйста,
пройдите по ссылке.