Memory-based history search

A method for history matching a data stream, the method comprising:

• sequentially introducing each word in the data stream, where introducing a current word in the input sequence includes:
• storing the current word in a storage location of a first memory having N storage locations such that the N most recently introduced words are stored in the first memory;
• storing the current word in an array of M second memories, each second memory including N word storage locations, the array defining a set of storage locations logically divided into N rows of M storage locations, each row including one storage location from each of the M second memories, wherein the current word is stored according to a storage location sequence which cycles through the set of storage locations such that M consecutively introduced words are each stored in a different second memory in the array;
• concurrently comparing data stored in the N storage locations of the first memory with data stored in a select row of the set of storage locations;
• and
• storing outputs of the comparisons as history match results;
• wherein the select row changes with the introduction of each word, the select row cycling through each of the N rows for every N introduced words.

A device for history matching a data stream, each word of the data stream being sequentially introduced, the device comprising:

• a first memory including N storage locations, the first memory configured to store a currently introduced word such that the N most recently introduced words are stored in the first memory;
• an array of M second memories, each second memory including N storage locations, the array defining a set of storage locations logically divided into N rows of M storage locations, each row including one storage location from each of the M second memories, the array of M second memories configured to store the currently introduced word at a select storage location of the set of storage locations;
• a plurality of comparators configured for comparing data from all of the storage locations in the first memory with data stored in a select row of the set of storage locations, where outputs of the comparators provide history matching data;
• a memory selector for identifying the select storage location, the memory selector configured to identify a next storage location in a storage location sequence with the introduction of each word, where the storage location sequence cycles through the set of storage locations such that M consecutively introduced words are each stored in a different second memory in the array;
• and
• a row selector for identifying the select row, the row selector configured to identify a next select row with the introduction of each word, the select row cycling through each of the N rows for every N introduced words.