[Вадим Н. 1]

Всем привет!

Тут, просто, ради интереса, довелось ответить на такой вопрос:

Пузырьковая сортировка в ПЛИС "за один такт".

Другими словами, только в виде комбинаторной логики, без синхросигнала и регистров.

Verilog (не System). На входе и на выходе - массивы. На выходе - отсортированный.
Чтобы было в общем виде, через параметры и циклы generate.

Оказалось довольно интересно.

Первое что поразило. Это слишком большая ошибка в оценке времени на разработку. Задача казалась очень простой.
Сразу было ясно, что это будет многократное повторение простейшего модуля с перестановкой двух элементов.
Сначала воспроизвёл алгоритм в perl, чтобы со стороны взглянуть на проблему.
На это ушёл вечер - не считаем его вообще.
Далее, накидал структуру модулей (перестановка, один проход, собственно сортировка и тестбенчи для всех)
и решил что вся разработка с этого момента займёт пару вечеров...
В первый вечер стало ясно, что знания по циклу generate не в один момент загружаются в голову...
Пришлось поменять тактику: раскидать модули по файлам, прикрутить контроль версий.
Долго-ли коротко-ли, ушло раз в 5-6 больше времени.
И это довольно характерный коэффициент для меня. Просто до смешного стабильный показатель ))

Это один результат, который надо ещё осмыслить ))

Ну и оказалось, что этот проект интересно разглядывать через утилиты Квартуса.
Особенно в процессе знакомства с generate + цикл. Очень наглядно:

1. RTL Viewer (см. скрин)
2. Timing Analyzer - путь с максимальной задержкой как меняется от размерностей массива
3. Technology Map Viewer (тут можно увидеть как всё конвертируется в таблицы истинности*)

* если я правильно понимаю

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

bubble_sort.7z

[Maverick_ 15]

добавьте клок напишите констрейн и посмотрите что дает тайминг анализ при больших количествах єлементов в массиве (16 и больше)?

[Serhiy_UA 1]

Эта задача из теоретических? Есть ограничения по числу данных и их разрядности? Хорошо бы ограничить.

Создавал лет 10 назад подобную сортировку в FPGA для 5-и 12-разрядных чисел для поиска максимального, чтобы его отбросить (возможная импульсная помеха), а потом усреднить оставшиеся. Это был тактируемый пяти-шаговый конвейер из групп сумматоров и мультиплексоров. Но ТС предлагает полностью однотактный, т.е асинхронный.

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

 

 

[des00 25]

1 hour ago, Serhiy_UA said:

Создавал лет 10 назад подобную сортировку в FPGA для 5-и 12-разрядных чисел для поиска максимального, чтобы его отбросить (возможная импульсная помеха), а потом усреднить оставшиеся.

на лету же можно сделать: складываем все, ищем максимум, потом вычитаем максимум из суммы)

[Serhiy_UA 1]

Это в PCI-плате для гражданской береговой РЛС. Где видео-сигнал оцифровывался на 25 МГц, а для подавления помехи использовалось скользящая некогерентная обработка по 5-и соседним свипам к кодам на одинаковых дальностях. Коды на конвейере сортировались, с отбрасыванием максимального и усреднялись. 

[firstvald 20]

а медиана хуже? или не пробовали?

[Serhiy_UA 1]

to firstvald

После сортировки 5-и кодов медиана была на позиции 3. Мы экспериментировали и с ней тоже, но остановились на том, как описано выше, посчитали, что так лучше.