Vectorization of program code
AssigneeInternational Business Machines Corporation
InventorsDorit Nuzman, Ira Rosen, Ayal Zaks
Life of this patent
Estimating the term…
Abstract
A method for vectorization of a block of code is provided. The method comprises receiving a first block of code as input; and converting the first block of code into at least a second block of code and a third block of code. The first block of code accesses a first set of memory addresses that are potentially misaligned. The second block of code performs conditional leaping address incrementation to selectively access a first subset of the first set of memory addresses. The third block of code accesses a second subset of the first set of memory addresses starting from an aligned memory address, simultaneously accessing multiple memory addresses at a time. No memory address belongs to both the first subset and the second subset of memory addresses.
Claims23
A computer implemented method for vectorization of a program loop, the method comprising:
- receiving a program loop as input, wherein the program loop accesses one or more sets of memory addresses and each set of memory addresses is associated with a potential independent misalignment;
- and
- converting the program loop into at least a selective loop and a vector loop, wherein the selective loop is comprised of a prologue loop and an epilogue loop in the program loop,
- wherein the selective loop performs a conditional leaping address incrementation for each set of memory addresses so that memory addresses accessed by the vector loop are aligned,
- wherein the vector loop simultaneously accesses a certain number of memory addresses in each set of memory addresses per iteration, and
- wherein the conditional leaping address incrementation comprises:
- incrementing a memory address in a first subset of memory addresses;
- determining whether the memory address is aligned;
- and
- incrementing the memory address by a number of memory addresses in a second subset of memory addresses, in response to determining that the memory address is aligned,
- wherein for the selective loop a number of iterations during execution of the selective loop is known at compile-time, such that a number of loops whose number of iterations will remain a compile time known constant is maximized, and
- wherein the number of iterations during execution of the prologue loop and the epilogue loop is unknown.
A computer implemented method for vectorization of a program loop, the method comprising:
- receiving a program loop as input, wherein the program loop accesses memory addresses associated with a single independent misalignment;
- converting the program loop into prologue, vector, and epilogue loops;
- re-ordering the prologue, vector, or epilogue loops to facilitate merging of the prologue and epilogue loops;
- and
- merging the prologue and epilogue loops into a selective loop that performs conditional leaping address incrementation so that the vector loop accesses memory addresses that are aligned,
- wherein the conditional leaping address incrementation comprises:
- incrementing a memory address in a first subset of memory addresses;
- determining whether the memory address is aligned;
- and
- incrementing the memory address by a number of memory addresses in a second subset of memory addresses, in response to determining that the memory address is aligned,
- wherein for the selective loop a number of iterations during execution of the selective loop is known at compile-time, such that a number of loops whose number of iterations will remain a compile time known constant is maximized, and
- wherein the number of iterations during execution of the prologue loop and the epilogue loop is unknown.
A system for vectorization of a program loop, the system comprising:
- at least one processor;
- a logic unit for receiving a program loop as input, wherein the program loop accesses memory addresses associated with a single independent misalignment;
- a logic unit for converting the program loop into prologue, vector, and epilogue loops;
- a logic unit for re-ordering the prologue, vector, or epilogue loops to facilitate merging of the prologue and epilogue loops;
- and
- a logic unit for merging the prologue and epilogue loops into a selective loop that performs conditional leaping address incrementation so that the vector loop accesses memory addresses that are aligned,
- wherein the conditional leaping address incrementation comprises:
- a logic unit for incrementing a memory address in a first subset of memory addresses;
- a logic unit for determining whether the memory address is aligned;
- and
- a logic unit for incrementing the memory address by a number of memory addresses in a second subset of memory addresses, in response to determining that the memory address is aligned,
- wherein one or more logic units are executed over the at least one processor in the system;
- wherein for the selective loop a number of iterations during execution of the selective loop is known at compile-time, such that a number of loops whose number of iterations will remain a compile time known constant is maximized, and
- wherein the number of iterations during execution of the prologue loop and the epilogue loop is unknown.
Dependencies are inferred from the claim text.