Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-08-10
2004-07-06
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S108000, C711S100000
Reexamination Certificate
active
06760821
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to a memory engine for the inspection and manipulation of data, and more particularly, to a memory engine which not only provides for the fast searching of data, in the form of strings of symbols (characters or the like), but also provides for the selective insertion and deletion of data within the character strings, as required.
BACKGROUND OF THE INVENTION
Searching a buffer, or other memory device, comprised of symbols for strings that match a given or predetermined string of symbols is a basic operation found in many applications, such as but not limited to databases, the processing of genetic information, data compression, and the processing of computer languages. Modification of a string by inserting new sequences in it, or deleting sequences from it, is also a basic operation in these domains, and the time taken by these string operations influences directly the execution time of the main applications.
When a serial computation is performed, that is, a matching operation, to find all occurrences of strings of N symbols in a buffer containing M symbols, the maximum number of steps required is N*M. When an insertion of a character is necessary inside the buffer, on the average of half of the symbols in the buffer have to be moved one cell to the right or to the left to make room for the new cell. In this case, an average of N/2 steps are required.
Serial algorithms have been proposed to improve these operations, and they are based on several techniques including hashing, or tree data structures. Hashing is used when the strings of interests are words of fixed length. In this case each word is associated with a unique number that is used as the index where that word is stored in a dictionary. This method has the disadvantage that it works well only when the information is static, and does not change location during processing. Furthermore, generating this number is a costly operation, and sometimes several words may be associated with the same number, requiring additional work to find the word sought. Suffix trees may also be utilized and are tree structures in which all the substrings present in the buffer are stored. When one wants to see if a given string is located in the buffer, one only has to descend the tree, one character of the sought string at a time, until the string is either found, or not found. In either case, if the string contains M symbols, at most M steps are required to decide if the string is in the buffer of length L. Although this search method is fast, building the suffix tree is oftentimes computationally expensive.
The Content Addressable Memory, or CAM, is a parallel solution for finding the location of a given symbol or word in a single memory access. This method works well for fixed length words, but does not extend easily to variable length strings of symbols. When the search can be performed in parallel in the buffer, that is when M comparisons can be performed at the same time, then the number of steps is reduced to N. Buffers with parallel comparators and markers storing the result of each comparison with a given symbol have been proposed to speed up string searches. See, for example, Almy et al., U.S. Pat. No. 4,575,818; Mayer, U.S. Pat. No. 5,319,762; Eskandari-Gharnin et al., U.S. Pat. No. 5,602,764; or Satoh, et al., U.S. Pat. No. 5,448,733. These known devices typically associate a comparator with each cell of the buffer, along with a one-bit marker storing the result of the last comparison performed. The comparator, storage cell and marker operate in such a way that a symbol from the string to be located in the buffer is broadcast to all the comparators of the buffer. These comparators in turn compare the given symbol to that stored in their associated storage cell. The result of the comparison is stored in the marker associated with the comparator and storage cell.
Buffers implemented as shift registers allow their contents to be shifted to the left or to the right in parallel, synchronously to a clock signal. In this case the whole contents of the buffer can be shifted in just one step. These buffers, however, do not offer only a section of their contents to be shifted, but offer only global shift operations. Moreover, the integration of separate comparators for each cell of the buffer tends to increase the size and complexity of the device as a whole, thus leading to excessive cost and energy use.
With the forgoing problems and concerns in mind, the present invention therefore seeks to utilize a memory apparatus which allows for very fast character strings searches, insertions and deletions, wherein a new type of memory storage circuit called a Connex Memory (hereinafter, CM) is utilized.
SUMMARY OF THE INVENTION
It is an object of the present invention to enable fast string search, insertion, and deletion operations to be performed on data.
It is another object of the present invention to enable fast string search, insertion, and deletion operations to be performed on data comprising a string of data characters.
It is another object of the present invention to enable fast string search, insertion, and deletion operations to be performed on data comprising a string of data characters, wherein the inspection and manipulation of any given data character is accomplished in a single clock cycle.
It is another object of the present invention to enable the inspection of variably-sized data fields within a string of data characters.
It is another object of the present invention to enable the marking of variably-sized data fields within a string of data characters.
It is another object of the present invention to utilize static or dynamic memory cells to temporarily store and manipulate a string of data characters.
It is another object of the present invention to inspect a string of data characters stored in the memory cells in either a forward or reverse direction.
According to one embodiment of the present invention, a memory engine combines associative memory and random-access memory for enabling fast string search, insertion, and deletion operations to be performed on data and includes a memory device for temporarily storing the data as a string of data characters. A controller is utilized for selectively outputting one of a plurality of commands to the memory device and receives data feedback therefrom, the memory device inspects data characters in the string in accordance with the commands outputted by the controller. A clock device is also utilized for outputting a clock signal comprised of a predetermined number of clock cycles per second to the memory device and the controller, the memory device inspecting and selectively manipulating one of the data characters within one of the clock cycles.
REFERENCES:
patent: 4575818 (1986-03-01), Almy et al.
patent: 5122984 (1992-06-01), Strehler
patent: 5150430 (1992-09-01), Chu
patent: 5319762 (1994-06-01), Mayer
patent: 5329405 (1994-07-01), Hou et al.
patent: 5373290 (1994-12-01), Lempel et al.
patent: 5440753 (1995-08-01), Hou et al.
patent: 5448733 (1995-09-01), Satoh et al.
patent: 5497488 (1996-03-01), Akizawa et al.
patent: 5602764 (1997-02-01), Eskandari-Gharnin et al.
patent: 5818873 (1998-10-01), Wall et al.
patent: 5828593 (1998-10-01), Schultz et al.
Mitu et al., “A CMOS Implementation of a Connex Memory,” pp. 579-582, IEEE, 1997.*
Stefan, Gheorghe, Silicon or Molecules? What's the Best for Splicing?, Technical Univ. of Bucharest, Dept. of Electronics, pp. 158-181, 1998.
Stefan, Gheorge, The Connex Memory. A Physical Support for Tree/List Processing, Tech. Univ. of Bucharest, Dept. of Electronics, pp. 1-22, 1994.
Stefan, Gheorge and Benea, Robert, Connex Memories & Rewriting Systems, Politehnica Univ. of Bucharest, Department of Electronics, pp. 1299-1303, 1998.
Stefan, Denisa and Stefan, Gheorghe, “Bi-thread Microcontroller as Digital Signal Processor” 1997 IEEE.
Hascsi, Zoltan; MITU, Bogdan; Petre, Mariana; Stefan, Gheorghe, “High-Level Synthesis of an Enhanced Connex Memory”, 1996 IEEE, pp. 163-166.
Stef
Stefan Gheorghe
Thiebaut Dominique
Elmore Stephen
Gemicer, Inc.
Kim Matthew
McCormick Paulding & Huber LLP
LandOfFree
Memory engine for the inspection and manipulation of data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory engine for the inspection and manipulation of data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory engine for the inspection and manipulation of data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3201052