METHOD USING SLP PACKING WITH STATEMENTS HAVING BOTH ISOMORPHIC AND NON-ISOMORPHIC EXPRESSIONS

• US 20090171919A1
• Filed: 12/26/2007
• Published: 07/02/2009
• Est. Priority Date: 12/26/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Eichenberger, Alexandre E., Wu, Peng, Wang, Kai-Ting Amy
• Granted Patent: US 8,266,587 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/456 Parallelism detection

Abstract

A computer implemented method is provided for using SLP in processing a plurality of statements, wherein the statements are associated with an array having a number of array positions, and each statement includes one or more expressions. The method includes the step of gathering expressions for each of the statements into a structure comprising a single merge stream, the merge streams being furnished with a location for each expression, wherein the location for a given expression is associated with one of the array positions. The method further comprises selectively identifying a plurality of expressions, and applying SLP packing operations to the identified expressions, in order to merge respective identified expressions into one or more isomorphic sub-streams. The method further comprises selectively combining the expressions of the isomorphic sub-streams, and other expressions of the single merge stream, into a number of input vectors that are substantially equal in length to one another. A location vector is generated that contains the respective locations for all of the expressions in the single merge stream. The method further comprises generating an output stream that comprises the expressions of the input vectors, wherein the expressions are arranged in the output stream an order determined by the respective locations contained in the location vector.

Claims

1. A computer implemented method for using Superword-Level Parallelism (SLP) in processing a plurality of statements, wherein the statements are associated with an array having a number of array positions, and each statement includes one or more expressions, said method comprising the steps of:

gathering the expressions for each of said statements into a structure comprising at least a single merge stream, said single merge stream being furnished with a location for each gathered expression, wherein the location for a given expression is associated with one of said positions of said array;

selectively identifying a plurality of said expressions in said single merge stream, and applying SLP packing operations to said identified expressions, in order to merge respective identified expressions into one or more isomorphic sub-streams;

selectively combining the expressions of said isomorphic sub-streams, and other expressions of said single merge stream, into a number of input vectors that are substantially equal in length to one another;

generating a location vector containing the respective locations for all of the expressions in said single merge stream; and

generating an output stream comprising the expressions of said input vectors, wherein said expressions are arranged in an order in said output stream that is determined by the respective locations contained in said location vector.

2. The method of claim 1, wherein:

said positions of said array respectively correspond to positions in a set of consecutive storage positions of a memory device.

3. The method of claim 1, wherein;

each identified expression comprises a semi-isomorphic expression, wherein two of said semi-isomorphic expressions are merged together by an SLP packing operation in order to provide one of said isomorphic sub-streams.

4. The method of claim 1, wherein:

said combining step is carried out by a permute operator that recursively aggregates streams of expressions, wherein a given recursion comprises aggregating expression streams that each contain a given number of expressions, in order to generate an aggregated stream comprising twice the given number of expressions.

5. The method of claim 4, wherein:

one or more lists containing the locations of respective expressions are maintained and updated, as respective streams of expressions are recursively combined.

6. The method of claim 4, wherein:

generation of a given one of said aggregated expression streams is accompanied by generation of a location stream, wherein the locations stream contains the location of all the expressions in the given expression streams, arranged in the same order as their respectively corresponding expressions.

7. The method of claim 4, wherein:

said expression streams are recursively combined in accordance with a binary tree procedure.

8. The method of claim 1, wherein:

at least some of said expressions are initially gathered into said single merge stream, in an order determined by the order of said positions of said array, and any remaining expressions are gathered into one or more other merge streams.

9. The method of claim 1, wherein:

the number of said input vectors, and the maximum data capacity of respective vectors, are selected to comply with requirements of a specified data processing device, and data found in said output stream is selectively grouped, to further comply with said requirements.

10. The method of claim 9, wherein:

there are two of said input vectors, each limited to a data capacity comprising a specified byte size.

11. A computer program product executable in a computer readable medium for using Superword-Level Parallelism (SLP) in processing a plurality of statements, wherein the statements are associated with an array having a number of array positions, and each statement includes one or more expressions, said computer program product comprising:

instructions for gathering the expressions for each of said statements into a structure comprising a single merge stream, said single merge stream being furnished with a location for each expression, wherein the location for a given expression is associated with one of said positions of said array;

instructions for selectively identifying a plurality of said expressions in said single merge stream, and applying SLP packing operations to said identified expressions, in order to merge respective identified expressions into one or more isomorphic sub-streams;

instructions for selectively combining the expressions of said isomorphic sub-streams, and other expressions of said single merge stream, into a number of input vectors that are substantially equal in length to one another;

instructions for generating a location vector containing the respective locations for all of the expressions in said single merge stream; and

instructions for generating an output stream comprising the expressions of said input vectors, wherein said expressions are arranged in said output stream in an order that is determined by the respective locations contained in said location vector.

12. The computer program product of claim 11, wherein:

said positions of said array respectively correspond to positions in a set of consecutive storage positions of a memory device.

13. The computer program product of claim 11, wherein;

each identified expression comprises a semi-isomorphic expression, wherein two of said semi-isomorphic expressions are merged together by an SLP packing operation in order to provide one of said isomorphic sub-streams.

14. The computer program product of claim 11, wherein:

said expressions are combined by a permute operator that recursively aggregates streams of expressions, wherein a given recursion comprises aggregating expression streams that each contain a given number of expressions, in order to generate an aggregated stream comprising twice the given number of expressions.

15. The computer program product of claim 14, wherein:

generation of a given one of said aggregated expression streams is accompanied by generation of a location stream, wherein the locations stream contains the location of all the expressions in the given expression streams, arranged in the same order as their respectively corresponding expressions.

16. A computer system adapted to use Superword-Level Parallelism (SLP) in processing a plurality of statements, wherein the statements are associated with an array having a number of array positions, and each statement includes one or more expressions, said system comprising the steps of:

a first component for gathering the expressions for each of said statements into a structure comprising a single merge stream, said single merge stream being furnished with a location for each expression, wherein the location for a given expression is associated with one of said positions of said array;

a second component for selectively identifying a plurality of said expressions in said single merge stream, and applying SLP packing operations to said identified expressions, in order to merge respective identified expressions into one or more isomorphic sub-streams;

a third component for selectively combining the expressions of said isomorphic sub-streams, and other expressions of said single merge stream, into a number of input vectors that are substantially equal in length to one another;

a fourth component for generating a location vector containing the respective locations for all of the expressions in said single merge stream; and

a fifth component for generating an output stream comprising the expressions of said input vectors, wherein said expressions are arranged in said output stream in an order in said output stream that is determined by the respective locations contained in said location vector.

17. The system of claim 16, wherein:

said positions of said array respectively correspond to positions in a set of consecutive storage positions of a memory device.

18. The system of claim 16, wherein;

each identified expression comprises a semi-isomorphic expression, wherein two of said semi-isomorphic expressions are merged together by an SLP packing operation in order to provide one of said isomorphic sub-streams.

19. The system of claim 16, wherein:

said third component combines the expressions by means of a permute operator that recursively aggregates streams of expressions, wherein a given recursion comprises aggregating expression streams that each contain a given number of expressions, in order to generate an aggregated stream comprising twice the given number of expressions

20. The system of claim 19, wherein:

generation of a given one of said aggregated expression streams is accompanied by generation of a location stream, wherein the locations stream contains the location of all the expressions in the given expression streams, arranged in the same order as their respectively corresponding expressions.