How best to implement search function in Verilog? - verilog

Mr. Ken wrote:
> An irregular array contains a[32] = {0, 3, 10, 17, 33, ..., 1000}, find the
> location my data is.
> For example, if data is between 0~3, result = 1, between 3~10, result = 2,
> etc.
>
> Do I write 64 comparators to find out the result (assuming single cycle
> operation).
>
> Thanks.

Nobody will do your homework, but I will give you a small tip:

Your array has members which are ordered.
Each search iteration can be done in one cycle.

If yes, then you don't need 64 comparators (why 64?).
Instead, you will need just ....
The rest of exercise goes to your assignment.

Have you ever heard "binary search"?

Utku.

Sorry I haven't read the sentence with "one cycle".
One cycle search is technically an overkill.

You must increase the number of clock cycles to pay less for silicon.

Utku.

utku.ozcan@gmail.com wrote:
> Mr. Ken wrote:
> > An irregular array contains a[32] = {0, 3, 10, 17, 33, ..., 1000}, find the
> > location my data is.
> > For example, if data is between 0~3, result = 1, between 3~10, result = 2,
> > etc.
> >
> > Do I write 64 comparators to find out the result (assuming single cycle
> > operation).
> >
> > Thanks.
>
> Nobody will do your homework, but I will give you a small tip:
>
> Your array has members which are ordered.
> Each search iteration can be done in one cycle.
>
> If yes, then you don't need 64 comparators (why 64?).
> Instead, you will need just ....
> The rest of exercise goes to your assignment.
>
> Have you ever heard "binary search"?
>
> Utku.

<utku.ozcan@gmail.com> wrote in message
news:1157581402.665566.124910@d34g2000cwd.googlegroups.com...
>
> Sorry I haven't read the sentence with "one cycle".
> One cycle search is technically an overkill.
>
> You must increase the number of clock cycles to pay less for silicon.
>
> Utku.
>



Yeah Utku.
If I am not wrong, binary search takes 5 stages of comparator right? I bet
that could well fit into
one clock cycle since my clock speed is a slow 20MHz, but maybe i will use 5
cycles anyhow.

> Yeah Utku.
> If I am not wrong, binary search takes 5 stages of comparator right? I bet
> that could well fit into
> one clock cycle since my clock speed is a slow 20MHz, but maybe i will use 5
> cycles anyhow.

To find what you searching in one clock cycle, you have to compare
everything in one clock. That means you must access ALL the address in
the table. This is not a very good design practice I think, even though
you run the thing in 20 MHz.

Utku.

Massive parallel comparison of data in single cycle is possible through
CAM design.
You could possible look at this option.

--josh

Mr. Ken wrote:
> An irregular array contains a[32] = {0, 3, 10, 17, 33, ..., 1000}, find the
> location my data is.
> For example, if data is between 0~3, result = 1, between 3~10, result = 2,
> etc.
>
> Do I write 64 comparators to find out the result (assuming single cycle
> operation).
>
> Thanks.