[Golikov 0]

Увы это не сортировка

Почему не сортировка? Очень даже сортировка.

После того как есть гистограмма распределения чисел, за 1 проход получается отсортированный массив.

 

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

 

для регистрации номера старого символа надо иметь ФИФО на 256 ячеек где сохранять номер(позицию в списке) последнего добавленного символа, соответственно с другого конца будет выпадать номер(позиция) самого старого символа.

 

И еще я бы сделал 2 массива, и перебрасывал бы из одного в другой.

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

 

И вот тут после наполнения массива середина будет в середине, всегда и однозначно. Потому что сохранены значения.

 

 

[RobFPGA 35]

Приветствую!

 

Мое предложение.

Имеем 256 х 16 память с произвольным доступом и сдвигом вперед, в которую можно записать данные по любому индексу, а следующие за ним - сдвинуть. Так получаем функцию вставки.

 

Ох - если бы Xilinx, Altera или кто еще сделал бы BRAM с такой функцией (ах мечты мечты) это было бы просто революция!!!.

Я в свое время пересел с Altera на Xilix только из за наличия LUT_RAM и SRL16 у последних. Как это упрощает жизнь простому FPGAшнику.

 

Удачи! Rob.

[ViKo 1]

А есть такая память?

256 х 16 = 4096 LE. :rolleyes:

[RobFPGA 35]

Приветствую!

 

256 х 16 = 4096 LE. :rolleyes:

дополнительно для LUT4

+ 32+256 LE write addres decoder,

+ (128+64+16+4)*16 LE read output mux

+ 256 LE shift control logic

 

Удачи! Rob.

[bognev 0]

По ресурсам в гистограммном фильтре получается:

ROM - 4 *36k Bram, 8 разрядные счетчики 256*8 FFs 8 Luts, и priority encoder 256->8, не могу оценить.Адекватно для решения поставленной задачи? Есть какие то подводные камни, которые я не вижу?

Изменено 21 мая, 2015 пользователем bognev

[RobFPGA 35]

Приветствую!

 

По ресурсам в гистограммном фильтре получается:

ROM - 4 *36k Bram, 8 разрядные счетчики 256*8 FFs 8 Luts, и priority encoder 256->8, не могу оценить.Адекватно для решения поставленной задачи? Есть какие то подводные камни, которые я не вижу?

 

Ага - ROM в 2 раза больше BRAM, + как минимум 2*256 LE + FFs для inc/dec логики, ну и priority наверное будет ~128 LE.

Ну и туча слоев в логике :cranky: . И это для 8бит входных данных .

 

Успехов! Rob.

 

[ViKo 1]

Задумался, можно ли применить сортировку Шелла. Так и не понял. Вот, сайт интересный нашел, с анимацией. :rolleyes:

http://www.sorting-algorithms.com/

[Maverick_ 15]

в дополнение к Вашему документу

 

Хочу узнать ваше мнение по поводу алгоритма в статье: http://www.ntu.edu.sg/home/sfahmy/files/papers/fpl2005.pdf

Большим его плюсом является независимость занимаемых ресурсов от окна, только количество bram для задержки потока данных на половину длины окна, гистограммный метод. По мне так он больше подходит для такого окна.

 

[bognev 0]

Реализовал гистограммный алгоритм в лоб, по planahead получил следующие занимаемые ресурсы в virtex 6:

LUT 4461

FD_LD 2844

SLICEL 654

SLICEM 462

На данные момент пока проект притормозится, до тех пор пока не разберусь сколько остается места на него.

Предполагаю сжимать данные из 16 бит в с помощью вычисления логарифма. Нашел множество примеров, с этим проблем нет. А вот с поиском вычисления показательной функции тяжеловато пошло. Нашел вот такую интересную статью. Может кто поделится своим способом возведения числа в степень на плис?

 

 

[Timmy 1]

Реализовал гистограммный алгоритм в лоб, по planahead получил следующие занимаемые ресурсы в virtex 6:

LUT 4461

FD_LD 2844

SLICEL 654

SLICEM 462

На данные момент пока проект притормозится, до тех пор пока не разберусь сколько остается места на него.

Предполагаю сжимать данные из 16 бит в с помощью вычисления логарифма. Нашел множество примеров, с этим проблем нет. А вот с поиском вычисления показательной функции тяжеловато пошло. Нашел вот такую интересную статью. Может кто поделится своим способом возведения числа в степень на плис?

Думаю, задачу можно решить значительно меньшими ресурсами, так данные поступают не очень быстро(медианный фильтр на 256 отсчётов при одном новом отсчёте за 40 тактов).

Система хранения данных разбивается на две половинки, одна половинка хранит данные, меньшие медианы, другая - большие.

К каждому отсчёту добавляется тэг с порядковым номером отсчёта по модулю 256. Тэг позволяет при последовательном просмотре массива находить и удалять самые старые отсчёты. Длина массива с половинкой данных составит 128 элементов, двухпортовая память позволит их все последовательно просмотреть и нормализовать за время поступления четырёх входных отсчётов.

Модуль управления хранения данных должен выполнять следующие функции

1) Сообщить, что массив данных содержит самый старый отсчёт, который должен быть удалён при поступлении нового.

2) Добавить в массив новый отсчёт с сортировкой (отсчёт может быть либо свежепоступившим, либо медианным).

3) Удалять из массива самый старый отсчёт

4) Выдавать наружу и удалять из массива крайний элемент(с максимальным или минимальным значением, в зависимости от отношения модуля к медиане)

 

Если бы отсчёты поступали с интервалом в тактах, превышающем длину массива, можно было бы добавлять новые элементы простой вставкой.

А в нашей ситуации новые отсчёты следует накапливать в отдельном сортированном массиве из не более чем четырёх элементов, в который можно быстро добавлять новые элементы вставкой. И раз в 160 тактов(за 4 новых отсчёта) запускать последовательное слияние двух отсортированных массивов - короткого на 4 элемента и длинного со всеми данными. Одновременно со слиянием следует, анализируя тэги, удалять старые элементы и строить вектор из четырёх бит, показывающий для будущих четырёх отсчётов, во время каких из них должны быть виртуально удалены старые элементы(реально они удалятся при следующем слиянии).

Слияние следует начинать с ближнего к медиане конца, чтобы легко снимать с этого конца крайние элементы прямо во время слияния(задерживая процедуру слияния на такт). Крайний элемент для функции (4) должен выбираться по экстремуму крайних элементов из двух массивов(большого и четырёхэлементного), кроме того, он может оказаться удаляемым на текущем отсчёте, тогда потребуется перейти к следующему.

Коротких массивов потребуется два - один участвует в слиянии, другой накапливает новые данные.

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

 

[Maverick_ 15]

Решил поделиться.

Во вложении - рисунок, который максимально отображет суть описания поиска 3 минимальных значений из входных паралельно приходящих 32 значений. Pipeline реализация. Также присутствует тестбенч и wlf файл для моделсима (просмотр симуляции).

 

Consequently we devised a network optimized, in terms of area and critical path, for the partial sorting of p=3 values among n=32, as depicted on figure. The structure is based on shuffle networks coupled with local minimal computation blocks. After the first shuffle stage, min1 is in the lower section while the upper section can either contain min2 or min3 or no minimum.

The same reasonning is applied recursively. After 5 shuffle stages, the minimum is determined while 5 values can still be min2 and min3. A local sorting of this 5 values enables the determination of min2 and min3 value. This partial sorting network requires 35 Compare and Select operators and 29 minimum elements.

The critical path consists in 9 comparisons stages.

 

PS Если расскажите как сделать оптимальнее, буду рад ...

pipeline_find_3min.rar