Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

architecture of pipelined for searching in memory

Status
Not open for further replies.

jalal.baba

Junior Member level 1
Joined
Feb 5, 2018
Messages
16
Helped
0
Reputation
0
Reaction score
0
Trophy points
1
Activity points
118
Hi friends.
I have two memory in my project(memA and memB).
I wants finding elements of memeA in memB . Actually i want searching elements of mem A in mem B and obtain row memB witch matching in memA.
s.JPG
What architecture of pipelined do you recommend?
Thanks
 

This is a CAM (content addressable memory) and they are very slow in FPGAs. You potentially need to search the whole of B to find the row the data is in, which will up to N clocks for a single lookup.
 

Hi,

Using an index could improve access time.

Klaus
 

Using an index could improve access time.
This needs more explanation.


For the OP, a general method is to have a full lookup ram. Eg, if the tags are 8 bit, you have a RAM that has all 256 tags with values to where they are in the next RAM. This clearly doesn't scale. For FPGA's, I'm not sure what approach would be best. A first thought would be something based on b-trees?

--edit: After posting this, I noticed that this might be read as hostile towards KlausST. This wasn't my intent. I don't know what the suggestion means and I suspect a novice user would also need a bit more info. I don't know if this is suggesting some form of caching, a full index LUT, or something else.
 
Last edited:

Hi,

The contents of the RAM can be seen as a database.
And I thought that "index" is a known phrase in this area.

OS (like Windows) use the same phrase for faster finding the files on their hard drives.

****
How it works.
Without an index the values are randomly spread over the whole memory.
Thus you may look at each single memory place to find out if the value matches.

Now and index is a number of pointers to the contents of the memory.
But the first pointer shows the address of the memory with the lowest value.
And the next pointer shows the address of the next higher value of your memory (or same value, if allowed).
So the index shows the adresses to the memory contents in ascending order of the values.

The benefit is that now you can use a "binary search".

Let's assume you have 1024 values in your memory.
Without indexing you may
* read ut to 1024 memory contents
* and do up to 1024 "compares"

With indexing you need to
* read up to 10 index contents (binary search)
* read up to 10 (indirect addressed via index content) memory content
* do up to 10 "compares"

That' s 2048 instructions vs 30 instructions. A huge improvement.

There are a lot of documents, even video tutorials about indexing and binary search.

Klaus
 

Ok, this makes sense. I mostly use "index" to refer to the key of an associative array or an integer into an array or etc... vs the data structure itself.
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top