Reconfigurable semantic processor

• US 20040148415A1
• Filed: 01/24/2003
• Published: 07/29/2004
• Est. Priority Date: 01/24/2003
• Status: Active Grant

• Current Assignee: GigaFin Networks, Inc. (Infinity Security Solutions, Inc.)
• Original Assignee: Mistletoe Technologies, Inc.
• Inventors: Sikdar, Somsubhra
• Granted Patent: US 7,130,987 B2
• Time in Patent Office: Days
• US Class Current: 709/230
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: G06F 9/45508 Runtime interpretation or emulation, e g. emulator loops, bytecode interpretation

Abstract

Data processors and methods for their configuration and use are disclosed. As opposed to traditional von Neumann microprocessors, the disclosed processors are semantic processors—they parse an input stream and direct one or more semantic execution engines to execute code segments, depending on what is being parsed. For defined-structure input streams such as packet data streams, these semantic processors can be both economical and fast as compared to a von Neumann system. Several optional components can augment device operation. For instance, a machine context data interface relieves the semantic execution engines from managing physical memory, allows the orderly access to memory by multiple engines, and implements common access operations. Further, a simple von Neumann exception-processing unit can be attached to a semantic execution engine to execute more complicated, but infrequent or non-time-critical operations.

Claims

1. A data processing system comprising:

an input port to receive data symbols;

a direct execution parser having a stack to store stack symbols, the parser capable of processing stack symbols in response to the received data symbols;

a parser table accessible by the parser, the parser table capable of population with production rule codes indexable by the combination of at least one received data symbol and a stack symbol supplied by the parser;

a production rule table accessible by the parser, the production rule table capable of population with production rules indexable by production rule codes;

a first semantic code execution engine capable of executing machine instructions when prompted by the direct execution parser, using machine instruction segments indicated by the parser; and

a semantic code table accessible by the semantic code execution engine, the semantic code table capable of population with machine instruction segments indexable by production rule codes.

2. The system of claim 1, further comprising a second semantic code execution engine capable of executing machine instructions when prompted by the direct execution parser, using machine instructions indicated by the parser, the first and second semantic code execution engines capable of parallel machine instruction execution.

3. The system of claim 2, further comprising an exception processing unit having a microprocessor and associated memory, the exception processing unit capable of performing tasks at the request of at least one of the semantic code execution engines.

4. The system of claim 2, further comprising a block input/output port connected to at least one of the semantic code execution engines, the block input/output port capable of initiating block input/output operations under control of the at least one semantic code execution engine.

5. The system of claim 2, wherein a production rule code allows the direct execution parser to determine whether a corresponding segment of semantic code table machine instructions can be directed to any available semantic code execution engine, or whether that segment should be directed to a specific semantic code execution engine.

6. The system of claim 1, further comprising an interface between the direct execution parser and the semantic code execution engine, the interface having the capability to suspend stack symbol processing by the direct execution parser when directed by the semantic code execution engine.

7. The system of claim 1, wherein the parser table, production rule table, and semantic code table at least partially reside in reprogrammable storage.

8. The system of claim 7, wherein the system processes data packets, each data packet formatted according to one or more network protocols, the parser table, production rule table, and semantic code table reprogrammable to support parsing for different network protocols.

9. The system of claim 8, wherein the system can load parser table reprogrammable storage with a network protocol while the system is processing data packets.

10. The system of claim 1, further comprising a machine context data interface connected to a data storage area and accessible by the semantic code execution engine, the machine context data interface managing the data storage area and performing data operations in response to machine context instructions issued by the semantic code execution engine.

11. The system of claim 10, the machine context data interface comprising a variable machine context data interface and an array machine context data interface, the array machine context data interface capable of managing and performing data operations on array data.

12. The system of claim 11, wherein the array machine context data interface accesses at least one data storage area with a data access format different from that of the data storage area accessed by the variable machine context data interface.

13. The system of claim 1, wherein at least the direct execution parser, the parser table, and the production rule table are implemented using software to configure a microprocessor and its attached memory.

14. The system of claim 1, wherein the production rule table is capable of storing bitmasked terminal symbols, each bitmasked terminal symbol capable of indicating that selected bits in a corresponding input symbol are “

don'"'"'t care”

bits.

15. The system of claim 1, wherein the direct execution parser performs a parsing method selected from the group of methods including LL parsing, LR parsing, LALR parsing, and recursive descent parsing.

16. The system of claim 1, wherein the direct execution parser is capable of parsing input symbols using a variable input symbol look-ahead that can be varied for each stack symbol.

17. The system of claim 16, wherein the variable input symbol look-ahead can be stored as a value in the production rule table along with the production rules, and wherein the direct execution parser loads the variable input symbol look-ahead when it loads a production rule into the stack.

18. The system of claim 16, wherein the parser table comprises a binary or ternary content-addressable memory (CAM) with a word size capable of storing entries corresponding to the combination of a stack symbol and up to N input symbols.

19. The system of claim 18, wherein the parser supplies N input symbols to the parser table on each access, each CAM entry determining which of the N input symbols affect the lookup for that CAM entry.

20. An integrated circuit comprising:

an input port to receive data symbols;

a direct execution parser having a stack to store stack symbols, the parser capable of processing stack symbols in response to the received data symbols;

a parser table accessible by the parser, the parser table capable of population with production rule codes indexable by the combination of a received data symbol and a stack symbol supplied by the parser;

a production rule table accessible by the parser, the production rule table capable of population with production rules indexable by production rule codes;

a first semantic code execution engine capable of executing machine instructions when prompted by the direct execution parser, using machine instruction segments indicated by the parser; and

a semantic code table accessible by the semantic code execution engine, the semantic code table capable of population with machine instruction segments indexable by production rule codes.

21. The integrated circuit of claim 20, further comprising a second semantic code execution engine capable of executing machine instructions when prompted by the direct execution parser, using machine instructions indicated by the parser, the first and second semantic code execution engines capable of parallel machine instruction execution.

22. The integrated circuit of claim 21, further comprising an exception processing unit having a microprocessor, the exception processing unit capable of performing programmable tasks at the request of at least one of the semantic code execution engines.

23. The integrated circuit of claim 21, further comprising a block input/output port connected to at least one of the semantic code execution engines, the block input/output port capable of initiating block input/output operations under control of the at least one semantic code execution engine.

24. The integrated circuit of claim 21, wherein a production rule code allows the direct execution parser to determine whether a corresponding segment of semantic code table machine instructions can be directed to any available semantic code execution engine, or whether that segment should be directed to a specific semantic code execution engine.

25. The integrated circuit of claim 20, further comprising an interface between the direct execution parser and the semantic code execution engine, the interface having the capability to suspend stack symbol processing by the direct execution parser when directed by the semantic code execution engine.

26. The integrated circuit of claim 20, wherein the parser table, production rule table and semantic code table at least partially reside in reprogrammable storage.

27. The integrated circuit of claim 26, wherein the parser table, production rule table, and semantic code table comprise caches for larger table residing in memory separate from the integrated circuit.

28. The integrated circuit of claim 20, further comprising a machine context data interface connectable to a data storage area and accessible by the semantic code execution engine, the machine context data interface managing the data storage area and performing data operations in response to machine context instructions issued by the semantic code execution engine.

29. The integrated circuit of claim 28, wherein the data storage area is at least partially integrated on the integrated circuit.

30. The integrated circuit of claim 28, the machine context data interface comprising a variable machine context data interface and an array machine context data interface, the array machine context data interface capable of managing and performing data operations on array data.

31. The integrated circuit of claim 30, wherein the array machine context data interface accesses at least one data storage area with a data access format different from that of the data storage area accessed by the variable machine context data interface.

32. An integrated circuit comprising:

an input port to receive data symbols;

a direct execution parser having a stack to store stack symbols, the parser capable of processing stack symbols in response to the received data symbols;

a parser table accessible by the parser, the parser table capable of population with production rule codes indexable by the combination of a received data symbol and a stack symbol supplied by the parser;

a production rule table accessible by the parser, the production rule table capable of population with production rules indexable by production rule codes;

multiple semantic code execution engines, each capable of executing machine instructions when prompted by the direct execution parser, using machine instruction segments indicated by the parser;

a semantic code table accessible by the semantic code execution engines, the semantic code table capable of population with machine instruction segments indexable by production rule codes; and

a machine context data interface connectable to a data storage area and accessible by the semantic code execution engines, the machine context data interface managing the data storage area and performing data operations in response to machine context instructions issued by the semantic code execution engines.

33. The integrated circuit of claim 32, further comprising:

a first bus between the semantic code execution engines and the semantic code table; and

a second bus between the semantic code execution engines and the machine context data interface.

34. The integrated circuit of claim 33, further comprising an input bus to allow the semantic code execution engines access to the data symbols.

35. The integrated circuit of claim 32, further comprising an interface between the direct execution parser and the semantic code execution engines, the interface having access to status information for each semantic code execution engine and having the capability to suspend stack symbol processing by the direct execution parser based on the status of a semantic code execution engine.

36. The integrated circuit of claim 35, wherein the status information comprises a set of semaphores corresponding to the semantic code execution engines and settable by the corresponding semantic code execution engines.

38. The integrated circuit of claim 36, further comprising at least a section of the parser table, production rule table, and semantic code table integrated on the circuit.

39. The integrated circuit of claim 36, wherein the production rule table is capable of storing bitmasked terminal symbols, each bitmasked terminal symbol capable of indicating that selected bits in a corresponding input symbol are “

don'"'"'t care”

bits.

40. The integrated circuit of claim 36, wherein the direct execution parser performs a parsing method selected from the group of methods including LL parsing, LR parsing, LALR parsing, and recursive descent parsing.

41. The integrated circuit of claim 36, wherein the direct execution parser is capable of parsing input symbols using a variable input symbol look-ahead that can be varied for each stack symbol.

42. The integrated circuit of claim 41, wherein the variable input symbol look-ahead can be stored as a value in the production rule table along with the production rules, and wherein the direct execution parser loads the variable input symbol look-ahead when it loads a production rule into the stack.

43. The integrated circuit of claim 41, wherein the parser table comprises a ternary content-addressable memory (CAM) with a word size capable of storing entries corresponding to the combination of a stack symbol and up to N input symbols.

44. The integrated circuit of claim 43, wherein the parser supplies N input symbols to the parser table on each access, each CAM entry determining which of the N input symbols affect the lookup for that CAM entry.

37. An integrated circuit comprising:

an input port to receive data symbols;

a direct execution parser comprising

a stack to store stack symbols, the parser capable of processing stack symbols in response to the received data symbols,

a parser table interface to allow the parser to access a parser table capable of population with production rule codes, each code indexable by the combination of a received data symbol and a stack symbol supplied by the parser,

a production rule table interface to allow the parser to access a production rule table capable of population with production rules, each rule indexable by production rule codes; and

a first semantic code execution engine capable of executing machine instructions when prompted by the direct execution parser, using machine instruction segments indicated by the parser; and

a semantic code table interface to allow the semantic code execution engine to access a semantic code table capable of population with machine instruction segments corresponding to production rules.

45. A method of configuring a data processor to process a datagram data input stream, the method comprising:

storing a set of production rules, for interpreting datagrams, in a production rule table, each rule comprising one or more symbols;

storing a set of semantic execution engine instructions in a semantic code table, the semantic execution engine instructions including code segments associated with at least some of the production rules; and

storing a set of production rule codes, referencing the production rules, in a parser table.

46. The method of claim 45, further comprising initializing a direct execution parser to begin parsing a datagram, according to the stored production rules, upon receipt of a start symbol in the datagram data input stream.

47. A method of operating a network processor, the method comprising:

detecting, at an input port, reception of the start of a datagram comprising multiple data symbols;

directing a direct execution parser to parse data symbols from the datagram according to a set of stored production rules; and

at least once during the parsing process, directing a semantic code execution engine to execute a code segment associated with a production rule.

48. The method of claim 47, further comprising during execution of the code segment, executing an instruction that generates a machine-context data request to an attached machine context data interface, and translating the machine context data request to at least one physical memory operation.

49. The method of claim 47, further comprising:

detecting the occurrence of datagram content that cannot be processed by a semantic code execution engine; and

directing an exception processing unit to process the datagram content.

50. The method of claim 47, wherein executing the code segment comprises directing a block input/output data operation to a block input/output port.

51. A method of implementing a network packet protocol, the method comprising:

dividing the protocol into a set of parseable grammatical production rules, each comprising at least one symbol selected from the group of terminal and non-terminal symbols, and a set of machine context tasks to be performed for at least some of the production rules by an execution engine;

assigning a non-terminal code and a production rule code to each production rule;

organizing the grammatical production rules in a machine-storable format, indexable by production rule code;

organizing the machine context tasks in an execution-engine instruction code format, indexable by the production rule code associated with the corresponding production rule; and

generating a parser table of production rule codes in machine-storable format, indexable by the combination of a non-terminal symbol and at least one symbol appearing in a packet to be parsed by the network packet protocol.

52. The method of claim 51, further comprising affixing a prefix code to the symbols in the machine-storable format production rules, the prefix code indicating whether each symbol is a terminal or non-terminal symbol.

53. The method of claim 52, the prefix code further indicating whether a terminal symbol can match any network packet protocol symbol that it is paired with.

54. The method of claim 51, further comprising, for at least one terminal symbol, assigning a bitmask to that symbol and storing the bitmask with the production rule containing that symbol.

55. The method of claim 51, further comprising setting at least some indices in the parser table based on the combination of a non-terminal symbol and multiple input symbols.

56. The method of claim 55, wherein each index in the parser table can be based on up to N input symbols in N index positions, and wherein setting at least some indices in the parser table comprises, for each indice, using between 1 and N index positions and setting the remainder of the index positions, if any, to a “

don'"'"'t care”

condition.