LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Algorithm used for Sort 1D Array

Sorry for the silly idea, but would it be possible to push from the host to the FPGA the "raw" arrays, and do the sort and other actions also on the FPGA? I never worked with FPGA, but I guess similarly as a GPU you can do sorting much faster with it? 

Message 11 of 33
(739 Views)

Not silly.  Just not sure.  FPGA's aren't ideal for working with arrays.  They only take fixed sized arrays.  I think it might be possible to store the data in some block memory or onboard FIFO on the FPGA once it receives it, but that may only hold hundreds of elements where as I would need to hold thousands.

 

One thought I had was to never merge the arrays.  Keep them separate and pull the data from them one at a time as needed depending on which one has the next item in order and stick that directly into my DMA FIFO.  But that is moving the processing a little further down stream.  That worries me a bit because I don't want to risk having my DMA FIFO run dry, so I'm trying to keep it with a nicely sorted order ready to go.  (Though with my slow processing, I might be starting to cause it to go dry right now.)

0 Kudos
Message 12 of 33
(727 Views)

I would think that since you have two already sorted arrays that you want to merge, a merge (half of the well-studied Merge Sort) would probably be as fast as anything.  In a Sort, the operations that you need to consider are (a) comparisons and (b) interchanges.  With a Merge, the worst case number of comparisons is O(N) -- you pass through the data only once, taking the smaller of the two leading elements of each list until one list is exhausted, so if the lists empty at the same rate, you'll have about N comparisons.  You don't need to do any exchanges.

 

Bob Schor

Message 13 of 33
(721 Views)

Nevermind, I did not read enough and did not see that you were already describing what I wrote in your first post! I'm blushing...

But I cannot see how anything could possibly be faster than that solution?

 

-------------------------

Original post:

 

If I understand you correctly, I think this should be a simple O(n) problem.

 

Init an array the size of both arrays.

Keep a pointer on each subarray position.

Compare the two elements at the pointer positions. (Eg first element 1 of array 1 and element 1 of array 2)

Copy the least element and advance the pointer of the array where the least element came from.

Repeat until you reached the end of both arrays.

Message 14 of 33
(719 Views)

On the FPGA, you'd need to DMA the arrays in and store them in two block memory locations. Then you could run the alogrithm you had and output the sorted data to a target scoped fifo. Thousands should be fine.


Another option: Is creating two DMAs and option? Let the FPGA do the arbitration of which one is active.

 

Message 15 of 33
(718 Views)

The FPGA card I am using only has 3 DMA's.  And I'm already using the other 2, 1 for grabbing analog inputs, the other for grabbing a string of data coming from digital inputs.  That leaves just 1 for the analog outputs.  I wish I had another DMA.  If I did the whole problem would go away, FPGA could then read both independently.

0 Kudos
Message 16 of 33
(697 Views)

I thought that might be the case. The newer targets have many more DMAs, for example, the SB9627 has 16.

 

Seems like you could still do it if you used target scoped FIFOs.


Bring it in on the DMA, write to target scoped fifo 1, then fifo 2

 

In another loop dequeue both target scoped fifos. Hold that in a shift register until the lower one hits. Dequeue from the one that hit.

Message 17 of 33
(687 Views)

nanocyte wrote:

In another loop dequeue both target scoped fifos. Hold that in a shift register until the lower one hits. Dequeue from the one that hit.


My thoughts were on the same line as this, except to use two different loops for the outputs.  So you have one loop acting as a moderator that reads the DMA and just dump the message into the FIFO it needs to be sent to.  Then your output loops handle all of the timing and reading from the FIFOs as needed.


There are only two ways to tell somebody thanks: Kudos and Marked Solutions
Unofficial Forum Rules and Guidelines
Message 18 of 33
(663 Views)

As a general rule of thumb I try to deal with throughput issues as close to the source as possible. The earlier the problem is dealt with the better.

 

Ben

Message 19 of 33
(657 Views)

@Ben wrote:

As a general rule of thumb I try to deal with throughput issues as close to the source as possible. The earlier the problem is dealt with the better.

 

Ben


I like that philosophy and is what I'm hoping to be able to do.

Message 20 of 33
(637 Views)