Apparatus and method for implementing adjacent, non-unit stride memory access patterns utilizing SIMD instructions

• US 20040006667A1
• Filed: 06/21/2002
• Published: 01/08/2004
• Est. Priority Date: 06/21/2002
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Bik, Aart J.C., Girkar, Milind
• Application Number:
  US10/177,556
• Publication Number:
  US 20040006667A1
• Time in Patent Office: Days
• US Class Current: 711/100
• CPC Class Codes: G06F 8/452 Loops

Abstract

An apparatus and method for implementing adjacent, single non-unit stride memory access patterns are described. In one embodiment, the method includes compiler analysis of a source program to detect vectorizable loops having serial code statements that collectively perform adjacent, non-unit stride memory access. Once a vectorizable loop containing code statements that collectively perform adjacent, non-unit stride memory access in detected, the compiler vectorizes the serial code statements of the detected loop to perform the adjacent, non-unit stride memory access utilizing SIMD instructions. As such, the compiler repeats the analysis and vectorization for each vectorizable loop within the source program code.

Claims

1. A method comprising:

analyzing a source program to detect vectorizable loops having one or more serial code statements that collectively perform adjacent, non-unit stride memory access; and

vectorizing serial code statements of each detected loop to perform adjacent, non-unit stride memory access utilizing SIMD instructions.

2. The method of claim 1, wherein analyzing further comprises:

selecting a vectorizable program loop from one or more detected vectorizable program loops of the source program;

analyzing serial code statements of the selected loop to determine whether one or more of the serial code statements collectively perform adjacent, non-unit stride memory access;

when one or more of the serial code statements of the selected loop collectively perform adjacent, non-unit stride memory access, identifying the one or more serial code statements of the selected loop for vectorization utilizing SIMD instructions; and

repeating the selecting and vectorizing for each vectorizable loop within the source program.

3. The method of claim 2, wherein analyzing further comprises:

scanning the serial code of the selected loop to detect successive, serial code statements that perform non-unit stride memory access;

when successive, serial code statements that perform non-unit stride memory access are detected, determining whether the successive code statements collectively access adjacent memory elements; and

when the successive serial code statements collectively access adjacent memory elements, identifying the selected loop as containing serial code statements that collectively perform adjacent, non-unit stride memory access.

4. The method of claim 1, wherein analyzing further comprises:

generating an internal representation of the source program code to enable vectorization analysis of serial code within the source program;

scanning the internal representation of source code of the source program to detect serial code loops;

when a serial code loop is detected, analyzing the detected loop to determine whether vector code can be utilized to replace serial code within the detected code loop;

when vector code replacement of serial code within the loop is detected, identifying the detected serial code loop as a vectorizable code loop within the internal source program representation; and

repeating the scanning, analyzing and identifying for each code loop within the source program.

5. The method of claim 1, wherein vectorizing further comprises:

selecting a loop from the one or more identified loops having one or more identified serial code statements that collectively perform adjacent, non-unit stride memory access;

generating, using an internal code representation, vector code statements to perform the adjacent, non-unit stride memory access of the one or more serial code statements of the selected loop;

replacing the one or more identified serial code statements with the generated vector code statements within an internal representation of the source program; and

repeating the selecting, generation and replacing for each identified loop.

6. The method of claim 5, wherein generating further comprises:

determining a count K of the one or more serial code statements of the selected loop that collectively perform the adjacent, non-unit stride memory access;

generating internal SIMD code statements to load adjacent memory elements into K-SIMD registers according to the one or more serial code statements; and

generating a plurality of internal SIMD code statements to reorder corresponding data elements, loaded within the plurality of SIMD registers, into respective registers according to a stride-K memory access pattern, to enable SIMD processing of the corresponding stride-K data elements.

7. The method of claim 6, wherein generating SIMD instructions to load adjacent memory elements further comprises:

generating an SIMD instruction to load N-adjacent data elements into a first SIMD register;

generating a second SIMD instruction to load a next N-adjacent data elements into a second SIMD register;

generating one or more SIMD code statements to store corresponding data elements from the first and second SIMD registers into a temporary SIMD register, according to a stride-2 memory access pattern; and

generating one or more SIMD code statements to store remaining data elements from the first and second SIMD registers into one of the first and second SIMD register, according to a stride-2 memory access pattern.

8. The method of claim 5, wherein generating further comprises:

determining a count K of the one or more serial code statements of the selected loop that collectively perform the adjacent, non-unit stride memory access;

generating a plurality of SIMD instructions to reorder, according to a unit-stride memory access, data elements stored within K-SIMD registers according to a K-stride memory access pattern to enable sequential memory storage of the reordered data elements into memory; and

generating a plurality of SIMD instructions to store the reordered data elements, contained within the K-SIMD registers, into memory.

9. The method of claim 8, wherein generating SIMD instruction to reorder data elements further comprises:

generating one or more stride-2 internal vector code statements to store, according to a unit-stride memory access pattern, data elements from a first SIMD register and a second SIMD register into a third SIMD register; and

generating one or more internal vector code statements to store, according to the unit-stride memory access pattern, remaining stride-2 data elements from the first SIMD register and the second SIMD register into one of the first SIMD register and the second SIMD register.

10. The method of claim 1, further comprising:

replacing remaining serial code statements within an internal representation of the source program, and contained within a vectorizable loop, with corresponding internal vector code statements; and

once an optimized internal representation of the source program code is complete, generating a target program from the optimized internal representation to utilize SIMD code statements to perform the collective adjacent, non-unit stride memory access of the source code of the source program.

11. A computer readable storage medium including program instructions that direct a computer to perform one or more operations when executed by a processor, the one or more operations comprising:

analyzing a source program to detect vectorizable loops having one or more serial code statements that collectively perform adjacent, non-unit stride memory access; and

vectorizing serial code statements of each detected loop to perform adjacent, non-unit stride memory access utilizing SIMD instructions.

12. The computer readable storage medium of claim 11, wherein analyzing further comprises:

selecting a vectorizable program loop from one or more detected vectorizable program loops of the source program;

analyzing serial code statements of the selected loop to determine whether one or more of the serial code statements collectively perform adjacent, non-unit stride memory access;

when one or more of the serial code statements of the selected loop collectively perform adjacent, non-unit stride memory access, identifying the one or more serial code statements of the selected loop for vectorization utilizing SIMD instructions; and

repeating the selecting and vectorizing for each vectorizable loop within the source program.

13. The computer readable storage medium of claim 12, wherein analyzing further comprises:

scanning the serial code of the selected loop to detect successive, serial code statements that perform non-unit stride memory access;

when successive, serial code statements that perform non-unit stride memory access are detected, determining whether the successive code statements collectively access adjacent memory elements; and

when the successive serial code statements collectively access adjacent memory elements, identifying the selected loop as containing serial code statements that collectively perform adjacent, non-unit stride memory access.

14. The computer readable storage medium of claim 11, wherein analyzing further comprises:

generating an internal representation of the source program code to enable vectorization analysis of serial code within the source program;

scanning the internal representation of source code of the source program to detect serial code loops;

when a serial code loop is detected, analyzing the detected loop to determine whether vector code can be utilized to replace serial code within the detected code loop;

when vector code replacement of serial code within the loop is detected, identifying the detected serial code loop as a vectorizable code loop within the internal source program representation; and

repeating the scanning, analyzing and identifying for each code loop within the source program.

15. The computer readable storage medium of claim 11, wherein vectorizing further comprises:

selecting a loop from the one or more detected loops having one or more serial code statements that collectively perform adjacent, non-unit stride memory access;

generating, using an internal code representation, vector code statements to perform the adjacent, non-unit stride memory access of the one or more serial code statements of the selected loop;

replacing the one or more identified serial code statements with the generated vector code statements within an internal representation of the source program; and

repeating the selecting, generation and replacing for each detected loop.

16. The computer readable storage medium of claim 15, wherein generating further comprises:

determining a count K of the one or more serial code statements of the selected loop that collectively perform the adjacent, non-unit stride memory access;

generating internal SIMD code statements to load adjacent memory elements into K-SIMD registers according to the one or more serial code statements; and

generating a plurality of internal SIMD code statements to reorder corresponding data elements, loaded within the plurality of SIMD registers, into a respective register according to a stride-K memory access pattern to enable SIMD processing of the corresponding stride-K data elements.

17. The computer readable storage medium of claim 16, wherein generating SIMD instructions to load adjacent memory elements further comprises:

generating an SIMD instruction to load N-adjacent data elements into a first SIMD register;

generating a second SIMD instruction to load a next N-adjacent data elements into a second SIMD register;

generating one or more SIMD code statements to store corresponding data elements from the first and second SIMD registers into a temporary SIMD register, according to a stride-2 memory access pattern; and

generating one or more SIMD code statements to store remaining data elements from the first and second SIMD registers into one or the first and second SIMD register, according to a stride-2 memory access pattern.

18. The computer readable storage medium of claim 15, wherein generating further comprises:

determining a count K of the one or more serial code statements of the selected loop that collectively perform the adjacent, non-unit stride memory access;

generating a plurality of SIMD) instructions to reorder according to a unit-stride memory access, data elements stored within K-SIMD registers according to a K-stride memory access pattern to enable sequential memory storage of the reordered data elements into memory; and

generating a plurality of SIMD instructions to store the reordered data elements, contained within the K-SIMD registers, into memory.

19. The computer readable storage medium of claim 18, wherein generating SIMD instruction to reorder data elements further comprises:

generating one or more stride-2 internal vector code statements to store, according to a unit-stride memory access pattern, data elements according from a first SIMD register and a second SIMD register into a third SIMD register; and

generating one or more internal vector code statements to store, according to the unit-stride memory access pattern, remaining stride-2 data elements from the first SIMD register and the second SIMD register into one of the first SIMD register and the second SIMD register.

20. The computer readable storage medium of claim 11, further comprising:

replacing remaining serial code statements within an internal representation of the source program and contained within a vectorizable loop, with corresponding internal vector code statement; and

once an optimized internal representation of the source program code is complete, generating a target program from the optimized internal representation to utilize SIMD code statements to perform the collective adjacent, non-unit stride memory access of the source code of the source program.

21. A system, comprising:

a processor having circuitry to execute instructions;

a system interface coupled to the processor, the system interface to receive source programs, and to provide target optimize programs once compiled from the source program;

a storage device coupled to the processor, having sequences of compiler instructions stored therein, which when executed by the processor cause the processor to;

analyze a source program to detect vectorizable loops having one or more serial code statements that collectively perform adjacent, non-unit stride memory access, and

vectorize serial code statements of each detected loop to perform adjacent, non-unit stride memory access utilizing SIMD instructions.

22. The system of claim 21, wherein the instruction to analyze further causes the processor to:

select a vectorizable program loop from one or more detected vectorizable program loops of the source program;

analyze serial code statements of the selected loop to determine whether one or more of the serial code statements collectively perform adjacent, non-unit stride memory access;

when one or more of the serial code statements of the selected loop collectively perform adjacent, non-unit stride memory access, identify the one or more serial code statements of the selected loop for vectorization utilizing SIMD instructions; and

repeat the select and vectorize instructions for each vectorizable loop within the source program.

23. The system of claim 22, wherein the instruction to analyze further causes the processor to:

scan the serial code of the selected loop to detect successive, serial code statements that perform non-unit stride memory access;

when successive, serial code statements that perform non-unit stride memory access are detected, determine whether the successive code statements collectively access adjacent memory elements; and

when the successive serial code statements collectively access adjacent memory elements, identify the selected loop as containing serial code statements that collectively perform adjacent, non-unit stride memory access.

24. The system of claim 21, wherein the instruction to analyze further causes the processor to:

generate an internal representation of the source program code to enable vectorization analysis of serial code within the source program;

scan the internal representation of source code of the source program to detect serial code loops;

when a serial code loop is detected, analyze the detected loop to determine whether vector code can be utilized to replace serial code within the detected code loop;

when vector code replacement of serial code within the loop is detected, identify the detected serial code loop as a vectorizable code loop within the internal source program representation; and

repeat the scan, analyze and identify instructions for each code loop within the source program.

25. The system of claim 21, wherein the instruction to vectorize further causes the processor to:

select a loop from the one or more identified loops having one or more identified serial code statements that collectively perform adjacent, non-unit stride memory access;

generate, using an internal code representation, vector code statements to perform the adjacent, non-unit stride memory access of the one or more serial code statements of the selected loop;

replace the one or more identified serial code statements with the generated vector code statements within an internal representation of the source program; and

repeat the select, generate and replace instructions for each identified loop.

26. The system of claim 25, wherein the instruction to generate further causes the processor to:

determine a count K of the one or more serial code statements of the selected loop that collectively perform the adjacent, non-unit stride memory access;

generate internal SIMD code statements to load adjacent memory elements into K-SIMD registers according to the one or more serial code statements; and

generate a plurality of internal SIMD code statements to reorder corresponding data elements, loaded within the plurality of SIMD registers, into respective registers according to a stride-K memory access pattern, to enable SIMD processing of the corresponding stride-K data elements.

27. The system of claim 26, wherein the instruction to generate further causes the processor to:

generate an SIMD instruction to load N-adjacent data elements into a first SIMD register;

generate a second SIMD instruction to load a next N-adjacent data elements into a second SIMD register;

generate one or more SIMD code statements to store corresponding data elements from the first and second SIMD registers into a temporary SIMD register, according to a stride-2 memory access pattern; and

generate one or more SIMD code statements to store remaining data elements from the first and second SIMD registers into one of the first and second SIMD register, according to a stride-2 memory access pattern.

28. The system of claim 25, wherein the instruction to generate further causes the processor to:

determine a count K of the one or more serial code statements of the selected loop that collectively perform the adjacent, non-unit stride memory access;

generate a plurality of SIMD instructions to reorder, according to a unit-stride memory access, data elements stored within K-SIMD registers according to a K-stride memory access pattern to enable sequential memory storage of the reordered data elements into memory; and

generate a plurality of SIMD instructions to store the reordered data elements, contained within the K-SIMD registers, into memory.

29. The system of claim 28, wherein the instruction to generate further causes the processor to:

generate one or more stride-2 internal vector code statements to store, according to a unit-stride memory access pattern, data elements from a first SIMD register and a second SIMD register into a third SIMD register; and

generate one or more internal vector code statements to store, according to the unit-stride memory access pattern, remaining stride-2 data elements from the first SIMD register and the second SIMD register into one of the first SIMD register and the second SIMD register.

30. The system of claim 21, wherein the processor is further caused to:

replace remaining serial code statements within an internal representation of the source program, and contained within a vectorizable loop, with corresponding internal vector code statements; and

once an optimized internal representation of the source program code is complete, generate a target program from the optimized internal representation to utilize SIMD code statements to perform the collective adjacent, non-unit stride memory access of the source code of the source program.