Data driven processor with data pairing apparatus combining a hash memory with counter directional data loops

Claim 2

In a data-driven data processing system having a data storage memory, means for receiving an incoming stream of data words, each data word having an address field and an identifier field comprising a predetermined number of bits, address hashing means responsive to said address field in each data word for generating a hashed address for each data word with a number of bits less than said predetermined number, means responsive to a hashed address of a first data word for reading a second data word from said data storage memory using said first data word hashed address as a memory address, and means responsive to a first identifier field included in said first data word and responsive to a second identifier field included in said second data word for generating a data pair word when said first identifier field has a first predetermined relationship to said second identifier field, the improvement comprising: means responsive to said first identifier field and to said second identifier field for loading said first data word into a first data loop register or a second data loop register when said first identifier field and said second identifier field do not have said first predetermined relationship, each data loop register having a plurality of stages; and means connected to register stages in said first data loop register and to register stages in said second data loop register and responsive to identifier fields in data words in said first data loop register and responsive to identifier fields in data words in said second data loop register for generating a data pair word when a third identifier field in a data word in said first data loop register has a second predetermined relationship to a fourth identifier field in a data word in said second data loop register.

Claim 3

In a data-driven data processing system, the improvement according to claim 1 wherein said first data loop register comprises a first shift register having a plurality of stages connected in a loop and said second data loop register comprises a second shift register having a plurality of stages connected in a loop.

Claim 4

In a data-driven data processing system, the improvement according to claim 2 further comprising means for shifting data words in said first shift register loop through said plurality of first shift register stages in a clockwise direction and means for shifting data words in said second shift register loop through said plurality of second shift register stages in a counter-clockwise direction.

Claim 5

In a data-driven data processing system, the improvement according to claim 1 wherein said data word address field comprises a plurality of low-order bits and a plurality of high-order bits and said address hashing means comprises means responsive to said data word address field for selecting a plurality of the low-order bits of said data word address field as said hashed address.

Claim 6

In a data-driven data processing system, the improvement according to claim 4 wherein said identifier field comprises a plurality of said high-order bits of said data word.

Claim 7

In a data-driven data processing system, the improvement according to claim 5 wherein said second data word comprises a data portion and an address portion and wherein said second identifier field is stored in said data storage memory together with said data portion of said second data word.

Claim 8

In a data-driven processing system having a data storage memory, apparatus for pairing a data word from said data storage memory with data words from an incoming data stream by comparing identifier fields contained within said data words, said apparatus comprising: address hashing means responsive to an address field, said address field having a predetermined number of address bits in each data word, said address hashing means generating a hashed address for each data word from said incoming data stream, said hashed address having a number of bits less than said predetermined number; means responsive to a hashed address of a first data word for reading a second data word from said data storage memory using said first data word hashed address as a memory address; first means responsive to a first identifier field included in said first data word and responsive to a second identifier field included in said second data word for generating a data pair word when said first identifier field has a first predetermined relationship to said second identifier field; means responsive to said first identifier field and to said second identifier field for loading said first data word into a first or second data loop register when said first identifier field and said second identifier field do not have said first predetermined relationship, each data loop register having a plurality of stages; and second means connected to register stages in said first data loop register and to register stages in said second data loop register and responsive to identifier fields in data words in said first data loop and responsive to identifier fields in data words in said second data loop for generating a data pair word when a third identifier field in a data word in said first data loop has a second predetermined relationship to a fourth identifier field in a data word in said second data loop.

Claim 9

In a data-driven processing system having a data storage memory, apparatus for pairing a data word from said data storage memory with data words from an incoming data stream by comparing identifier fields contained within said data words, said apparatus comprising: address hashing means responsive to an address field, said address field having a predetermined number of address bits in each data word, said address hashing means generating a hashed address for each data word from said incoming data stream, said hashed address having a number of bits less than said predetermined number; means responsive to a hashed address of a first data word for reading a second data word from said data storage memory using said first data word hashed address as a memory address; first means responsive to a first identifier field included in said first data word and responsive to a second identifier field included in said second data word for generating a data pair word when said first identifier field has a first predetermined relationship to said second identifier field; means responsive to said first identifier field and to said second identifier field for loading said first data word into a first or second data loop register when said first identifier field and said second identifier field do not have said first predetermined relationship, each data loop register having a plurality of stages; and second means connected to register stages in said first data loop register and to register stages in said second data loop register and responsive to identifier fields in data words in said first data loop and responsive to identifier fields in data words in said second data loop for generating a data pair word when a third identifier field in a data word in said first data loop has a second predetermined relationship to a fourth identifier field in a data word in said second data loop.

Claim 10

In a data-driven data processing system, apparatus for pairing data words according to claim 7 wherein said first data loop register comprises a fist shift register having a plurality of stages connected in a loop and said second data loop register comprises a second shift register having a plurality of stages connected in a loop.

Claim 11

In a data-driven data processing system, apparatus for pairing data words according to claim 8 further comprising means for shifting data words in said first shift register through said plurality of first shift register stages in a clockwise direction and means for shifting data words in said second shift register through said plurality of second shift register stages in a counter-clockwise direction.

Claim 12

In a data-driven data processing system, apparatus for pairing data words according to claim 7 wherein said data word address field comprises a plurality of low-order bits and a plurality of high-order bits and said address hashing means comprises means responsive to said data word address field for selecting a plurality of the low-order bits of said data word address field as said hashed address.

Claim 13

In a data-driven data processing system, apparatus for pairing data words according to claim 10 wherein said first identifier field comprises a plurality of said high-order bits of said first data word and said second identifier field comprises a plurality of said high-order bits of said second data word.

Claim 14

In a data-driven data processing system, apparatus for pairing data words according to claim 11 wherein said second data word comprises a data portion and an address portion and wherein said second identifier field is stored in said data storage memory together with said data portion of said second data word.

Claim 15

In a data-driven data processing system, apparatus for pairing data words according to claim 7 further comprising means responsive to said second data word read out from said memory for generating an occupation signal, said occupation signal being stored in said data storage memory together with said second data word to generate a stored occupation signal, said occupation signal generating means setting the occupation signal to an on state when the stored occupation signal is in an off state and resetting said occupation signal to an off state when said stored occupation signal is in an on state, said apparatus further comprising means responsive to said stored occupation signal for writing said first data word into said memory.

Claim 16

In a data-driven data processing system, apparatus for pairing data words according to claim 7 further comprising means connecting said second generating means to said address hashing means for transferring said first data word from said second generating means to said address hashing means when said third identifier field does not have said second predetermined relationship to said fourth identifier field.

Claim 17

A data-driven processing system comprising: means for receiving a stream of incoming data words; a program storage memory for storing a plurality of codes, each code having a low-order bit field and a high-order bit field; means responsive to each incoming data word for reading said program memory and for appending to each data word one of said plurality of codes; a template matching memory; means responsive to a first low-order bit field of a code appended to a first data word for reading a data packet from said template matching memory using said first low-order bit field as a memory address, said data packet including a second data word and an appended code; first means responsive to a first code appended to said first data word and responsive to a second code appended to said data packet for generating a data pair word when a first high-order bit field of the first code has a first predetermined relationship to a second high-order bit field of said second code; means responsive to said first high-order bit field and to said second high-order bit field for loading said first data word and its appended code into a first or second data loop register when said first high-order bit field and said second high-order bit field do not have said first predetermined relationship, said data loop registers each having a plurality of stages; means for shifting data words in said first data loop register through said plurality of first data loop register stages in a clockwise direction and means for shifting data words in said second data loop register through said plurality of second data loop register stages in a counter-clockwise direction; and second means connected to said first and second data loop register stages and responsive to high-order bit fields of codes in said first and second data loop registers for generating a data pair word when a high-order bit field of a code in said first data loop register has a second predetermined relationship to a high-order bit field of a code in said second data loop register.

Claim 18

A data-driven processing system comprising: means for receiving a stream of incoming data words; a program storage memory for storing a plurality of codes, each code having a low-order bit field and a high-order bit field; means responsive to each incoming data word for reading said program memory and for appending to each data word one of said plurality of codes; a template matching memory; means responsive to a first low-order bit field of a code appended to a first data word for reading a data packet from said template matching memory using said first low-order bit field as a memory address, said data packet including a second data word and an appended code; first means responsive to a first code appended to said first data word and responsive to a second code appended to said data packet for generating a data pair word when a first high-order bit field of the first code has a first predetermined relationship to a second high-order bit field of said second code; means responsive to said first high-order bit field and to said second high-order bit field for loading said first data word and its appended code into a first or second data loop register when said first high-order bit field and said second high-order bit field do not have said first predetermined relationship, said data loop registers each having a plurality of stages; means for shifting data words in said first data loop register through said plurality of first data loop register stages in a clockwise direction and means for shifting data words in said second data loop register through said plurality of second data loop register stages in a counter-clockwise direction; and second means connected to said first and second data loop register stages and responsive to high-order bit fields of codes in said first and second data loop registers for generating a data pair word when a high-order bit field of a code in said first data loop register has a second predetermined relationship to a high-order bit field of a code in said second data loop register.

Claim 19

A data-driven data processing system according to claim 15 further comprising an arithmetic logic unit and means for applying a generated data pair to said arithmetic logic unit, said arithmetic logic unit processing said generated data pair and generating an output as a result thereof.

Claim 20

A data-driven data processing system, according to claim 15 further comprising means responsive to said data packet read out from said template matching memory for generating an occupation signal, said occupation signal being stored in said template matching memory together with said data packet to generate a stored occupation signal, said occupation signal generation means setting the occupation signal to an on state when the stored occupation signal is in an off state and resetting said occupation signal to an off state when said stored occupation signal is in an on state, said apparatus further comprising means responsive to said stored occupation signal for writing said first data word and said first high-order bit field into said template matching memory.

Claim 21

A data-driven data processing system according to claim 15 further comprising means connecting said second generating means to said reading means for transferring said first data word from said second generating means to said reading means when said high-order bit field in a code in said first data loop does not have said second predetermined relationship to said high-order bit field in a code in said second data loop register.

Claim 22

In a data-driven processing system having a data storage memory, a method of pairing data packets from said data storage memory with data packets from an incoming data stream by comparing identifier fields contained within said data packets, each of said data packets comprising a data word and a set of address bits divided into a first address bit subset and a second address bit subset, said method comprising the steps of: A. generating a hashed address from said first address bit subset for a first data packet from said incoming data stream; B. reading a second data packet from said data memory using said first data packet hashed address as a memory address; C. generating a data pair packet when said second address bit subset of said first data packet equals said second address bit subset of said second data packet; D. loading said first data packet into a first or second data loop register when said second address bit subset of said first data packet and said second address bit subset of said second data packet are not equal, each of said data loop registers having a plurality of stages; E. comparing first and second address bit subsets of selected data packets in said first data loop register to first and second address bit subsets of selected data packets in said second data loop register; and F. generating a data pair packet when both a first and second address bit subset of a data packet in said first data loop register equals a first and second address bit subset of a data packet in said second data loop register.

Claim 23

In a data-driven processing system having a data storage memory, a method of pairing data packets from said data storage memory with data packets from an incoming data stream by comparing identifier fields contained within said data packets, each of said data packets comprising a data word and a set of address bits divided into a first address bit subset and a second address bit subset, said method comprising the steps of: A. generating a hashed address from said first address bit subset for a first data packet from said incoming data stream; B. reading a second data packet from said data memory using said first data packet hashed address as a memory address; C. generating a data pair packet when said second address bit subset of said first data packet equals said second address bit subset of said second data packet; D. loading said first data packet into a first or second data loop register when said second address bit subset of said first data packet and said second address bit subset of said second data packet are not equal, each of said data loop registers having a plurality of stages; E. comparing first and second address bit subsets of selected data packets in said first data loop register to first and second address bit subsets of selected data packets in said second data loop register; and F. generating a data pair packet when both a first and second address bit subset of a data packet in said first data loop register equals a first and second address bit subset of a data packet in said second data loop register.

Claim 24

In a data-driven data processing system having a data storage memory, the method of pairing data packets according to claim 19 wherein step A comprises the step of: A1. arranging bits in said first address bit subset in a predetermined order.

Claim 25

In a data-driven data processing system having a data storage memory, the method of pairing data packets according to claim 19 wherein step C comprises the steps of: C1. forming a paired address by combining said first address bit subset and said second address bit subset in a predetermined order; C2. forming a paired data word by combining a data word from said first data packet and a data word from said second data packet in a predetermined order; and C3. appending said paired data word to said paired address.

Claim 26

In a data-driven data processing system having a data storage memory, the method of pairing data packets according to claim 19 wherein step D comprises the steps of: D1. continuously shifting data in said first data loop register in a clockwise direction; and D2. continuously shifting data in said second data loop register in a counter-clockwise direction.

Claim 27

In a data-driven data processing system having a data storage memory, the method of pairing data packets according to claim 19 wherein step E comprises the step of: E1. comparing the second address bit subsets of data packets temporarily stored in predetermined stages of said first data loop register to second address bit subsets of data packets temporarily stored in predetermined stages of said second data loop register.

Claim 28

In a data-driven data processing system having a data storage memory, the method of pairing data packets according to claim 19 wherein step F comprises the steps of: F1. forming a paired address by combining said first address bit subset and said second address bit subset in a predetermined order; F2. forming a paired data word by combining a data word from said first data packet and a data word from said second data packet in a predetermined order; and F3. appending said paired data word to said paired address.

Claim 29

In a data-driven data processing system having a data storage memory, an apparatus for pairing data packets from said data storage memory with data packets from an incoming data stream by comparing identifier fields contained within said data packets, each of said data packets comprising a data word and a plurality of address bits, the identifier field of a data packet being a subset of said address bits, said apparatus comprising: means for generating a hashed address for a first data packet from the plurality of address bits of said first data packet; means for reading a second data packet from said data storage memory using said first data packet hashed address as a memory address; first means for generating a paired data packet when the identifier field of said first data packet is equal to the identifier field of said second data packet; a first data transmission line for transmitting unmatched data packets in a first direction; a second data transmission line for transmitting unmatched data packets in a second direction, said second direction being opposite said first direction; means for loading said first data packet into said first or second data transmission line when the identifier fields of said first data packet and said second data packet are not equal; means for comparing the identifier field of unmatched data packets in the first data transmission line to the identifier field of unmatched data packets in said second data transmission line; and second means for generating a paired data packet from a first unmatched data packet in said first data transmission line and a second unmatched data packet in the second data transmission line when the identifier fields of said first and second unmatched data packets are equal, as determined by said means for comparing.

Claim 30

In a data-driven data processing system having a data storage memory, an apparatus for pairing data packets from said data storage memory with data packets from an incoming data stream by comparing identifier fields contained within said data packets, each of said data packets comprising a data word and a plurality of address bits, the identifier field of a data packet being a subset of said address bits, said apparatus comprising: means for generating a hashed address for a first data packet from the plurality of address bits of said first data packet; means for reading a second data packet from said data storage memory using said first data packet hashed address as a memory address; first means for generating a paired data packet when the identifier field of said first data packet is equal to the identifier field of said second data packet; a first data transmission line for transmitting unmatched data packets in a first direction; a second data transmission line for transmitting unmatched data packets in a second direction, said second direction being opposite said first direction; means for loading said first data packet into said first or second data transmission line when the identifier fields of said first data packet and said second data packet are not equal; means for comparing the identifier field of unmatched data packets in the first data transmission line to the identifier field of unmatched data packets in said second data transmission line; and second means for generating a paired data packet from a first unmatched data packet in said first data transmission line and a second unmatched data packet in the second data transmission line when the identifier fields of said first and second unmatched data packets are equal, as determined by said means for comparing.

Claim 31

In a data-driven data processing system having a data storage memory, the apparatus according to claim 25 wherein said first means for generating a paired data packet comprises: means for forming a paired address by combining the plurality of address bits and identifier field of said first data packet in a predetermined order; means for forming a paired data word by combining a data word from said first data packet and a data word from said second packet in a predetermined order; and means for appending said paired data word to said paired address.

Claim 32

In a data-driven data processing system having a data storage memory, the apparatus according to claim 25 wherein said first data transmission line comprises a shift register means having a plurality of registers coupled in a loop configuration for continuously shifting data words in a clockwise direction and wherein said second data transmission line comprises a shift register means having a plurality of registers coupled in a loop configuration for continuously shifting data words in a counter-clockwise direction.

Claim 33

In a data-driven data processing system having a data storage memory, the apparatus according to claim 25 wherein said second means for generating a paired data packet from said first and second data packets comprises: means for forming a paired address by combining the plurality of address bits and identifier field of said first unmatched data packet in a predetermined order; means for forming a paired data word by combining a data word from said first unmatched data packet and a data word from said second unmatched data packet in a predetermined order; and means for appending said paired data word to said paired address.