Завершаю вычесывать багов в новой программе быстрого преобразования Хартли (сверхбыстрое преобразование Фурье).
ftp://kolibrios.org/users/art_zh/FHT/
основной код лежит в файле FHT4i.inc и представляет собой основательно оптимизированный (вручную) порт моей старой сишной программы четырехточечного FHT.
Требуется совет специалистов: как лучше доработать код, чтобы превратить его в нормальную, доступную другим приложениям библиотеку?
Такая библиотека была бы очень полезна для широкого круга приложений (частотный анализ, статобработка данных, решение дифференциальных уравнений, сжатие и распознавание звука и изображений, и многое другое)
Fast Fourier Transform
-
Евангелие от Иоанна: стих 1[/size]
Code: Select all
; В начале было Слово: B32: mov ax, os_stack ; Selector for os
Не считаю себя большим специалистом, но рекомендовал бы обратиться к опыту Box_Lib:
1) Все данные хранятся не в коде программы, а либо в стеке, либо в специально выделенном блоке данных, который впрочем может использоваться как список указателей для других динамически выделяемых областей памяти. Это обеспечит реентерабельность - все равно со временем сделаем менеджер библиотек с разделяемой памятью и загружаться туда будут только реентерабельные библиотеки.
2) Вызов кода желательно делать в стандарте ЯВУ, т.е. предавая через стек данные, например указатель на блок данных как в Box_Lib.
3) Один из регистров будет использоваться как базовый и будет указывать на начало блока данных. Лучше всего на эту роль подходит EBP. В крайнем случае его можно затолкнуть в стек и восстановить обратно при необходимости. В начале программы определяются EQU для подмены в коде.
1) Все данные хранятся не в коде программы, а либо в стеке, либо в специально выделенном блоке данных, который впрочем может использоваться как список указателей для других динамически выделяемых областей памяти. Это обеспечит реентерабельность - все равно со временем сделаем менеджер библиотек с разделяемой памятью и загружаться туда будут только реентерабельные библиотеки.
2) Вызов кода желательно делать в стандарте ЯВУ, т.е. предавая через стек данные, например указатель на блок данных как в Box_Lib.
3) Один из регистров будет использоваться как базовый и будет указывать на начало блока данных. Лучше всего на эту роль подходит EBP. В крайнем случае его можно затолкнуть в стек и восстановить обратно при необходимости. В начале программы определяются EQU для подмены в коде.
Mario
Спасибо.
по пункту 1) тут всё ясно - библиотека будет просто перемалывать массив данных, указатель на которых ей передаст пользовательская программа. А уж что это будет за массив, будет ли он статическим или выделяться динамически по ходу дела - это забота пользователя.
Есть еще заморочка со вспомогательными массивами синусов и косинусов. Эти массивы нужны, чтобы не тратить время на повторные вычисления при каждом новом преобразовании. Сейчас они статически хранятся в FHT4i.inc, но если исходить из принципа "одна реентерабельная библиотека для всех приложений", то их тоже надо будет отправить на территорию пользователя.
п. 2) - тут желательно поподробнее, с Box_Lib я совершенно не знаком. Какой конкретно кусок кода можно использовать как прототип?
3) ebp у меня нигде не используется, так что тут проблем не будет.
Спасибо.
по пункту 1) тут всё ясно - библиотека будет просто перемалывать массив данных, указатель на которых ей передаст пользовательская программа. А уж что это будет за массив, будет ли он статическим или выделяться динамически по ходу дела - это забота пользователя.
Есть еще заморочка со вспомогательными массивами синусов и косинусов. Эти массивы нужны, чтобы не тратить время на повторные вычисления при каждом новом преобразовании. Сейчас они статически хранятся в FHT4i.inc, но если исходить из принципа "одна реентерабельная библиотека для всех приложений", то их тоже надо будет отправить на территорию пользователя.
п. 2) - тут желательно поподробнее, с Box_Lib я совершенно не знаком. Какой конкретно кусок кода можно использовать как прототип?
3) ebp у меня нигде не используется, так что тут проблем не будет.
Проще всего смотреть более простой код. Например pathshow.mac - это самый маленький и простой для понимания кусок кода на текущий момент. Как оформлена сама библиотека смотри в box_lib.asmп. 2) - тут желательно поподробнее, с Box_Lib я совершенно не знаком. Какой конкретно кусок кода можно использовать как прототип?
Можно еще Proc_Lib посмотреть как пример. Только я не думаю, что тебе стоит именно туда функцию помещать - для математических функций думаю лучше отдельную библиотеку сделать. Что-то типа Mach_Lib.obj
Mario
Еще раз спасибо, посмотрю.
________________________________________
Тут еще один вопрос возник по ходу дела: в случае с реентерабельной библиотекой нужно будет как-то разруливать конкуренцию за ресурсы FPU. Сохранение контекста FPU очень дорого обходится при переключении задач.
Может, имеет смысл какой-то мьютекс предусмотреть? Или лучше очередь запросов?
________________________________________
N.B. На эту тему принцип "предлагаешь - делай сам" НЕ РАСПРОСТРАНЯЕТСЯ.
Любые компетентные соображения, вопросы и хотелки по сабжу горячо приветствуются.
Еще раз спасибо, посмотрю.
Фурье-методы слишком громоздкие и специализированные, для них подошла бы отдельная, не зависящая от других мат. функций библиотека (как в Линуксе).Только я не думаю, что тебе стоит именно туда функцию помещать - для математических функций думаю лучше отдельную библиотеку сделать.
________________________________________
Тут еще один вопрос возник по ходу дела: в случае с реентерабельной библиотекой нужно будет как-то разруливать конкуренцию за ресурсы FPU. Сохранение контекста FPU очень дорого обходится при переключении задач.
Может, имеет смысл какой-то мьютекс предусмотреть? Или лучше очередь запросов?
________________________________________
N.B. На эту тему принцип "предлагаешь - делай сам" НЕ РАСПРОСТРАНЯЕТСЯ.
Любые компетентные соображения, вопросы и хотелки по сабжу горячо приветствуются.
Я могу ошибаться, то тема FPU уже поднималась раньше и ядро сохраняет и восстанавливает это дело при переключении. Насчет мьютексов думай сам - я тут не представляю как выкручиваться.
art_zh
Смена контекста FPU обходится не так и дорого. Мьютекс здесь поможет мало потому что FPU используется ядром в отрисовке фона и звуковыми драйверами. Квант задачи 10 миллисекунд. Переключение FPU - несколько микросекунд. Это можно уточнить. Потеря в быстродействии на ожидании мьютекса будет больше.
Если массив создаваемый MakeSinCosTable всегда одинаков то его лучше сделать статическим в сегменте кода. diamond давно сделал библиотеки расшаренными. Или использовать общую память.
Смена контекста FPU обходится не так и дорого. Мьютекс здесь поможет мало потому что FPU используется ядром в отрисовке фона и звуковыми драйверами. Квант задачи 10 миллисекунд. Переключение FPU - несколько микросекунд. Это можно уточнить. Потеря в быстродействии на ожидании мьютекса будет больше.
Если массив создаваемый MakeSinCosTable всегда одинаков то его лучше сделать статическим в сегменте кода. diamond давно сделал библиотеки расшаренными. Или использовать общую память.
Сейчас поговорил с diamond'ом и выяснил неизвестные для себя вещи - они мельком описаны на форуме. Хотя ради такого глобального шага можно было целую тему создать.Serge wrote:art_zh
diamond давно сделал библиотеки расшаренными. Или использовать общую память.
Как выясняется со слов автора разработки:
Теперь можно сколько угодно копий библиотеки вызывать - если она реентерабельна, то код не будет дублироваться.Принцип copy-on-write
Не измененные страницы у одной и той же библиотеки во всех процессах физически ссылаются на исходную копию.
Все работает через обычную загрузку библиотек через ф.68.
Изначально при загрузке все страницы библиотеки ссылаются на надёжную копию внутри ядра. При первой записи на страницу внутри библиотеки происходит копирование и возникает специальная страница для этого процесса. В итоге все не измененные страницы во всех процессах ссылаются на одну и ту же физическую.
Изначально реализовано в ревизии 1289, потом ещё несколько фиксов было (1292, 1311).
Дублирование библиотек проверяется по полному имени файла (включая полный путь к файлу) и времени модификации. Система помнит, какие библиотеки загружены.
Как только библиотека записывает что-то внутрь себя - ссылка на исходную копию рвётся и создаётся специальная версия страницы под записавший процесс.
Если все приложения использующие библиотеку завершены, тогда библиотека выгружается.
Есть счётчик ссылок как только он обнуляется - происходит выгрузка.
Наличие расшаривания библиотеки можно проверить по размеру свободной памяти.
Если честно я очень рад.
![Mr. Green :mrgreen:](./images/smilies/icon_mrgreen.gif)
это точно. А еще лучше - статью в Вики. Ковыряясь в исходниках, ни за что не поймешь в чем была суть гениальной задумки...Mario wrote:Сейчас поговорил с diamond'ом и выяснил неизвестные для себя вещи - они мельком описаны на форуме. Хотя ради такого глобального шага можно было целую тему создать.
А я - не очень.Принцип copy-on-write... При первой записи на страницу внутри библиотеки происходит копирование и возникает специальная страница для этого процесса....
Теперь можно сколько угодно копий библиотеки вызывать - если она реентерабельна, то код не будет дублироваться.
Если честно я очень рад.
Получается, что если используется хотя бы одна локальная переменная для временного хранения данных (у меня их 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.
Реентреабельная имеет полностью неизменный код, в котором не хранятся локальные переменные. Так что придется допиливать и помещать все либо в стек, либо в блок данных, либо в выделяемую область памяти указатель на которую храниться в стеке и или блоке данных. В самом реентерабельном коде могут храниться только константы.
Реентреабельная имеет полностью неизменный код, в котором не хранятся локальные переменные. Так что придется допиливать и помещать все либо в стек, либо в блок данных, либо в выделяемую область памяти указатель на которую храниться в стеке и или блоке данных. В самом реентерабельном коде могут храниться только константы.
С точки зрения 68-й функции - да, не может. Теперь мне это очевидно.Mario wrote:Библиотека использующая локальное хранилище данных внутри себя, а не в отдельной выделяемой области - по определению не может считаться реентерабельной.
А в принципе - очень даже может: если имеет конвейерную структуру с полной изоляцией последующей фазы конвейера от предыдущей.
Фурье-анализ в этом отношении - классический пример конвейеризируемого алгоритма.
Serge, а как реентерабельность обеспечена в ATIKMS?
Last edited by art_zh on Tue Sep 21, 2010 9:08 pm, edited 1 time in total.
Так ведь текущие условия соблюсти тоже не особо сложно. Зачем выдавливать из себя страшный код, когда можно под текущие условия адаптировать. Мне так кажется мы спорим на пустом месте. Среда есть и под не пишутся библиотеки, а никак не наоборот.
Mario
Я не спорю с очевидными фактами.
Так, ворчу по поводу необходимости переделки кода.
И заодно интересуюсь как лучше это сделать.
Я не спорю с очевидными фактами.
Так, ворчу по поводу необходимости переделки кода.
И заодно интересуюсь как лучше это сделать.
Евангелие от Иоанна: стих 1[/size]
Code: Select all
; В начале было Слово:
B32: mov ax, os_stack ; Selector for os
art_zh
В примере размер был прописан в исходниках.
Если величина таблицы зависит от объёма входных данных то под каждую задачу стоит создавать отдельный контекст и хранить там все локальные параметры
context = fht_create_context(params);
и освобождать его при завершении работы
fht_destroy_context(context);
В atikms линуксовая часть драйвера защищена мьютексами. А самописная нет
Теоретически два потока могут одновременно устанавливать разные видеорежимы. В следующем релизе я это исправлю.
В примере размер был прописан в исходниках.
Если величина таблицы зависит от объёма входных данных то под каждую задачу стоит создавать отдельный контекст и хранить там все локальные параметры
context = fht_create_context(params);
и освобождать его при завершении работы
fht_destroy_context(context);
А каков размер буфера ?У меня, например, каждую микросекунду во входном фреймбуфере накапливается около пятисот новых пикселей. Переполнения буфера приводят к заметным дырам.
В atikms линуксовая часть драйвера защищена мьютексами. А самописная нет
![Embarassed :oops:](./images/smilies/icon_redface.gif)
Serge
Угу, так и будет: в контексте приложения останутся
1) массивы данных (их может быть много) и
2) тригонометрические таблицы. Их в большинстве случаев нужно две, но может потребоваться несколько пар (например для сжатия данных или при решении сеточных уравнений с частными производными).
А может и не потребоваться ни одной: если массив данных состоит из 16 элементов, то вся тригонометрия сводится к простым суммам, а в 64-элементном преобразовании требуются всего 48 операций умножения на 4 разных константы.
Локальные переменные (внутри библиотеки) придется забивать в стек. Хорошо что регистр EBP оставил про запас - он для этого очень пригодится.
Чтение целого фрейма в принципе возможно, но реально это будет рваная картинка из нескольких десятков наложенных друг на друга полос из разных кадров.
Поэтому приходится заранее выбирать внутри кадра несколько десятков небольших областей (64х16 пикселей) и считывать/обрабатывать/сохранять информацию только с этих мест, синхронно с внешним модулятором. А остальную картинку - выкидывать, чтоб не зевнуть новый кадр.
Угу, так и будет: в контексте приложения останутся
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: No registered users and 23 guests