# US 8,543,992 B2 · Method and apparatus for partitioning programs to balance memory latency > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,992 B2 - Document ID: US8543992B2 - Status: Granted - Kind: B2 - Application number: 10/585,680 - Filed: 2005-12-17 - Published: 2009-07-30 - Granted: 2013-09-24 - Earliest claimed: 2005-12-17 - Assignees: Intel Corporation - Applicants: Xiaodan Jiang; Jinquan Dai - Inventors: Xiaodan Jiang; Jinquan Dai - Web page: https://patentgrep.com/patent/US8543992B2 ## CPC - G06F 8/4442: {Reducing the number of cache misses; Data prefetching (cache prefetching G06F12/0862)} - G06F 8/45: {Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method of compiling code that includes partitioning instructions in the code among a plurality of processors based on memory access latency associated with the instructions is disclosed. According to one aspect of the invention, partitioning instructions includes partitioning memory access dependence chains. Other embodiments are described and claimed. ## Claims ### Claim 1 A method of compiling code, comprising: partitioning instructions in the code among a plurality of processors based on memory access latency associated with the instructions by: partitioning memory access dependence chains into an upstream stage by assigning a first number of desired upstream nodes to the upstream stage, and also assigning instructions in the code on which the first number of desired upstream nodes are dependent to the upstream stage, wherein the first number of desired upstream nodes is N/d where N is a length of the memory access dependence chain and d is a pipelining degree; and partitioning the memory access dependence chains into a downstream stage by assigning a last number of desired downstream nodes to the downstream stage, and assigning instructions in the code which are dependent on the last number of desired downstream nodes to the downstream stage, wherein the last number of desired downstream nodes is N*(d−1)/d; performing the partitioning a plurality of times with subsequent partitioning being performed on the instructions assigned to the downstream stage. ### Claim 2 (depends on 1) The method of claim 1, wherein the length of the memory access dependence chain N is a number reflecting all available tasks in a sequence of memory read and write instructions. ### Claim 3 (depends on 1) The method of claim 1, further comprising: if a weight required for execution of the upstream stage exceeds a predetermined value, re-computing the number of desired upstream nodes; assigning the re-computed number of desired upstream nodes to the upstream stage; and assigning instructions in the code on which the re-computed number of desired upstream nodes are dependent to the upstream stage. ### Claim 4 (depends on 1) The method of claim 1, wherein generating the memory access dependence chains comprises identifying instruction dependence information. ### Claim 5 (depends on 1) The method of claim 1, wherein generating the memory access dependence chains comprises constructing a memory access dependence graph. ### Claim 6 (depends on 1) The method of claim 1, wherein generating the memory access dependence chains comprises: constructing a memory access dependence graph; and identifying a memory access dependence chain from the memory access dependence graph. ### Claim 7 An article of manufacture comprising a non-transitory machine accessible medium including sequences of instructions, the sequences of instructions including instructions which when executed cause the machine to perform: partitioning instructions in code among a plurality of processors based on memory access latency associated with the instructions by: partitioning memory access dependence chains into an upstream stage by assigning a first number of desired upstream nodes to the upstream stage, and also assigning instructions in the code on which the first number of desired upstream nodes are dependent on to the upstream stage, wherein the first number of desired upstream nodes is N/d where N is a length of the memory access dependence chain and d is a pipelining degree; and partitioning the memory access dependence chains into a downstream stage by assigning a last number of desired downstream nodes to the downstream stage, and assigning instructions in the code which are dependent on the last number of desired downstream nodes to the downstream stage, wherein the last number of desired downstream nodes is N*(d−1)/d; performing the partitioning a plurality of times with subsequent partitioning being performed on the instructions assigned to the downstream stage. ### Claim 8 (depends on 7) The article of manufacture of claim 7, further comprising instructions which when executed cause the machine to further perform constructing a memory access dependence graph. ### Claim 9 A code analysis unit implemented on a processor, comprising: a dependence information unit to identify dependencies between instructions in code; and a code partitioning unit to partition instructions in the code into a plurality of pipeline stages to be executed by a plurality of processors based on memory access latency associated with the instructions by partitioning memory access dependence chains into an upstream stage by assigning a first number of desired upstream nodes to the upstream stage, and also assigning instructions in the code on which the first number of desired upstream nodes are dependent to the upstream stage, wherein the first number of desired upstream nodes is N/d where N is a length of the memory access dependence chain and d is a pipelining degree; and partitioning the memory access dependence chains into a downstream stage by assigning a last number of desired downstream nodes to the downstream stage, and assigning instructions in the code which are dependent on the last number of desired downstream nodes to the downstream stage, wherein the last number of desired downstream nodes is N*(d−1)/d; performing the partitioning a plurality of times with subsequent partitioning being performed on the instructions assigned to the downstream stage. ### Claim 10 (depends on 9) The apparatus of claim 9, wherein the code partition unit comprises: an evaluation unit to determine whether a weight of the upstream stage exceeds a predetermined value. ### Claim 11 (depends on 10) The apparatus of claim 10, wherein the length unit determines a new number of desired length of upstream nodes in response to the evaluation unit determining that the weight of the upstream stage exceeds the predetermined value. ### Claim 12 (depends on 10) The apparatus of claim 10, wherein an evaluation unit to determine whether a weight of the downstream stage exceeds the predetermined value. ### Claim 13 (depends on 12) The apparatus of claim 12, further comprising a balancing unit to assign remaining instructions to the upstream stage and the downstream stage in a manner that substantially balances weight. ### Claim 14 (depends on 10) The apparatus of claim 10, further comprising a code partition manager that receives instruction dependence information and the memory access dependence chains. ### Claim 15 (depends on 9) The apparatus of claim 9, wherein the dependence information unit generates a memory access dependence graph and memory access dependence chains from instruction dependence information.