Я не думаю, что вы можете обойтись, используя деревья компараторов, если хотите найти два самых маленьких элемента комбинационно. Однако, если ваша цель не низкая задержка, чем последовательная схема (возможно, конвейерная) также может быть вариантом.
Один подход, который я могу придумать на месте, состоит в том, чтобы разбить операцию, выполняющую вид неполной сортировки пузырьков в оборудовании с использованием небольших сетей сортировки. В зависимости от количества площади, которую вы готовы потратить, вы можете использовать меньшую или большую сеть p-сортировки, которая объединяет p-элементы в момент, когда p> = 3. Затем вы можете применить эту сеть к своему входному набору размера N, сортировка p элементов за раз. два наименьших элемента в каждой итерации хранятся в некоторой памяти (например, в памяти SRAM, если вы хотите обрабатывать большее количество элементов).
Вот пример для p = 3 (в скобках указано группирование элементов, к которым применяется p-сортировщик):
(4 0 9) (8 6 7) (4 2 1) -> ( 0 4 9) ( 6 7 8) ( 1 2 4) -> 0 4 6 7 1 2
Теперь вы начинаете следующий раунд: вы применяете p-сортировщик к результатам первого раунда. Снова вы сохраняете два наименьших выхода вашего p-сортировщика в те же значения перезаписи памяти из предыдущего раунда.
Вот продолжение примера:
(0 4 6) (7 1 2) -> ( 0 4 6) ( 1 2 7) -> 0 4 1 2
В каждом раунде вы можете уменьшить количество элементов смотреть в 2 раза. Например, с p == 4 вы сбрасываете половину элементов в каждом раунде, пока два самых маленьких элемента не будут сохранены в первых двух ячейках памяти. Таким образом, алгоритм имеет сложность времени / цикла O (n log (n)). Для реальной аппаратной реализации вы, вероятно, захотите придерживаться степеней двойки для размера p сортировочной сети.
Хотя управляющая логика c такой схемы не является тривиальной для реализации области должна быть в основном преобладают размер вашей сортировочной сети и объем памяти, в котором вы должны хранить первые 2 / p * N промежуточных результатов (при условии, что ваши входные сигналы еще не сохранены в памяти, которую вы можете использовать для этой цели). Если вы хотите настроить свою схему на пропускную способность, вы можете увеличить p и направить сортировочную сеть за счет дополнительной области. Дополнительное ускорение может быть достигнуто за счет замены одной памяти с использованием до двух двухпортовых запоминающих устройств (по 1 для чтения и 1 для каждого порта записи), что позволит вам получать и записывать данные для сети сортировки за один цикл, увеличивая тем самым коэффициент использования. Соотношение компараторов в сортировочной сети.