Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-14
2003-10-28
Popovici, Dov (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06640220
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertains to the field of searching computer databases. In particular, it relates to the design of high-speed search coprocessors for connection to general purpose computing equipment for use in searching computer databases or performing fuzzy logic.
BACKGROUND OF THE INVENTION
Computer databases have become ubiquitous. They range from the relatively small directory databases that keep track of files on desktop computers, to enormous databases like the U.S. Patent Office database of issued patents and the Westlaw and Lexis databases of case law.
Databases must often be searched for information of interest to a particular user, relevant to a particular topic, or needed to conduct a particular transaction. Searching of databases, such as routing tables, is often required of embedded systems, in addition to the more visible database searching performed by conventional computer systems. Searching of databases is known often to require considerable processor time.
Artificial intelligence software, including fuzzy logic and neural network applications as well as pattern-recognition applications such as voice recognition and machine-vision applications, often require matching a pattern to a closest pattern in a database of known patterns. Matching a pattern to a closest pattern in a database is also of use in rule-based language translation applications. Matching a pattern to a closest database pattern requires computation of a distance between the desired pattern and each of multiple database patterns; a process that can consume considerable processor time on conventional systems.
The U.S. Patent Office supports a database of patents that is text searchable for specific words. Similarly, Lexis and Westlaw support massive databases that are text searchable for specific words. Typically, such text-searchable databases allow for a Boolean search, where it may be necessary to search for, and construct a list of, all those database entries having a first matching key. This list may then be combed for occurrences of a second matching key, or merged with another list. It is known that searching such databases requires considerable processor time on conventional computer systems because of the many key comparisons that may be required.
Many databases, including text searchable databases and computer filesystem directory databases, are searchable with search strings. These searches require finding all matching records of a database, a task that often requires numerous comparisons and considerable processor time on conventional computer systems.
It is known that Internet IP addresses have a sequence of, typically four, bytes. The first byte of the sequence represents a network number, the last byte of the sequence represents an individual machine number on a subnetwork or sub-subnetwork, the intermediate bytes represents a subnetwork and sub-subnetwork. Each service provider or network forming part of the internet is assigned a network, subnetwork, or sub-subnetwork identification. While it may be possible for any given router to route some packets according to their network number, others may require routing according to both their network number and subnetwork number. Still others may require routing according to more bits, perhaps including their sub-subnetwork and machine numbers, while packets that match network and subnetwork but mismatch sub-subnetwork and machine being routed according to a different, default, route table entry.
A Longest Prefix Match search is a search for the key having the most significant bits—where significant bits are determined by a code attached to the key—that match a key being searched for. A longest prefix match search is useful in Internet packet routing; and will be of use with IPV-4 or future Internet routing protocols where the byte boundary distinction is blurred and additional bytes may be provided.
Recognizing that there is a need for high-speed searching of computer databases, UTMC Microelectronics Systems Inc., a subsidiary of Aeroflex, Incorporated, has marketed a UTCAM-Engine device. This device provides hardware high-speed search capability for large key tables in an attached static RAM, versions of this device have been in production since October 1998; a more recent, enhanced, version supporting larger, multiple, key tables located in attached PC-100 SDRAM (SDRAM means Synchronous Dynamic Random Access Memory) and Longest Prefix Match searches, was first produced in June of 1999.
Each key table entry in the memory attached to a UTCAM-Engine may have an association attached to it, the association often being a pointer or other reference to data in a database. When the UTCAM-Engine device finds a requested key, the association may then be followed to locate desired data. A detailed discussion of this device can be found on the UTMC website, at www.utmc.com.
The UTCAM-Engine is a pipelined, high-speed, device capable of rapidly searching for the matching key of up to thirty-two bytes in a hash-coded table, searching a table for the closest match of a pattern to a key-table pattern using either sum-of-the-squares or straight-sum distance computations, or of searching for a longest prefix match. The UTCAM engine can perform these searches at a rate of up to over fifty million comparisons per second. Some additional detail on the UTCAM-Engine is available in U.S. Pat. No. 6,226,710, also filed as PCT patent application PCT/US98/24288, more information is posted on the UTMC Microelectronics website at www.utmc.com.
The UTCAM-Engine can not, by itself, perform logical operations on lists of matching keys, nor can it extract a sequence of multiple matching keys to form a list of matching key/reference pairs. Both these operations are of frequent interest in database operations.
It is known that the PCI bus specification imposes a power limit of 25 watts per PCI card. This limit is intended to ensure that the bus edge connector pins, motherboard interconnect, wiring between motherboard and power supply, and typical system power supplies are not overloaded as well as limiting the heat that must be removed by the often inadequate fans provided in typical systems. Overloading of power supplies, motherboard interconnect, and wiring between motherboard and power supply is known to have potential to cause improper operating voltages within a computer system, thereby causing faulty operation.
SUMMARY OF THE INVENTION
A search coprocessor for connection to general purpose computing equipment has a programmable processor, a program and data memory, multiple dedicated search engines each having a key-table memory, and a port for communicating over a PCI bus with a host computer. Central to the coprocessor is a buffered command interchange device that interconnects the search engines with the programmable processor.
Each of the dedicated search engines has its own key-table memory, wherein is stored key or index information and association information for locating information in one or more databases. It is expected that key or index information will be distributed between the multiple key-table memories of the coprocessor.
The programmable processor, a MIPS RISC processor, of each coprocessor is capable of parsing search commands into atomic searches performed on the search engines, and for combining results of these atomic searches into overall search results for the search commands. In this way, the search coprocessor can perform logical operations on intermediate search result lists, including AND and OR operations.
Each coprocessor has an auxiliary power connector and voltage regulator module so as to avoid exceeding the PCI limit of 25 watts drawn through a motherboard connector. Provisions are made for as many as four of coprocessors to coexist in a computer system; it is expected that future models will provide for a greater maximum number of coprocessors per system.
REFERENCES:
patent: 4758982 (1988-07-01), Price
patent: 4758983 (1988-07-01), Berndt
patent: 5383146 (1995-01-01), Threewitt
patent: 5423015 (199
Firlit Thaddeus Michael
Melchior Timothy Allan
Webster James Rodney
Abel-Jalil Neveen
Aeroflex UTMC Microelectronic Systems Inc.
Hogan & Hartson LLP
Kubida William J.
Meza Peter J.
LandOfFree
Search coprocessor subsystem having multiple search engines... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Search coprocessor subsystem having multiple search engines..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Search coprocessor subsystem having multiple search engines... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3155167