# US 8,572,595 B1 · Methods and apparatus for aggressive scheduling in source code compilation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,572,595 B1 - Document ID: US8572595B1 - Status: Granted - Kind: B1 - Application number: 13/204,517 - Filed: 2011-08-05 - Granted: 2013-10-29 - Earliest claimed: 2008-02-08 - Assignees: Reservoir Labs, Inc. - Applicants: Richard A. Lethin; Allen K. Leung; Benoit J. Meister; Nicolas T. Vasilache - Inventors: Richard A. Lethin; Allen K. Leung; Benoit J. Meister; Nicolas T. Vasilache - Web page: https://patentgrep.com/patent/US8572595B1 ## CPC - G06F 8/452: {Loops} - G06F 8/443: {Optimisation} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) The method of claim 1, wherein the scheduling step comprises employing a scheduling function. ### Claim 4 (depends on 3) The method of claim 3, wherein the scheduling function assigns a partial execution order between iterations of an operation in the set of operations. ### Claim 5 (depends on 1) The method of claim 1, further comprising representing dependencies within the set of operations as a generalized dependence graph (GDG). ### Claim 6 (depends on 5) The method of claim 5, further comprising adding a copy-out operation to the GDG. ### Claim 7 (depends on 1) The method of claim 1, further comprising transforming all weak memory references in the set of operations into strong memory references. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 1) 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. ### Claim 11 (depends on 10) 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. ### Claim 12 (depends on 1) The method of claim 1, further comprising correcting a dependency violation after the scheduling step. ### Claim 13 (depends on 12) 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. ### Claim 14 (depends on 13) The method of claim 13, wherein the dependency violation is a liveness violation. ### Claim 15 (depends on 13) 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. ### Claim 16 (depends on 12) 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. ### Claim 17 (depends on 11) 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. ### Claim 18 (depends on 1) 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 18) The method of claim 18, wherein the selecting step comprises selecting all memory-based dependencies causing a semantic violation. ### Claim 21 (depends on 1) The method of claim 1, wherein the program after the scheduling step retains a dependency violation that is not a semantic violation. ### Claim 22 (depends on 1) 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. ### Claim 23 (depends on 1) The method of claim 1, further comprising employing operation placement for the operations in the set of operations to filter semantic violations. ### Claim 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. ### Claim 25 (depends on 24) 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. ### Claim 26 (depends on 24) The computing apparatus of claim 24, wherein the schedule is obtained by a scheduling function. ### Claim 27 (depends on 26) 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. ### Claim 28 (depends on 24) 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). ### Claim 29 (depends on 28) The computing apparatus of claim 28, wherein the configuration further comprises a configuration to add a copy-out operation to the GDG. ### Claim 30 (depends on 24) 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. ### Claim 31 (depends on 24) 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. ### Claim 32 (depends on 24) 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. ### Claim 33 (depends on 24) 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. ### Claim 34 (depends on 33) 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. ### Claim 35 (depends on 24) The computing apparatus of claim 24, wherein the configuration further comprises a configuration to correct a dependency violation after the scheduling. ### Claim 36 (depends on 35) 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. ### Claim 37 (depends on 36) The computing apparatus of claim 36, wherein the dependency violation is a liveness violation. ### Claim 38 (depends on 36) 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. ### Claim 39 (depends on 35) 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. ### Claim 40 (depends on 34) 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. ### Claim 41 (depends on 24) 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. ### Claim 42 (depends on 41) 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. ### Claim 43 (depends on 41) The computing apparatus of claim 41, wherein the selection the memory-based dependency comprises a selection all memory-based dependencies causing a semantic violation. ### Claim 44 (depends on 24) The computing apparatus of claim 24, wherein the program after the schedule retains a dependency violation that is not a semantic violation. ### Claim 45 (depends on 24) 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. ### Claim 46 (depends on 24) 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. ### Claim 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. ### Claim 48 (depends on 47) 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. ### Claim 49 (depends on 47) The article of claim 47, wherein the schedule is obtained by a scheduling function. ### Claim 50 (depends on 49) The article of claim 49, wherein the scheduling function assigns a partial execution order between iterations of an operation in the set of operations. ### Claim 51 (depends on 47) 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). ### Claim 52 (depends on 51) The article of claim 51, wherein the instructions further configure the machine to add a copy-out operation to the GDG. ### Claim 53 (depends on 47) 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. ### Claim 54 (depends on 47) 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. ### Claim 55 (depends on 47) 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. ### Claim 56 (depends on 47) 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. ### Claim 57 (depends on 56) 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. ### Claim 58 (depends on 47) The article of claim 47, wherein the instructions further configure the machine to correct a dependency violation after the scheduling. ### Claim 59 (depends on 58) 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. ### Claim 60 (depends on 59) The article of claim 59, wherein the dependency violation is a liveness violation. ### Claim 61 (depends on 59) 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. ### Claim 62 (depends on 58) 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. ### Claim 63 (depends on 57) 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. ### Claim 64 (depends on 47) 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. ### Claim 65 (depends on 64) 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. ### Claim 66 (depends on 64) The article of claim 64, wherein the selection comprises a selection all memory-based dependencies causing a semantic violation. ### Claim 67 (depends on 47) The article of claim 47, wherein the program after the schedule retains a dependency violation that is not a semantic violation. ### Claim 68 (depends on 47) 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. ### Claim 69 (depends on 47) 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.