Fast Fourier Transform

...
  • Вообще-то, согласно докам, точность представления данных в FPU - это рудимент каких-то там древних совместимостей, и никак не должна влиять на скорость вычислений.
    Но раз уж такое дело - для очистки совести поэкспериментировал со словом управления FPU, поставил разные размеры данных и разные режимы округления, а заодно и разные маски состояния.

    Эффекта нет.
  • art_zh wrote:Mario и Serge
    Эта тема тоже немного для другой дискуссии создавалась. Эта тема про Фурье. Очень надеюсь без обид.
    Никаких обид тему зачистил - выделил оффтопные посты в новую тему. Тема с микроядром тоже будет зачищена.
  • art_zh

    Похоже на проблему с кешем в данных или коде.
    Надо проверить выравнивание данных, выравнять циклы на линейку кеша, переместить код в другое место.
  • Перенес все локальные статические переменные в стек (вспомнил, что кэш программы объявляется недостоверным при каждой записи в него)
    Помогло, но незначительно - ускорение примерно на 10% (около 110 тыс. тактов против 80 тыс. в Винде).
    Масдай пока еще рулит: сдается мне, что там стек кешируется по writeback.
    А чего бы и у нас такую штуку не попробовать?
  • art_zh

    Так у нас вся память writeback кроме экранного буфера. Тот writecombined. А исходники тестирующей программы есть ? Может в них дело ?
  • Serge
    Свой старый Сишный исходник я тебе кидал в личку пару месяцев назад. Сейчас отправлю оптимизирванную версию.

    Выкладывать масдаевский код на FTP не буду, там только Колибри-версия без права портирования на другие платформы.
    Но принципиально они ничем не отличаются.

    Кстати, для чистоты эксперимента тестирование проводилось на двух совершенно одинаковых компутерах с одними настройками BIOS.
    Процессор - одноголовый Sempron 140 (1М кэш2), на котором у Винды по идее не должно быть никаких преимуществ.
  • Блин, нашел в чем дело!

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

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

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

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

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

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

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

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

    Code: Select all

    ; В начале было Слово:
    B32:        mov     ax, os_stack       ; Selector for os
    [/size]
  • А как насчет применения MMX и SSE(1,2,3)?
  • Mario
    Лет 8 назад я попробовал первые 2 шага преобразования переписать под инструкции 3DNow! первых Атлонов (про SSE тогда еще почти никто не слышал).
    Прирост скорости был довольно значительный (почти в 3 раза).

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

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

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

    Но самое крутое, конечно, это "портировать" задачу на GPU...
    Евангелие от Иоанна: стих 1

    Code: Select all

    ; В начале было Слово:
    B32:        mov     ax, os_stack       ; Selector for os
    [/size]
  • art_zh

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

    Зачем х64 для SSE3 ? SSE2/3 считает с двойной точностью.
    movapd, mulpd, addpd, minpd и т.п.
  • Serge
    SSE:Угу, теперь вижу. Будет очень интересно попробовать.

    : офигеть! так это можно крутить ядро (включая диспетчер задач и менеджер памяти) в х32, а приложения - в х64 ?
  • Можно, но в пределах 4 Гб адресов.
  • Можно и выше - главное чтобы таблицы страниц лежали ниже 4Г.
  • Who is online

    Users browsing this forum: No registered users and 3 guests