Determining maximum acceptable scheduling load latency using hierarchical search
AssigneeSun Microsystems, Inc.
InventorBrian E. Bliss
Life of this patent
Estimating the term…
Abstract
The present application describes techniques for determining maximum acceptable modeled load latency (e.g., a model number of clock cycles required between the time a load issues and the time its use can issue) for instruction scheduling which uses less compile time, on the order of log2 (Maximum load latency—Minimum load latency). Typically, during instruction scheduling, register pressure is monotonically non-decreasing with respect to the scheduled load latency. Therefore, in some embodiments, a hierarchical search method is used to determine the acceptable schedule with the largest modeled load latency. According to an embodiment, a binary search is employed which reduces the compile time required to determine maximum load latency for which registers can be assigned.
Claims27
A method of preparing code for efficient execution on a target processor, said method comprising:
- evaluating candidate sequences of instructions based on, at least in part, register usage expected for execution of respective ones of the candidate sequences on the target processor, wherein the candidate sequences each correspond to the code, but differ with respect to a load latency criterion, and
- selecting successive ones of the candidate sequences for the evaluating based on successive values for the load latency criterion, wherein the successive values of the load latency criterion are selected using a hierarchical search strategy, the hierarchical search strategy including a binary search strategy.
A code preparation facility, comprising:
- at least one processor configured to:
- evaluate candidate sequences of instructions based on, at least in part, register usage expected for execution of respective ones of the candidate sequence on the target processor, wherein the candidate sequences each correspond to the code, but differ with respect to a load latency criterion, and select successive ones of the candidate sequences for the evaluating based on successive values for the load latency criterion, wherein the successive values of the load latency criterion are selected using a hierarchical search strategy, the hierarchical search strategy including a binary search strategy.
A code preparation facility comprising:
- at least one processor that employs a hierarchical, load latency criterion based search strategy in evaluating successive candidate code schedules, wherein the hierarchical search strategy includes a binary search strategy.
Dependencies are inferred from the claim text.