Board.KolibriOS.org

Официальный форум KolibriOS
Текущее время: Вс дек 17, 2017 12:52 pm

Часовой пояс: UTC+03:00




Начать новую тему  Ответить на тему  [ 57 сообщений ]  На страницу 1 2 3 4 След.
Автор Сообщение
 Заголовок сообщения: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 10:04 am 
Не в сети
Kernel Developer
Аватара пользователя

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

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

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

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

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


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


Вернуться к началу
   
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 11:24 am 
Не в сети
Kernel Developer
Аватара пользователя

Зарегистрирован: Пт авг 14, 2009 1:46 am
Сообщения: 1291
Mario

Спасибо.

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

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

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


Вернуться к началу
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 11:38 am 
Цитата:
п. 2) - тут желательно поподробнее, с Box_Lib я совершенно не знаком. Какой конкретно кусок кода можно использовать как прототип?

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

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


Вернуться к началу
   
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 12:29 pm 
Не в сети
Kernel Developer
Аватара пользователя

Зарегистрирован: Пт авг 14, 2009 1:46 am
Сообщения: 1291
Mario

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

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

________________________________________

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

________________________________________

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

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


Вернуться к началу
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 1:16 pm 
Я могу ошибаться, то тема FPU уже поднималась раньше и ядро сохраняет и восстанавливает это дело при переключении. Насчет мьютексов думай сам - я тут не представляю как выкручиваться.


Вернуться к началу
   
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 3:08 pm 
Не в сети
Kernel Developer

Зарегистрирован: Ср мар 08, 2006 6:25 pm
Сообщения: 3929
art_zh

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

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


Вернуться к началу
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 3:47 pm 
Serge писал(а):
art_zh
diamond давно сделал библиотеки расшаренными. Или использовать общую память.

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

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

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


Вернуться к началу
   
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 8:11 pm 
Не в сети
Kernel Developer
Аватара пользователя

Зарегистрирован: Пт авг 14, 2009 1:46 am
Сообщения: 1291
Mario писал(а):
Сейчас поговорил с diamond'ом и выяснил неизвестные для себя вещи - они мельком описаны на форуме. Хотя ради такого глобального шага можно было целую тему создать.

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

Цитата:
Принцип copy-on-write... При первой записи на страницу внутри библиотеки происходит копирование и возникает специальная страница для этого процесса....
Теперь можно сколько угодно копий библиотеки вызывать - если она реентерабельна, то код не будет дублироваться.
Если честно я очень рад. :mrgreen:

А я - не очень.
Получается, что если используется хотя бы одна локальная переменная для временного хранения данных (у меня их 20), то такая библиотека уже не будет считаться реентерабельной, и такой код будет дублироваться ( ! ) персонально для каждого нового вызывающего приложения?
Serge писал(а):
Смена контекста FPU обходится не так и дорого. Мьютекс здесь поможет мало потому что FPU используется ядром в отрисовке фона и звуковыми драйверами. Квант задачи 10 миллисекунд. Переключение FPU - несколько микросекунд. Это можно уточнить. Потеря в быстродействии на ожидании мьютекса будет больше.

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

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


Последний раз редактировалось art_zh Вт сен 21, 2010 8:45 pm, всего редактировалось 1 раз.

Вернуться к началу
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 8:17 pm 
Библиотека использующая локальное хранилище данных внутри себя, а не в отдельной выделяемой области - по определению не может считаться реентерабельной. Либо выдаст неверный результат при двух и более обращениях одновременно, либо приведет выходу за пределы границ памяти с генерацией исключения Page Fault.

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


Вернуться к началу
   
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 8:56 pm 
Не в сети
Kernel Developer
Аватара пользователя

Зарегистрирован: Пт авг 14, 2009 1:46 am
Сообщения: 1291
Mario писал(а):
Библиотека использующая локальное хранилище данных внутри себя, а не в отдельной выделяемой области - по определению не может считаться реентерабельной.


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

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

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

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


Последний раз редактировалось art_zh Вт сен 21, 2010 9:08 pm, всего редактировалось 1 раз.

Вернуться к началу
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 9:03 pm 
Так ведь текущие условия соблюсти тоже не особо сложно. Зачем выдавливать из себя страшный код, когда можно под текущие условия адаптировать. Мне так кажется мы спорим на пустом месте. Среда есть и под не пишутся библиотеки, а никак не наоборот.


Вернуться к началу
   
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 9:13 pm 
Не в сети
Kernel Developer
Аватара пользователя

Зарегистрирован: Пт авг 14, 2009 1:46 am
Сообщения: 1291
Mario

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

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

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

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


Вернуться к началу
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Вт сен 21, 2010 10:53 pm 
Не в сети
Kernel Developer

Зарегистрирован: Ср мар 08, 2006 6:25 pm
Сообщения: 3929
art_zh

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

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


Вернуться к началу
 Заголовок сообщения: Re: Fast Fourier Transform
СообщениеДобавлено: Ср сен 22, 2010 1:16 am 
Не в сети
Kernel Developer
Аватара пользователя

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

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

Цитата:
А каков размер буфера ?

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

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


Вернуться к началу
Показать сообщения за:  Поле сортировки  
Начать новую тему  Ответить на тему  [ 57 сообщений ]  На страницу 1 2 3 4 След.

Часовой пояс: UTC+03:00


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 1 гость


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Limited
Русская поддержка phpBB