TUNING OF LOOP ORDERS IN BLOCKED DENSE BASIC LINEAR ALGEBRA SUBROUTINES

• US 20190318225A1
• Filed: 06/27/2019
• Published: 10/17/2019
• Est. Priority Date: 06/27/2019
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Heinecke, Alexander, Georganas, Evangelos, Gottschlich, Justin
• Granted Patent: US 11,354,564 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 9/30065 Loop control instructions; iterative instructions, e.g. LOOP, REPEAT
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation
• CPC Class Codes: G06N 3/0418 using chaos or fractal principles
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/047 Probabilistic or stochastic networks
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 3/082 modifying the architecture, e.g. adding, deleting or silencing nodes or connections

Abstract

An example includes a sequence generator to generate a plurality of sequence pairs, a first one of the sequence pairs including: (i) a first input sequence representing first accesses to first tensors in a first loop nest of a first computer program, and (ii) a first output sequence representing a first tuned loop nest corresponding to the first accesses to the first tensors in the first loop nest; a model trainer to train a recurrent neural network based on the sequence pairs as training data, the recurrent neural network to be trained to tune loop ordering of a second computer program based on a second input sequence representing second accesses to a second tensor in a second loop nest of the second computer program; and a memory interface to store, in memory, a trained model corresponding to the recurrent neural network.

Claims

1. An apparatus to tune loop ordering in computer programs, the apparatus comprising:

a sequence generator to generate a plurality of sequence pairs, a first one of the sequence pairs including;

(i) a first input sequence representing first accesses to first tensors in a first loop nest of a first computer program, and (ii) a first output sequence representing a first tuned loop nest corresponding to the first accesses to the first tensors in the first loop nest;

a model trainer to train a recurrent neural network using the sequence pairs as training data, the recurrent neural network to be trained to tune loop ordering of a second computer program based on a second input sequence representing second accesses to second tensors in a second loop nest of the second computer program; and

a memory interface to store, in memory, a trained model corresponding to the recurrent neural network.

2. The apparatus as defined in claim 1, further including:

a comparator to compare a target performance to a second performance of a second output sequence predicted by the trained model, the second output sequence representing a second tuned loop nest corresponding to the second accesses to the second tensors in the second loop nest; and

when the comparison indicates that the second performance satisfies the target performance, the model trainer is to re-train the trained model based on a second sequence pair including the second input sequence and the second output sequence.

3. The apparatus as defined in claim 2, wherein when the second performance does not satisfy the target performance, the model trainer is to re-train the trained model based on a third sequence pair including the second input sequence and a third output sequence, the third output sequence based on a manual tuning of the second input sequence.

4. The apparatus as defined in claim 2, wherein the target performance is based on a loop order tuning performed separate from the trained model.

5. The apparatus as defined in claim 1, wherein the recurrent neural network is a long short-term memory network or a generative adversarial network.

6. The apparatus as defined in claim 1, wherein the first input sequence includes a variable that encodes an affine transformation of a loop index of the first loop nest.

7. A non-transitory computer readable storage medium comprising instructions that, when executed by a processor, cause the processor to at least:

generate a plurality of sequence pairs, a first one of the sequence pairs including;

(i) a first input sequence representing first accesses to first tensors in a first loop nest of a first computer program, and (ii) a first output sequence representing a first tuned loop nest corresponding to the first accesses to the first tensors in the first loop nest;

train a recurrent neural network using the sequence pairs as training data, the recurrent neural network to be trained to tune loop ordering of a second computer program based on a second input sequence representing second accesses to second tensors in a second loop nest of the second computer program; and

store, in memory, a trained model corresponding to the recurrent neural network.

8. The non-transitory computer readable storage medium as defined in claim 7, wherein the instructions are further to cause the processor to:

compare a target performance to a second performance of a second output sequence predicted by the trained model, the second output sequence representing a second tuned loop nest corresponding to the second accesses to the second tensors in the second loop nest; and

when the comparison indicates that the second performance satisfies the target performance, re-train the trained model based on a second sequence pair including the second input sequence and the second output sequence.

9. The non-transitory computer readable storage medium as defined in claim 8, wherein when the second performance does not satisfy the target performance, the instructions are further to cause the processor to re-train the trained model based on a third sequence pair including the second input sequence and a third output sequence, the third output sequence based on a manual tuning of the second input sequence.

10. The non-transitory computer readable storage medium as defined in claim 8, wherein the target performance is based on a loop order tuning performed separate from the trained model.

11. The non-transitory computer readable storage medium as defined in claim 7, wherein the recurrent neural network is a long short-term memory network or a generative adversarial network.

12. The non-transitory computer readable storage medium as defined in claim 7, wherein the first input sequence includes a variable that encodes an affine transformation of a loop index of the first loop nest.

13. A method to tune loop ordering in computer programs, the method comprising:

generating a plurality of sequence pairs, a first one of the sequence pairs including;

(i) a first input sequence representing first accesses to first tensors in a first loop nest of a first computer program, and (ii) a first output sequence representing a first tuned loop nest corresponding to the first accesses to the first tensors in the first loop nest;

training a recurrent neural network using the sequence pairs as training data, the recurrent neural network to be trained to tune loop ordering of a second computer program based on a second input sequence representing second accesses to second tensors in a second loop nest of the second computer program; and

storing, in memory, a trained model corresponding to the recurrent neural network.

14. The method as defined in claim 13, further including:

comparing a target performance to a second performance of a second output sequence predicted by the trained model, the second output sequence representing a second tuned loop nest corresponding to the second accesses to the second tensors in the second loop nest; and

when the comparison indicates that the second performance satisfies the target performance, re-training the trained model based on a second sequence pair including the second input sequence and the second output sequence.

15. The method as defined in claim 14, further including, when the second performance does not satisfy the target performance, re-training the trained model based on a third sequence pair including the second input sequence and a third output sequence, the third output sequence based on a manual tuning of the second input sequence.

16. The method as defined in claim 14, wherein the target performance is based on a loop order tuning performed separate from the trained model.

17. The method as defined in claim 13, wherein the recurrent neural network is a long short-term memory network or a generative adversarial network.

18. The method as defined in claim 13, wherein the first input sequence includes a variable that encodes an affine transformation of a loop index of the first loop nest.

19. An apparatus to tune loop ordering in computer programs, the apparatus comprising:

means for generating a plurality of sequence pairs, a first one of the sequence pairs including;

(i) a first input sequence representing first accesses to first tensors in a first loop nest of a first computer program, and (ii) a first output sequence representing a first tuned loop nest corresponding to the first accesses to the first tensors in the first loop nest;

means for training a recurrent neural network using the sequence pairs as training data, the recurrent neural network to be trained to tune loop ordering of a second computer program based on a second input sequence representing second accesses to second tensors in a second loop nest of the second computer program; and

means for storing, in memory, a trained model corresponding to the recurrent neural network.

20. The apparatus as defined in claim 19, further including:

means for comparing a target performance to a second performance of a second output sequence predicted by the trained model, the second output sequence representing a second tuned loop nest corresponding to the second accesses to the second tensors in the second loop nest; and

when the comparison indicates that the second performance satisfies the target performance, the means for training is to re-train the trained model based on a second sequence pair including the second input sequence and the second output sequence.

21. The apparatus as defined in claim 20, wherein when the second performance does not satisfy the target performance, the means for training is to re-train the trained model based on a third sequence pair including the second input sequence and a third output sequence, the third output sequence based on a manual tuning of the second input sequence.

22. The apparatus as defined in claim 20, wherein the target performance is based on a loop order tuning performed separate from the trained model.

23. The apparatus as defined in claim 19, wherein the recurrent neural network is a long short-term memory network or a generative adversarial network.

24. The apparatus as defined in claim 19, wherein the first input sequence includes a variable that encodes an affine transformation of a loop index of the first loop nest.