HYBRID AND EFFICIENT APPROACH TO ACCELERATE COMPLICATED LOOPS ON COARSE-GRAINED RECONFIGURABLE ARRAYS (CGRA) ACCELERATORS

• US 20200133672A1
• Filed: 10/26/2018
• Published: 04/30/2020
• Est. Priority Date: 10/26/2018
• Status: Abandoned Application

• Current Assignee: Arm Limited (SoftBank Group Corp.), Arizona Board of Regents (University of Arizona)
• Original Assignee: Arizona Board of Regents (University of Arizona)
• Inventors: Balasubramanian, Mahesh, Dave, Shail, Shrivastava, Aviral, Jeyapaul, Reiley
• Application Number:
  US16/172,254
• Publication Number:
  US 20200133672A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 9/30069 Instruction skipping instructions, e.g. SKIP
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A coarse-grained reconfigurable array includes a processing element array, instruction memory circuitry, data memory circuitry, and an instruction fetch unit. The processing element array includes a number of processing elements. The instruction memory circuitry is coupled to the processing element array and configured to store a set of instructions. During each one of a number of processing cycles, the instruction memory circuitry provides instructions from the set of instructions to the processing elements. The instruction fetch unit is coupled to the processing element array and the instruction memory circuitry and configured to receive a result of a conditional instruction evaluated by one of the processing elements and provide the instruction fetch signals based at least in part on the result of the conditional instruction such that only instructions associated with a correct branch of the conditional instruction are provided to the plurality of processing elements.

Claims

1. A coarse-grained reconfigurable array comprising:

a processing element array comprising a plurality of processing elements;

instruction memory circuitry coupled to the processing element array and configured to;

store a set of instructions; and

during each one of a plurality of processing cycles, provide instructions from the set of instructions to the plurality of processing elements based on instruction fetch signals; and

an instruction fetch unit coupled to the processing element array and the instruction memory circuitry and configured to;

receive a result of a conditional instruction evaluated by one of the plurality of processing elements; and

provide the instruction fetch signals based at least in part on the result of the conditional instruction such that only instructions associated with a correct branch of the conditional instruction are provided to the plurality of processing elements.

2. The coarse-grained reconfigurable array of claim 1 wherein the instruction fetch unit comprises a conditional lookaside buffer such that:

the conditional lookaside buffer stores an instruction skip value associated with the conditional instruction; and

the instruction fetch unit is configured to provide the instruction fetch signals based on the result of the conditional instruction and the instruction skip value associated with the conditional instruction.

3. The coarse-grained reconfigurable array of claim 2 wherein the instruction fetch signals cause the instruction memory circuitry to skip a number of instructions in the instruction memory based on the instruction skip value, such that these instructions are not provided to the processing elements.

4. The coarse-grained reconfigurable array of claim 1 wherein the instruction memory circuitry comprises:

an instruction buffer configured to provide the instructions from the set of instructions to the plurality of processing elements; and

an instruction memory configured to store the set of instructions and provide instructions from the set of instructions to the instruction buffer based on the instruction fetch signals.

5. The coarse-grained reconfigurable array of claim 4 wherein the instruction fetch unit comprises a conditional lookaside buffer such that:

the conditional lookaside buffer stores an instruction skip value associated with the conditional instruction; and

the instruction fetch unit is configured to provide the instruction fetch signals based on the result of the conditional instruction and the instruction skip value associated with the conditional instruction.

6. The coarse-grained reconfigurable array of claim 5 wherein the instruction fetch signals cause the instruction memory circuitry to skip a number of instructions in the instruction memory based on the instruction skip value, such that these instructions are not provided to the processing elements.

7. The coarse-grained reconfigurable array of claim 6 wherein the instruction fetch signals cause the instruction memory to selectively provide instructions from the set of instructions to the instruction buffer.

8. The coarse-grained reconfigurable array of claim 5 wherein the instruction buffer is configured to provide the instruction skip value to the conditional lookaside buffer when the conditional instruction is provided from the instruction memory to the instruction buffer.

9. The coarse-grained reconfigurable array of claim 1 wherein the conditional instruction is a nested conditional instruction.

10. The coarse-grained reconfigurable array of claim 1 wherein the instruction fetch unit is configured to provide the instruction fetch signals such that only instructions from a single branch of a nested conditional instruction are provided from the instruction memory circuitry to the plurality of processing elements.

11. A method comprising:

receiving input code;

generating a set of instructions from the input code, wherein the set of instructions includes;

a first subset of instructions;

a second subset of instructions, wherein;

a number of instructions in the first subset of instructions are equal to a number of instructions in the second subset of instructions; and

the first subset of instructions includes instructions to be evaluated if a conditional instruction is true and the second subset of instructions includes instructions to be evaluated if the conditional instruction is false; and

an instruction skip value associated with the first set of instructions and the second set of instructions, wherein the instruction skip value specifies a number of instructions in the first subset of instructions and the second subset of instructions.

12. The method of claim 11 wherein the conditional instruction is a nested conditional instruction.

13. The method of claim 11 wherein the generating the set of instructions comprises generating at least one no-op instruction such that the number of instructions in the first subset of instructions are equal to the number of instructions in the second subset of instructions.

14. The method of claim 13 wherein the conditional instruction is a nested conditional instruction.

15. The method of claim 11 wherein the set of instructions further includes:

a third subset of instructions; and

a fourth subset of instructions, wherein;

a number of instructions in the third subset of instructions are equal to a number of instructions in the fourth subset of instructions;

the third subset of instructions includes instructions to be evaluated if an additional conditional instruction is true and the fourth subset of instructions includes instructions to be evaluated if the additional conditional instruction is false; and

the additional conditional instruction is nested within the conditional instruction.

16. An apparatus comprising:

processing circuitry; and

a memory storing instructions, which, when executed by the processing circuitry cause the apparatus to;

receive input code;

generate a set of instructions from the input code, wherein the set of instructions includes;

a first subset of instructions,

a second subset of instructions, wherein;

a number of instructions in the first subset of instructions are equal to a number of instructions in the second subset of instructions; and

the first subset of instructions includes instructions to be evaluated if a conditional instruction is true and the second subset of instructions includes instructions to be evaluated if the conditional instruction is false; and

an instruction skip value associated with the first set of instructions and the second set of instructions, wherein the instruction skip value specifies a number of instructions in the first subset of instructions and the second subset of instructions.

17. The apparatus of claim 16 wherein the conditional instruction is a nested conditional instruction.

18. The apparatus of claim 16 wherein generating the set of instructions comprises generating at least one no-op instruction such that the number of instructions in the first subset of instructions are equal to the number of instructions in the second subset of instructions.

19. The apparatus of claim 18 wherein the conditional instruction is a nested conditional instruction.

20. The apparatus of claim 16 wherein the set of instructions further includes:

a third subset of instructions; and

a fourth subset of instructions, wherein;

a number of instructions in the third subset of instructions are equal to a number of instructions in the fourth subset of instructions;

the third subset of instructions includes instructions to be evaluated if an additional conditional instruction is true and the fourth subset of instructions includes instructions to be evaluated if the additional conditional instruction is false; and

the additional conditional instruction is nested within the conditional instruction.