THREE-DIMENSIONAL CHIP-BASED REGULAR EXPRESSION SCANNER

• US 20170061304A1
• Filed: 09/01/2015
• Published: 03/02/2017
• Est. Priority Date: 09/01/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Coghlan, James, Joseph, Douglas J., Van Lunteren, Jan
• Granted Patent: US 10,740,116 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/343 Logical level
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347
• CPC Class Codes: G06F 9/4498 Finite state machines

Abstract

A method for performing enhanced pattern scanning includes the steps of: providing a three-dimensional memory structure including multiple physical memory elements; compiling multiple programmable finite state machines, each of the programmable finite state machines representing at least one deterministic finite automation data structure, the data structure being distributed over at least a subset of the physical memory elements; configuring a subset of the programmable finite state machines to operate in parallel on a same input data stream, while each of the subset of programmable finite state machines processes a different pattern subset; and providing a local result processor, the local result processor transferring at least a part of a match state from the deterministic finite automation data structures to corresponding registers within the local result processor, the part of the match state being manipulated being based on instructions embedded within the deterministic finite automation data structures.

Claims

1. A method for performing enhanced pattern scanning, comprising:

providing a three-dimensional memory structure including a plurality of physical memory elements;

compiling a plurality of programmable finite state machines, each of the programmable finite state machines representing at least one deterministic finite automation data structure, the data structure being distributed over at least a subset of said plurality of physical memory elements;

configuring a subset of the programmable finite state machines to operate in parallel on a same input data stream, while each of said subset of programmable finite state machines processes a different pattern subset; and

providing a local result processor, the local result processor transferring at least a part of a match state from said deterministic finite automation data structures to corresponding registers within said local result processor, said part of the match state being manipulated based on instructions embedded within the deterministic finite automation data structures.

2. The method of claim 1, wherein said plurality of physical memory elements are interconnected together using through-silicon vias.

3. The method of claim 1, wherein said compiling the plurality of programmable finite state machines comprises compiling said at least one deterministic finite automation data structure with integrated instructions that are distributed over dedicated static random-access memory in a field-programmable gate array logic layer and over a plurality of embedded dynamic random-access memory clusters in corresponding embedded dynamic random-access memory array layers which are interconnected by said through-silicon vias to form a corresponding embedded dynamic random-access memory cluster column.

4. The method of claim 1, further comprising implementing said local result processor in a distributed manner using smaller processing elements that are integrated into said memory structure, each of at least a subset of the smaller processing elements being configured for executing local result processor instructions dispatched by said plurality of programmable finite state machines.

5. The method of claim 4, further comprising configuring said local result processor such that each of at least a subset of the smaller processing elements operates on local result processor data vectors corresponding to a different active data stream.

6. The method of claim 4, further comprising:

providing an instruction dispatcher module;

encoding local result processor instructions integrated into said deterministic finite automation data structures to an available instruction vector width and supported subset of instructions corresponding to the smaller processing elements; and

recoding, by said instruction dispatcher module, instruction vectors processed by said local result processor so that the instruction vectors are adapted to fit a transfer data unit over said through-silicon vias to the distributed smaller processing elements.

7. The method of claim 1, further comprising configuring each of said plurality of programmable finite state machines to operate independently of one another on said same input data stream.

8. The method of claim 1, further comprising:

providing at least one input buffer configured to store data received from a corresponding input data stream;

providing a plurality of read pointers to the at least one input buffer and controlling each of the read pointers by a corresponding one of the plurality of programmable finite state machines operating on said same input data stream, such that each of said plurality of programmable finite state machines operate independently of one another on said same input data stream.

9. The method of claim 1, further comprising synchronizing at least two instructions dispatched by separate corresponding programmable finite state machines operating on said same local result processor data so that instructions are dispatched and executed by the programmable finite state machines in a same order as defined by offset tags corresponding to input values for which said instructions were dispatched.

10. The method of claim 1, further comprising supporting a plurality of active scan sessions processed on different input data streams in an interleaved fashion by storing and retrieving a session state corresponding to each of said plurality of active scan sessions on different input data streams, said session state being stored in a corresponding one of the plurality of physical memory elements.

11. The method of claim 10, wherein said storing and retrieving session states corresponding to the plurality of active scan sessions comprises:

allowing a subset of the programmable finite state machines in a given active scan session to proceed to a prescribed position in a corresponding input data stream which said subset of the programmable finite state machines are processing, thereby ensuring that read pointers corresponding to the subset of the programmable finite state machines have a same value; and

storing and retrieving said value for the read pointers as part of the session state for the given active scan session.

12. A pattern scanning apparatus, comprising:

a three-dimensional memory structure including a plurality of physical memory elements;

a plurality of programmable finite state machines, each of the programmable finite state machines being adapted to receive an input data stream and representing at least one deterministic finite automation data structure, the data structure being distributed across at least a subset of said plurality of physical memory elements;

at least one local result processor, the local result processor comprising a plurality of processing units distributed across at least the subset of said plurality of physical memory elements, the local result processor being configured to transfer at least a part of a match state from said deterministic finite automation data structures to corresponding registers within said local result processor, said part of the match state being manipulated based on instructions embedded within the deterministic finite automation data structures; and

a match report function module configured to generate a match output, the match output identifying a prescribed pattern in the input data stream detected as a function of state information obtained from the plurality of programmable finite state machines.

13. The apparatus of claim 12, wherein said plurality of physical memory elements are interconnected together using through-silicon vias.

14. The apparatus of claim 12, wherein the three-dimensional memory structure is configured having a plurality of memory array layers, each memory array layer comprising a two-dimensional array of memory clusters, with each memory cluster including at least one memory block and a cluster controller, the three-dimensional memory structure being configured such that memory clusters covering at least a subset of said memory array layers are vertically linked together by through-silicon vias to form corresponding cluster columns.

15. The apparatus of claim 12, further comprising an instruction dispatcher module operatively coupled with the three-dimensional memory structure and said plurality of programmable finite state machines, the instruction dispatcher module being configured to receive instructions from at least a subset of the programmable finite state machines and to forward said instructions to the three-dimensional memory structure using prescribed types of memory accesses.

16. The apparatus of claim 15, wherein the instruction dispatcher module comprises a recoding module, the recoding module being configured to encode local result processor instruction vectors attached to transitions in said plurality of programmable finite state machines, to thereby efficiently fit available instruction vector widths in a corresponding data structure, and to recode said instruction vectors into a format that fits a transfer size and execution of the instruction vectors over said through-silicon vias.

17. The apparatus of claim 12, wherein the apparatus is configured to associate an offset tag with each of at least a subset of local result processor instructions dispatched by the programmable finite state machines, said offset tag indicating a position of a current input byte within the input data stream, the apparatus further comprising a synchronization module configured to synchronize at least two instructions dispatched by separate corresponding programmable finite state machines operating on same local result processor data so that instructions are dispatched and executed by the programmable finite state machines in a same order as defined by an offset tag corresponding to said instructions being synchronized.

18. The apparatus of claim 12, further comprising at least one controller operatively coupled with said three-dimensional memory structure, the controller being configured to support a plurality of active scan sessions processed on different input data streams in an interleaved fashion by storing and retrieving a session state corresponding to each of said plurality of active scan sessions on different input data streams, said session state being stored in a corresponding one of the plurality of physical memory elements.

19. The apparatus of claim 18, wherein said session state comprises at least one of a state of each of the plurality of programmable finite state machines utilized in a given scan operation, a read pointer associated with each of the plurality of programmable finite state machines, and a local result processor data vector corresponding to a given scan session, the data vector including a pointer in an instruction dispatcher module configured to direct instructions to a prescribed memory controller associated with a corresponding one of the physical memory elements.

20. A pattern scanning apparatus, comprising:

a three-dimensional memory structure including a plurality of physical memory elements interconnected together using through-silicon vias; and

at least one processor coupled with the memory structure, the at least one processor being configured;

to compile a plurality of programmable finite state machines, each of the programmable finite state machines representing at least one deterministic finite automation data structure, the data structure being distributed over at least a subset of said plurality of physical memory elements;

to configure a subset of the programmable finite state machines to operate in parallel on a same input data stream, while each of said subset of programmable finite state machines processes a different pattern subset; and

to transfer at least a part of a match state from said deterministic finite automation data structures to corresponding registers within said processor, said part of the match state being manipulated based on instructions embedded within the deterministic finite automation data structures.