Computing resource allocation based on flow graph translation

Patent metadata

Field	Value
Publication number	US-10042966-B2
Application number	US-201514928314-A
Country	US
Kind code	B2
Filing date	Oct 30, 2015
Priority date	Oct 31, 2014
Publication date	Aug 7, 2018
Grant date	Aug 7, 2018

Abstract

Systems and methods are disclosed for computing resource allocation based on flow graph translation. First, a high-level description of logic circuitry is obtained and translated to generate a flow graph representing sequential operations. Using the flow graph, similar processing elements in an array are interchangeably allocated to perform computational, communication, and storage tasks as needed. The sequential operations are executed using the array of interchangeable processing elements. Data is provided from the storage elements through the communication elements to the computational elements. Computational results are stored in the storage elements. Outputs from some of the computational elements provide inputs to other computational elements. Execution of the instructions can be controlled with time stepping. The processors are reallocated as needed, based on changes to the flow graph.

First claim

What is claimed is:

1. A computer-implemented method for dynamic configuration of hardware computing resources comprising:
generating a flow graph, wherein the flow graph is generated by translating a high-level description into the flow graph;
configuring a first plurality of hardware processing elements within a reconfigurable array for computational purposes, based on the flow graph;
configuring a second plurality of hardware processing elements within the reconfigurable array, based on the flow graph, for communication purposes including communication between the first plurality of processing elements, and wherein communication from one processing element to a second processing element is accomplished via an accumulator input on the second processing element; and
configuring a third plurality of processing elements within the reconfigurable array for storage purposes, wherein elements from the first plurality of processing elements, elements from the second plurality of processing elements, and elements from the third plurality of processing elements are interchangeable on subsequent time steps, wherein the configuring of the first plurality of processing elements, the second plurality of processing elements, and the third plurality of processing elements is accomplished by static scheduling, and further comprising identifying conflicts based on the flow graph and performing time slicing to handle identified conflicts.

2. The method of claim 1 wherein the flow graph is generated using a flow graph generation tool.

3. The method of claim 1 wherein the translating comprises generating an intermediate representation based on the high-level description and then translating the intermediate representation into the flow graph.

4. The method of claim 1 wherein the configuring of the first plurality and the configuring of the second plurality are accomplished, in part, by a user pre-configuring certain of the processing elements.

5. The method of claim 1 further comprising performing execution of the flow graph using the first plurality of processing elements and the second plurality of processing elements.

6. The method of claim 5 wherein elements from the first plurality of processing elements and elements from the second plurality of processing elements are substantially similar.

7. The method of claim 5 wherein elements from the first plurality of processing elements and elements from the second plurality of processing elements are interchangeable.

8. The method of claim 5 wherein elements from the first plurality of processing elements are used for communication purposes at a subsequent time step.

9. The method of claim 5 wherein elements from the second plurality of processing elements are used for computational purposes at a subsequent time step.

10. The method of claim 1 further comprising configuring a third plurality of processing elements within the array for storage operations.

11. The method of claim 10 wherein data output from one processing element in the third plurality is used as an input to another processing element that is part of the first plurality of processing elements or the second plurality of processing elements.

12. The method of claim 1 wherein the configuring the first plurality and the second plurality is accomplished by static scheduling.

13. The method of claim 1 wherein the flow graph includes a control data flow graph (CDFG).

14. The method of claim 13 wherein the CDFG includes information related to sequential operation.

15. The method of claim 1 wherein the flow graph includes a hyper graph.

16. The method of claim 1 further comprising identifying conflicts within the first plurality of processing elements.

17. The method of claim 1 further comprising identifying conflicts within the second plurality of processing elements.

18. The method of claim 1 further comprising performing time slicing to handle identified conflicts.

19. The method of claim 1 wherein the flow graph is executed across a series of time steps.

20. The method of claim 19 wherein the first plurality of processing elements and the second plurality of processing elements are coordinated across the series of time steps.

21. The method of claim 1 wherein configuring the first plurality of hardware processing elements includes allocating the first plurality of hardware processing elements for computational purposes.

22. The method of claim 1 wherein configuring the second plurality of hardware processing elements includes allocating the second plurality of hardware processing elements for communication purposes.

23. The method of claim 1 further comprising performing a logical calculation using the first plurality of processing elements and the second plurality of processing elements.

24. The method of claim 23 further comprising presenting a result of the logical calculation on a display.

25. A computer program product embodied in a non-transitory computer readable medium for implementation of a logical calculation apparatus, the computer program product comprising code which causes one or more processors to perform operations of:
generating a flow graph, wherein the flow graph is generated by translating a high-level description into the flow graph;
configuring a first plurality of hardware processing elements within a reconfigurable array for computational purposes, based on the flow graph;
configuring a second plurality of hardware processing elements within the reconfigurable array, based on the flow graph, for communication purposes including communication between the first plurality of processing elements, wherein communication from one processing element to a second processing element is accomplished via an accumulator input on the second processing element; and
configure a third plurality of processing elements within the reconfigurable array for storage purposes, wherein elements from the first plurality of processing elements, elements from the second plurality of processing elements, and elements from the third plurality of processing elements are interchangeable on subsequent time steps, wherein the configuring of the first plurality of processing elements, the second plurality of processing elements, and the third plurality of processing elements is accomplished by static scheduling, and further comprising identifying conflicts based on the flow graph and performing time slicing to handle identified conflicts.

26. A computer system for implementation of a logical calculation apparatus comprising:
a memory which stores instructions;
one or more processors coupled to the memory wherein the one or more processors are configured to:
generate a flow graph, wherein the flow graph is generated by translating a high-level description into the flow graph;
configure a first plurality of hardware processing elements within a reconfigurable array for computational purposes, based on the flow graph;
configure a second plurality of hardware processing elements within the reconfigurable array, based on the flow graph, for communication purposes including communication between the first plurality of processing elements, wherein communication from one processing element to a second processing element is accomplished via an accumulator input on the second processing element; and
configuring a third plurality of processing elements within the reconfigurable array for storage purpos

Assignees

• Wave Semiconductor Inc
• Wave Computing Inc

Inventors

• Chaudhuri Samit
• Esbensen Henrik
• Shiring Kenneth
• Suaris Peter Ramyalal

Classifications

• G06F30/34 Primary

  for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] · CPC title

• G06F17/5054 Primary

  Physics · mapped topic