使用 Verilog 查找数字数组中的最小值以实现优先级队列
我对 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,-,-,-}
I'm quite a novice to Verilog, but I have an array of 16-elements (each element is 16-bits long) and I wish to find the minimum entry the array, return the minimum, and re-arrange all the entries in the array that come after the minimum so that the array is one contiguous block of entries. I know I have to use a comparator, but I really have no idea where to start with regards to comparing a large group of numbers and determining the minimum.
EDIT: What I'm actually making is a priority queue. I have the queue functionality implemented, but instead of returning what's at the head of the queue, I want to return the entry with the smallest value, and keep the storage contiguous.
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,-,-,-}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您没有减少门或 LUT 数量的压力，一个简单的方法是实现树型结构。
如果队列中的条目为 A0, A1, ... A7，请执行以下步骤：
在每一步中，还传递较小条目的索引。
这需要同时访问所有数据，因此意味着整个存储位于触发器中，而不是 RAM 中。
鉴于所有数据都在触发器中，重新打包并不太难，只需创建一些逻辑来有条件地从存储中的下一个更高条目加载每个条目，并将要删除的元素的索引解码为向量，从而使对于要删除的元素上方的每个条目，向下移动。
如果您想提高效率，可以考虑的一个变量是比较是在入队还是出队时进行。您可能还需要考虑每次出队后是否确实有必要重新打包。
A simple approach, if you don't have pressure to reduce the number of gates or LUTs, is to implement a tree-type structure.
If the entries in the queue are A0, A1, ... A7, do the following steps:
At each step, also pass along the index of whichever entry is smaller.
This requires access to all the data simultaneously, so it implies the entire storage is in flip-flops, rather than RAM.
Given that all the data is in flip-flops, repacking isn't too hard, just create some logic to conditionally load each entry from the next higher entry in the storage, and decode the index of the element being removed into a vector enabling the shift-down for each entry above the element being removed.
One variable to play with if you want to make it more efficient is whether the comparison is done at enqueue or dequeue time. You may also want to consider whether repacking after each dequeue is really necessary.
SystemVerilog 为数组提供了
sort方法。请参阅 IEEE Std 1800-2009 中的“数组排序方法”，第 7.12.2 节。SystemVerilog provides a
sortmethod for arrays. Refer to "Array ordering methods", section 7.12.2 in the IEEE Std 1800-2009.