Browse Prior Art Database

Efficient compilation of instructions into DFA structure Disclosure Number: IPCOM000235931D
Publication Date: 2014-Mar-31
Document File: 3 page(s) / 48K

Publishing Venue

The Prior Art Database


A method for storage-efficient compilation of instructions into a compressed DFA structure

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 50% of the total text.

Page 01 of 3

Efficient compilation of instructions into DFA structure

    Disclosed is a method for the efficient construction of a compressed data structure for a deterministic finite automaton (DFA) that includes instructions attached to selected transitions, and for which the compression is based on the B-FSM concept described in [1]. A B-FSM compressed data structure is constructed from so called transition rules, which define the transition behavior between states in the DFA. These transition rules are organized into multiple hash tables, which each contain a maximum number of P transition rules in each table entry, with P being an implementation parameter typically in the range from 2 to 8. The compressed data structure can be executed by a so called B-FSM engine, which applies a hash function for a given state and input combination to index a hash-table entry with at most P transition rules from the data structure from which one transition rule is selected using parallel evaluation of the rule conditions, and which is then used to branch to a next state in the DFA. The compressed data structure is constructed by the so called B-FSM compiler. This compiler will ensure that at most P transition rules are mapped on each hash-table entry.

    Figure 1 shows a fragment of a DFA that includes two transitions with instructions attached, labeled as instr1 and instr2. As described in [1], these instructions can be embedded into the data structure, by replacing transition rules in hash-table entries by instruction vectors. This is illustrated in Figure 2, which shows several hash-table entry configurations containing at most P=3 transition rules. The top hash-table entry configuration involves exactly P=3 transition rules. In the other three configurations, one transition rule is replaced by an instruction vector that is associated with the first, the second, or both transition rules, respectively, that have been mapped on the same hash-table entry. The applied configuration is encoded in the entry-type field.


Page 02 of 3

Figure 1. DFA fragment. Figure 2. Sample table-entry configurations.

    In this example involving at most P=3 transition rules being mapped on a single hash-table entry, there can be at most one instruction vector replacing a transition rule (assuming that at most one instruction can be attached to a given transition rule). However, for hash tables that can store more than 3 transition rules per entry (P>3), additional combinations of transition rules and instructions are possible in a given hash-table entry. For example, hash tables storing up to P=6 transition rules per table entry, can contain 4 regular transition rules and 1 transition rule with an instruction attached, or 2 regular transition rules and 2 transition rules with instructions attached, or 3 transition rules with instructions attached. Because the hardware implementation of a B-FSM engine typically imposes a constraint on the maximum number of instructions that can be...