Fast Fourier Transform

...
  • Нет, 1сек это полный абсурд - мне для этого потребуется гигабайтный буфер!

    Я понял к чему ты клонишь - в равноправной многозадачной среде надо гарантировать, что за полный цикл управления заданиями не произойдет переполнения входного буфера.

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

    Другой вариант - сделать среду неравноправной, с приоритетом одной "специальной" задачи. Простейший вариант - приоритетной задаче назначаются все четные кванты времени, а нечетные отдаются всем остальным.

    Я пока использую первый подход, но (в Kolibri-A) хочу попробовать и второй.
    Евангелие от Иоанна: стих 1

    Code: Select all

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

    В ядре часто встречается cli. 1 секунда наверное перебор, но 0.2 сек. желательно. А сколько там мегабайт в секунду прокачивается ?
  • Serge
    cli вроде бы встречаются часто, но мешают редко. Самые длинные закрытые для прерываний окна - во время дисковых операций - действительно способны сломать любой буфер, будь он хоть на 2Г. Кто хоть раз копировал репозиторий с одного диска на другой :( , тот в теме.

    после них с большим отрывом идут cli как необходимое зло при операциях менеджера памяти и переключении задач . Тут счет идет на единицы...десятки микросекунд, мегабайтного буфера хватит за глаза.

    (или я что-то упустил? инициализация системы не в счет)

    У меня во фреймбуфер (= первичный буфер) закачивается до 700МБ/с (максимум), но реально скорость приходится аппаратно ограничивать в пределах 200МБ/с.
    Пиковая пропускная способность PCIe x8 в BM_DMA-режиме - почти 2Гбайт/с. Насколько я знаю, ни одна х86-система не способна работать с такой лавиной информации в реальном времени.
  • art_zh

    usb клава, мышь и диски обрабатываются через SMM. Сколько длится этот выход в астрал неизвестно. Под такие задачи надо оптимизировать ядро и систему. Ставить PS/2, отключить сетевой стек, разрешение экрана поменьше.
    Куда эти байты потом идут ? На диск ?

    У меня ещё нубский вопрос. Когда устройство пишет в системную память что происходит с кешем процессора. Автоматом помечается как недостоверный или там некешируемая память ?
  • Serge wrote:usb клава, мышь и диски обрабатываются через SMM. Сколько длится этот выход в астрал неизвестно. Под такие задачи надо оптимизировать ядро и систему. Ставить PS/2, отключить сетевой стек, разрешение экрана поменьше.
    Куда эти байты потом идут ? На диск ?
    (умеешь ты задавать больные вопросы, однако).
    На уровне BIOS отключено все что только можно.
    После обработки данные в сильно сжатом виде записываются в собственный "длинный" буфер программы, откуда сливаются на диск... каждый час. Пока что эксперименты идут меньше часа, но когда пойдут длинные измерения - будут и длинные дыры.

    Входной буфер конечно некешируемый.
    Для Фурье хочу один физический блок маппить на два разных линейных диапазона: один кешируемый (для быстрой обработки), другой - нет (для загрузки/выгрузки данных).
  • art_zh

    Кеш работает с физическими адресами.
    Интел обещает непредсказуемое поведение процессора если одна физическая память мапится с разными атрибутами кеширования.

    А если сделать кешируемый буфер (write-back) и перед обработкой данных выполнять цикл clfush ? Скорость чтения должна вырасти в разы. Предполагается что процессор только читает данные из буфера.
  • Спасибо что предупредил - я об этой заморочке не слышал.

    Тогда надо конечно явно закрутить кэш-контроль как положено. Скорость действительно должна резко возрасти, если только не будет смены задачи с принудительной выгрузкой кэша
  • art_zh

    В продолжение нубского вопроса. Разве PCI не умеет разруливать проблемы с кешем ? Специальные циклы сообщающие процессору о недостоверности кеша. В SMP кеш разных процессоров ведь синхронизируется.
  • PCI тут ни при чем - она только кладет данные во входной буфер, откуда драйвер делает предвыборку для входных массивов приложения-обработчика.

    Именно с этими массивами будет работать Фурье (цифровые фильтры + корреляция по координате).

    ИМХО Фурье должен дважды явно объявлять кэш этих массивов недостоверным: на входе и после окончания преобразования. В процессе работы они должны кэшироваться.
  • art_zh

    Достаточно один раз, перед чтением.

    В Линуксе память выделяется из специальной зоны для ДМА. Разбирался с какими аттрибутами кеширования там мапятся страницы, но исходники сильно запутаны. Думаю что там обычная write-back память. Пример с clflush приводился Intel для AGP, когда буфер граббера мапится через agp gart, потому что agp не поддерживала синхронизацию процессорного кеша. PCI должна такую синхронизацию поддерживать. Драйвера usb выделяют буферы из обычной кешируемой памяти. Драйвер HD в Колибри тоже держит буфер в кешируемой памяти. Store fence перед записью на диск там бы не помешал.
  • Доковырял fht4i.inc (пока еще небиблиотечную версию), выудил оттуда 20 мелких багов.

    Отладка FPU-кода в Колибри - совершенно безнадежное занятие, пришлось портировать FASM-код в MASM-вид и вставлять один за другим ассемблерные куски в исходную Сишную программу.

    С каждым новым блоком программа набирала обороты (кто еще там говорит о достоинствах 'современных оптимизирующих компиляторов'?):
    - исходный Си-код (преобразование по 1024 точкам) - 180 тыс. тактов;
    - замена BitInvert и Step1 чистым ассемблерным кодом - 160 тыс.
    - замена Step2 - 120 тыс
    - замена Step3 - 80 тыс. тактов!

    И это - в масдае.
    Сейсчас доведу тестовую программу под Колибри - посмотрим как у нас.
  • Serge wrote:Драйвер HD в Колибри тоже держит буфер в кешируемой памяти.
    Оно так исключительно по причине древнего DMA контроллера (изначально я писал этот код). Да и еще он работает только с реальными адресами ниже 16 Мб. Возможно на SATA контроллерах что-то и поменялось, но я уже там мне ковырялся.

    art_zh wrote: С каждым новым блоком программа набирала обороты (кто еще там говорит о достоинствах 'современных оптимизирующих компиляторов'?):
    - исходный Си-код (преобразование по 1024 точкам) - 180 тыс. тактов;
    - замена BitInvert и Step1 чистым ассемблерным кодом - 160 тыс.
    - замена Step2 - 120 тыс
    - замена Step3 - 80 тыс. тактов!

    И это - в масдае.
    От души смеялся в очередной раз. Код на ассемблере при общих условиях всегда быстрее. Те кто кричит про компиляторы - реально не писали много кода на ассемблере, в связи со многими вопросами. Главный (и на самом деле главнейший из них) упирается в лень. Однако наличие других людей, пишущих код на ассемблере, портит всю картину и люди начинают доказывать, прежде всего для самих себя, что они правы, но мы то знаем... :lol:

    Сейчас Серж скажет, что я дурак и вообще. :wink:

    Но реально до Менует, а впоследствии Колибри не было таких крупных проектов написанных на ассемблере. Но если автор первой писал исключительно ради возможности доказать что это возможно, то мы пишем не ради этого. Все уже доказано. :mrgreen:
  • Mario

    Не скажу. Для подобных числодробительных задач ассемблер самое то. Особенно если писать с учётом архитектуры, развернуть циклы, вставить префетчи, нагрузить SSE. А вот писать на асме обычный код имхо тратить время впустую.
  • Теперь о грустном: в Колибри БПХ по 1024 точкам крутится в среднем около 120 тыс. тактов - на 50% дольше, чем в Винде.
    В чем дело - пока еще не разобрался
    Last edited by art_zh on Sun Oct 03, 2010 1:20 pm, edited 1 time in total.
  • Who is online

    Users browsing this forum: No registered users and 2 guests