03-13-2017 10:24 AM - edited 03-13-2017 10:26 AM
Well, your execution is NOT parallel. Your swapping VI is non-reentrant so it is serialized for execution.
The next point: Do you really want to waste a significant amount of FPGA space just to get a small % of performance gain?
And lastly: I am still confident that your implementation does not what you want it to do.
Example:
The reason for your algorithm to sort like that is because you only swap even pairs, but not uneven pairs. And i seriously doubt that this is what you want to have!
EDIT: Note that my code should also run on FPGA. However, here is another implementation of bubble sort.
Note that my algorithm performs faster if there are only little amounts of swaps necessary, the linked one is better if there are many swaps necessary.
03-13-2017 10:27 AM
I don't think you can truly make a bubble sort parallel because the next comparison is always dependent on the previous comparison.
Perhaps there is a way to make a shell sort in parallel. But even that is questionable because the sizes of the shells are always going to vary, so there is no way to hard code that in there.
Did your truly have the patience to make all those constants and all of those wires? The organization was very good. But that still looks like a huge amount of work to make such a monstrous VI.
03-13-2017 10:45 AM
The code I demonstrated wasn't finished. That is why it sorts only even indexes. I got stuck half way, then I posted my problem here.
The parallel execution would be only the two blocks of swaps in For Loop.
The subVIs will be reentrant when my algorithm will function. 🙂
03-13-2017 10:46 AM
I did this VI using LabVIEW scripting. It would be a nightmare to do it by myself.
03-13-2017 10:55 AM
@VUC wrote:
[...]
The subVIs will be reentrant when my algorithm will function. 🙂
And in that moment, your FPGA usage will have an abrupt rise. That means that if you need most of the FPGA for other stuff, you will end up with code which cannot be compiled for your target.
As Ravens states, most sorting algorithms cannot be parallelized; at least not in a matter to gain significant execution speed. If for any reason, your sorting is indeed parallelizable (which i doubt), you should split up your data set in a more efficient manner.
If you fear subVI overhead, you can inline subVIs.
03-13-2017 11:02 AM
You could look up a concept called "pipelining" which allows you to essentially operate on sequential operations in a parallel fashion.
But I think you need to explain a bit more of the "bigger picture". (pun wasn't intended, originally.) How often do you need to sort a 1-D array that you need to do it so fast on an FPGA? And why?
03-13-2017 11:18 AM
On a side note, your subVI could be replaced by this node (available on FPGA).
Except for the first pass, Quicksort can be partially parallelized, with the number of independent sub-ranges doubling with every pass.
03-13-2017 05:13 PM - edited 03-13-2017 05:14 PM
@Norbert_B wrote:
... this is how an ascending sort in "brute force bubble sort" would look like:
Brute force does not use anything green. Way too many decisions! 😮 😄 Also getting the size belongs outside the loop (well the compiler will probably do it, but still.... ;))
Here's my quick attempt. Would be equally easy to use the IPE, of course.
03-13-2017 05:26 PM
You've very quick to dismiss being pointed towards a better algorithm. Let's take a quick moment to analyze this.
One of two things are correct here. Either it's an intended limitation or it's not. If it is, you need to correct your algorithm to get around it. If it's not, a CAR will be filed to get the bug fixed. In the meantime, you need to address this in your code. The workaround would be finding a more efficient algorithm.
In either event, it doesn't really make sense to push back so hard on finding a better way to do what you're doing. It also shows a fundamental misunderstanding of both the algorithms you're using and FPGA itself to claim that it must be more parallel. Just because things CAN be more parallel on FPGA doesn't mean they SHOULD be.
03-13-2017 05:36 PM - edited 03-15-2017 12:24 PM
@natasftw wrote:
You've very quick to dismiss being pointed towards a better algorithm
Exactly. A google search has plenty of material about sorting using FPGA. Even wikipedia points out sorting algorithms that seem to parallelize well, e.g. merge sort.