Fast Fourier Transform

Sat Oct 02, 2010 7:34 pm

Блин, нашел в чем дело!

Выравнивание меток по границе 4байта ничего не дало - в программе очень много вычислений, но мало переходов.
Зато при отладке увидел, что стек вызывающей программы не был выровнен - отсюда и все непродуктивные задержки.

Большое спасибо Марату и Огромное - Сергею !

теперь рейтинг систем такой:
winXP - 82тыс тактов, Колибри - 71 тыс.

Может это и не абсолютный рекорд, но во всяком случае - одна из самых быстрых Фурье-систем *) на однопроцессорной РС-платформе, на чистом FPU без специализированных ускорителей и SSE.

*) вообще-то FHT - это не совсем FFT, нужен еще цикл пересчета реальных гармоник в комплексные, и этот цикл съест еще тысяч 10 тактов. Но и с ним все равно будет очень быстро.
К тому же в ряде случаев (свертка, корреляция, спектральный анализ, диффуравнения) все можно делать и в Хартли-пространстве

Mon Oct 04, 2010 2:36 am

#1641 - внедрил Фурье в экспериментальное ядро, заодно опробовал передачу параметров через стек в нестандартных syscall-вызовах.

Производительность выросла еще процентов на 5-10, для больших массивов - в разы, но это конечно запрещенный прием - внутри syscall действует режим cli.

Для массивов 256, 1К и 4К точек эффективная производительность Sempron140 (2.7GHz) достигла 1Гфлопс. Похоже, это уже предел.

Посмотрите кому интересно - в следующих версиях я это безобразие уберу, ему в ядре не место.

Mon Oct 04, 2010 8:38 am

А как насчет применения MMX и SSE(1,2,3)?

Mon Oct 04, 2010 12:06 pm

Mario
Лет 8 назад я попробовал первые 2 шага преобразования переписать под инструкции 3DNow! первых Атлонов (про SSE тогда еще почти никто не слышал).
Прирост скорости был довольно значительный (почти в 3 раза).

Но Step3 я так и не смог довести - там очень сложные вычисления, а распараллеливать их вручную - вообще свихнешся.
Кроме того, оказалось что "короткая" 32-битная арифметика для наших задач не подходит - из-за вычислительных погрешностей возникали грубые ошибки в обработке экспериментальных данных. На 64 битах всё считалось гладко.

С другой стороны, для аудио- и видеоприложений 32бит вполне достаточно. Если у кого есть желание - могу кинуть 3DNow!-код в личку.

На полноценном SSE3 ускорение будет больше чем в 2 раза, однозначно. Но, насколько я знаю, для этого нужно сначала войти в х64-режим.
Еще круче было бы задействовать ресурсы второго (третьего, четвертого...) процессора.
: Кстати, кто-нибудь знает, может ли одно ядро CPU работать в 64-битном режиме, если вторая голова крутится на 32 битах?

Но самое крутое, конечно, это "портировать" задачу на GPU...

Mon Oct 04, 2010 12:39 pm

art_zh

Оффтопик.
Могут. Инициализация примерно так и проходит.

Зачем х64 для SSE3 ? SSE2/3 считает с двойной точностью.
movapd, mulpd, addpd, minpd и т.п.

Mon Oct 04, 2010 1:18 pm

Serge
SSE:Угу, теперь вижу. Будет очень интересно попробовать.

: офигеть! так это можно крутить ядро (включая диспетчер задач и менеджер памяти) в х32, а приложения - в х64 ?

Mon Oct 04, 2010 1:56 pm

Можно, но в пределах 4 Гб адресов.

Mon Oct 04, 2010 2:13 pm

Можно и выше - главное чтобы таблицы страниц лежали ниже 4Г.

Mon Oct 04, 2010 3:25 pm

Мало поможет. Тем более что таблицы страниц там разные. И 32х ядро не может получить доступ к данным выше 4 Гб без ремапа, геморрой одним словом.

Tue Oct 05, 2010 1:49 am

Serge
(выпрыгивая из оффтопика прямиком в сабж) Только открыл SSE-букварь и вижу:

AMD64 Programmer's Manual том 4 wrote:"Длинный" 64-битный режим предоставляет SSE-программам четыре существенных преимущества:
1) доступ к восьми дополнительным XMM регистрам;
2) доступ к восьми дополнительным 64-битным РОНам;
3) 64-битное виртуальное адресное пространство, и
4) RIP-адресацию.

Не знаю, будет ли двухголовая "Колибри32 + SSE_64" большим геморроем, чем просто "Колибри64"
Но сейчас все равно не до этого.

Tue Oct 05, 2010 4:31 pm

Стопроцентно будет. Для х64 нужны свои обработчики прерываний/исключений и переключатель контекстов. Но такой гибридный вариант интересен для числодробилок. На загрузочном ядре работает х32, а на остальных ядрах задачи х64 в пакетном режиме + минимальный гипервизор для обслуживания ввода-вывода. Это конечно совсем не SMP, но намного проще и понятней чем CPU+GPU. Мне даже интересно стало.

Wed Nov 03, 2010 6:05 pm

бывают же такие совпадения:

12 октября Вилле добавил Фурье-серсис в ядро MeOS64

Code: Select all

SYSTEM CALL 150
From version 0.94, an 'Audio Processing' system call was introduced in Menuet 64. The following functions are available, and may be expanded later:
   1. Complex to complex inplace FFT (Radix-4 decimation in time)
   2. Sample format and wave format converter
   3. FFT convolution kernel (equalizer)
   4. SINC resampling kernel

вместе с БПФ в ядро забили SSE-упаковку данных и свертку функций (convolution).
невероятно, но факт: спектр-эквалайзинг и сшивка фреймов тоже будут выполняться ядром (?)

Wed Nov 03, 2010 6:59 pm

Мне так кажется он по прежнему идет путем, которым шло первоначальное развитие Linux. От которого уже отказались в сторону модульности.

Wed Nov 03, 2010 8:53 pm

Там и 3D есть, чего мелочиться.

Mon Sep 19, 2011 2:03 am

Залил на SVN.
programs/other/fft

Fast Fourier Transform

Who is online