Pre-computation slice merging for prefetching in a computer processor

{
  "publication_number": "US9430240B1",
  "country": "US",
  "kind": "B1",
  "title": "Pre-computation slice merging for prefetching in a computer processor",
  "abstract": "Embodiments relate to pre-computation slice (p-slice) merging for prefetching in a computer processor. An aspect includes determining a plurality of p-slices corresponding to a delinquent instruction. Another aspect includes selecting a first p-slice and a second p-slice of the plurality of p-slices. Another aspect includes traversing the first p-slice and the second p-slice to determine that divergent instructions exist between the first p-slice and the second p-slice. Another aspect includes, based on determining that divergent instructions exist between the first p-slice and the second p-slice, determining whether the first p-slice and the second p-slice converge after the divergent instructions. Another aspect includes, based on determining that the first p-slice and the second p-slice converge after the divergent instructions, merging the first p-slice and the second p-slice into a single merged p-slice.",
  "claims": [
    "1. A computer implemented method for pre-computation slice (p-slice) merging for prefetching in a computer processor, the method comprising: determining a plurality of p-slices corresponding to a delinquent instruction; selecting a first p-slice and a second p-slice of the plurality of p-slices; traversing the first p-slice and the second p-slice to determine that divergent instructions exist between the first p-slice and the second p-slice; based on determining that divergent instructions exist between the first p-slice and the second p-slice, determining whether the first p-slice and the second p-slice converge after the divergent instructions; and based on determining that the first p-slice and the second p-slice converge after the divergent instructions, merging the first p-slice and the second p-slice into a single merged p-slice.",
    "2. The method of claim 1, further comprising, before merging the first p-slice and the second p-slice: determining whether a number of the divergent instructions is greater than a threshold; based on the number of the divergent instructions being greater than the threshold, not merging the first p-slice and the second p-slice; and based on the number of the divergent instructions not being greater than the threshold, merging the first p-slice and the second p-slice.",
    "3. The method of claim 1, further comprising determining a signature for each of the plurality of p-slices, wherein the signature of a given p-slice comprises: a program counter of a first instruction in the given p-slice; targets of any branches, jumps, or calls in the given p-slice; and, for a conditional branch, if the conditional branch is not taken, a program counter of a following instruction of the conditional branch.",
    "4. The method of claim 3, further comprising determining a set of unique p-slices for the delinquent instruction based on the determined signatures.",
    "5. The method of claim 3, wherein determining whether the first p-slice and the second p-slice converge after the divergent instructions comprises: determining a first program counter in the first p-slice that does not match a second program counter in the second p-slice based on traversal of the signature of the first p-slice and the second p-slice; continuing traversal of the signature of the first p-slice to determine whether the second program counter exists in the first p-slice; continuing traversal of the signature of the second p-slice to determine whether the first program counter exists in the second p-slice; based on determining that the second program counter exists in the first p-slice and the first program counter exists in the second p-slice, determining that the first p-slice and the second p-slice converge.",
    "6. The method of claim 1, further comprising executing the merged p-slice in a prefetch module of a configurable prefetching engine, the configurable prefetch engine comprising: a prefetch configuration logic; and a plurality of prefetch modules, each of the prefetch modules comprising distinct hardware modules, wherein the prefetch configuration logic is configured to enable and disable the plurality of prefetch modules based on data access patterns in a cache of the computer processor.",
    "7. The method of claim 6, wherein the plurality of prefetch modules each run a different prefetching method comprising one of strided, constant, stream, and a p-slice.",
    "8. A computer program product for implementing pre-computation slice (p-slice) merging for prefetching in a computer processor, the computer program product comprising: a computer readable non-transitory medium having program instructions embodied therewith, the program instructions readable by a processing circuit to cause the processing circuit to perform a method comprising: determining a plurality of p-slices corresponding to a delinquent instruction; selecting a first p-slice and a second p-slice of the plurality of p-slices; traversing the first p-slice and the second p-slice to determine that divergent instructions exist between the first p-slice and the second p-slice; based on determining that divergent instructions exist between the first p-slice and the second p-slice, determining whether the first p-slice and the second p-slice converge after the divergent instructions; and based on determining that the first p-slice and the second p-slice converge after the divergent instructions, merging the first p-slice and the second p-slice into a single merged p-slice.",
    "9. The computer program product of claim 8, the method further comprising, before merging the first p-slice and the second p-slice: determining whether a number of the divergent instructions is greater than a threshold; based on the number of the divergent instructions being greater than the threshold, not merging the first p-slice and the second p-slice; and based on the number of the divergent instructions not being greater than the threshold, merging the first p-slice and the second p-slice.",
    "10. The computer program product of claim 8, the method further comprising determining a signature for each of the plurality of p-slices, wherein the signature of a given p-slice comprises: a program counter of a first instruction in the given p-slice; targets of any branches, jumps, or calls in the given p-slice; and, for a conditional branch, if the conditional branch is not taken, a program counter of a following instruction of the conditional branch.",
    "11. The computer program product of claim 10, the method further comprising determining a set of unique p-slices for the delinquent instruction based on the determined signatures.",
    "12. The computer program product of claim 10, wherein determining whether the first p-slice and the second p-slice converge after the divergent instructions comprises: determining a first program counter in the first p-slice that does not match a second program counter in the second p-slice based on traversal of the signature of the first p-slice and the second p-slice; continuing traversal of the signature of the first p-slice to determine whether the second program counter exists in the first p-slice; continuing traversal of the signature of the second p-slice to determine whether the first program counter exists in the second p-slice; based on determining that the second program counter exists in the first p-slice and the first program counter exists in the second p-slice, determining that the first p-slice and the second p-slice converge.",
    "13. The computer program product of claim 8, the method further comprising executing the merged p-slice in a prefetch module of a configurable prefetching engine, the configurable prefetch engine comprising: a prefetch configuration logic; and a plurality of prefetch modules, each of the prefetch modules comprising distinct hardware modules, wherein the prefetch configuration logic is configured to enable and disable the plurality of prefetch modules based on data access patterns in a cache of the computer processor.",
    "14. The computer program product of claim 13, wherein the plurality of prefetch modules each run a different prefetching method comprising one of strided, constant, stream, and a p-slice.",
    "15. A computer system for pre-computation slice (p-slice) merging for prefetching in a computer processor, the system comprising: a memory; and the computer processor communicatively coupled to said memory, the computer system configured to perform a method comprising: determining a plurality of p-slices corresponding to a delinquent instruction; selecting a first p-slice and a second p-slice of the plurality of p-slices; traversing the first p-slice and the second p-slice to determine that divergent instructions exist between the first p-slice and the second p-slice; based on determining that divergent instructions exist between the first p-slice and the second p-slice, determining whether the first p-slice and the second p-slice converge after the divergent instructions; and based on determining that the first p-slice and the second p-slice converge after the divergent instructions, merging the first p-slice and the second p-slice into a single merged p-slice.",
    "16. The system of claim 15, the method further comprising, before merging the first p-slice and the second p-slice: determining whether a number of the divergent instructions is greater than a threshold; based on the number of the divergent instructions being greater than the threshold, not merging the first p-slice and the second p-slice; and based on the number of the divergent instructions not being greater than the threshold, merging the first p-slice and the second p-slice.",
    "17. The system of claim 15, the method further comprising determining a signature for each of the plurality of p-slices, wherein the signature of a given p-slice comprises: a program counter of a first instruction in the given p-slice; targets of any branches, jumps, or calls in the given p-slice; and, for a conditional branch, if the conditional branch is not taken, a program counter of a following instruction of the conditional branch.",
    "18. The system of claim 17, the method further comprising determining a set of unique p-slices for the delinquent instruction based on the determined signatures.",
    "19. The system of claim 17, wherein determining whether the first p-slice and the second p-slice converge after the divergent instructions comprises: determining a first program counter in the first p-slice that does not match a second program counter in the second p-slice based on traversal of the signature of the first p-slice and the second p-slice; continuing traversal of the signature of the first p-slice to determine whether the second program counter exists in the first p-slice; continuing traversal of the signature of the second p-slice to determine whether the first program counter exists in the second p-slice; based on determining that the second program counter exists in the first p-slice and the first program counter exists in the second p-slice, determining that the first p-slice and the second p-slice converge.",
    "20. The system of claim 15, the method further comprising executing the merged p-slice in a prefetch module of a configurable prefetching engine, the configurable prefetch engine comprising: a prefetch configuration logic; and a plurality of prefetch modules, each of the prefetch modules comprising distinct hardware modules, wherein the prefetch configuration logic is configured to enable and disable the plurality of prefetch modules based on data access patterns in a cache of the computer processor."
  ],
  "description_excerpt": "The present invention relates generally to prefetching in a computer processor, and more specifically, to pre-computation slice (p-slice) merging for prefetching in a computer processor.\n\nDuring execution on a processor, an application may fetch data from a relatively large, slow main memory to a smaller, faster cache memory that is local to the processor in order to perform operations using the data. The time required to fetch the data (i.e., data access latency) may dominate the application execution time. Data prefetching uses a combination of hardware and/or software to hide this latency by predicting the data that an application will need and fetching the data ahead of time into the desired level of cache hierarchy. A prefetcher may track regular data access patterns (e.g., streaming, stride, or constant) that are observed during application execution, and prefetch future data references based on the prediction that a pattern will recur. However, a prefetcher may not be successful in tracking or prefetching for irregular data access patterns.\n\nSpeculative pre-computation slices, or p-slices, are used to perform prefetching for instructions having irregular data access patterns that may incur cache misses, also referred to as delinquent instructions. For a given delinquent instruction, a backward slice of instructions called a p-slice, made up of all instructions that directly or indirectly produce the source operands of the delinquent instruction, is extracted.",
  "cpc": [
    "G06F 9/3802",
    "G06F 9/30058",
    "G06F 9/383",
    "G06F 9/3838",
    "G06F 9/3842",
    "G06F 9/3851"
  ],
  "ipc": [
    "G06F 9/30",
    "G06F 9/38"
  ],
  "assignees": [
    "International Business Machines Corp"
  ],
  "inventors": [
    "Islam Atta",
    "Ioana M. Baldini Soares",
    "Kailash Gopalakrishnan",
    "Vijayalakshmi Srinivasan"
  ],
  "filing_date": "2015-12-10",
  "publication_date": "2016-08-30",
  "grant_date": "2016-08-30",
  "priority_date": "2015-12-10",
  "application_number": "US-201514964740-A",
  "family_id": "56739866",
  "cited_by_count": 12,
  "citations": [
    "US20020144083A1",
    "US8046752B2",
    "US20060020775A1",
    "US8762968B2",
    "US20100269102A1",
    "US8505001B2"
  ]
}