DYNAMIC RECONFIGURATION OF PROGRAMMABLE HARDWARE

• US 20140215424A1
• Filed: 01/30/2013
• Published: 07/31/2014
• Est. Priority Date: 01/30/2013
• Status: Active Grant

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Fine, Kevin, Kruglick, Ezekiel
• Granted Patent: US 9,361,416 B2
• Time in Patent Office: Days
• US Class Current: 716/117
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

Abstract

Technologies related to dynamic reconfiguration of programmable hardware are generally described. In some examples, coprocessor regions in programmable hardware such as a Field Programmable Gate Array (FPGA) may be dynamically assigned to transition the FPGA from a starting arrangement of coprocessor regions to an efficient arrangement. A placement algorithm may be executed to determine the efficient arrangement, and a path finding algorithm may be executed to determine path finding operations leading from the starting arrangement to the efficient arrangement. The path finding operations may be performed to implement the transition.

Claims

1. A method for dynamically assigning coprocessor regions in a Field Programmable Gate Array (FPGA), the method comprising:

executing a placement algorithm to determine at least one efficient arrangement of a plurality of coprocessor regions within the FPGA;

executing a path finding algorithm to determine one or more path finding operations from a starting arrangement of coprocessor regions to the efficient arrangement of coprocessor regions, each path finding operation comprising;

establishing a reconfiguration region of the FPGA, wherein at least one coprocessor region is outside the reconfiguration region, and wherein at least one coprocessor region is inside the reconfiguration region;

disabling coprocessors having coprocessor regions in the reconfiguration region while allowing coprocessors having coprocessor regions outside the reconfiguration region to continue to operate;

assigning one or more new coprocessor regions in the reconfiguration region; and

loading coprocessors in each of the new coprocessor regions; and

performing the one or more path finding operations to transition the FPGA from the starting arrangement of coprocessor regions to the efficient arrangement of coprocessor regions.

2. The method of claim 1, further comprising scheduling Virtual Machines (VMs) that use coprocessors in the coprocessor regions within the FPGA according to coprocessor availability during performance of the one or more path finding operations, so that VMs using coprocessors that are disabled during a path finding operation are provided with reduced execution time during the path finding operation.

3. The method of claim 2, wherein the reduced execution time during the path finding operation is substantially no execution time during the path finding operation.

4. The method of claim 2, wherein the scheduling VMs comprises making one or more VM scheduling recommendations to a hypervisor effective to configure the hypervisor to perform the scheduling.

10. The method of claim 1, wherein the placement algorithm comprises a greedy algorithm, a first fit algorithm, a best fit decreasing algorithm, or a first-fit decreasing algorithm.

11. The method of claim 1, wherein the at least one efficient arrangement of coprocessor regions comprises an arrangement that is at least more efficient than the starting arrangement of coprocessor regions by using more of the FPGA for coprocessor regions than is used by the starting arrangement of coprocessor regions.

12. The method of claim 1, wherein the path finding algorithm comprises a best fit search algorithm, an A* algorithm, a B* algorithm, a beam search algorithm, or a Dijkstra'"'"'s algorithm.

5-9. -9. (canceled)

13. A non-transitory computer readable storage medium having computer executable instructions executable by a processor, the instructions that, when executed by the processor, implement a programmable hardware optimizer, which causes the processor to:

execute a placement algorithm to determine at least one efficient arrangement of a plurality of coprocessor regions within a Field Programmable Gate Array (FPGA);

execute a path finding algorithm to determine one or more path finding operations from a starting arrangement of coprocessor regions to the efficient arrangement of coprocessor regions, each path finding operation comprising;

establishing a reconfiguration region of the FPGA, wherein at least one coprocessor region is outside the reconfiguration region, and wherein at least one coprocessor region is inside the reconfiguration region;

disabling coprocessors having coprocessor regions in the reconfiguration region while allowing coprocessors having coprocessor regions outside the reconfiguration region to continue to operate;

assigning one or more new coprocessor regions in the reconfiguration region; and

loading coprocessors in each of the new coprocessor regions; and

perform the one or more path finding operations to transition the FPGA from the starting arrangement of coprocessor regions to the efficient arrangement of coprocessor regions.

14-24. -24. (canceled)

25. A computing device configured to provide a programmable hardware optimizer, comprising:

a processor;

a memory; and

a programmable hardware optimizer stored in the memory and executable by the processor, wherein the programmable hardware optimizer is configured to;

execute a placement algorithm to determine at least one efficient arrangement of a plurality of coprocessor regions within a Field Programmable Gate Array (FPGA);

execute a path finding algorithm to determine one or more path finding operations from a starting arrangement of coprocessor regions to the efficient arrangement of coprocessor regions, each path finding operation comprising;

establishing a reconfiguration region of the FPGA, wherein at least one coprocessor region is outside the reconfiguration region, and wherein at least one coprocessor region is inside the reconfiguration region;

disabling coprocessors having coprocessor regions in the reconfiguration region while allowing coprocessors having coprocessor regions outside the reconfiguration region to continue to operate;

assigning one or more new coprocessor regions in the reconfiguration region; and

loading coprocessors in each of the new coprocessor regions; and

perform the one or more path finding operations to transition the FPGA from the starting arrangement of coprocessor regions to the efficient arrangement of coprocessor regions.

26. The computing device of claim 25, wherein the computing device is configured to schedule Virtual Machines (VMs) that use coprocessors in the coprocessor regions within the FPGA according to coprocessor availability during performance of the one or more path finding operations, so that VMs using coprocessors that are disabled during a path finding operation are provided with reduced execution time during the path finding operation.

27. The computing device of claim 26, wherein the reduced execution time during the path finding operation is substantially no execution time during the path finding operation.

28. The computing device of claim 26, wherein the scheduling VMs comprises making one or more VM scheduling recommendations to a hypervisor effective to configure the hypervisor to perform the scheduling.

29. The computing device of claim 25, wherein the computing device is configured to determine multiple path finding operation options, each path finding operation option comprising establishing a different reconfiguration region of the FPGA and disabling different coprocessors.

30. The computing device of claim 29, wherein the placement algorithm is applied to determine multiple efficient arrangements of coprocessor regions within the FPGA, and wherein the multiple path finding operation options correspond to the multiple efficient arrangements of coprocessor regions.

31. The computing device of claim 29, wherein the programmable hardware optimizer is configured to make multiple Virtual Machine (VM) scheduling recommendations to a hypervisor, wherein the multiple VM scheduling recommendations correspond to the multiple path finding operation options.

32. The computing device of claim 31, wherein the computing device is configured to perform a path finding operation option corresponding to a hypervisor selected VM scheduling recommendation in response to selection by the hypervisor of the VM scheduling recommendation from among the multiple VM scheduling recommendations.

33. The computing device of claim 25, wherein the computing device is configured to provide a configware identifier for each of the new coprocessor regions to a configuration controller, to adapt the configuration controller to load identified configware in each of the new coprocessor regions, and wherein loading identified configware is effective to load the coprocessors in each of the new coprocessor regions.

34. The computing device of claim 25, wherein the placement algorithm comprises a greedy algorithm, a first fit algorithm, a best fit decreasing algorithm, or a first-fit decreasing algorithm.

35. The computing device of claim 25, wherein the at least one efficient arrangement of coprocessor regions comprises an arrangement that is at least more efficient than the starting arrangement of coprocessor regions by using more of the FPGA for coprocessor regions than is used by the starting arrangement of coprocessor regions.

36. The computing device of claim 25, wherein the path finding algorithm comprises a best fit search algorithm, an A* algorithm, a B* algorithm, a beam search algorithm, or a Dijkstra'"'"'s algorithm.

37-53. -53. (canceled)