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

postal
Сообщения: 4
Зарегистрирован: 17 мар 2023, 19:24

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

Сообщение postal »

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

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

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

Сообщение Бахурин Сергей »

Можно узнать для чего потребовалось FFT такого размера?
Что значит тонет в шумах? Переполнение разрядности нигде не происходит?

postal
Сообщения: 4
Зарегистрирован: 17 мар 2023, 19:24

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

Сообщение postal »

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

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

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

Сообщение Бахурин Сергей »

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

IgorV
Сообщения: 17
Зарегистрирован: 02 мар 2021, 17:36

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

Сообщение IgorV »

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

postal
Сообщения: 4
Зарегистрирован: 17 мар 2023, 19:24

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

Сообщение postal »

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

postal
Сообщения: 4
Зарегистрирован: 17 мар 2023, 19:24

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

Сообщение postal »

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

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

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

Сообщение Бахурин Сергей »

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

IgorV
Сообщения: 17
Зарегистрирован: 02 мар 2021, 17:36

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

Сообщение IgorV »

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

Ответить