System and method for analyzing complex sequences in trace arrays using multiple finite automata

• US 5,299,206 A
• Filed: 10/24/1991
• Issued: 03/29/1994
• Est. Priority Date: 10/24/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Beaverson, Arthur J., DeVane, Charles J.
• Primary Examiner(s): Nguyen, Hoa T.
• Application Number:
  US07/781,889
• Time in Patent Office: 887 Days
• Field of Search: 371/22.1, 371/27, 371/22.2-22.6, 371/19, 371/21.5, 395/595, 364/926.7, 364/275.9
• US Class Current: 714/724
• CPC Class Codes: G06F 11/25 Testing of logic operation, e.g. by logic analysers

Abstract

A system and method for analyzing complex overlapping sequences of events in trace arrays, with the system having an input for receiving regular expressions that have been grouped in a predetermined manner, a generator for receiving the grouped regular expressions and generating multiple finite automata based on the groupings of regular expressions, with each finite automaton being generated using arithmetic/logic expressions to permit the use of a substantially infinite alphabet, an input for the trace array, and an analyzer for searching the trace array simultaneously with the multiple finite automata and providing a way by which the multiple finite automata may communicate with one another during searching, with the analyzer further outputting the results of the search.

Claims

1. A system for searching complex sequences in trace arrays, comprising:

first input means for receiving regular expressions in predetermined groupings, with the regular expressions defining desired patterns to be searched for in a trace array;

generator means connected to the input means for receiving the grouped regular expressions input via the first input means and generating a finite automaton for each of the groupings of regular expressions, with each finite automaton using arithmetic/logic expressions;

second input means for receiving the trace array; and

analyzer means that is connected to the second input means and an output of the generator means, and for searching for predetermined patterns of data in the trace array based on the multiple finite automata which use arithmetic/logic expressions.

2. The system as recited in claim 1, wherein the trace array has extra columns for writing to if a finite automaton of multiple finite automata finds a desired pattern in the trace array.

3. The system as recited in claim 1, wherein the system further comprises means for communicating among the multiple finite automata.

4. The system are recited in claim 1, wherein the analyzer further comprises means for searching the trace array simultaneously with multiple finite automata.

5. The system as recited in claim 1, wherein the arithmetic/logic expressions are capable of defining a substantially infinite alphabet.

6. The system as recited in claim 5, wherein the arithmetic/logic expressions may comprise predetermined operators, numbers, and fields.

7. The system as recited in claim 5, wherein the substantially infinite alphabet having a character set of 2¹⁹² and greater characters may be supported by using arithmetic/logic expressions.

8. The system as recited in claim 1, wherein the trace array has up to and greater than 192 columns for signals being sampled at a point in time.

9. The system as recited in claim 1, wherein the trace array has up to and greater than 2,097,152 rows for samples of all signals that are taken.

10. A method for searching complex sequences in trace arrays, comprising the steps of:

(a) inputting regular expressions in predetermined groupings, with the regular expressions defining desired patterns to be searched for in the trace array;

(b) generating multiple finite automata which use arithmetic/logic expressions, with the each grouping of regular expressions forming a finite automaton;

(c) reading the trace array and searching for predetermined patterns with the multiple finite automata which use arithmetic/logic expressions; and

(d) outputting results of the search.

11. The method as recited in claim 10, wherein the method further comprises the step of communicating among the finite automata during searching.

12. The method as recited in claim 10, wherein step (b) further comprises generating multiple finite automata which use arithmetic/logic expressions that permit the use of a substantially infinite alphabet.

13. The method as recited in claim 12, wherein the step (b) further comprises generating multiple finite automata which use arithmetic/logic expressions, with the expressions including predetermined operators, numbers, and fields.

14. The method as recited in claim 10, wherein step (b) further comprises generating multiple finite automata which use arithmetic/logic expressions, with the arithmetic/logic expressions permitting the use of a substantially infinite alphabet having a character set of up to and greater than 2¹⁹² characters.

15. The method as recited in claim 10, wherein step (c) further comprises searching simultaneously with multiple finite automata.