Method and apparatus for parallel XSL transformation with low contention and load balancing

• US 20090007115A1
• Filed: 06/26/2007
• Published: 01/01/2009
• Est. Priority Date: 06/26/2007
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kalekin, Udi, Cahoon, Brendon, Tsoi, Howard P., Zhang, Qi, Sun, Yuanhao, Li, Tianyou
• Application Number:
  US11/819,217
• Publication Number:
  US 20090007115A1
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 40/131 Fragmentation of text files, e.g. creating reusable text-blocks; Linking to fragments, e.g. using XInclude; Namespaces
• 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 8/456 Parallelism detection
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method for parallel transformation of an XML document by a plurality of execution modules and the serialization of output according to semantic order of the XML document.

Claims

1. A method comprising:

producing an executable code such that said code when executed transforms instructions in an Extensible Stylesheet Language (XSL) document into tasks and executes said tasks;

executing concurrently by a plurality of execution modules said executable code, wherein an XML document is provided as input, and wherein each execution module executes said executable code; and

producing one or more output documents from outputs of said execution modules.

2. The method of claim 1, wherein said execution modules are threads of execution.

3. The method of claim 1, wherein said execution modules are hardware modules.

4. The method of claim 1, wherein producing said executable code comprises:

locating xsl;

for-each and xsl;

apply-templates instructions in said XSL document, and

producing said executable code such that said code when executed transforms each of said located xsl;

for-each and xsl;

apply-templates instructions into a plurality of tasks.

5. The method of claim 1, wherein producing said executable code comprises:

locating autonomous instructions in said XSL document, and

producing said executable code such that said code when executed transforms said located autonomous instructions into one or more tasks.

6. The method of claim 1, wherein at least some of said tasks when executed create additional tasks.

7. The method of claim 1, wherein said plurality of execution modules comprise:

a first execution module to place tasks in a first stack, and to further retrieve for execution a task from a top of said first stack; and

a second execution module to retrieve tasks from a bottom of said first stack, to place said retrieved tasks in a second stack, and to retrieve for execution a task from a top of said second stack.

8. The method of claim 7, wherein said execution modules distribute execution of said tasks among said execution modules based on at least one load balancing parameter.

9. The method of claim 7, wherein said first and second execution modules direct execution output to respective first and second output objects, wherein second output objects produced based on tasks retrieved from said first stack are linked to first output objects, and wherein producing said output document comprises collecting output from said first and second output objects according to said linking.

10. An article of manufacture for use in a computer system, the article of manufacture comprising a computer usable medium having computer readable program code means embodied in the medium, the program code including computer readable program code that when executed causes a computer to:

produce an executable code such that said code when executed transforms instructions in an Extensible Stylesheet Language (XSL) document into tasks and executes said tasks;

execute simultaneously by a plurality of execution modules said executable code, wherein an XML document is provided as input, and wherein each execution module executes said executable code; and

produce an output document from outputs of said execution modules.

11. The article of claim 10, wherein the computer readable program code when executed causes a computer to produce said executable code by:

locating xsl;

for-each and xsl;

apply-templates instructions in said XSL document, and

producing said executable code such that said code when executed transforms each of said located xsl;

for-each and xsl;

apply-templates instructions into a plurality of tasks.

12. The article of claim 10, wherein the computer readable program code when executed causes a computer to produce said executable code by:

locating autonomous instructions in said XSL document, and

producing said executable code such that said code when executed transforms said located autonomous instructions into one or more tasks.

13. The article of claim 10, wherein at least some of said tasks when executed create additional tasks.

14. The article of claim 10 wherein said plurality of execution modules comprise:

a first execution module to place tasks in a first stack, and to further retrieve for execution a task from a top of said first stack; and

a second execution module to retrieve tasks from a bottom of said first stack, to place said retrieved tasks in a second stack, and to retrieve for execution a task from a top of said second stack.

15. The article of claim 14, wherein said first and second execution modules direct execution output to respective first and second output objects, wherein second output objects produced based on tasks retrieved from said first stack are linked to first output objects, and wherein producing said output document comprises collecting output from said first and second output objects according to said linking.