LabVIEW FPGA Idea Exchange

cancel
Showing results for 
Search instead for 
Did you mean: 
Ken_Brey

Math Error in Lattice Bubble Sort in High-Performance FPGA Developer's Guide 1.1

Status: New

The document High Performance FPGA Devleoper's guide lists a parallelized bubble sort.  I tried this out, and found that it actually doesn't work.  This this matrix successfully gets the max value on top, and the minimum value on the bottom, it doesn't completely sort the values between. 

Bubble Sort.JPG

 

In this example, if the highest value started at the end of the array (red), and the 2nd highest value started 2nd from the end (pink), the high value ends up at the top, and the 2nd highest value ends up 3rd from the top. 

Bubble Sort - Markup.JPG

This lattice can be completed to sort the middle sections by adding 3 more columns, one with 3 Min/Max blocks comparing the center 6 values, one with 3 Min/Max blocks comparing the center 4, and a final Min/Max operation comparing the middle 2. This will complete the sort, but will take 7 sequential steps instead of the 4 listed.  The following works to sort the entire array:

Bubble Sort - Corrected.JPG