Method and apparatus for partitioning programs to balance memory latency

• US 8,543,992 B2
• Filed: 12/17/2005
• Issued: 09/24/2013
• Est. Priority Date: 12/17/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Jiang, Xiaodan, Dai, Jinquan
• Primary Examiner(s): MITCHELL, JASON D
• Application Number:
  US10/585,680
• Publication Number:
  US 20090193405A1
• Time in Patent Office: 2,838 Days
• Field of Search: None
• US Class Current: 717/149
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

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

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.

2. 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.

3. 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.

4. The method of claim 1, wherein generating the memory access dependence chains comprises identifying instruction dependence information.

5. The method of claim 1, wherein generating the memory access dependence chains comprises constructing a memory access dependence graph.

6. 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.

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.

8. 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.

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.

10. 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.

11. 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.

12. The apparatus of claim 10, wherein an evaluation unit to determine whether a weight of the downstream stage exceeds the predetermined value.

13. 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.

14. The apparatus of claim 10, further comprising a code partition manager that receives instruction dependence information and the memory access dependence chains.

15. 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.