Оптимизированная оптимизация в реальном времени/в аппаратном обеспечении (fpga)

Question

Я пытаюсь сортировать массив из 8-битных чисел с помощью vhdl. Я пытаюсь найти метод, который оптимизирует задержку, и другой, который будет использовать меньше аппаратного обеспечения.

Размер массива фиксирован. Но мне также интересно расширить функциональность до переменной длины. Я пришел через 3 алгоритмов до сих пор:

1. Bathcher Parallel
2. Метод Грина Сортировать
3. Van Vorris Сортировать

Какой из них будет делать лучшую работу? Есть ли другие методы, над которыми я должен смотреть? Спасибо.

Answer 1

Я читал об этом в книге Кнута, и согласно этой книге параллельный слияние Batcher является самым быстрым алгоритмом, а также наиболее эффективным аппаратным.

Answer 2

В этом разделе много научных статей. Вы можете попробовать искать в Интернете. Я сделал поиск «Сортировка сетей» и придумал множество сравнений различных алгоритмов и насколько хорошо они интегрировались в ПЛИС.

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

Лично я бы подумал о некотором постоянном времени, таком как merge-sort, который имеет постоянное время сортировки, поэтому вы можете легко назначить сортировку для массива фиксированного размера. Однако я не уверен, насколько хорошо это масштабируется или работает с произвольными размерами массивов. Вероятно, вам придется установить верхний предел размера массива, и этот подход лучше всего работает, если все данные хранятся в регистрах.