Hardware compilation of cascaded grammars

Patent metadata

Field	Value
Publication number	US-10198646-B2
Application number	US-201615201146-A
Country	US
Kind code	B2
Filing date	Jul 1, 2016
Priority date	Jul 1, 2016
Publication date	Feb 5, 2019
Grant date	Feb 5, 2019

Abstract

A cascaded finite-state-transducer array includes a plurality of finite-state-transducers, the finite-state-transducers being distributed in space. The finite-state-transducer array is configured with dedicated data transfer channels between the finite-state-transducers to transfer specific data types. Each data stream on a dedicated data transfer channel may transmit a particular data type, which may be sorted in increasing order of start offsets or token IDs.

First claim

What is claimed is:

1. A cascaded finite-state-transducer array, comprising:
a plurality of finite-state-transducers, the finite-state-transducers being distributed in space, at least one finite-state-transducer including a loop; and
a finite-state-machine based controller adapted to control stalling of processing of the loop by the at least one finite-state-transducer;
wherein the array is configured with dedicated data transfer channels between the finite-state-transducers to transfer specific data types.

2. The cascaded finite-state-transducer array of claim 1 , wherein:
each data stream on a dedicated data transfer channel transmits a particular data type, which is sorted in increasing order of start offsets or token IDs.

3. The cascaded finite-state-transducer array of claim 1 , further comprising circuitry for each finite-state-transducer adapted to synchronize input streams of the respective finite-state-transducers by requiring either a valid-data or an input-end signal on each stream.

4. The cascaded finite-state-transducer array of claim 3 , wherein the input-end signal comprises one of an end-of-stream, end-of-sentence, and an end-of-paragraph signal.

5. The cascaded finite-state-transducer array of claim 3 , further comprising circuitry for each finite-state-transducer adapted to produce an input-end signal for the finite-state-transducer when all input data streams of the finite-state-transducer contain an input-end signal.

6. The cascaded finite-state-transducer array of claim 1 , further comprising input buffering circuitry for each finite-state-transducer adapted to stall or pause processing of the finite-state-transducer until all input data streams of the finite-state-transducer contain data that can be consumed.

7. The cascaded finite-state-transducer array of claim 1 , further comprising circuitry for each finite-state-transducer adapted to fetch data only from the input streams containing valid data and having a smallest start offset or start token ID.

8. A cascaded finite-state-transducer array, comprising:
a plurality of finite-state-transducers, the finite-state-transducers being distributed in space;
a top-level pipeline comprising a decoder adapted to decode data types of data input to the array; and
a multiplexer to multiplex data types of data output from the array;
wherein the array is configured with dedicated data transfer channels between the finite-state-transducers to transfer specific data types.

9. A cascaded finite-state-transducer array, comprising:
a plurality of finite-state-transducers, at least one finite-state-transducer including a loop, the finite-state-transducers comprising a network of nondeterministic finite state automatons, the nondeterministic finite state automatons being distributed in space; and
a finite-state-machine based controller adapted to control stalling of processing of the loop by the at least one finite-state-transducer;
wherein the array is configured with dedicated data transfer channels between the finite-state-transducers to transfer specific data types.

10. The cascaded finite-state-transducer array of claim 9 , further comprising circuitry for each finite-state-transducer adapted to locally store, in each finite-state-transducer state, a number of features incrementally built from input data streams of the finite-state-transducer.

11. The cascaded finite-state-transducer array of claim 10 , further comprising circuitry for each finite-state-transducer adapted to update the locally stored features on state transitions, or write the locally stored features to outputs of the finite-state-transducer on state transitions.

12. The cascaded finite-state-transducer array of claim 11 , wherein each finite-state-transducer comprises circuitry adapted to determine when two independent state transitions lead to a same destination state and to update the locally stored features based on a state transition that is associated with a higher priority data type, a state transition originating from a source state that stores a smaller start-offset value, or a state transition that is associated with a data type that stores a larger end-offset or end-token-ID value.

13. A cascaded finite-state-transducer array, comprising:
a plurality of finite-state-transducers, the finite-state-transducers comprising a network of nondeterministic finite state automatons, the nondeterministic finite state automatons being distributed in space; and
a top-level pipeline comprising a decoder adapted to decode data types of data input to the array, and a multiplexer to multiplex data types of data output from the array;
wherein the array is configured with dedicated data transfer channels between the finite-state-transducers to transfer specific data types.

14. A computer-implemented method for generating a cascaded finite-state-transducer implementation, comprising:
compiling a grammar file containing specification of cascading grammar analytics to a hardware description file containing a hardware description of finite-state-transducer circuitry to implement a plurality of scanners using the cascading grammar analytics;
generating, for each finite-state-transducer, a hardware description of a cascade of finite-state-transducers based on data dependencies within each scanner; and
generating, for each finite-state-transducer, a hardware description of a cascade of scanners based on data dependencies across the plurality of scanners.

15. The method of claim 14 , wherein the grammar file is compiled by:
intercepting intermediate data structures in the grammar file to determine nondeterministic finite state automaton representations of the plurality of finite-state-transducers;
reducing complexity of nondeterministic finite state automaton representations; and
generating a hardware description of finite-state-transducer circuitry based on the reduced nondeterministic finite state automaton representations.

16. The method of claim 15 , wherein the hardware description of the cascade of finite-state-transducers based on data dependencies within each scanner is generated by:
constructing a data-flow-graph representation of each scanner, wherein nodes of the data-flow-graph representation represent finite-state-transducers of the scanner and the edges represent the data types transferred between the finite-state-transducers of the scanner; and
generating the hardware description based on the data-flow-graph representations.

17. The method of claim 15 , wherein the hardware description of the cascade of finite-state-transducers across the plurality of scanners is generated by:
constructing a data-flow-graph representation of each scanner, wherein nodes of the data-flow-graph representation represent the scanners and the edges represent the data types transferred between the scanners; and
generating the hardware description based on the data-flow-graph representations.

Assignees

• IBM

Inventors

• Atasu Kubilay
• Nakayama Akihiro
• Polig Raphael
• Xu Tong

Classifications

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• G06F40/30 Primary

  Semantic analysis · CPC title

• G06F17/2785

  Physics · mapped topic

• G06K9/00442

  Physics · mapped topic

• G06K9/00986 Primary

  Physics · mapped topic