Fast Fourier Transform

...
  • Не считаю себя большим специалистом, но рекомендовал бы обратиться к опыту Box_Lib:
    1) Все данные хранятся не в коде программы, а либо в стеке, либо в специально выделенном блоке данных, который впрочем может использоваться как список указателей для других динамически выделяемых областей памяти. Это обеспечит реентерабельность - все равно со временем сделаем менеджер библиотек с разделяемой памятью и загружаться туда будут только реентерабельные библиотеки.
    2) Вызов кода желательно делать в стандарте ЯВУ, т.е. предавая через стек данные, например указатель на блок данных как в Box_Lib.
    3) Один из регистров будет использоваться как базовый и будет указывать на начало блока данных. Лучше всего на эту роль подходит EBP. В крайнем случае его можно затолкнуть в стек и восстановить обратно при необходимости. В начале программы определяются EQU для подмены в коде.
  • Mario

    Спасибо.

    по пункту 1) тут всё ясно - библиотека будет просто перемалывать массив данных, указатель на которых ей передаст пользовательская программа. А уж что это будет за массив, будет ли он статическим или выделяться динамически по ходу дела - это забота пользователя.
    Есть еще заморочка со вспомогательными массивами синусов и косинусов. Эти массивы нужны, чтобы не тратить время на повторные вычисления при каждом новом преобразовании. Сейчас они статически хранятся в FHT4i.inc, но если исходить из принципа "одна реентерабельная библиотека для всех приложений", то их тоже надо будет отправить на территорию пользователя.

    п. 2) - тут желательно поподробнее, с Box_Lib я совершенно не знаком. Какой конкретно кусок кода можно использовать как прототип?

    3) ebp у меня нигде не используется, так что тут проблем не будет.
  • п. 2) - тут желательно поподробнее, с Box_Lib я совершенно не знаком. Какой конкретно кусок кода можно использовать как прототип?
    Проще всего смотреть более простой код. Например pathshow.mac - это самый маленький и простой для понимания кусок кода на текущий момент. Как оформлена сама библиотека смотри в box_lib.asm

    Можно еще Proc_Lib посмотреть как пример. Только я не думаю, что тебе стоит именно туда функцию помещать - для математических функций думаю лучше отдельную библиотеку сделать. Что-то типа Mach_Lib.obj
  • Mario

    Еще раз спасибо, посмотрю.
    Только я не думаю, что тебе стоит именно туда функцию помещать - для математических функций думаю лучше отдельную библиотеку сделать.
    Фурье-методы слишком громоздкие и специализированные, для них подошла бы отдельная, не зависящая от других мат. функций библиотека (как в Линуксе).

    ________________________________________

    Тут еще один вопрос возник по ходу дела: в случае с реентерабельной библиотекой нужно будет как-то разруливать конкуренцию за ресурсы FPU. Сохранение контекста FPU очень дорого обходится при переключении задач.
    Может, имеет смысл какой-то мьютекс предусмотреть? Или лучше очередь запросов?

    ________________________________________

    N.B. На эту тему принцип "предлагаешь - делай сам" НЕ РАСПРОСТРАНЯЕТСЯ.

    Любые компетентные соображения, вопросы и хотелки по сабжу горячо приветствуются.
  • Я могу ошибаться, то тема FPU уже поднималась раньше и ядро сохраняет и восстанавливает это дело при переключении. Насчет мьютексов думай сам - я тут не представляю как выкручиваться.
  • art_zh

    Смена контекста FPU обходится не так и дорого. Мьютекс здесь поможет мало потому что FPU используется ядром в отрисовке фона и звуковыми драйверами. Квант задачи 10 миллисекунд. Переключение FPU - несколько микросекунд. Это можно уточнить. Потеря в быстродействии на ожидании мьютекса будет больше.

    Если массив создаваемый MakeSinCosTable всегда одинаков то его лучше сделать статическим в сегменте кода. diamond давно сделал библиотеки расшаренными. Или использовать общую память.
  • Serge wrote:art_zh
    diamond давно сделал библиотеки расшаренными. Или использовать общую память.
    Сейчас поговорил с diamond'ом и выяснил неизвестные для себя вещи - они мельком описаны на форуме. Хотя ради такого глобального шага можно было целую тему создать.

    Как выясняется со слов автора разработки:
    Принцип copy-on-write
    Не измененные страницы у одной и той же библиотеки во всех процессах физически ссылаются на исходную копию.
    Все работает через обычную загрузку библиотек через ф.68.
    Изначально при загрузке все страницы библиотеки ссылаются на надёжную копию внутри ядра. При первой записи на страницу внутри библиотеки происходит копирование и возникает специальная страница для этого процесса. В итоге все не измененные страницы во всех процессах ссылаются на одну и ту же физическую.
    Изначально реализовано в ревизии 1289, потом ещё несколько фиксов было (1292, 1311).
    Дублирование библиотек проверяется по полному имени файла (включая полный путь к файлу) и времени модификации. Система помнит, какие библиотеки загружены.
    Как только библиотека записывает что-то внутрь себя - ссылка на исходную копию рвётся и создаётся специальная версия страницы под записавший процесс.
    Если все приложения использующие библиотеку завершены, тогда библиотека выгружается.
    Есть счётчик ссылок как только он обнуляется - происходит выгрузка.
    Наличие расшаривания библиотеки можно проверить по размеру свободной памяти.
    Теперь можно сколько угодно копий библиотеки вызывать - если она реентерабельна, то код не будет дублироваться.
    Если честно я очень рад. :mrgreen:
  • Mario wrote:Сейчас поговорил с diamond'ом и выяснил неизвестные для себя вещи - они мельком описаны на форуме. Хотя ради такого глобального шага можно было целую тему создать.
    это точно. А еще лучше - статью в Вики. Ковыряясь в исходниках, ни за что не поймешь в чем была суть гениальной задумки...
    Принцип copy-on-write... При первой записи на страницу внутри библиотеки происходит копирование и возникает специальная страница для этого процесса....
    Теперь можно сколько угодно копий библиотеки вызывать - если она реентерабельна, то код не будет дублироваться.
    Если честно я очень рад. :mrgreen:
    А я - не очень.
    Получается, что если используется хотя бы одна локальная переменная для временного хранения данных (у меня их 20), то такая библиотека уже не будет считаться реентерабельной, и такой код будет дублироваться ( ! ) персонально для каждого нового вызывающего приложения?
    Serge wrote: Смена контекста FPU обходится не так и дорого. Мьютекс здесь поможет мало потому что FPU используется ядром в отрисовке фона и звуковыми драйверами. Квант задачи 10 миллисекунд. Переключение FPU - несколько микросекунд. Это можно уточнить. Потеря в быстродействии на ожидании мьютекса будет больше.
    Иногда и микросекунды приходится считать поштучно.
    У меня, например, каждую микросекунду во входном фреймбуфере накапливается около пятисот новых пикселей. Переполнения буфера приводят к заметным дырам.
    Конечно, не у всех такой экстрим, но все-таки хотелось бы для библиотеки быстрого частотного анализа продумать какую-то оптимизацию по времени.
    Serge wrote:Если массив создаваемый MakeSinCosTable всегда одинаков то его лучше сделать статическим в сегменте кода. diamond давно сделал библиотеки расшаренными. Или использовать общую память.
    Размер массивов разный (четверть размера массива данных).
    А что есть почитать насчет общей памяти?
    Last edited by art_zh on Tue Sep 21, 2010 8:45 pm, edited 1 time in total.
  • Библиотека использующая локальное хранилище данных внутри себя, а не в отдельной выделяемой области - по определению не может считаться реентерабельной. Либо выдаст неверный результат при двух и более обращениях одновременно, либо приведет выходу за пределы границ памяти с генерацией исключения Page Fault.

    Реентреабельная имеет полностью неизменный код, в котором не хранятся локальные переменные. Так что придется допиливать и помещать все либо в стек, либо в блок данных, либо в выделяемую область памяти указатель на которую храниться в стеке и или блоке данных. В самом реентерабельном коде могут храниться только константы.
  • Mario wrote:Библиотека использующая локальное хранилище данных внутри себя, а не в отдельной выделяемой области - по определению не может считаться реентерабельной.
    С точки зрения 68-й функции - да, не может. Теперь мне это очевидно.

    А в принципе - очень даже может: если имеет конвейерную структуру с полной изоляцией последующей фазы конвейера от предыдущей.

    Фурье-анализ в этом отношении - классический пример конвейеризируемого алгоритма.

    Serge, а как реентерабельность обеспечена в ATIKMS?
    Last edited by art_zh on Tue Sep 21, 2010 9:08 pm, edited 1 time in total.
  • Так ведь текущие условия соблюсти тоже не особо сложно. Зачем выдавливать из себя страшный код, когда можно под текущие условия адаптировать. Мне так кажется мы спорим на пустом месте. Среда есть и под не пишутся библиотеки, а никак не наоборот.
  • Mario

    Я не спорю с очевидными фактами.

    Так, ворчу по поводу необходимости переделки кода.

    И заодно интересуюсь как лучше это сделать.
    Евангелие от Иоанна: стих 1

    Code: Select all

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

    В примере размер был прописан в исходниках.
    Если величина таблицы зависит от объёма входных данных то под каждую задачу стоит создавать отдельный контекст и хранить там все локальные параметры
    context = fht_create_context(params);
    и освобождать его при завершении работы
    fht_destroy_context(context);
    У меня, например, каждую микросекунду во входном фреймбуфере накапливается около пятисот новых пикселей. Переполнения буфера приводят к заметным дырам.
    А каков размер буфера ?

    В atikms линуксовая часть драйвера защищена мьютексами. А самописная нет :oops: Теоретически два потока могут одновременно устанавливать разные видеорежимы. В следующем релизе я это исправлю.
  • Serge
    Угу, так и будет: в контексте приложения останутся
    1) массивы данных (их может быть много) и
    2) тригонометрические таблицы. Их в большинстве случаев нужно две, но может потребоваться несколько пар (например для сжатия данных или при решении сеточных уравнений с частными производными).
    А может и не потребоваться ни одной: если массив данных состоит из 16 элементов, то вся тригонометрия сводится к простым суммам, а в 64-элементном преобразовании требуются всего 48 операций умножения на 4 разных константы.

    Локальные переменные (внутри библиотеки) придется забивать в стек. Хорошо что регистр EBP оставил про запас - он для этого очень пригодится.
    А каков размер буфера ?
    8Mb, если точнее - счетверённый фреймбуфер (по 2Мб на каждый "цвет") с BM_DMA-записью из PCIe x8 устройства блоками по 128 байт. В самом устройстве есть собственный входной 2М FIFO-буфер и крутонавороченный контроль DMA с возможностью обрезки ненужных мест кадра (см. ниже).
    Чтение целого фрейма в принципе возможно, но реально это будет рваная картинка из нескольких десятков наложенных друг на друга полос из разных кадров.

    Поэтому приходится заранее выбирать внутри кадра несколько десятков небольших областей (64х16 пикселей) и считывать/обрабатывать/сохранять информацию только с этих мест, синхронно с внешним модулятором. А остальную картинку - выкидывать, чтоб не зевнуть новый кадр.
  • Who is online

    Users browsing this forum: Ahrefs [Bot] and 4 guests