SEQUENCE OPTIMIZATIONS IN A HIGH-PERFORMANCE COMPUTING ENVIRONMENT

• US 20190042218A1
• Filed: 06/25/2018
• Published: 02/07/2019
• Est. Priority Date: 06/25/2018
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Zhang, Yongzhi
• Granted Patent: US 10,776,087 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/44 Encoding
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/4432 Reducing the energy consumption

Abstract

Embodiments are directed to techniques to determine dataflow graph instructions comprising one or more pick/switch instruction pairs and generate a reverse static single assignment graph based on the dataflow graph instructions, the reverse static single assignment graph comprising strongly connected components, each of the strongly connected components associated with at least one of the one or more pick/switch instruction pairs. Embodiments also include traversing the reverse static single assignment graph depth-first, and replace pick/switch instructions associated with strongly connected components having configuration values with compound instructions.

Claims

1. An apparatus, comprising:

memory to store executable computer program instructions; and

processing circuitry coupled with the memory, the processing circuitry operable to execute the instructions, that when executed, enable processing circuitry to;

determine dataflow graph instructions comprising one or more pick/switch instruction pairs;

generate a reverse static single assignment graph based on the dataflow graph instructions, the reverse static single assignment graph comprising strongly connected components, each of the strongly connected components associated with at least one of the one or more pick/switch instruction pairs; and

traverse the reverse static single assignment graph depth-first, and replace pick/switch instructions associated with strongly connected components having configuration values with compound instructions.

2. The apparatus of claim 1, the processing circuitry to:

determine a strongly connected component associated with an induction variable has configuration values comprising an initial value, a boundary value, and a stride; and

replace pick/switch instructions associated with the induction variable with one or more compound instructions.

3. The apparatus claim 2, the processing circuitry to:

determine whether the induction variable is affine or linear;

in response to the determination that the induction variable is affine, replace the pick/switch instructions associated with the induction variable with a plurality of compound instructions; and

in response to the determination that the induction variable is linear, replace the pick/switch instructions associated with the induction variable with a single compound instruction to drive stride for one or more other instructions during execution.

4. The apparatus of claim 1, the processing circuitry to:

determine a strongly connected component associated with an address has configuration values comprising an initial value, and a stride; and

replace pick/switch instructions associated with the address with one or more compound instructions.

5. The apparatus of claim 1, the processing circuitry to:

generate a dataflow graph for the dataflow graph instructions prior to generation of the reverse static single assignment graph; and

generate the reverse static single assignment graph by reversing flow direction of edges of the dataflow graph.

6. The apparatus of claim 1, the processing circuitry to process a strongly connected component for an induction variable prior to processing strongly connected components for one or more address instructions when traversing the reverse static single assignment graph depth-first.

7. The apparatus of claim 1, wherein the dataflow graph instructions are based on one or more loop instructions in a high-level computer programming language.

8. The apparatus of claim 1, wherein each of the one or more compound instructions comprising one of a sequence instruction, a sequence reduction instruction, a repeat instruction, a sequence stride instruction, a nestrepeat instruction, a filter instruction, a replace instruction, and a replicate instruction.

9. The apparatus of claim 1, wherein the processing circuitry operable to execute the one or more instructions during a compilation operation for a configurable spatial accelerator to perform high-performance computing, the configurable spatial accelerator comprising an array of processing elements coupled by a network.

10. A computer-implemented method, comprising:

determining dataflow graph instructions comprising one or more pick/switch instruction pairs;

generating a reverse static single assignment graph based on the dataflow graph instructions, the reverse static single assignment graph comprising strongly connected components, each of the strongly connected components associated with at least one of the one or more pick/switch instruction pairs; and

traversing the reverse static single assignment graph depth-first, and replace pick/switch instructions associated with strongly connected components having configuration values with compound instructions.

11. The computer-implemented method of claim 10, comprising:

determining a strongly connected component associated with an induction variable has configuration values comprising an initial value, a boundary value, and a stride; and

replacing pick/switch instructions associated with the induction variable with one or more compound instructions.

12. The computer-implemented method of claim 11, comprising:

determining whether the induction variable is affine or linear;

in response to the determination that the induction variable is affine, replacing the pick/switch instructions associated with the induction variable with a plurality of compound instructions; and

in response to the determination that the induction variable is linear, replacing the pick/switch instructions associated with the induction variable with a single compound instruction to drive stride for one or more other instructions during execution.

13. The computer-implemented method of claim 10, comprising:

determining a strongly connected component associated with an address includes configuration values comprising an initial value, and a stride; and

replacing pick/switch instructions associated with the address with one or more compound instructions.

14. The computer-implemented method of claim 10, comprising:

generating a dataflow graph for the dataflow graph instructions prior to generation of the reverse static single assignment graph; and

generating the reverse static single assignment graph by reversing flow direction of edges of the dataflow graph.

15. The computer-implemented method of claim 10, comprising processing a strongly connected component for an induction variable prior to processing strongly connected components for one or more address instructions when traversing the reverse static single assignment graph depth-first.

16. The computer-implemented method of claim 10, wherein each of the one or more compound instructions comprising one of a sequence instruction, a sequence reduction instruction, a repeat instruction, a sequence stride instruction, a nestrepeat instruction, a filter instruction, a replace instruction, and a replicate instruction.

17. The computer-implemented method of claim 10, wherein the dataflow graph instructions are based on one or more loop instructions in a high-level computer programming language.

18. A non-transitory computer-readable storage medium, comprising a plurality of instructions, that when executed, enable processing circuitry to:

determine dataflow graph instructions comprising one or more pick/switch instruction pairs;

generate a reverse static single assignment graph based on the dataflow graph instructions, the reverse static single assignment graph comprising strongly connected components, each of the strongly connected components associated with at least one of the one or more pick/switch instruction pairs; and

traverse the reverse static single assignment graph depth-first, and replace pick/switch instructions associated with strongly connected components having configuration values with compound instructions.

19. The non-transitory computer-readable storage medium of claim 18, comprising a plurality of instructions, that when executed, enable processing circuitry to:

determine a strongly connected component associated with an induction variable has configuration values comprising an initial value, a boundary value, and a stride; and

replace pick/switch instructions associated with the induction variable with one or more compound instructions.

20. The non-transitory computer-readable storage medium of claim 19, comprising a plurality of instructions, that when executed, enable processing circuitry to:

determine whether the induction variable is affine or linear;

in response to the determination that the induction variable is affine, replace the pick/switch instructions associated with the induction variable with a plurality of compound instructions; and

in response to the determination that the induction variable is linear, replace the pick/switch instructions associated with the induction variable with a single compound instruction to drive stride for one or more other instructions during execution.

21. The non-transitory computer-readable storage medium of claim 18, comprising a plurality of instructions, that when executed, enable processing circuitry to:

determine a strongly connected component associated with an address has configuration values comprising an initial value, and a stride; and

replace pick/switch instructions associated with the address with one or more compound instructions.

22. The non-transitory computer-readable storage medium of claim 18, comprising a plurality of instructions, that when executed, enable processing circuitry to:

generate a dataflow graph for the dataflow graph instructions prior to generation of the reverse static single assignment graph; and

generate the reverse static single assignment graph by reversing flow direction of edges of the dataflow graph.

23. The non-transitory computer-readable storage medium of claim 18, comprising a plurality of instructions, that when executed, enable processing circuitry to process a strongly connected component for an induction variable prior to processing strongly connected components for one or more address instructions when traversing the reverse static single assignment graph depth-first.

24. The non-transitory computer-readable storage medium of claim 18, wherein the dataflow graph instructions are based on one or more loop instructions in a high-level computer programming language.

25. The non-transitory computer-readable storage medium of claim 18, wherein each of the one or more compound instructions comprising one of a sequence instruction, a sequence reduction instruction, a repeat instruction, a sequence stride instruction, a nestrepeat instruction, a filter instruction, a replace instruction, and a replicate instruction.