Memory with integrated search engine

• US 5,893,089 A
• Filed: 11/15/1996
• Issued: 04/06/1999
• Est. Priority Date: 11/15/1996
• Status: Expired due to Fees

• Current Assignee: Lextron Systems, Inc.
• Original Assignee: Lextron Systems, Inc.
• Inventors: Kikinis, Dan
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/749,992
• Time in Patent Office: 872 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 1/1, 365/230.03, 365/185.33, 365/218
• US Class Current: 1/1
• CPC Class Codes: G06F 15/7839 with memory
• CPC Class Codes: G06F 9/30018 Bit or string instructions
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A memory chip has an on-board search engine adapted to accept programming from a system CPU and to perform a search for a search object or pattern independently of further action by the CPU, wherein the CPU is free to perform other tasks while a search of memory banks composed of two or more such chips takes place. In some embodiments the memory chip has a dedicated bus connection for programming by the system CPU and for reporting the results of a search. In some embodiments as well the on-board search engine has a dedicated on-board bus for communication with column amplifiers and decoders of memory cell arrays on the chip. CPU and memory combinations are disclosed and methods for practicing the invention.

Claims

1. A Dynamic Random Access Memory (DRAM) chip comprising:

at least one memory array;

a programmable search engine implemented on the DRAM chip; and

a programming interface to a CPU;

wherein the programmable search engine receives a search standard from the CPU on the programming interface, the search standard defining stored data to be found in the memory array, and accomplishes a search according to the standard.

2. The memory chip of claim 1 further comprising upper and lower overlap zones at the upper and lower ends of the memory address space assigned to the chip, wherein a range of addresses at an upper end of the address space of an address-numerically-adjacent chip is redundantly stored in the lower overlap zone, and a range of addresses at a lower end of the address space of an address-numerically-adjacent chip is redundantly stored in the upper overlap zone.

3. The memory chip of claim 1 further comprising a redundant on-chip bus between the search engine and column amplifiers and decoders of the memory arrays on the chip.

4. The memory chip of claim 1 wherein the chip comprises a connection to a conventional address and data bus, and further comprises a connection from the search engine to the programming interface adapted for programming the search engine.

5. The memory chip of claim 4 wherein the programming interface includes one or more assertion lines adapted for informing a CPU of accomplishment of a search object.

6. A combined CPU and memory system, comprising:

a CPU;

a plurality of DRAM chips, wherein two or more of the DRAM chips have an on-board programmable search engine;

a conventional bus coupling the CPU and the two or more DRAM chips; and

a programming interface coupling the search engines to the CPU;

wherein the CPU programs the two or more search engines to perform substantially simultaneous searches on the associated DRAM chips independently of further action of the CPU after the programming is accomplished.

7. The combined system of claim 6 wherein the search engines are adapted to report the accomplishment of a search object to the CPU via the programming interface.

8. The combined system of claim 6 wherein the memory chips further comprise upper and lower overlap zones at the upper and lower ends of the memory address space assigned to the chips, wherein a range of addresses at an upper end of the address space of an address-numerically-adjacent chip is redundantly stored in the lower overlap zone, and a range of addresses at a lower end of the address space of an address-numerically-adjacent chip is redundantly stored in the upper overlap zone.

9. The combined system of claim 6 wherein each DRAM chip further comprises a redundant on-chip bus between the search engine and column amplifiers and decoders of the memory arrays on the chip.

10. A method for performing a search by a system CPU in a bank of memory chips, comprising steps of:

(a) implementing a programmable search engine on two or more of the memory chips in the bank of memory chips;

(b) programming by the CPU of the two or more search engines to substantially simultaneously perform the search independently of further action by the CPU; and

(c) receiving search results by the CPU.