Method and apparatus for finding loop— lever parallelism in a pointer based application
AssigneeIntel Corporation
InventorsMohammad R. Haghighat, Milind Girkar
Life of this patent
Estimating the term…
Abstract
A method and apparatus for finding loop_level parallelism in a sequence of instructions. In one embodiment, the method includes the steps of determining if a variable which identifies a memory address of a data structure is an induction variable; and determining if execution of the sequence of instructions terminates in response to a comparison of the variable to an invariant value. If the two conditions of the present invention are found to be true, the respective sequence of instructions is a candidate to be flagged for multi-threading execution, assuming the loop of the instructions terminates.
Claims21
A computer-implemented method for finding loop_level parallelism in a sequence of instructions during a binary translation, the method comprising:
- receiving said sequence of instructions for translating said instructions executable in a source instruction set Architecture into instructions executable in a target instruction set Architecture during a binary translation;
- determining if a variable identifying a memory address of a data structure is an induction variable;
- and
- determining if an execution of the sequence of instructions terminates in response to a comparison of said variable to an invariant value, said invariant value invariant within said sequence of instructions, to identify said sequence of instructions as having loop_level parallelism.
A computer-readable medium having stored thereon a plurality of instructions, including a first set of instructions for finding loop_level parallelism, during a binary translation, in a sequence of instructions to be executed, said first set of instructions, when executed by a processor, cause said processor to perform a computer method of:
- receiving said sequence of instructions for translating said instructions executable in a source instruction set Architecture into instructions executable in a target instruction set Architecture during a binary translation;
- determining if a variable identifying a memory address of a data structure is an induction variable;
- and
- determining if an execution of the sequence of instructions terminates in response to a comparison of said variable to an invariant value, said invariant value invariant within said sequence of instructions, to identify said sequence of instructions as having loop_level parallelism.
A binary translator implemented on a computer-system to find loop_level parallelism in a sequence of instructions, the translator comprising of:
- a first set of instructions translate said instructions executable in a source instruction set Architecture into instructions executable in a target instruction set Architecture during a binary translation;
- a first set of instructions to determine if a variable identifying a memory address of a data structure is an induction variable;
- and a second set of instructions to determine if an execution of the sequence of instructions terminates in response to a comparison of said variable to an invariant value, said invariant value invariant within said sequence of instructions, to identify said sequence of instructions as having loop_level parallelism.
Dependencies are inferred from the claim text.