Parallelizing applications of script-driven tools

• US 7,047,232 B1
• Filed: 01/13/1999
• Issued: 05/16/2006
• Est. Priority Date: 01/13/1999
• Status: Expired due to Term

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Software Corporation
• Inventors: Serrano, Martin
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/229,849
• Time in Patent Office: 2,680 Days
• Field of Search: 707 3- 5, 707100-1041, 707 1- 10, 707200-206, 717144-157, 717/100, 717/125, 717/160, 717/115, 717/168, 717/119, 715/514, 715/900, 709/100, 709/217, 709/218, 709/219
• US Class Current: 1/1
• CPC Class Codes: G06F 8/456 Parallelism detection
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for parallelizing applications of script-driven software tools. Scripts in the software tool scripting language are automatically analyzed in order to produce a specification for a parallel computation plus a set of “script fragments”, the combination of which is functionally equivalent to the original script. The computational specification plus the script fragments are then executed by a parallel runtime system, which causes multiple instances of the original software tool and/or supplemental programs to be run as parallel processes. The resulting processes will read input data and produce output data, performing the same computation as was specified by the original script. The combination of the analyzer, runtime system, original software tool, and supplemental programs will, for a given script and input data, produce the same output data as the original software tool alone, but has the capability of using multiple processors in parallel for substantial improvements in overall “throughput”. The invention includes computer program embodiments of an automatic script analyzer.

Claims

1. A method for parallelizing a computer application program based on a script of a script-driven software tool, comprising automatically analyzing the script and producing a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements comprising at least processing steps and dataset definitions;

(b) constructing a serial dataflow graph from the parsed statements, the serial dataflow graph having nodes connected by directed edges, the nodes representing datasets, processing steps, and intermediate results; and

(c) constructing a parallel dataflow graph from the nodes of the serial dataflow graph such that the parallel dataflow graph may be executed by a parallel runtime system.

3. The method of claims 1 or 2, wherein constructing the serial dataflow graph includes:

(a) constructing a serial dataset table of datasets used by the script;

(b) constructing a serial processing step table of statements performed by the script; and

(c) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table.

4. The method of claim 3, wherein constructing the parallel dataflow graph includes:

(a) constructing a parallel dataset table of datasets based on the serial dataset table;

(b) constructing a parallel processing step table of statements based on the serial processing step table;

(c) constructing a dataset access table based on the serial dataset access table; and

(d) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries.

5. The method of claim 4, further including resolving any existing partitioning conflicts in the constructed parallel dataflow graph.

6. The method of claim 4, wherein at least one pre-defined parallelization rewrite rule is an algorithm selected from the group comprising simple partitioning, key-based partitioning, local-global division, external parallelism algorithm, and statement decomposition.

7. The method of claims 1 or 2, wherein the script-driven software tool is SAS®

.

8. The method of claims 1 or 2, wherein producing the parallel computation specification includes applying at least one pre-defined parallelization rewrite algorithm selected from the group comprising simple partitioning, key-based partitioning, local-global division, external parallelism algorithm, and statement decomposition.

2. A method for parallelizing a computer application program based on a script of a script-driven software tool, comprising automatically analyzing the script and producing a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements comprising at least processing steps and dataset definitions;

(b) constructing a serial dataflow graph from the parsed statements, the serial dataflow graph having nodes connected by directed edges, the nodes representing datasets, processing steps, and intermediate results;

(c) constructing a parallel dataflow graph from the nodes of the serial dataflow graph such that the parallel dataflow graph may be executed by a parallel runtime system; and

(d) analyzing the parallel dataflow graph to generate script fragments in a form that enables the script-driven software tool to execute some of the processing steps.

9. A computer program, residing on a computer-readable medium, for parallelizing a computer application program based on a script of a script-driven software tool, the computer program comprising instructions for causing a computer to automatically analyze the script and produce a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements comprising at least processing steps and dataset definitions;

(b) constructing a serial dataflow graph from the parsed statements, the serial dataflow graph having nodes connected by directed edges, the nodes representing datasets, processing steps, and intermediate results; and

(c) constructing a parallel dataflow graph from the nodes of the serial dataflow graph such that the parallel dataflow graph may be executed by a parallel runtime system.

10. A computer program, residing on a computer-readable medium, for parallelizing a computer application program based on a script of a script-driven software tool, the computer program comprising instructions for causing a computer to automatically analyze the script and produce a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements comprising at least processing steps and dataset definitions;

(b) constructing a serial dataflow graph from the parsed statements, the serial dataflow graph having nodes connected by directed edges, the nodes representing datasets, processing steps, and intermediate results;

(c) constructing a parallel dataflow graph from the nodes of the serial dataflow graph such that the parallel dataflow graph may be executed by a parallel runtime system; and

(d) analyzing the parallel dataflow graph to generate script fragments in a form that enables the script-driven software tool to execute some of the processing steps.

11. The computer program of claims 9 or 10, wherein constructing the serial dataflow graph includes:

(a) constructing a serial dataset table of datasets used by the script;

(b) constructing a serial processing step table of statements performed by the script; and

(c) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table.

12. The computer program of claim 11, wherein constructing the parallel dataflow graph includes:

(a) constructing a parallel dataset table of datasets based on the serial dataset table;

(b) constructing a parallel processing step table of statements based on the serial processing step table;

(c) constructing a dataset access table based on the serial dataset access table; and

(d) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries.

13. The computer program of claim 12, further including resolving any existing partitioning conflicts in the constructed parallel dataflow graph.

14. The computer program of claim 12, wherein at least one pre-defined parallelization rewrite rule is an algorithm selected from the group comprising simple partitioning, key-based partitioning, local-global division, external parallelism algorithm, and statement decomposition.

15. The computer program of claims 9 or 10, wherein the script-driven software tool is SAS®

.

16. The computer program of claims 9 or 10, wherein producing the parallel computation specification includes applying at least one pre-defined parallelization rewrite algorithm selected from the group comprising simple partitioning, key-based partitioning, local-global division, external parallelism algorithm, and statement decomposition.

17. A system for parallelizing a computer application program based on a script of a script-driven software tool, and for automatically analyzing the script and producing a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, including:

(a) means for parsing the script into statements comprising at least processing steps and dataset definitions;

(b) means for constructing a serial dataflow graph from the parsed statements, the serial dataflow graph having nodes connected by directed edges, the nodes representing datasets, processing steps, and intermediate results; and

(c) means for constructing a parallel dataflow graph from the nodes of the serial dataflow graph such that the parallel dataflow graph may be executed by a parallel runtime system.

19. The system of claims 17 or 18, wherein the means for constructing the serial dataflow graph includes means for:

(a) constructing a serial dataset table of datasets used by the script;

(b) constructing a serial processing step table of statements performed by the script; and

(c) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table.

20. The system of claim 19, wherein the means for constructing the parallel dataflow graph includes means for:

(a) constructing a parallel dataset table of datasets based on the serial dataset table;

(b) constructing a parallel processing step table of statements based on the serial processing step table;

(c) constructing a dataset access table based on the serial dataset access table; and

(d) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries.

21. The system of claim 20, further including means for resolving any existing partitioning conflicts in the constructed parallel dataflow graph.

22. The system of claim 20, wherein at least one pre-defined parallelization rewrite rule is an algorithm selected from the group comprising simple partitioning, key-based partitioning, local-global division, external parallelism algorithm, and statement decomposition.

23. The system of claims 17 or 18, wherein the script-driven software tool is SAS®

.

24. The system of claims 17 or 18, wherein the means for producing the parallel computation specification includes means for applying at least one pre-defined parallelization rewrite algorithm selected from the group comprising simple partitioning, key-based partitioning, local-global division, external parallelism algorithm, and statement decomposition.

18. A system for parallelizing a computer application program based on a script of a script-driven software tool, and for automatically analyzing the script and producing a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, including:

(a) means for parsing the script into statements comprising at least processing steps and dataset definitions;

(b) means for constructing a serial dataflow graph from the parsed statements, the serial dataflow graph having nodes connected by directed edges, the nodes representing datasets, processing steps, and intermediate results;

(c) means for constructing a parallel dataflow graph from the nodes of the serial dataflow graph such that the parallel dataflow graph may be executed by a parallel runtime system; and

(d) means for analyzing the parallel dataflow graph to generate script fragments in a form that enables the script-driven software tool to execute some of the processing steps.

25. A method for parallelizing a computer application program based on a script of a script-driven software tool, comprising automatically analyzing the script and producing a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements;

(b) constructing a serial dataflow graph from the parsed statements, said constructing including

(i) constructing a serial dataset table of datasets used by the script,

(ii) constructing a serial processing step table of statements performed by the script, and

(iii) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table; and

(c) constructing a parallel dataflow graph from the serial dataflow graph.

26. A method for parallelizing a computer application program based on a script of a script-driven software tool, comprising automatically analyzing the script and producing a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements;

(b) constructing a serial dataflow graph from the parsed statements, said constructing including

(i) constructing a serial dataset table of datasets used by the script;

(ii) constructing a serial processing step table of statements performed by the script; and

(iii) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table; and

(c) constructing a parallel dataflow graph from the serial dataflow graph.

27. A method for parallelizing a computer application program based on a script of a script-driven software tool, comprising automatically analyzing the script and producing a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements;

(b) constructing a serial dataflow graph from the parsed statements, said constructing including

(i) constructing a parallel dataset table of datasets based on the serial dataset table;

(ii) constructing a parallel processing step table of statements based on the serial processing step table;

(iii) constructing a dataset access table based on the serial dataset access table; and

(iv) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries; and

(c) constructing a parallel dataflow graph from the serial dataflow graph.

28. A method for parallelizing a computer application program based on a script of a script-driven software tool, comprising automatically analyzing the script and producing a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements;

(b) constructing a serial dataflow graph from the parsed statements, said instructing including

(i) constructing a parallel dataset table of datasets based on the serial dataset table;

(ii) constructing a parallel processing step table of statements based on the serial processing step table;

(iii) constructing a dataset access table based on the serial dataset access table; and

(iv) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries; and

(c) constructing a parallel dataflow graph from the serial dataflow graph.

29. A computer program, residing on a computer-readable medium, for parallelizing a computer application program based on a script of a script-driven software tool, the computer program comprising instructions for causing a computer to automatically analyze the script and produce a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements;

(b) constructing a serial dataflow graph from the parsed statements, said constructing including

(i) constructing a serial dataset table of datasets used by the script;

(ii) constructing a serial processing step table of statements performed by the script; and

(iii) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table; and

(c) constructing a parallel dataflow graph from the serial dataflow graph.

30. A computer program, residing on a computer-readable medium, for parallelizing a computer application program based on a script of a script-driven software tool, the computer program comprising instructions for causing a computer to automatically analyze the script and produce a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements;

(b) constructing a serial dataflow graph from the parsed statements, said constructing including

(i) constructing a serial dataset table of datasets used by the script;

(ii) constructing a serial processing step table of statements performed by the script; and

(iii) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table; and

(c) constructing a parallel dataflow graph from the serial dataflow graph.

31. A computer program, residing on a computer-readable medium, for parallelizing a computer application program based on a script of a script-driven software tool, the computer program comprising instructions for causing a computer to automatically analyze the script and produce a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements;

(b) constructing a serial dataflow graph from the parsed statements, said constructing including

(i) constructing a parallel dataset table of datasets based on the serial dataset table;

(ii) constructing a parallel processing step table of statements based on the serial processing step table;

(iii) constructing a dataset access table based on the serial dataset access table; and

(iv) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries; and

(c) constructing a parallel dataflow graph from the serial dataflow graph.

32. A computer program, residing on a computer-readable medium, for parallelizing a computer application program based on a script of a script-driven software tool, the computer program comprising instructions for causing a computer to automatically analyze the script and produce a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, by:

(a) parsing the script into statements;

(b) constructing a serial dataflow graph from the parsed statements, said constructing including

(i) constructing a parallel dataset table of datasets based on the serial dataset table;

(ii) constructing a parallel processing step table of statements based on the serial processing step table;

(iii) constructing a dataset access table based on the serial dataset access table; and

(iv) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries; and

(c) constructing a parallel dataflow graph from the serial dataflow graph.

33. A system for parallelizing a computer application program based on a script of a script-driven software tool, comprising means and for automatically analyzing the script and means for producing a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, including:

(a) means for parsing the script into statements;

(b) means for constructing a serial dataflow graph from the parsed statements, said means including means for

(i) constructing a serial dataset table of datasets used by the script;

(ii) constructing a serial processing step table of statements performed by the script; and

(iii) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table; and

(c) means for constructing a parallel dataflow graph from the serial dataflow graph.

34. A system for parallelizing a computer application program based on a script of a script-driven software tool, comprising means and for automatically analyzing the script and means for producing a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, including:

(a) means for parsing the script into statements;

(b) means for constructing a serial dataflow graph from the parsed statements, said means including means for

(i) constructing a serial dataset table of datasets used by the script;

(ii) constructing a serial processing step table of statements performed by the script; and

(ii) constructing a serial dataset access table indicating datasets in the dataset table used by statements in the processing step table; and

(c) means for constructing a parallel dataflow graph from the serial dataflow graph.

35. A system for parallelizing a computer application program based on a script of a script-driven software tool, comprising means and for automatically analyzing the script and means for producing a parallel computation specification based on such analysis, where such parallel computation specification provides functional equivalence to the script when executed by a parallel runtime system, including:

(a) means for parsing the script into statements;

(b) means for constructing a serial dataflow graph from the parsed statements, said means including means for

(i) constructing a parallel dataset table of datasets based on the serial dataset table;

(ii) constructing a parallel processing step table of statements based on the serial processing step table;

(iii) constructing a dataset access table based on the serial dataset access table; and

(iv) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries; and

(c) means for constructing a parallel dataflow graph from the serial dataflow graph.

36. A system for parallelizing a computer application program based on a script of a script-driven software tool, comprising means and for automatically analyzing the script and means for producing a parallel computation specification plus a script fragment set based on such analysis, where such parallel computation specification and script fragment set provides functional equivalence to the script when executed by a parallel runtime system, including:

(a) means for parsing the script into statements;

(b) means for constructing a serial dataflow graph from the parsed statements, said means including means for

(i) constructing a parallel dataset table of datasets based on the serial dataset table;

(ii) constructing a parallel processing step table of statements based on the serial processing step table;

(iii) constructing a dataset access table based on the serial dataset access table; and

(iv) determining, for each processing step identified in the parallel processing step table, if a corresponding pre-defined parallelization rewrite rule exists for such processing step, and if so, then applying the corresponding pre-defined parallelization rewrite rule to redefine associated entries in the parallel dataset table, the parallel processing step table, and the dataset access table as parallel processing entries; and

if not, then defining such associated entries as serial processing entries; and

(c) means for constructing a parallel dataflow graph from the serial dataflow graph.