Showing results for 
Show  only  | Search instead for 
Did you mean: 
Registered: ‎06-10-2008

How to implement a pipelined sorting tree in an FPGA

How do I implement a pipelined sorting tree to sort 1024 numbers in FPGA? I want to begin building the tree as soon as the first number becomes available, and insert the next number into the tree when it becomes safe to perform the insertion operation. By "safe" I do not mean that the first operation is completed, what I mean is that the previous number has walked far enough in the tree that it will have settled when (and if) the next number reach that node in the sorting tree.

It does not have to be a sorting tree, even a linked list would do fine. The main problem is that pipelined operation requires that multiple numbers are walking down the tree simultaneously, each trying to find its own "sorted" position in the tree, and therefore if I implement the tree using a memory structure, multiple operations will need to performed on this memory structure simultaneously. The only thing that I can guarantee is that by putting a delay between consequtive insert operations, no two numbers will need to access the same memory cell at this same time, but they will all be operating on the same array. To my knowledge, the default memory blocks in system generator do not let me to do this.

Does anybody have an idea about how to implement this in an FPGA?


0 Kudos
0 Replies