查找用Verilog为优先级队列实现数字阵列最低 [英] Find minimum in array of numbers using Verilog for Priority Queue implementation

问题描述

我是相当新手Verilog的，但我有16个元素（每个元素都是16位长）的数组，我希望能够找到的最低入学数组，返回最小，并重新安排所有数组中的条目的最小后来，以使阵列是其中一个条目的连续块。我知道我必须使用一个比较，但我真的不知道在哪里的问候开始比较大的组号码，并确定最低。

编辑：我正在做其实是一个优先级队列。我已经实现了队列功能，但不是返回位于队列的头什么的，我想回到与最小值的条目，并保持连续存储。

 例如。 {2,3,4,1,5,6， - ， - }
分是1  - ＆GT; {2,3,4， - ，5,6， - ， - }
重新排列，所以一切之后返回分钟被移动到索引preceding它 - ＆GT;
{2,3,4,5,6， - ， - ， - }
 

解决方案

有一个简单的方法，如果你没有pressure降低门或LUT数量，是实现一个树型结构。

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

1. 计算B 0 =分钟（A0，A1），B1 =分钟（A2，A3），B2 =分钟（A4，A5），B3 =分钟（A6，A7）


2. 计算C0 =分钟（B0，B1），C1 =分钟（B2，B3）


3. 计算D =分钟（C0，C1）

在每一个步骤，也可沿取其入境较小的指数过去。

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

由于所有数据都在触发器

，重新包装不是太难，只是创造一些逻辑来有条件地加载从存储的下一个更高的进入每个条目，以及德code中的元素的索引被移除成使对上述被删除的元素的每个条目的减档的载体。

使用，如果你想使之更有效率起到一个变量是比较是否在排队或出队的时间内完成。您可能还需要考虑是否重新打包后每个离队确实是必要的​​。

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

解决方案

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:

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

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.

这篇关于查找用Verilog为优先级队列实现数字阵列最低的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！