a quick searching problem

[Zhen]

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,

 

[Nicholas C. Weaver]

This may be a homework problem, but it is summer school, so why not?
I'm bored.

In article <7b390929.0308100714.550cc60a@posting.google.com>,
Zhen <zhenxu2000@hotmail.com> wrote:

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.

If the arrays are sortable, you could sort V1 and V2 in
O(n lg + 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.

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?

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

 

[Martin Euredjian]

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" <zhenxu2000@hotmail.com> 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,

 

[Jim Wu]

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
jimwu88NOOOSPAM@yahoo.com

"Martin Euredjian" <0_0_0_0_@pacbell.net> wrote in message news:<cUPZa.10$Vd.1194175@newssvr14.news.prodigy.com>...

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"