Transformation module for transforming documents from one format to other formats with pipelined processor having dedicated hardware resources

• US 7,925,971 B2
• Filed: 10/25/2006
• Issued: 04/12/2011
• Est. Priority Date: 10/31/2005
• Status: Active Grant

• Current Assignee: Solace Corp.
• Original Assignee: Solace Systems, Inc. (United Kingdom)
• Inventors: Brodeur, Patrick, Babkine, Philippe-Andre, Horton, David W., Funnekotter, Edward D., Kondrat, Paul, Whelan, Jason, Cadieux, Stephen, Bosloy, Jonathan
• Primary Examiner(s): Hong; Stephen S
• Assistant Examiner(s): SCOTT, MICHAEL E
• Application Number:
  US11/552,849
• Publication Number:
  US 20070100920A1
• Time in Patent Office: 1,630 Days
• Field of Search: 715/234, 715/235, 715/236, 715/239, 715/249
• US Class Current: 715/236
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/149 Adaptation of the text data for streaming purposes, e.g. Efficient XML Interchange [EXI] format
• CPC Class Codes: G06F 40/151 Transformation
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A method and apparatus for converting documents from one format to another in a speed efficient way involves a hardware module which implements several operating pipeline stages which work in parallel. The transformations are supplied and decomposed into sequences of control units. The transformation of documents consists of applying control unit sequences to input documents. The control units are themselves executed by a set of dedicated hardware resources. Furthermore the pipeline is capable of operating on more than one document at a time. Fast document transformation is a key capability of document processing systems. The use of parallel processing techniques and hardware that implements highly specialized transformation resources make this invention particularly scalable for its use in large, high speed content networks.

Claims

1. A transformation module for transforming XML documents from one format to one or more other formats according to one or many transformation functions, the transformation module comprising:

a stylesheet translation tool for pre-processing XSLT stylesheets that describe how a given transformation is performed on a document, said stylesheet translation tool decomposing said stylesheets into an accelerator specific language consisting of static data structures comprising a set of control units that are atomic transformation operations that can be directly performed on the documents, a constant string table containing string constants for the stylesheets, and a template match information table used to compute which XSLT template to apply to a document at any a given time;

a memory storing said XSLT stylesheets decomposed into said static data structures;

a document node memory storing tree data structures that represent nodes of the XML documents;

a document string memory storing string values associated with the nodes of the documents stored in the document node memory, wherein the document node memory stores references that point to memory locations in the document node memory; and

a processor with a plurality of pipelined stages for executing the control units as atomic operations on a plurality of dedicated hardware resources, said processor being capable of executing several transformations in parallel; and

wherein said processor comprises an XPath scheduling unit executing control units derived from Xpath expressions in said stylesheets and an XSLT scheduling unit executing control units derived from a remaining portion of said stylesheets, and said XSLT scheduling unit comprises a template matching dedicated hardware resource for performing template matching operations, a node set and variable dedicated hardware resource for accessing elements of a node set, where a node set is a list of a document'"'"'s constituents, and an output generation dedicated hardware resource for building constituents of an output document, and said Xpath scheduling unit comprises a tree walker dedicated hardware resource for perforating searches on the documents, a string operation dedicated hardware resource for providing string manipulation operations, a math operation dedicated hardware resource of providing various math functions, and a node set dedicated hardware resource for building node sets.

2. A transformation module as claimed in claim 1, wherein the documents are transferred to the pipelined processor as DMA fragments.

3. A transformation module as claimed in claim 1, wherein the pipelined stages comprise in sequence:

an interface stage for handling the physical transfer of the documents from a host;

a reassembly stage for transforming document segments into a document stream consisting of a stream of bytes;

a parser block for ensuring that Ore-input documents are formed according to predetermined criteria;

a document storage block for building an internal representation of the input documents, said document storage block comprising said document node memory and said document string memory;

an execution stage for dispatching commands obtained from the said memory storing XSLT stylesheets to said respective hardware resources of said processor;

an output generation block for issuing output documents based on the commands received from the previous stages; and

an output interface for transforming an interleaved stream of documents into DMA fragments for transfer to a host.

4. A transformation module as claimed in claim 3, wherein said control units are made up of three fields, namely a function field specifying what transformation function should be executed, a data field specifying the data which the control unit should operate on, and a result field that specifies what should be done with the result returned from said transformation function.

5. A transformation module as claimed in claim 4, wherein the documents are issued by the output interface in one of several encodings as specified by the set of allowable transformations.

6. A transformation module as claimed in claim 3, wherein the XPath scheduling unit is a resource of the XSLT scheduling unit and is used to schedule an XPath subset of operations of the XSLT language.

7. A transformation module as claimed in claim 1, which is configured such that stylesheets can be added and removed from memory while the processor is performing its transformation functions without interrupting the operation thereof.

8. A transformation module as claimed in claim 7, wherein the processor further comprises:

a module for transforming the input stylesheets into a set of control unit symbols, memory location symbols, variable symbols and constant symbols;

an assembly stage for accepting the output of a transformation tool and resolving the control unit symbols into their binary representation as understood by the XSLT and XPath scheduling units and their resources; and

a loader stage which takes the output of the assembly stage and resolves references to symbols for the memory location, the variable symbols and constant symbols into references to absolute memory addresses.

9. A transformation module as claimed in claim 8, wherein the loader stage is configured to optimize the use of elements of one or more transformations by enabling different transformations to share common elements.

10. A content router, comprising:

a routing module for routing incoming XML documents based on their content; and

a transformation module for transforming the documents from one format to one or more other formats according to one or many transformation functions, said transformation module comprising;

a stylesheet translation tool for pre-processing XSLT stylesheets that describe how a given transformation is performed on a document, said stylesheet translation tool decomposing said stylesheets into an accelerator specific language consisting of into static data structures comprising a set of control units that are atomic transformation operations that can be directly performed on the documents, a constant string table containing string constants for the stylesheets, and a template match information table used to compute which XSLT template to apply to a document at any a given time

a memory storing said XSLT stylesheets decomposed into said static data structures;

a document node memory storing tree data structures that represent nodes of the XML documents;

a document string memory storing string values associated with the nodes of the documents stored in the document node memory, wherein the document node memory stores references that point to memory locations in the document node memory;

a processor with a plurality of pipelined stages for executing the control units as atomic operations on a plurality of dedicated hardware resources said processor being capable of executing several transformations in parallel;

wherein said processor comprises an XPath scheduling unit executing control units derived from Xpath expressions in said stylesheets and an XSLT scheduling unit executing control units derived from a remaining portion of said stylesheets, and said XSLT scheduling unit comprises a template matching dedicated hardware resource for performing template matching operations, a node set and variable dedicated hardware resource for accessing elements of a node set, where a node set is a list of a document'"'"'s constituents, and an output generation dedicated hardware resource for building constituents of an output document, and said Xpath scheduling unit comprises a tree walker dedicated hardware resource for perforating searches on the documents, a string operation dedicated hardware resource for providing string manipulation operations, a math operation dedicated hardware resource of providing various math functions, and a node set dedicated hardware resource for building node sets; and

a bus for transferring documents from the routing module to the transformation module during processing by the router.

11. A content router as claimed in claim 10, wherein the pipelined stages comprise, in sequence:

an interface stage for handling the physical transfer of documents from a host through direct memory access;

a reassembly stage for transforming message segments into a document stream consisting of a stream of bytes;

a parser block for ensuring that the input documents are formed according to predetermined criteria;

a document storage block for building an internal representation of the input documents, said document storage block comprising said document node memory and said document string memory;

an execution stage for dispatching commands obtained from the said memory storing said XSLT stylesheets to said respective hardware resources;

an output generation block for issuing the output documents based on the commands received from the previous stages; and

an output interface for transforming an interleaved stream of documents into DMA fragments for transfer to the host through the direct memory access.