[Maverick_ 15]

:help:

Требуется реализовать сортировку входных данных (допустим 16 bit) по любому алгоритму, и чтобы сохранялись 16 максимальных значений. Главное требование чтобы он заработал на 100 МГц в Virtex II (XC2V1000).

Хотелось бы выслушать предложения и может быть готовые решения.

[des00 25]

:help:

Требуется реализовать сортировку входных данных (допустим 16 bit) по любому алгоритму, и чтобы сохранялись 16 максимальных значений. Главное требование чтобы он заработал на 100 МГц в Virtex II (XC2V1000).

Хотелось бы выслушать предложения и может быть готовые решения.

 

требования ко времени выработки результата?

[MrYuran 23]

чтобы сохранялись 16 максимальных значений

16 значений из чего? Из пакета, блока, потока (окна?)

[Maverick_ 15]

требования ко времени выработки результата?

16 значений из чего? Из пакета, блока, потока (окна?)

На данном этапе это пока не критично (главное вложиться в период низкоскоростного потока), конечно чем меньше требуется времени(тактов), тем лучше. Частота потока - ориентировочно (310-315) кГц.

[des00 25]

Частота потока - ориентировочно (310-315) кГц.

 

на 100 МГц тактовой даже не интересно %) решение может быть от лобового до решения с хранением упорядоченного массива.

 

ЗЫ. вот если бы поток был 100 МГц, тогда было бы над чем подумать %)

[Maverick_ 15]

на 100 МГц тактовой даже не интересно %) решение может быть от лобового до решения с хранением упорядоченного массива.

 

ЗЫ. вот если бы поток был 100 МГц, тогда было бы над чем подумать %)

 

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

Меня сейчас интересует сортировка в режиме съема информации(real-time). Сейчас пока между отсчетами данных имеется 300 тактов частоты 100 МГц(тогда Fвходного потока =310 кГц), если доведете до 20 тактов(тогда F входного потока = 6МГц) (будет СУПЕР!!!), тогда подниму частоту входных данных до 5-6 МГц (16-20 тактов)), а не постобработка.

ЗЫ Еденицы и тем более десятки МГц входного потока - есть ближащая перспектива на будущее.

ЗЫ ЗЫ Моя реализация во вложении, там WORD документ с кратким описанием, к сожалению она не работает на 100 МГц.

SORT.rar

[des00 25]

ЗЫ Еденицы и тем более десятки МГц входного потока - есть ближащая перспектива на будущее.

для 16 бит, на одном рамб18 постройте гистограмму входного потока. остается только считать 16 старших флагов, работать будет на частотах пока память еще шевелиться :)

[Oldring 0]

Тривиально. При поступлении очередного числа автомат проходит по списку из 16 максимальных чисел сверху вниз и обменивает текущее число с числом в списке, если текущее больше. И так до низа списка. Всего компаратор и пара мультиплексоров. Список можно хранить в сдвиговом регистре.

[AJIEKCEu 0]

для 16 бит, на одном рамб18 постройте гистограмму входного потока. остается только считать 16 старших флагов, работать будет на частотах пока память еще шевелиться :)

Аплодирую! Отличная идея. Я об этом не подумал.

 

Только если "16 максимальных значений" воспринимать в смысле "если пришло за все время 16 раз 0xFFFF - то выдать надо 16 0xFFFF" - то кол-во необходимой памяти резко возрастает. в 16 раз.

Ну и расширять сложно....

 

У меня пока только идея о упорядоченном регистре и метод дихотомии - 4 такта на отсчет.

[Maverick_ 15]

Тривиально. При поступлении очередного числа автомат проходит по списку из 16 максимальных чисел сверху вниз и обменивает текущее число с числом в списке, если текущее больше. И так до низа списка. Всего компаратор и пара мультиплексоров. Список можно хранить в сдвиговом регистре.

Согласен, я так и реализовал. Посмотрите мое вложение.

 

для 16 бит, на одном рамб18 постройте гистограмму входного потока. остается только считать 16 старших флагов, работать будет на частотах пока память еще шевелиться :)

Извините, не могли бы поподробнее объяснить - я не понял

[Oldring 0]

Согласен, я так и реализовал. Посмотрите мое вложение.

 

Хм... Вам платят по количеству написанных строк кода?

[Maverick_ 15]

Хм... Вам платят по количеству написанных строк кода?

не понял???

ЗЫ Там сохранились предыдущие версии разработки, но они неправильные, и они закоментированы.

ЗЫ ЗЫ На них не обращайте внимания или удалите

[AJIEKCEu 0]

Извините, не могли бы поподробнее объяснить - я не понял

Надеюсь, что des00 не обидится...

 

Адресом памяти является входное значение. Значением по адресу - признак "появлялось ли такое значение в потоке".

Соответственно после обнуления схемы во все ячейки памяти записываются нули. При приходе значения на вход - по соответствующему адресу записывается '1'.

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

 

Только мне кажется des00 (ну и я тоже) немного ошиблись - нужно 4 BRAM даже для 1-го варианта схемы. Т.к. 16 бит адреса - это 64Кбита (то есть 4 памяти).

 

 

А Oldring видимо имел ввиду, что Ваш код написан не очень компактно(мягко говоря), и, надо сказать, сложновато для понимания. Не говоря уже бешенном количестве закомментированных строк.

[Oldring 0]

не понял???

 

Очень громоздко. И читать такой код не хочется.

[des00 25]

Только мне кажется des00 (ну и я тоже) немного ошиблись - нужно 4 BRAM даже для 1-го варианта схемы. Т.к. 16 бит адреса - это 64Кбита (то есть 4 памяти).

 

смотря какая фпга, на виртексе 2 скорее всего вы правы, но на тех же спартанах 3/виртекс 4 1 блок памяти это 16к х 1 (RAMB18).