SYSTEMS AND METHODS FOR PARALLELIZATION OF PROGRAM CODE, INTERACTIVE DATA VISUALIZATION, AND GRAPHICALLY-AUGMENTED CODE EDITING

• US 20160291942A1
• Filed: 10/21/2014
• Published: 10/06/2016
• Est. Priority Date: 10/20/2012
• Status: Active Grant

• Current Assignee: Luke Hutchison
• Original Assignee: Luke Hutchison
• Inventors: Hutchison, Luke
• Granted Patent: US 10,209,963 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 8/311 Functional or applicative languages; Rewrite languages
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083

Abstract

A system for providing a computer configured to read an immutable value for a variable; read the value of the variable at a specific timestamp, thereby providing an ability to create looping constructs; set a current or next value of a loop variable as a function of previous or current loop variable values; read a set of all values that a variable will assume; push or scattering the values into unordered collections; and reduce the collections into a single value.

Claims

1. A computer (100) comprising a processor (105);

the processor comprising one or more cores (110 and 111) capable of executing instructions;

tangible computer readable storage media (130) connected to the processor (105); and

a communications bus (120) or network interface for connecting the processor (105) to one or more additional processors (106);

wherein the storage media comprises instructions to cause the processor (105) to execute (200P) in memory (140) a compiler-interpreter (200) for a language (151) stored in a language storage device (150), said language (151) conforming to a syntax (152);

the compiler-interpreter (200) comprising;

a syntax validator (210) configured to apply the syntax (152) of the language (151) to source code (134) of a program (133) written in the language (151) to validate (205P) the program (133);

the syntax (152) including one or more operators (240) selected from the group consisting of;

a push operator (250) and a recurrence expression (260);

wherein the syntax (152) has syntax configurators (270) set to prevent destructively overwriting a current value of a variable or memory location.

2. The computer of claim 1, wherein the language is a functional programming language comprising functional programming language operators.

3. The computer of claim 1, wherein the language is an imperative programming language comprising restrictions on certain imperative programming language operators.

4. The computer of claim 1, wherein the compiler-interpreter (200) comprises a code generator (310) configured to use an index key (311) to generate code (312) that inserts values (316-317) into collections (315) or into indexed bins (400) or buckets.

5. The compiler-interpreter of claim 4, wherein specific values are pushed into a collection or into an indexed bin or bucket from multiple different places in the program.

6. The compiler-interpreter of claim 4, wherein the collection (315) comprises one or more values, and wherein the indexed bin or bucket is a map (410) comprising one or more mappings from a key (311) to a value (316) or to a collection (315) of values.

7. The storage media of claim 1, wherein the push operator (250) is configured to receive instructions from a user through a computer interface (105) to insert (530P) a specific value (520) into a collection (315) or into an indexed bin (400) or bucket given an index key (311).

8. The storage media of claim 1, wherein the recurrence expression (260) is a syntactic form that defines a sequence of values (610, 620, 630) using iteration or recursion, and wherein each further value of the sequence is defined as a function of values computed earlier in the iteration or recursion.

9. The storage media of claim 1, wherein the compiler-interpreter is configured to disambiguate (640P) values or variable references in loops (650) or recursive code (660) based on the recurrence expression (260).

10. The storage media of claim 1, wherein the compiler-interpreter comprises a DDG generator (730) configured to generate (730P) a data dependency graph (DDG) (700) having structure, the DDG comprising an implementation of nodes and arcs (710).

11. The storage media of claim 9, wherein the compiler-interpreter comprises a work unit generator (845) configured to generate work units, the compiler interpreter configured to generate a time and space complexity estimate of each node in the DDG to identity an optimal division of the DDG into work units comprising one or more nodes connected by arcs such that an expected total execution time of the program is minimized while respecting constraints on memory and storage available to each processor, wherein the work units are schedulable to run on one or more processors and have inputs and outputs.

12. The storage media of claim 9, wherein each node is linked with:

an expression (910) for computing a value (920) or collection of values given the value or collection of values computed by data dependencies; and

the value (920) or collection of values (930) computed by the expression.

13. The storage media of claim 1, further comprising instruction to instantiate an execution plan (860) comprising a partial ordering of operations to be executed, including launch logic (880) for launching operations in parallel across multiple processors or threads, and synchronization logic (890) for synchronizing these operations to conform to the partial ordering.

14. The storage media of claim 11, wherein the compiler-interpreter comprises a time and space estimator (1010) configured to estimate time and space complexity requirements to compute the value or collection of values for each node in the DDG as a function of the time and space complexity of the node'"'"'s data dependencies.

15. The storage media of claim 9, wherein the compiler-interpreter may comprise a structural analyzer (1020) configured to analyze the structure of the DDG (700) to determine whether DDG has the structure of a Directed Acyclic Graph (DAG) consistent with a partial ordering or partially ordered set.

16. The storage media of claim 15, wherein the DDG generator 730 comprises an arc generator 740 connecting a first node to a second node whenever the expression in the second node is a function of, or accepts as input, the value or collection of values computed by the first node.

17. The storage media of claim 15, wherein the DDG comprises a first and second node;

wherein the first node is a data dependency, the second node is a dependent node; and

the dependent node requires the value or collection of values produced by the expression in the data dependency to compute its own value or collection of values.

18. The storage media of claim 15, wherein the compiler-interpreter comprises a code analyzer (1110) configured to identify parallelization in the code (134) opportunities beyond those directly determinable from the partial ordering of the DDG;

said code analyzer configured to;

compare algebraic properties of values or collections of values to algebraic properties of expressions or computational operations that operate on them; and

from that comparison using a conversion analyzer (1140) determine whether it is mathematically valid to convert a serial, iterative expression or operation (1150) into a parallel divide-and-conquer form (1160).

19. The storage media of claim 18, wherein the compiler-interpreter comprises a property tracker (1160) to track algebraic properties of collections of values.

20. The storage media of claim 19, wherein collections of values have algebraic properties (1170) selected from the group consisting of:

orderedness (1171), element duplicity (1172), element type (1173), and sparseness (1174).

21. The storage media of claim 18, wherein the compiler-interpreter comprises an error handler 1090 configured to report an error if:

the DDG generator cannot generate (1050P) a DDG because the DDG is not directly determinable from the source code of the program, the structural analyzer (1020) determines the structure of the DDG is not a DAG, or an instruction analyzer (1080) determines that the program comprises an instruction applying an operator to a value or collection of values of incompatible type (1080P).

22. The storage media of claim 21, wherein the compiler-interpreter comprises an operator converter (1155) configured to transform a serial fold or reduce operation on a collection into a parallel “

divide-and-conquer”

reduce operation if conversion analyzer (1140) determines;

a. the reduce operation is commutative, or

b. the reduce operation is associative but not commutative and the collection is ordered.

23. The storage media of claim 18, wherein the expressions or computational operations have algebraic properties selected from the group consisting of:

commutativity, associativity, distributivity, and idempotence.

24. The storage media of claim 15, wherein the compiler-interpreter is configured to receive an estimate of an expected time and space complexity of elemental operations and communications in a specified target architecture.

25. The storage media of claim 24, wherein the compiler-interpreter is configured to substitute the estimated time and space complexity for elemental operations and communications in a given target architecture into the time and space complexity estimates for nodes in the DDG to produce a more accurate estimate of time and space complexity for each node in the DDG on the given target architecture.

26. The storage media of claim 9, wherein the compiler-interpreter is configured to generate logic that automatically restarts and re-executes an idempotent computation if the computation is killed or terminated due to a system failure.

27. The storage media of claim 26, wherein the compiler-interpreter comprising a node path analyzer (1310) configured to:

identify pairs of nodes in the DDG between which there is no directed path having an unbroken series of one or more arcs, and an execution plan generator (1320) configured to produce an execution plan (1330) for the program wherein the expressions linked to these pairs of nodes are scheduled to execute in parallel.

28. The storage media of claim 1, wherein the work unit generator (845) is configured to generate synchronization logic at the inputs and outputs of each work unit or at a beginning and an end of each node to ensure the partial ordering of the DDG is respected as the work units or nodes are processed or executed.

29. The storage media of claim 28, wherein the re-execution logic (1190) is configured to determine which expressions, computational operations or communications may be safely restarted on failure due to an idempotence property of linked nodes or work units.

30. The storage media of claim 9, wherein the compiler-interpreter is configured to receive an estimate of time complexity for arcs in the DDG according to the implementation of the arcs in a specified target architecture, selected from the group consisting of:

reading from or writing to memory, reading from or writing to a database or file, and receiving data from or sending data to another processor over a communications channel.

31. The storage media of claim 9, wherein the compiler-interpreter is configured to receive:

an estimate of size or space complexity for all inputs to the DDG; and

an estimate of size or space complexity for constant value nodes in the DDG that do not have dependencies.

32. The storage media of claim 9, wherein the compiler-interpreter comprises a DDG analyzer (1315) configured to receive data concerning the arcs connecting a node in the DDG to its dependency nodes and dependent nodes;

and generate memory allocation and deallocation logic for the nodes;

wherein

a. the memory allocation logic is configured to allocate memory for the intermediate values generated during the computation of the expression corresponding to a specific DDG node, and for the final value or collection of values generated by the expression, wherein;

i. the memory allocation logic is configured to be inserted into the object code such that memory allocation logic executes before the code generated for the expression;

or

ii. the memory allocation logic is executed by the compiler-interpreter, an interpreter or a runtime environment before the expression is executed;

b. the memory deallocation logic is configured;

i. to free memory for the intermediate values generated during the computation of the expression corresponding to a specific DDG node once the expression has been executed, and

ii. to free memory for the final value or collection of values generated by the expression once the final value or collection of values is no longer needed, wherein the memory allocation logic is;

1. inserted into the object code such that it executes after the code generated for each dependent node of the specific DDG node has read the dependent node'"'"'s dependencies;

or

2. executed by the compiler-interpreter, an interpreter or a runtime environment after reading the dependencies for all dependent nodes of the specific DDG node.

33. The storage media of claim 9, wherein the compiler-interpreter comprises a code writer (1410) configured to generate executable code from the expression or computational operation linked to each node or work unit in the DDG.

34. The storage media of claim 9, wherein the compiler-interpreter is configured to:

generate code from a data dependency represented by each are in the DDG, wherein the compiler-interpreter is configured to;

read from memory;

write to memory;

read from a database;

read from a file;

write to a database;

write to a file;

receive data from another processor over a communications channel;

or send data to another processor over a communications channel.

35. The storage media of claim 9, wherein the compiler-interpreter comprises a cache generator (1510) configured to generate disableable memoization or caching logic (1520) for each node in the DDG.

36. The storage media of claim 9, wherein the compiler-interpreter is configured to compile code to reuse previously-cached values, or to reuse previously-cached values, whenever the same code is executed with the same inputs, to avoid recomputing values.

37. The storage media of claim 9, comprising instructions to cause the processor to execute a program editor configured to reuse previously-cached values to provide support to a user for partial evaluation and reactive programming.

38. The storage media of claim 9, wherein the compiler-interpreter is configured to generate object code for the computations, synchronization logic, memory allocation and memory deallocation logic, and restart-on-failure logic of each DDG node or work unit.

39. The storage media of claim 38, wherein the object code is selected from the group consisting of:

intermediate representation (IR) code, bytecode, binary code, code in another programming language, logic circuit configurations, and machine code.

40. The storage media of claim 9, wherein the compiler-interpreter is configured to compare two versions of a program'"'"'s source code to determine differences between the two programs.

41. The storage media of claim 9, wherein the compiler-interpreter is configured to perform differential compilation by generating differential object code corresponding to parts of the program that have changed between two versions of a program'"'"'s source code.

42. The storage media of claim 9, wherein the compiler-interpreter is configured to interpret and execute the program directly from source code form that does not depend upon external inputs.

43. The storage media of claim 9, wherein the compiler-interpreter is configured to interpret or execute, then cache or memoize, any parts of the program that do not depend upon external inputs.

44. The storage media of claim 9, wherein the compiler-interpreter is configured incorporate cached or memoized values into generated object code as constant or lookup table (LUT) form.

45. The storage media of claim 9, wherein the compiler-interpreter is configured to read user-provided settings that specify how much overhead, in terms of compilation time, RAM, disk space or additional space that may be taken up in the generated object code, for evaluating portions of a program that do not depend on external inputs, and for storing the interpreted, executed or pre-computed instructions directly from source code form during compilation in order to trade off the size of generated object code and the amount of time spent by the compiler-interpreter in interpreting or executing code against total expected execution time of the generated object code.

46. A computer comprising a processor;

tangible computer readable storage media accessible to the processor; and

a communications bus or network interface for connecting the processor to one or more additional processors;

wherein the storage media comprises instructions to cause the processor to execute a compiler-interpreter for a language conforming to a syntax;

the syntax including one or more operators selected from the group consisting of;

a push operator and a recurrence expression;

the compiler-interpreter being configured, by conforming to the syntax, to not attempt to read a value before the value is computed.

47-73. -73. (canceled)