CONFIGURING COARSE-GRAINED RECONFIGURABLE ARRAYS (CGRAs) FOR DATAFLOW INSTRUCTION BLOCK EXECUTION IN BLOCK-BASED DATAFLOW INSTRUCTION SET ARCHITECTURES (ISAs)

• US 20170083313A1
• Filed: 09/22/2015
• Published: 03/23/2017
• Est. Priority Date: 09/22/2015
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Sankaralingam, Karthikeyan, WRIGHT, Gregory Michael
• Application Number:
  US14/861,201
• Publication Number:
  US 20170083313A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture
• CPC Class Codes: G06F 15/7892 Reconfigurable logic embedded in CPU, e.g. reconfigurable unit
• CPC Class Codes: G06F 15/825 Dataflow computers
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3854 Instruction completion, e.g. retiring, committing or graduating
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3897 with adaptable data path
• CPC Class Codes: G06F 9/4494 data driven

Abstract

Configuring coarse-grained reconfigurable arrays (CGRAs) for dataflow instruction block execution in block-based dataflow instruction set architectures (ISAs) is disclosed. In one aspect, a CGRA configuration circuit is provided, comprising a CGRA having an array of tiles, each of which provides a functional unit and a switch. An instruction decoding circuit of the CGRA configuration circuit maps a dataflow instruction within a dataflow instruction block to one of the tiles of the CGRA. The instruction decoding circuit decodes the dataflow instruction, and generates a function control configuration for the functional unit of the mapped tile to provide the functionality of the dataflow instruction. The instruction decoding circuit further generates switch control configurations for switches along a path of tiles within the CGRA so that an output of the functional unit of the mapped tile is routed to each tile corresponding to consumer instructions of the dataflow instruction.

Claims

1. A coarse-grained reconfigurable array (CGRA) configuration circuit of a block-based dataflow instruction set architecture (ISA), comprising:

a CGRA comprising a plurality of tiles, each tile among of the plurality of tiles comprising a functional unit and a switch; and

an instruction decoding circuit configured to;

receive, from a block-based dataflow computer processor core, a dataflow instruction block comprising a plurality of dataflow instructions; and

for each dataflow instruction of the plurality of dataflow instructions;

map the dataflow instruction to a tile of the plurality of tiles of the CGRA;

decode the dataflow instruction;

generate a function control configuration for the functional unit of the mapped tile to correspond to a functionality of the dataflow instruction; and

for each consumer instruction of the dataflow instruction, generate a switch control configuration of the switch of each of one or more path tiles of the plurality of tiles of the CGRA to route an output of the functional unit of the mapped tile to a destination tile of the plurality of tiles of the CGRA corresponding to the consumer instruction.

2. The CGRA configuration circuit of claim 1, wherein the instruction decoding circuit is further configured to, prior to generating the switch control configuration:

identify the destination tile of the plurality of tiles of the CGRA corresponding to the consumer instruction;

determine the one or more path tiles of the plurality of tiles of the CGRA comprising a path from the mapped tile to the destination tile, the one or more path tiles including the mapped tile and the destination tile.

3. The CGRA configuration circuit of claim 2, wherein the instruction decoding circuit is configured to determine the one or more path tiles of the plurality of tiles of the CGRA comprising the path from the mapped tile to the destination tile by determining a shortest Manhattan distance between the mapped tile and the destination tile.

4. The CGRA configuration circuit of claim 2, wherein the functional unit of each tile among the plurality of tiles comprises logic for providing a plurality of word-level operations;

and

the functional unit is configured to selectively perform a word-level operation of the plurality of word-level operations responsive to the generated function control configuration.

5. The CGRA configuration circuit of claim 2, wherein the switch of each tile among the plurality of tiles is communicatively coupled to the functional unit of the tile and to a plurality of switches of the corresponding plurality of tiles;

and

the switch is configured to transmit data among the functional unit and one or more of the plurality of switches of the corresponding plurality of tiles responsive to the generated switch control configuration.

6. The CGRA configuration circuit of claim 2, wherein the consumer instruction comprises an instruction that receives an output of the dataflow instruction as an input.

7. The CGRA configuration circuit of claim 1, wherein:

the instruction decoding circuit further comprises a centralized hardware state machine; and

the instruction decoding circuit is further configured to output the function control configuration and the switch control configuration for each mapped tile to a CGRA configuration buffer.

8. The CGRA configuration circuit of claim 1, wherein:

the instruction decoding circuit further comprises a plurality of distributed decoder units, each integrated into a tile of the plurality of tiles of the CGRA; and

the instruction decoding circuit is configured to decode each dataflow instruction and generate the function control configuration and the switch control configuration for each mapped tile using a distributed decoder unit of the plurality of distributed decoder units corresponding to the mapped tile.

9. The CGRA configuration circuit of claim 1, wherein the instruction decoding circuit is further configured to select, at runtime, one of the CGRA and the block-based dataflow computer processor core to execute the dataflow instruction block.

10. The CGRA configuration circuit of claim 9, wherein the instruction decoding circuit is further configured to determine, at runtime, whether generation of the function control configuration and the switch control configuration for each mapped tile was successful;

the instruction decoding circuit configured to;

select the CGRA to execute the dataflow instruction block responsive to determining that the generation of the function control configuration and the switch control configuration for each mapped tile was successful; and

select the block-based dataflow computer processor core to execute the dataflow instruction block responsive to determining that the generation of the function control configuration and the switch control configuration for each mapped tile was not successful.

11. The CGRA configuration circuit of claim 9, wherein the instruction decoding circuit is further configured to detect, at runtime, whether the CGRA provides a required resource;

the instruction decoding circuit configured to;

select the CGRA to execute the dataflow instruction block responsive to determining that the CGRA provides the required resource; and

select the block-based dataflow computer processor core to execute the dataflow instruction block responsive to determining that the CGRA does not provide the required resource.

12. The CGRA configuration circuit of claim 1 integrated into an integrated circuit (IC).

13. The CGRA configuration circuit of claim 1 integrated into a device selected from the group consisting of:

a set top box;

an entertainment unit;

a navigation device;

a communications device;

a fixed location data unit;

a mobile location data unit;

a mobile phone;

a cellular phone;

a computer;

a portable computer;

a desktop computer;

a personal digital assistant (PDA);

a monitor;

a computer monitor;

a television;

a tuner;

a radio;

a satellite radio;

a music player;

a digital music player;

a portable music player;

a digital video player;

a video player;

a digital video disc (DVD) player; and

a portable digital video player.

14. A method for configuring a coarse-grained reconfigurable array (CGRA) for dataflow instruction block execution in a block-based dataflow instruction set architecture (ISA), comprising:

receiving, by an instruction decoding circuit from a block-based dataflow computer processor core, a dataflow instruction block comprising a plurality of dataflow instructions; and

for each dataflow instruction of the plurality of dataflow instructions;

mapping the dataflow instruction to a tile of a plurality of tiles of a CGRA, each tile among of the plurality of tiles comprising a functional unit and a switch;

decoding the dataflow instruction;

generating a function control configuration for the functional unit of the mapped tile to correspond to a functionality of the dataflow instruction; and

for each consumer instruction of the dataflow instruction, generating a switch control configuration of the switch of each of one or more path tiles of the plurality of tiles of the CGRA to route an output of the functional unit of the mapped tile to a destination tile of the plurality of tiles of the CGRA corresponding to the consumer instruction.

15. The method of claim 14, further comprising, prior to generating the switch control configuration:

identifying the destination tile of the plurality of tiles of the CGRA corresponding to the consumer instruction; and

determining the one or more path tiles of the plurality of tiles of the CGRA comprising a path from the mapped tile to the destination tile, the one or more path tiles including the mapped tile and the destination tile.

16. The method of claim 15, wherein determining the one or more path tiles of the plurality of tiles of the CGRA comprising the path from the mapped tile to the destination tile comprises determining a shortest Manhattan distance between the mapped tile and the destination tile.

17. The method of claim 14, wherein:

the instruction decoding circuit comprises a centralized hardware state machine; and

the method further comprises outputting the function control configuration and the switch control configuration for each mapped tile to a CGRA configuration buffer.

18. The method of claim 14, wherein:

the instruction decoding circuit comprises a plurality of distributed decoder units, each integrated into a tile of the plurality of tiles of the CGRA; and

the method further comprises decoding each dataflow instruction and generating the function control configuration and the switch control configuration for each mapped tile using a distributed decoder unit of the plurality of distributed decoder units corresponding to the mapped tile.

19. The method of claim 14, further comprising selecting, at runtime, one of the CGRA and the block-based dataflow computer processor core to execute the dataflow instruction block.

20. The method of claim 19, further comprising determining, at runtime, whether generation of the function control configuration and the switch control configuration for each mapped tile was successful;

the method comprising;

selecting the CGRA to execute the dataflow instruction block responsive to determining that the generation of the function control configuration and the switch control configuration for each mapped tile was successful; and

selecting the block-based dataflow computer processor core to execute the dataflow instruction block responsive to determining that the generation of the function control configuration and the switch control configuration for each mapped tile was not successful.

21. The method of claim 19, further comprising determining, at runtime, whether the CGRA provides a required resource;

the method comprising;

selecting the CGRA to execute the dataflow instruction block responsive to determining that the CGRA provides the required resource; and

selecting the block-based dataflow computer processor core to execute the dataflow instruction block responsive to determining that the CGRA does not provide the required resource.

22. A coarse-grained reconfigurable array (CGRA) configuration circuit of a block-based dataflow instruction set architecture (ISA) for configuring a CGRA comprising a plurality of tiles, each tile among of the plurality of tiles comprising a functional unit and a switch, comprising:

a means for receiving, from a block-based dataflow computer processor core, a dataflow instruction block comprising a plurality of dataflow instructions; and

for each dataflow instruction of the plurality of dataflow instructions;

a means for mapping the dataflow instruction to a tile of a plurality of tiles of a CGRA;

a means for decoding the dataflow instruction;

a means for generating a function control configuration of the functional unit of the mapped tile to correspond to a functionality of the dataflow instruction; and

for each consumer instruction of the dataflow instruction, a means for generating a switch control configuration of the switch of each of one or more path tiles of the plurality of tiles of the CGRA to route an output of the functional unit of the mapped tile to a destination tile of the plurality of tiles of the CGRA corresponding to the consumer instruction.

23. The CGRA configuration circuit of claim 22, further comprising:

a means for identifying the destination tile of the plurality of tiles of the CGRA corresponding to the consumer instruction prior to generating the switch control configuration; and

a means for determining the one or more path tiles of the plurality of tiles of the CGRA comprising a path from the mapped tile to the destination tile, the one or more path tiles including the mapped tile and the destination tile.

24. The CGRA configuration circuit of claim 23, wherein the means for determining the one or more path tiles of the plurality of tiles of the CGRA comprising the path from the mapped tile to the destination tile comprises a means for determining a shortest Manhattan distance between the mapped tile and the destination tile.

25. The CGRA configuration circuit of claim 22, further comprising a means for outputting the function control configuration and the switch control configuration for each mapped tile to a CGRA configuration buffer.

26. The CGRA configuration circuit of claim 22, further comprising a means for decoding each dataflow instruction and generating the function control configuration and the switch control configuration for each mapped tile using a distributed decoder unit of a plurality of distributed decoder units corresponding to the mapped tile.

27. The CGRA configuration circuit of claim 22, further comprising a means for selecting, at runtime, one of the CGRA and the block-based dataflow computer processor core to execute the dataflow instruction block.

28. The CGRA configuration circuit of claim 27, further comprising a means for determining, at runtime, whether generation of the function control configuration and the switch control configuration for each mapped tile was successful;

wherein the means for selecting, at runtime, one of the CGRA and the block-based dataflow computer processor core to execute the dataflow instruction block comprises;

a means for selecting the CGRA to execute the dataflow instruction block responsive to determining that the generation of the function control configuration and the switch control configuration for each mapped tile was successful; and

a means for selecting the block-based dataflow computer processor core to execute the dataflow instruction block responsive to determining that the generation of the function control configuration and the switch control configuration for each mapped tile was not successful.

29. The CGRA configuration circuit of claim 27, further comprising a means for determining, at runtime, whether the CGRA provides a required resource;

wherein the means for selecting, at runtime, one of the CGRA and the block-based dataflow computer processor core to execute the dataflow instruction block comprises;

a means for selecting the CGRA to execute the dataflow instruction block responsive to determining that the CGRA provides the required resource; and

a means for selecting the block-based dataflow computer processor core to execute the dataflow instruction block responsive to determining that the CGRA does not provide the required resource.