Board.KolibriOS.org

Завершаю вычесывать багов в новой программе быстрого преобразования Хартли (сверхбыстрое преобразование Фурье).

ftp://kolibrios.org/users/art_zh/FHT/

основной код лежит в файле FHT4i.inc и представляет собой основательно оптимизированный (вручную) порт моей старой сишной программы четырехточечного FHT.

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

_________________
Узкий специалист подобен флюсу: полнота его - односторонняя.
Козьма Прутков

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

Mario

Спасибо.

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

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

3) ebp у меня нигде не используется, так что тут проблем не будет.

Проще всего смотреть более простой код. Например pathshow.mac - это самый маленький и простой для понимания кусок кода на текущий момент. Как оформлена сама библиотека смотри в box_lib.asm

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

Mario

Еще раз спасибо, посмотрю.

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

________________________________________

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

________________________________________

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

Любые компетентные соображения, вопросы и хотелки по сабжу горячо приветствуются.

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

art_zh

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

Если массив создаваемый MakeSinCosTable всегда одинаков то его лучше сделать статическим в сегменте кода. diamond давно сделал библиотеки расшаренными. Или использовать общую память.

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

Как выясняется со слов автора разработки:

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

это точно. А еще лучше - статью в Вики. Ковыряясь в исходниках, ни за что не поймешь в чем была суть гениальной задумки...


А я - не очень.
Получается, что если используется хотя бы одна локальная переменная для временного хранения данных (у меня их 20), то такая библиотека уже не будет считаться реентерабельной, и такой код будет дублироваться ( ! ) персонально для каждого нового вызывающего приложения?

Иногда и микросекунды приходится считать поштучно.
У меня, например, каждую микросекунду во входном фреймбуфере накапливается около пятисот новых пикселей. Переполнения буфера приводят к заметным дырам.
Конечно, не у всех такой экстрим, но все-таки хотелось бы для библиотеки быстрого частотного анализа продумать какую-то оптимизацию по времени.

Размер массивов разный (четверть размера массива данных).
А что есть почитать насчет общей памяти?

Библиотека использующая локальное хранилище данных внутри себя, а не в отдельной выделяемой области - по определению не может считаться реентерабельной. Либо выдаст неверный результат при двух и более обращениях одновременно, либо приведет выходу за пределы границ памяти с генерацией исключения Page Fault.

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

С точки зрения 68-й функции - да, не может. Теперь мне это очевидно.

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

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

Serge, а как реентерабельность обеспечена в ATIKMS?

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

Mario

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

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

И заодно интересуюсь как лучше это сделать.

_________________
Узкий специалист подобен флюсу: полнота его - односторонняя.
Козьма Прутков

art_zh

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

В atikms линуксовая часть драйвера защищена мьютексами. А самописная нет Теоретически два потока могут одновременно устанавливать разные видеорежимы. В следующем релизе я это исправлю.

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

Локальные переменные (внутри библиотеки) придется забивать в стек. Хорошо что регистр EBP оставил про запас - он для этого очень пригодится.


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

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