Страница 1 из 1

Целочисленное преобразование Фурье большого порядка

Добавлено: 17 мар 2023, 19:32
postal
Есть задача на процессорах ARM вычислять БПФ больших порядков (до 2^20). Работа с double медленна, потому хочется в целых числах. Я написал реализацию, которая работает нормально примерно до порядка 12. Потом (на порядках выше) все тонет в шумах. На просторах интернета тоже видел целочисленные реализации, но они тоже касаются маленьких порядков типа 2^8 или 2^10.

Re: Целочисленное преобразование Фурье большого порядка

Добавлено: 18 мар 2023, 08:15
Бахурин Сергей
Можно узнать для чего потребовалось FFT такого размера?
Что значит тонет в шумах? Переполнение разрядности нигде не происходит?

Re: Целочисленное преобразование Фурье большого порядка

Добавлено: 21 мар 2023, 16:01
postal
Да, тонуло не в шумах, а тонуло в переполнениях. Подчистил код, стало работать. Причем порядок можно ставить и больше 20.
Но вот незадача: я делал это все для скорости выполнения, а скорости так и не достиг. 64-разрядный int работает примерно в полтора раза медленнее, чем float, а 32-битный примерно так же, как и float, но его разрядности для порядка 20 не хватает.

Re: Целочисленное преобразование Фурье большого порядка

Добавлено: 22 мар 2023, 21:46
Бахурин Сергей
Делайте промежуточные округления и не будет пепеполняться int32. Масштаб можно учесть по выходу

Re: Целочисленное преобразование Фурье большого порядка

Добавлено: 23 мар 2023, 18:08
IgorV
postal писал(а):
21 мар 2023, 16:01
Да, тонуло не в шумах, а тонуло в переполнениях. Подчистил код, стало работать. Причем порядок можно ставить и больше 20.
Но вот незадача: я делал это все для скорости выполнения, а скорости так и не достиг. 64-разрядный int работает примерно в полтора раза медленнее, чем float, а 32-битный примерно так же, как и float, но его разрядности для порядка 20 не хватает.
Можно еще больше удивиться если сравнить скорость выполнения например atan2 и сложения дублей. Они почти одинаковые плюс-минус, А это выворачивает как строить эффективные алгоритмы наизнанку.

Re: Целочисленное преобразование Фурье большого порядка

Добавлено: 24 мар 2023, 13:35
postal
Бахурин Сергей писал(а):
22 мар 2023, 21:46
Делайте промежуточные округления и не будет пепеполняться int32. Масштаб можно учесть по выходу
Да, верно, разобрался. В принципе, и на int16 можно делать преобразование Фурье больших порядков. Проблема только в скорости выполнения: она почти не отличается от float. Я получил, что int16 от float на задаче расчета БПФ отличается примерно на 10%. Это не то, что я ожидал. На задаче расчета свертки я получил, что int16 от float отличается в ~8 раз в пользу int. Это на том же процессоре и с теми же ключами компиляции. Подозреваю, что источник такой радости - промахи кэша: при вычислении свертки их почти нет, а в БПФ есть.

Re: Целочисленное преобразование Фурье большого порядка

Добавлено: 24 мар 2023, 13:38
postal
IgorV писал(а):
23 мар 2023, 18:08
Можно еще больше удивиться если сравнить скорость выполнения например atan2 и сложения дублей. Они почти одинаковые плюс-минус, А это выворачивает как строить эффективные алгоритмы наизнанку.
Поясните, пожалуйста, подробнее. Это как-то касается БПФ?

Re: Целочисленное преобразование Фурье большого порядка

Добавлено: 24 мар 2023, 18:45
Бахурин Сергей
Это касается в том смысле что на скорость влияет много неочевидных на первый взгляд факторов. Например расчёт и хранение поворотных множителей, или как осуществляется перенос данных из оперативной памяти в ядро. По хорошему надо смотреть что делает ядро? Молотит ли оно вычисления каждый такт, или занимается тем, что бегает в память, за каждым новым отсчетом и ждёт, когда данные подвезут.

Re: Целочисленное преобразование Фурье большого порядка

Добавлено: 26 мар 2023, 21:19
IgorV
postal писал(а):
24 мар 2023, 13:38
IgorV писал(а):
23 мар 2023, 18:08
Можно еще больше удивиться если сравнить скорость выполнения например atan2 и сложения дублей. Они почти одинаковые плюс-минус, А это выворачивает как строить эффективные алгоритмы наизнанку.
Поясните, пожалуйста, подробнее. Это как-то касается БПФ?
Бахурин Сергей ответил.
Чаще всего БПФ - это не самоцель. Вокруг БПФ что-то еще вычисляться должно, я просто уже столкнулся с "не очевидными" сюрпризами по скорости вычисления. И что float и double - без разницы в ПК, но разница в МК. Тоже самое если сравнивать работу в интах и флоатах для ПК может быть быстрее в плавающей, но онднозначно инты рулят для средненьких МК.