Optimizing compiler having data cache prefetch spreading

• US 5,854,934 A
• Filed: 08/23/1996
• Issued: 12/29/1998
• Est. Priority Date: 08/23/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Staley, Loren, Hsu, Wei
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): DAM, TUAN QUANG
• Application Number:
  US08/702,359
• Time in Patent Office: 858 Days
• Field of Search: 395/709, 395/705, 395/383, 395/381, 395/584, 395/583, 395/588, 711/118, 711/137, 711/171, 711/217, 711/213, 711/218
• US Class Current: 717/161
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862

Abstract

A method of scheduling prefetch instructions in a compiler is described that improves performance by minimizing the performance degradation due to dirty cache misses. The method determines the length N of a loop (step 66). The number of prefetch instructions were M within that loop are then determined (step 68). A prefetch spacing P is then calculated according to the formula P=N/M, where the length of the loop is expressed in cycles (step 70). This prefetch spacing is then attached to each prefetch instruction and the instruction scheduler schedules the prefetch instructions so as to space the prefetch instructions apart by approximately the prefetch spacing P (step 72). After the scheduler arranged for P cycles, a prefetch instruction will be assigned a higher priority for scheduling in the next lot.

Claims

1. A method of scheduling instructions for execution on a computer system including a data cache or data cache hierarchy, the method comprising the steps of:

determining a length of a loop;

generating a plurality (M) of prefetch instructions; and

scheduling the plurality of prefetch instructions to space out the prefetch instructions throughout the length of the loop.

2. The method of scheduling instructions for execution on a computer system according to claim 1 wherein the step of spacing out the prefetch instructions throughout the length of the loop includes spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction so as to minimize performance degradation due to dirty misses in the cache caused by the prefetch instructions.

3. The method of scheduling instructions for execution on a computer system according to claim 2 wherein the step of determining a length of a loop includes determining a number of cycles (N) required by the loop.

4. The method of scheduling instructions for execution on a computer system according to claim 3 wherein the step of determining a number of cycles (N) required by the loop includes:

determining resource constraints within the system; and

determining latency constraints within the system.

5. The method of scheduling instructions for execution on a computer system according to claim 4 wherein the step of determining a number of cycles (N) required by the loop includes:

determining a number of cycles required by each instruction in the loop; and

adding the number of cycles required by each instruction together to determine the number of cycles required by the loop.

6. The method of scheduling instructions for execution on a computer system according to claim 3 wherein the step of spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes spacing a prefetch instruction approximately N/M cycles from a prior prefetch instruction.

7. The method of scheduling instructions for execution on a computer system according to claim 3 wherein the step of spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes spacing a prefetch instruction approximately N/M cycles from a subsequent prefetch instruction.

8. The method of scheduling instructions for execution on a computer system according to claim 3 wherein the step of spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes spacing each prefetch instruction apart from a subsequent prefetch instruction by a respective number of cycles, wherein the total spacing between a first prefetch instruction and a last prefetch instruction is equal to the number of cycles (N) required by the loop.

9. The method of scheduling instructions for execution on a computer system according to claim 2 wherein the step of spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes spacing each prefetch instruction approximately N/M cycles from a prior prefetch instruction.

10. An optimizing compiler stored in a computer-readable memory device and executable by a computer system having a data cache or data cache hierarchy, the compiler comprising:

means for identifying a loop;

means for determining a length of the loop;

means for generating a plurality (M) of prefetch instructions; and

means for spacing out the prefetch instructions throughout the length of the loop.

11. The optimizing compiler according to claim 10 wherein the means for spacing out the prefetch instructions throughout the length of the loop includes means for spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction.

12. The optimizing compiler according to claim 11 wherein the means for determining a length of the loop includes means for determining a number of cycles (N) required by the loop.

13. The optimizing compiler according to claim 12 wherein the means for determining a number of cycles (N) required by the loop includes:

means for determining resource constraints within the system; and

means for determining latency constraints within the system.

14. The optimizing compiler according to claim 11 wherein the means for spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes:

means for determining a number of cycles (N) required by the loop;

means for dividing the number of cycles (N) by the number of prefetch instructions to produce a prefetch spacing (S); and

means for spacing out the prefetch instructions by approximately the prefetch spacing (S).

15. The optimizing compiler according to claim 14 wherein the means for spacing out the prefetch instructions by approximately prefetch spacing (S) includes means for rounding the prefetch spacing to an integer number of cycles.

16. The optimizing compiler according to claim 15 wherein the means for spacing out the prefetch instructions by approximately prefetch spacing (S) includes means for rounding the prefetch spacing up to an integer number of cycles.

17. The optimizing compiler according to claim 15 wherein the means for spacing out the prefetch instructions by approximately prefetch spacing (S) includes means for rounding the prefetch spacing down to an integer number of cycles.

18. The optimizing compiler according to claim 11 wherein the means for spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes:

means for determining a number of cycles (N) required by the loop; and

means for spacing each prefetch instruction apart from a subsequent prefetch instruction by a respective number of cycles, wherein the total spacing between a first prefetch instruction and a last prefetch instruction is equal to the number of cycles (N) required by the loop.

19. The optimizing compiler according to claim 18 wherein the means for spacing each prefetch instruction apart from a subsequent prefetch instruction by a respective number of cycles, wherein the total spacing between a first prefetch instruction and a last prefetch instruction is equal to the number of cycles (N) required by the loop includes means for spacing each prefetch instruction apart from a subsequent prefetch instruction by an equal number of cycles.