Methods and apparatus for aggressive scheduling in source code compilation
View Patent ↗Computer-executed transformation of source code enables optimization of the code for one or more of parallelism, locality, and memory footprint of operations represented in the source code on a computing apparatus. This Abstract is provided for the sole purpose of complying with the Abstract requirement rules that allow a reader to quickly ascertain the subject matter of the disclosure contained herein. This Abstract is submitted with the explicit understanding that it will not be used to interpret or to limit the scope or the meaning of the claims.
1. A method of scheduling operations of a program on a multi-execution unit computing apparatus, the method comprising:
receiving, at a first computing apparatus, a computer program comprising a set of operations; and
optimizing the computer program for execution on a second computing apparatus, the second computing apparatus comprising at least two execution units,
wherein the optimizing step comprises (i) initializing a set of memory-based dependencies, (ii) performing dataflow analysis to identify one or more dataflow dependencies within the set of operations, and (iii) scheduling the set of operations, the scheduling being based at least in part on a performance cost of a schedule and a memory-usage cost of the schedule,
whereby (a) any dependency in the set of memory-based dependencies and the identified one or more dataflow dependencies are not violated, and (b) a subset of operations in the set of operations is scheduled for execution by a first unit of the at least two execution units and a subset of operations in the set of operations is scheduled for execution by a second unit of the at least two execution units.
2. The method of claim 1 , wherein the scheduling step comprises at least one of minimizing the performance cost and limiting the memory-usage cost to a specified value.
3. The method of claim 1 , wherein the scheduling step comprises employing a scheduling function.
4. The method of claim 3 , wherein the scheduling function assigns a partial execution order between iterations of an operation in the set of operations.
5. The method of claim 1 , further comprising representing dependencies within the set of operations as a generalized dependence graph (GDG).
6. The method of claim 5 , further comprising adding a copy-out operation to the GDG.
7. The method of claim 1 , further comprising transforming all weak memory references in the set of operations into strong memory references.
8. The method of claim 1 , wherein the initializing the set of memory-based dependencies comprises adding one or more memory-based dependencies associated with a weak memory reference in the set of operations to the set of memory-based dependencies.
9. The method of claim 1 , further comprising determining a placement of operations in the set of operations according to a property of the second computing apparatus.
10. The method of claim 1 , further comprising:
collecting dependency violations after the scheduling step; and
identifying a dependency violation that causes a semantic violation in the program.
11. The method of claim 10 , further comprising determining a loop type associated with an operation in the set of operations, wherein the semantic violation is related to the loop type.
12. The method of claim 1 , further comprising correcting a dependency violation after the scheduling step.
13. The method of claim 12 , wherein a memory write operation in the set of operations causes the dependency violation, and the correcting step comprises renaming a memory location associated with the memory write operation as a new memory location.
14. The method of claim 13 , wherein the dependency violation is a liveness violation.
15. The method of claim 13 , further comprising replacing a memory read operation in the set of operations, reading from the renamed memory location, with a new memory read operation reading from the new memory location.
16. The method of claim 12 , wherein the correcting step comprises expanding a write operation in the set of operations to provide a new memory location, thereby removing the semantic violation.
17. The method of claim 11 , further comprising performing index-set splitting transformation of a write operation in the set of operations, wherein the write operation causes the semantic violation.
18. The method of claim 1 , wherein the optimizing step further comprises:
comparing the memory-usage cost with a specified memory limit; and
if the memory limit is exceeded, (i) selecting a memory-based dependency, (ii) updating the set of memory-based dependencies with the selected memory-based dependency, and (iii) repeating the scheduling step.
19. The method of claim 18 , wherein the selecting step comprises identifying a memory-based dependency causing more semantic violations than any other memory-based dependency.
20. The method of claim 18 , wherein the selecting step comprises selecting all memory-based dependencies causing a semantic violation.
21. The method of claim 1 , wherein the program after the scheduling step retains a dependency violation that is not a semantic violation.
22. The method of claim 1 , wherein the optimizing step further comprises:
determining a set of conditions that preserve the semantic correctness of the program;
representing the set of conditions preserving semantic correctness in the form of a generalized dependence graph;
classifying the conditions into producer-consumer dependencies and memory-based dependencies;
deriving at least one multidimensional piecewise affine function to schedule operations in the optimized program.
23. The method of claim 1 , further comprising employing operation placement for the operations in the set of operations to filter semantic violations.
24. A computing apparatus comprising:
a processor; and
a memory coupled to the processor, the memory comprising a set of processor executable instructions that, when executed by the processor, configure the computing apparatus to modify a computer program comprising a set of operations for execution on a second computing apparatus, the second computing apparatus comprising at least two execution units, the configuration comprising a configuration to:
(i) initialize a set of memory-based dependencies;
(ii) perform dataflow analysis to identify one or more dataflow dependencies within the set of operations; and
(iii) schedule the set of operations, the schedule being based at least in part on a performance cost of the schedule and a memory-usage cost of the schedule,
whereby (a) any dependency in the set of memory-based dependencies and the identified one or more dataflow dependencies are not violated, and (b) a subset of operations in the set of operations is scheduled for execution by a first unit of the at least two execution units and a subset of operations in the set of operations is scheduled for execution by a second unit of the at least two execution units.
25. The computing apparatus of claim 24 , wherein the schedule corresponds to at least one of a minimized performance cost and the memory-usage cost limited to a specified value.
26. The computing apparatus of claim 24 , wherein the schedule is obtained by a scheduling function.
27. The computing apparatus of claim 26 , wherein the scheduling function assigns a partial execution order between iterations of an operation in the set of operations.
28. The computing apparatus of claim 24 , wherein the configuration further comprises a configuration to represent dependencies within the set of operations as a generalized dependence graph (GDG).
29. The computing apparatus of claim 28 , wherein the configuration further comprises a configuration to add a copy-out operation to the GDG.
30. The computing apparatus of claim 24 , wherein the configuration further comprises a configuration to transform all weak memory references in the set of operations into strong memory references.
31. The computing apparatus of claim 24 , wherein the initialization of the set of memory-based dependencies comprises an addition of one or more memory-based dependencies associated with a weak memory reference in the set of operations to the set of memory-based dependencies.
32. The computing apparatus of claim 24 , wherein the configuration further comprises a configuration to determine a placement of operations in the set of operations according to a property of the second computing apparatus.
33. The computing apparatus of claim 24 , wherein the configuration further comprises a configuration to:
collect dependency violations after the scheduling; and
identify a dependency violation that causes a semantic violation in the program.
34. The computing apparatus of claim 33 , wherein the configuration further comprises a configuration to determine a loop type associated with an operation in the set of operations, wherein the semantic violation is related to the loop type.
35. The computing apparatus of claim 24 , wherein the configuration further comprises a configuration to correct a dependency violation after the scheduling.
36. The computing apparatus of claim 35 , wherein a memory write operation in the set of operations causes the dependency violation, and the correction of the dependency violation comprises a renamed memory location associated with the memory write operation as a new memory location.
37. The computing apparatus of claim 36 , wherein the dependency violation is a liveness violation.
38. The computing apparatus of claim 36 , wherein the configuration further comprises a configuration to replace a memory read operation in the set of operations, that reads from the renamed memory location, with a new memory read operation that reads from the new memory location.
39. The computing apparatus of claim 35 , wherein the correction of the dependency violation comprises an expansion of a write operation in the set of operations to provide a new memory location, thereby removing the semantic violation.
40. The computing apparatus of claim 34 , wherein the configuration further comprises a configuration to perform index-set splitting transformation of a write operation in the set of operations, wherein the write operation causes the semantic violation.
41. The computing apparatus of claim 24 , wherein the configuration further comprises a configuration to:
compare the memory-usage cost with a specified memory limit; and
if the memory limit is exceeded, to: (i) select a memory-based dependency, (ii) update the set of memory-based dependencies with the selected memory-based dependency, and (iii) repeat the schedule.
42. The computing apparatus of claim 41 , wherein the selection of the memory-based dependency comprises an identification of a memory-based dependency causing more semantic violations than any other memory-based dependency.
43. The computing apparatus of claim 41 , wherein the selection the memory-based dependency comprises a selection all memory-based dependencies causing a semantic violation.
44. The computing apparatus of claim 24 , wherein the program after the schedule retains a dependency violation that is not a semantic violation.
45. The computing apparatus of claim 24 , wherein the configuration further comprises a configuration to:
determine a set of conditions that preserve the semantic correctness of the program;
represent the set of conditions preserving semantic correctness in the form of a generalized dependence graph;
classify the conditions into producer-consumer dependencies and memory-based dependencies;
derive at least one multidimensional piecewise affine function to schedule operations in the optimized program.
46. The computing apparatus of claim 24 , the configuration further comprises a configuration to employ operation placement for the operations in the set of operations to filter semantic violations.
47. An article of manufacture, comprising a non-transitory machine-readable medium storing instructions that, when executed by a machine, configure the machine to:
receive, at a first computing apparatus, a computer program comprising a set of operations; and
optimize the computer program for execution on a second computing apparatus, the second computing apparatus comprising at least two execution units,
wherein the optimization comprises a configuration to (i) initialize a set of memory-based dependencies, (ii) perform dataflow analysis to identify one or more dataflow dependencies within the set of operations, and (iii) schedule the set of operations, the schedule being based at least in part on a performance cost of the schedule and a memory-usage cost of the schedule,
whereby (a) any dependency in the set of memory-based dependencies and the identified one or more dataflow dependencies are not violated, and (b) a subset of operations in the set of operations is scheduled for execution by a first unit of the at least two execution units and a subset of operations in the set of operations is scheduled for execution by a second unit of the at least two execution units.
48. The article of claim 47 , wherein the schedule corresponds to at least one of a minimized performance cost and the memory-usage cost limited to a specified value.
49. The article of claim 47 , wherein the schedule is obtained by a scheduling function.
50. The article of claim 49 , wherein the scheduling function assigns a partial execution order between iterations of an operation in the set of operations.
51. The article of claim 47 , wherein the instructions further configure the machine to represent dependencies within the set of operations as a generalized dependence graph (GDG).
52. The article of claim 51 , wherein the instructions further configure the machine to add a copy-out operation to the GDG.
53. The article of claim 47 , wherein the instructions further configure the machine to transform all weak memory references in the set of operations into strong memory references.
54. The article of claim 47 , wherein the initialization of the set of memory-based dependencies comprises an addition of one or more memory-based dependencies associated with a weak memory reference in the set of operations to the set of memory-based dependencies.
55. The article of claim 47 , wherein the instructions further configure the machine to determine a placement of operations in the set of operations according to a property of the second computing apparatus.
56. The article of claim 47 , wherein the instructions further configure the machine to:
collect dependency violations after the scheduling; and
identify a dependency violation that causes a semantic violation in the program.
57. The article of claim 56 , wherein the instructions further configure the machine to determine a loop type associated with an operation in the set of operations, wherein the semantic violation is related to the loop type.
58. The article of claim 47 , wherein the instructions further configure the machine to correct a dependency violation after the scheduling.
59. The article of claim 58 , wherein a memory write operation in the set of operations causes the dependency violation, and the correction comprises a renamed memory location associated with the memory write operation as a new memory location.
60. The article of claim 59 , wherein the dependency violation is a liveness violation.
61. The article of claim 59 , wherein the instructions further configure the machine to replace a memory read operation in the set of operations, that reads from the renamed memory location, with a new memory read operation that reads from the new memory location.
62. The article of claim 58 , wherein the correction comprises an expansion of a write operation in the set of operations to provide a new memory location, thereby removing the semantic violation.
63. The article of claim 57 , wherein the instructions further configure the machine to perform index-set splitting transformation of a write operation in the set of operations, wherein the write operation causes the semantic violation.
64. The article of claim 47 , wherein the optimization further comprises a configuration to:
compare the memory-usage cost with a specified memory limit; and
if the memory limit is exceeded, to: (i) select a memory-based dependency, (ii) update the set of memory-based dependencies with the selected memory-based dependency, and (iii) repeat the schedule.
65. The article of claim 64 , wherein the selection comprises an identification of a memory-based dependency causing more semantic violations than any other memory-based dependency.
66. The article of claim 64 , wherein the selection comprises a selection all memory-based dependencies causing a semantic violation.
67. The article of claim 47 , wherein the program after the schedule retains a dependency violation that is not a semantic violation.
68. The article of claim 47 , wherein the optimization further comprises:
a determination of a set of conditions that preserve the semantic correctness of the program;
a representation of the set of conditions preserving semantic correctness in the form of a generalized dependence graph;
a classification of the conditions into producer-consumer dependencies and memory-based dependencies;
a derivation of at least one multidimensional piecewise affine function to schedule operations in the optimized program.
69. The article of claim 47 , wherein the instructions further configure the machine to employ operation placement for the operations in the set of operations to filter semantic violations.