使用Verilog for Priority Queue实现查找最小数组使用Verilog

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

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

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,-,-,-}

来源

2011-04-26 GobiasKoffi

一个简单的方法，如果你没有压力来减少门或LUT的数量，那就是实现一个树形结构。

如果在队列中的条目是A0，A1，... A7，执行下列步骤：

计算B0 =分钟（A0，A1），B1 =分钟（A2，A3）， B2 = min（A4，A5），B3 = min（A6，A7）
compute C = min（B0，B1），C1 = min（B2，B3）
compute D = min（C0，C1）

在每个步骤中，还传递哪一个条目较小的索引。

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

鉴于所有数据都在触发器中，重新打包并不太难，只需创建一些逻辑来有条件地从存储中的下一个较高条目加载每个条目，并将要删除的元素的索引解码为一个向量使得元素上方每个条目的移位都被移除。

如果您想使其更有效，可以使用一个变量是比较是在入队还是出队时完成的。您可能还想考虑在每次出队后重新打包是否真的有必要。

来源

2011-04-26 05:23:20 Andy

谢谢。我一定会听从你的所有建议。我仍然不确定重新排列队列的问题。我提出这个想法的原因是因为如果我不把它重新打包成连续的存储空间，看起来就像是“浪费的空间”。 – GobiasKoffi 2011-04-26 18:43:50

是否浪费取决于您的重新分配政策。如果您不需要跟踪事件入队的顺序，则可以为阵列保留一个有效/空位向量，并搜索它以查找空闲条目。这有一定的代价，但它比find-minimum-value逻辑便宜得多。 – Andy 2011-04-26 19:18:06

实际上，空/满条目阵列听起来真的是个好主意。也许我会考虑实施。实际上，我所关心的只是从队列中删除最小条目，所以它的位置并不重要。谢谢您的帮助。对此，我真的非常感激。 – GobiasKoffi 2011-04-27 14:43:02

SystemVerilog为数组提供了一个sort方法。请参阅IEEE Std 1800-2009中的第7.12.2节“阵列排序方法”。

来源

2011-04-26 13:12:50 toolic

'sort'方法用于将数组从最小值重新排列到最大值。但我认为在这种情况下，'min'方法对于找到最小数量更有用。 – 2017-11-03 03:17:55

使用Verilog for Priority Queue实现查找最小数组使用Verilog

回答

相关问题