LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Big size LabVIEW VI

Solved!
Go to solution

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:

SortResult.PNG

 

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.

Norbert
----------------------------------------------------------------------------------------------------
CEO: What exactly is stopping us from doing this?
Expert: Geometry
Marketing Manager: Just ignore it.
0 Kudos
Message 11 of 29
(1,495 Views)

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.

0 Kudos
Message 12 of 29
(1,493 Views)

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. 🙂

0 Kudos
Message 13 of 29
(1,480 Views)

I did this VI using LabVIEW scripting. It would be a nightmare to do it by myself.

0 Kudos
Message 14 of 29
(1,478 Views)

@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.

Norbert
----------------------------------------------------------------------------------------------------
CEO: What exactly is stopping us from doing this?
Expert: Geometry
Marketing Manager: Just ignore it.
0 Kudos
Message 15 of 29
(1,472 Views)

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?

0 Kudos
Message 16 of 29
(1,467 Views)

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.

0 Kudos
Message 17 of 29
(1,456 Views)

@Norbert_B wrote:

...  this is how an ascending sort in "brute force bubble sort" would look like:

Brute1DArrayBubbleSort.PNG


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.

 

 

0 Kudos
Message 18 of 29
(1,415 Views)

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.

Message 19 of 29
(1,410 Views)

@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.

 

Message 20 of 29
(1,407 Views)