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:
- compute B0 = min (A0, A1), B1 = min (A2, A3), B2 = min (A4, A5), B3 = min (A6, A7)
- compute C0 = min (B0, B1), C1 = min (B2, B3)
- 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.
SystemVerilog provides a sort method for arrays. Refer to "Array ordering methods", section 7.12.2 in the IEEE Std 1800-2009.
