High performance VLSI data filter

• US 5,050,075 A
• Filed: 10/04/1988
• Issued: 09/17/1991
• Est. Priority Date: 10/04/1988
• Status: Expired due to Term

• Current Assignee: TTI Inventions C LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Matoba, Takako, Herman, Gary E., Lee, Kuo-Chu
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): CHUN, DEBRA
• Application Number:
  US07/253,240
• Time in Patent Office: 1,078 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 7/026 Magnitude comparison, i.e. determining the relative order of operands based on their numerical value, e.g. window comparator
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A single chip high speed VLSI data filter is disclosed. The data filter performs relational and simple numeric operations on a high speed input data stream using a unique instruction set containing no branching instructions.

Claims

1. A data filter for performing queries on a high speed data stream organized into a sequence of records which form a database, said data filter comprising

buffer means for receiving and buffering each of said records forming the high speed data stream in sequence,

memory means for storing a batch of instructions arranged in a specific order for carrying out a query in response to a request for information from the database,

pipelined processing means in communication with said buffer means and said memory means for executing said instructions stored in said memory in said specific order for each of said records while each record is buffered in said buffer means, and

intermediate result accumulation means in communication with said processing means for storing an output of said processing means resulting from the execution of particular ones of said instructions by said processing means and for providing an input to said processing means for enabling said processing means to execute subsequent ones of said instructions depending on the contents of the intermediate result accumulation means.

2. The data filter of claim 1

wherein at least some of the instructions stored in said memory means include a pattern and an address indicating a portion of each record to be compared with the pattern, a first opcode for indicating a test to be performed on an output of the comparison, and a second opcode indicating an operation to be performed on an output of said test, and

wherein said pipelined processing means comprises an arithmetic logic unit for performing said comparison, means for performing said test on the output of said comparison, and means for performing said operation on an output of said test and for storing the output of said operation in said intermediate result accumulation means.

3. The data filter of claim 2 wherein said operation utilizes as a first input the output of said test and as a second input the contents of said intermediate result accumulation means.

4. The data filter of claim 2 wherein said instructions stored in said memory include a conditional assignment instruction in which said arithmetic logic unit performs an operation on first and second operands stored in said filter depending on the contents of said intermediate result accumulation means.

5. The data filter of claim 1 wherein said intermediate result accumulation means comprises a one-bit storage means for storing a logic "1" or a logic "0".

6. The data filter of claim 1 wherein said intermediate result accumulation means comprises a stack.

7. The data filter of claim 1 wherein said pipelined processing means is in communication with said memory means via a decoder for decoding said instructions.

8. A data filtering method for performing queries on a high speed data stream comprising a plurality of records which form a database, said method comprising the steps of

buffering in a buffer each of the records comprising said high speed data stream in a sequence,

storing in a memory a batch of instructions arranged in a specific order for carrying out a query on the records of said high speed data stream in response to a request for information from said database,

executing said instructions stored in said memory utilizing a pipelined processor in said specific order for each of said records while each record is buffered in said buffer, said pipelined processor being in communication with said buffer and said memory, and

storing an output of said processor resulting from the execution of particular ones of said instructions by said pipelined processor in an intermediate result accumulator in communication with said processor and utilizing the contents of said intermediate result accumulator as an input to said processor for the execution of subsequent ones of said instructions depending on the contents of said intermediate result accumulator.

9. The method of claim 8 wherein the step of executing at least one of said instructions comprises the steps of comparing a pattern contained in the instruction with data contained in the record currently in the buffer, performing a test on an output of the comparison in accordance with a first opcode contained in the instruction, performing an operation on an output of the test in accordance with a second opcode contained in the instruction, and storing the output of said operation in said intermediate result accumulator.

10. The method of claim 9 wherein the inputs to said operation are the output of said test and the current contents of said intermediate result accumulator.

11. The method of claim 9 wherein one of said instructions stored in said memory is a conditional assignment in which case said execution step comprises

performing an operation on an operand contained in said filter depending on the contents of said intermediate result accumulator.