Generalized distributed hardware architecture for fast pattern search in large databases

In this thesis we propose a distributed Content Addressable Memory (CAM) based architecture for fast pattern search and data retrieval. The proposed architecture is implemented on an Altera's Cyclone II FPGA using a Quartus II platform. Instead of searching the given data pattern sequentially in a targeted database, we search the user input patterns in parallel in distributed blocks of data from a given database. Analysis of the effects of a CAM block sizes in terms of varying bit-lengths is also performed. There is need for a mechanism to load multiple CAMs efficiently from available memories, to deal with patterns larger than an allowed bit-length on a single CAM. To achieve this purpose we develop a Special Purpose Random Access Memory (SPRAM), which can be loaded normally from a source of data external to the FPGA, and which has the property and ability to write simultaneously into multiple locations in the CAMs.;As it is known it takes one clock cycle for a CAM to generate result outputs in terms of a data match or a mismatch along with the matched address. However it may take a larger amount of time to load a CAM depending upon the CAM's depth. In the proposed architecture we deal with this problem, and show here how the CAMs are fed faster, which reduces the over head time. One other objective of the thesis is to check the time and space complexities and performance of a pattern search using two different proposed architectures. Namely, non-distributed architecture (single set of CAMs) and distributed approach, having more than one data-path. The effect of the varying buffer size on the total system performance is also investigated and measured in terms of the number of clock cycles that are required to perform a pattern comparison and retrieval.