Board.KolibriOS.org

Official KolibriOS board
It is currently Fri May 24, 2019 4:13 am

All times are UTC+03:00




Post new topic  Reply to topic  [ 57 posts ]  Go to page 1 2 3 4 Next
Author Message
 Post subject: Fast Fourier Transform
PostPosted: Tue Sep 21, 2010 10:04 am 
Offline
Kernel Developer
User avatar

Joined: Fri Aug 14, 2009 1:46 am
Posts: 1328
Завершаю вычесывать багов в новой программе быстрого преобразования Хартли (сверхбыстрое преобразование Фурье).

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

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

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

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


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


Top
   
PostPosted: Tue Sep 21, 2010 11:24 am 
Offline
Kernel Developer
User avatar

Joined: Fri Aug 14, 2009 1:46 am
Posts: 1328
Mario

Спасибо.

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

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

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


Top
   
PostPosted: Tue Sep 21, 2010 11:38 am 
Quote:
п. 2) - тут желательно поподробнее, с Box_Lib я совершенно не знаком. Какой конкретно кусок кода можно использовать как прототип?

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

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


Top
   
PostPosted: Tue Sep 21, 2010 12:29 pm 
Offline
Kernel Developer
User avatar

Joined: Fri Aug 14, 2009 1:46 am
Posts: 1328
Mario

Еще раз спасибо, посмотрю.
Quote:
Только я не думаю, что тебе стоит именно туда функцию помещать - для математических функций думаю лучше отдельную библиотеку сделать.

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

________________________________________

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

________________________________________

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

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


Top
   
PostPosted: Tue Sep 21, 2010 1:16 pm 
Я могу ошибаться, то тема FPU уже поднималась раньше и ядро сохраняет и восстанавливает это дело при переключении. Насчет мьютексов думай сам - я тут не представляю как выкручиваться.


Top
   
PostPosted: Tue Sep 21, 2010 3:08 pm 
Offline
Kernel Developer

Joined: Wed Mar 08, 2006 6:25 pm
Posts: 3952
art_zh

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

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


Top
   
PostPosted: Tue Sep 21, 2010 3:47 pm 
Serge wrote:
art_zh
diamond давно сделал библиотеки расшаренными. Или использовать общую память.

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

Как выясняется со слов автора разработки:
Quote:
Принцип copy-on-write
Не измененные страницы у одной и той же библиотеки во всех процессах физически ссылаются на исходную копию.
Все работает через обычную загрузку библиотек через ф.68.
Изначально при загрузке все страницы библиотеки ссылаются на надёжную копию внутри ядра. При первой записи на страницу внутри библиотеки происходит копирование и возникает специальная страница для этого процесса. В итоге все не измененные страницы во всех процессах ссылаются на одну и ту же физическую.
Изначально реализовано в ревизии 1289, потом ещё несколько фиксов было (1292, 1311).
Дублирование библиотек проверяется по полному имени файла (включая полный путь к файлу) и времени модификации. Система помнит, какие библиотеки загружены.
Как только библиотека записывает что-то внутрь себя - ссылка на исходную копию рвётся и создаётся специальная версия страницы под записавший процесс.
Если все приложения использующие библиотеку завершены, тогда библиотека выгружается.
Есть счётчик ссылок как только он обнуляется - происходит выгрузка.
Наличие расшаривания библиотеки можно проверить по размеру свободной памяти.

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


Top
   
PostPosted: Tue Sep 21, 2010 8:11 pm 
Offline
Kernel Developer
User avatar

Joined: Fri Aug 14, 2009 1:46 am
Posts: 1328
Mario wrote:
Сейчас поговорил с diamond'ом и выяснил неизвестные для себя вещи - они мельком описаны на форуме. Хотя ради такого глобального шага можно было целую тему создать.

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

Quote:
Принцип 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.

Top
   
PostPosted: Tue Sep 21, 2010 8:17 pm 
Библиотека использующая локальное хранилище данных внутри себя, а не в отдельной выделяемой области - по определению не может считаться реентерабельной. Либо выдаст неверный результат при двух и более обращениях одновременно, либо приведет выходу за пределы границ памяти с генерацией исключения Page Fault.

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


Top
   
PostPosted: Tue Sep 21, 2010 8:56 pm 
Offline
Kernel Developer
User avatar

Joined: Fri Aug 14, 2009 1:46 am
Posts: 1328
Mario wrote:
Библиотека использующая локальное хранилище данных внутри себя, а не в отдельной выделяемой области - по определению не может считаться реентерабельной.


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

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

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

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


Last edited by art_zh on Tue Sep 21, 2010 9:08 pm, edited 1 time in total.

Top
   
PostPosted: Tue Sep 21, 2010 9:03 pm 
Так ведь текущие условия соблюсти тоже не особо сложно. Зачем выдавливать из себя страшный код, когда можно под текущие условия адаптировать. Мне так кажется мы спорим на пустом месте. Среда есть и под не пишутся библиотеки, а никак не наоборот.


Top
   
PostPosted: Tue Sep 21, 2010 9:13 pm 
Offline
Kernel Developer
User avatar

Joined: Fri Aug 14, 2009 1:46 am
Posts: 1328
Mario

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

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

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

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


Top
   
PostPosted: Tue Sep 21, 2010 10:53 pm 
Offline
Kernel Developer

Joined: Wed Mar 08, 2006 6:25 pm
Posts: 3952
art_zh

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

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


Top
   
PostPosted: Wed Sep 22, 2010 1:16 am 
Offline
Kernel Developer
User avatar

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

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

Quote:
А каков размер буфера ?

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

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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 57 posts ]  Go to page 1 2 3 4 Next

All times are UTC+03:00


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited