Method to exploit superword-level parallelism using semi-isomorphic packing
AssigneeInternational Business Machines Corporation
InventorsAlexandre E. Eichenberger, Kai-Ting Amy Wang, Peng Wu, Peng Zhao
Life of this patent
Estimating the term…
Abstract
A computer program product is provided for extracting SIMD parallelism. The computer program product includes instructions for providing a stream of input code comprising basic blocks; identifying pairs of statements that are semi-isomorphic with respect to each other within a basic block; iteratively combining into packs, pairs of statements that are semi-isomorphic with respect to each other, and combining packs into combined packs; collecting packs whose statements can be scheduled together for processing; and generating SIMD instructions for each pack to provide for extracting the SIMD parallelism..
Claims14
A computer program product stored on machine readable media and providing instructions for extracting SIMD parallelism from statements that are not isomorphic with respect to each other, the instructions comprising:
- providing a stream of input code comprising basic blocks;
- identifying within a basic block pairs of statements that are semi-isomorphic with respect to each other;
- iteratively combining into packs the pairs of statements and combining the packs into combined packs;
- collecting the combined packs whose statements can be scheduled together for processing;
- and
- generating SIMD instructions for each collected combined pack to provide for extracting SIMD parallelism.
A computer implemented method to extract SIMD parallelism from statements that are not isomorphic with respect to each other, the method comprising:
- providing a stream of input code comprising basic blocks;
- identifying within a basic block, pairs of statements that are stride-one semi-isomorphic with respect to each other;
- iteratively combining into packs the pairs of statements and combining packs into combined packs;
- collecting combined packs whose statements can be scheduled together for processing;
- aggregating into packs loop statements that are stride-one semi-isomorphic with respect to each other at the loop level;
- and
- generating SIMD instructions for each pack of loop statements and each of the combined packs to extract SIMD parallelism.
A computer program product stored on machine readable media and providing instructions for extracting SIMD parallelism from statements that are not isomorphic with respect to each other, the instructions comprising:
- providing a stream of input code comprising basic blocks;
- identifying within a basic block, pairs of statements that are semi-isomorphic with respect to each other by satisfying at least one condition where:
- X and Y are identical, X and Y are literals, X and Y are loaded from adjacent memory locations, X and Y are stored in adjacent memory locations and the stored values are semi-isomorphic with respect to each other, X and Y have the same number of operands and their corresponding operands are semi-isomorphic with respect to each other;
- iteratively combining into packs, the pairs of statements and combining packs into combined packs;
- collecting combined packs whose statements can be scheduled together for processing;
- and
- generating SIMD instructions for each collected pack to provide for extracting SIMD parallelism.
Dependencies are inferred from the claim text.