使用Verilog为优先级队列实现查找数组中的最小值

Question

我是Verilog的新手，但我有一个16个元素的数组(每个元素都是16位长)，我希望找到数组的最小条目，返回最小值，并重新排列最小值之后的数组中的所有条目，以便数组是一个连续的条目块。我知道我必须使用比较器，但我真的不知道从哪里开始比较一大群数字并确定最小值。

编辑:我实际上做的是一个优先队列。我已经实现了队列功能，但不是返回队列头部的内容，而是返回具有最小值的条目，并保持存储连续。

e.g. {2,3,4,1,5,6,-,-} 
min is 1 --> {2,3,4,-,5,6,-,-} 
Rearrange so everything following the returned min is moved to the index preceding it-->
{2,3,4,5,6,-,-,-}

Answer 1

如果您没有减少门或lut数量的压力，一个简单的方法是实现一个树型结构。

如果队列中的条目为A0, A1，…A7，执行以下步骤:

1. 计算B0 = min (A0, A1)， B1 = min (A2, A3)， B2 = min (A4, A5)， B3 = min (A6, A7)
2. 计算C0 = min (B0, B1)， C1 = min (B2, B3)
3. 计算D = min (C0, C1)

在每一步中，也传递较小条目的索引。

这需要同时访问所有数据，因此这意味着整个存储空间都是触发器，而不是RAM。

考虑到所有的数据都是触发器，重新打包并不太难，只需创建一些逻辑来有条件地从存储中的下一项加载每一项，并将被删除元素的索引解码为一个向量，以便对被删除元素之上的每一项进行下移操作。

如果您想使比较更有效，可以使用一个变量，即比较是在排队时间进行还是在排队时间进行。您可能还需要考虑是否真的有必要在每次dequeue之后重新打包。

Answer 2

SystemVerilog为数组提供了一个sort方法。参考IEEE Std 1800-2009第7.12.2节"数组排序方法"。