a quick searching problem

If the arrays are sortable, you could sort V1 and V2 in O(n lg(n) + m lg(m)) time and once thats complete, compare the two sorted arrays sequentially, moving forward one step at a time, so O(n + m) steps for comparison once the array is sorted.

Systolic. The brute force comparison is O(M*N) in TIME * SPACE. Thus if you have 1 comparison cell, it takes O(M*N) time. But if you have N comparison cells, each holding one of the element, it takes O(M) time and O(N) FPGA resources.

--
Nicholas C. Weaver                                 nweaver@cs.berkeley.edu

You are thinking in terms of feeding the vectors into an FPGA in parallel. That is hardly necessary (unless you generate entire new vectors every

10ns).

Questions you need to answer:

-How quickly are new vectors generated?

-Where will the vectors come from (or be stored)?

-How quickly do you need an answer?

-What is the maximum value of M and N?

-Is it guaranteed that there will be only one matching value for all possible vector combinations?

-How many different 20 bit values can a vector element have? Is it a straight unsigned binary value or some sort of a code that would limit the number of distinct values to less than 2**20?

Just as an example, if M = N = 512, with the FPGA running at 100MHz, you could do a brute force comparison of two vectors in 2.6 ms. Your M = N = 60 example would take 36 microseconds. Keep in mind, these are worst-case figures.

For the above use two SelectRAM memories preloaded with your vectors. You could load your vectors one word at a time at whatever rate your source could handle. If, say, your source happens to be SDRAM connected to the FPGA you could load the vectors at 133MHz (or 2x with DDR). Depending on the width of the data path that would mean one or more 20 bit word per clock. No need to consume I/O to pass the vectors in parallel.

So, a rough estimate of a complete load->compare->result cycle would be: M = N = 512 ... load = 7.7us; compare = 2.6ms M = N = 60 ... load = 0.9us; compare = 36us

Is that fast enough? You could always run the FPGA faster.

If SDRAM was involved I would probably run the logic at the SDRAM clock (or

2x) rather than an unrelated frequency (like 100MHz).

There are a million possible variations of this concept. It all depends on the constraints you have to work within. A binary search, for example, would provide a very significant improvement in performance. You could replicate the circuit X times in order to obtain a further X-time improvement in reaching a match.

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
0_0_0_0_@pacbell.net
where
"0_0_0_0_"  =  "martineu"




"Zhen"  wrote in message
news:7b390929.0308100714.550cc60a@posting.google.com...
> There are two vectors, named V1 and V2, the sizes of which are 1*M and
> 1*N, respectively. We have known that there is at most one common
> element in both vectors. I am looking for the quick algorithm to
> search this common element.
>
> The general algorithm is to compare every element in V1 with each
> element in V2. the comparison complexity will be O(M*N). Is there any
> efficient method to complete it?
> I hope it can be done in FPGA. If M=N=60, and each element is 20 bit
> long,there isn't enough pins for the general search algorithms at one
> time. It need some loops to do it. So I am looking for an efficient
> algorithm and expect that the common element can be found in around
> 10ns~50ns. Is it possible?
> Thanks,

Suppose every element in V1 is in a memory and V2 has only one element called E2_0. Now the problem becomes to find out if E2_0 exists in the V1 memory. Sounds a lot like IP address lookup, doesn't it? A CAM would be a good choice for this type of problem. The search time would be in the order of N not M*N.

Jim Wu snipped-for-privacy@yahoo.com