How to store and output the kth largest number in verilog

Hi all,
I met a problem and I can not come up with a solution. Hope someone can give me a hint.

Suppose there is a 1000x1000 matrix. The data come in one by one @ every clock cycle. (A00,A01,A02...A0999,A10...A999999). And I want to divide the 1000x1000 matrix to 100x100 small blocks, each small blocks have 10x10 numbers. The required output is the 20th largest number for each small block. So total I need to store the 100x100 20th largest number for this 1000x1000 matrix.

Hope someone can help me!

To find the 20th largest, you need to find the top 20 largest numbers and store them in a 20-item array. (Eventually it shall contain the twenty highest numbers, in sorted sequence.)

When a number comes in, compare it with #20. If it is greater then insert it in proper order among the top 20. When all data has been read, item #20 is automatically the 20th largest.

So how can I store them in a sorted array? Assume that the array is empty at first and I store the first incoming number, how can I track the smallest number and replace it with a larger one? If the first smallest is replaced, how can I where is the second smallest one?

It is unclear how many numbers you wish to sort, whether a hundred or ten thousand or a million, or merely to find the 20th largest number in a group.

A sorting routine compares two numbers at a time, and it is easiest to do such a routine on a one-dimensional array. Or are you trying to sort a two-dimensional array? This will require writing a custom routine that keeps careful track of rows and columns, with a complexity that is could be unmanageable.

I want to find the 20th largest number for every 10x10 matrix in a total 1000x800 matrix. Seems that keep them in a sorted array is difficult. Is there any other ways?

sssssunday said:

I want to find the 20th largest number for every 10x10 matrix in a total 1000x800 matrix. Seems that keep them in a sorted array is difficult. Is there any other ways?

Click to expand...

Alternate method. It is simpler although it may take more cycles and more time.

(1) Look at the first number. (Call it X.)
(2) Execute a loop comparing X to each of the other 99 numbers in turn. Increment a counter whenever one of the other numbers is larger than X.
(3) When you finish the loop, if the counter reads 19 then it automatically means that X is the 20th largest.
(4) If the counter reads anything other than 19, then look at the next number and call that X. Repeat steps 2 through 4.

At a minimum due to the row ordering of the 1000x1000 matrix input data you will need to keep track of 10 100x100 matrices. As each row arrives you'll have 100 elements to sort for each of the 10 smaller matrices. 10 rows will complete the first row of smaller matrices allowing you to offload the 10 20th element sorted values so you can reuse the FSM for the next 10 rows.

The worst problem in this will be the sorting itself. Hardware sort algorithms are slow as you have to deal with reading each value to find where the newest value fits within the list. It might be easier to not sort until the first 10 rows have arrived then run 10 sort algorithms in parallel to sort the 10 100x100 memories. FYI, no matter how you implement this it will be very slow. If you need speed then you'll have to not use memory and use FFs to store the 10 100x100 elements or a combination of FFs and memory as you would want access to at minimum of 1 100x100 elements to create a pipelined sort (very large amount of logic required).

As you can see this is a lot of logic and will end up taking 100 clock cycles to complete (10 for a list of 10 items). A merge sort would likely be a better approach for a parallel implementation, but I haven't looked at it.. Another option is to perform a FSM based sort, which will be very slow.

So how can I store them in a sorted array? Assume that the array is empty at first and I store the first incoming number, how can I track the smallest number and replace it with a larger one? If the first smallest is replaced, how can I where is the second smallest one?

Click to expand...

As I understand it, you need to implement some type of sorting logic.
This thread of mine might give you ideas (although I have never implemented it). https://www.edaboard.com/threads/359880/#post1541203

My initial impression is that you'll probably need to create a bubble sort for each 100 x 100 sub-matrices. That'll be 100^2 comparisons and clock cycles overall! You'll need 100 bubble sort units for the entire 1000 x 1000 matrix. This is probably not the most efficient approach. Since you only need the kth largest number, it's possible there are some optimizations you could do to reduce the storage requirement.... The bubble sort has a simple architecture, but the latency is large. What is your latency requirement?