Systems and methods for improved mapping of computational loops on reconfigurable architectures

1. A system, comprising:

a processor in communication with a memory and a coarse-grained reconfigurable architecture (CGRA) unit, the memory including instructions, which when executed, cause the processor to:

generate a data flow graph expressive of a computational loop configured for execution on the CGRA unit, wherein the data flow graph includes a plurality of nodes;

determine an upper bound modulo timeslot for each node in the data flow graph, the upper bound modulo timeslot being representative of an upper scheduling bound of a CGRA schedule for each node of the plurality of nodes; and

iteratively generate a random schedule for population within the CGRA schedule that schedules each node of the data flow graph to a random timeslot between a lower bound modulo timeslot and the upper bound modulo timeslot of the CGRA schedule with respect to an initiation interval value.

2. The system of claim 1 , wherein the memory further includes instructions, which, when executed, cause the processor to:

map the CGRA schedule onto the CGRA unit, the CGRA schedule including the random schedule.

3. The system of claim 1 , wherein the step of generating a random schedule that schedules each node of the data flow graph to a random modulo timeslot further comprises:

schedule a node indicative of a current schedule operation of the plurality of nodes of the data flow graph at a randomly selected modulo timeslot between the lower bound modulo timeslot and the upper bound modulo timeslot;

consecutively displace one or more nodes that have resource conflicts with the node;

update the lower bound modulo timeslot and the upper bound modulo timeslot for the node based on the current schedule operation;

displace one or more previously-scheduled nodes having dependence conflicts with the node; and

add one or more displaced nodes to a queue of unscheduled nodes.

4. The system of claim 1 , wherein the memory includes instructions, which when executed, further cause the processor to:

evaluate a feasibility of the random schedule with respect to resource usage of the random schedule as populated within the CGRA schedule; and

generate a new random schedule with the same initiation interval if the random schedule is evaluated to be infeasible.

5. The system of claim 4 , wherein the step of evaluating feasibility of the random schedule includes:

estimate resource usage considering path sharing for each of a plurality of routing resources of the CGRA unit;

confirm that resource overuse does not occur in each modulo timeslot of the CGRA schedule according to a Modulo Resource Table; and

confirm that a total number of unique nodes including the routing nodes scheduled within a modulo timeslot of the plurality of modulo timeslots of the CGRA schedule is less than or equal to a number of processing elements of the CGRA unit scheduled within the modulo timeslot.

6. The system of claim 4 , wherein the memory includes instructions, which when executed, further cause the processor to:

increase the initiation interval after λ random schedules have been generated for a current value of the initiation interval.

7. The system of claim 1 , wherein the upper bound modulo timeslot for each node of the plurality of nodes of the data flow graph is determined by identifying a Resource-Constrained As Late As Possible timeslot through a bottom-up depth-first search approach starting from nodes of the plurality of nodes that do not have any outgoing edges.

8. The system of claim 1 , wherein the memory includes instructions, which when executed, further cause the processor to:

determine the lower bound modulo timeslot for each node of the plurality of nodes of the data flow graph by identifying a Resource-Constrained As Soon As Possible timeslot through a top-down, depth-first search approach starting from nodes of the plurality of nodes that do not have any incoming edges.

9. A method, comprising:

generating, by a processor, a data flow graph expressive of a computational loop configured for execution on the CGRA unit, wherein the data flow graph includes a plurality of nodes;

determining an upper bound modulo timeslot for each node in the data flow graph, the upper bound modulo timeslot being representative of an upper scheduling bound of a CGRA schedule for each node of the plurality of nodes; and

iteratively generating a random schedule for population within the CGRA schedule that schedules each node of the data flow graph to a random timeslot between a lower bound modulo timeslot and the upper bound modulo timeslot of the CGRA schedule with respect to an initiation interval value.

10. The method of claim 9 , further comprising:

mapping the CGRA schedule onto the CGRA unit, the CGRA schedule including the random schedule.

11. The method of claim 9 , wherein the step of generating a random schedule that schedules each node of the data flow graph to a random modulo timeslot further comprises:

scheduling a node of the plurality of nodes of the data flow graph at a randomly selected modulo timeslot between the lower bound modulo timeslot and the upper bound modulo timeslot;

consecutively displacing one or more nodes that have resource conflicts with a current schedule operation;

updating the lower bound modulo timeslot and the upper bound modulo timeslot for the node based on the current schedule operation;

displacing one or more previously-scheduled nodes having dependence conflicts with the current schedule operation; and

adding one or more displaced nodes to a queue of unscheduled nodes.

12. The method of claim 9 , further comprising:

evaluating a feasibility of the random schedule with respect to resource usage of the random schedule as populated within the CGRA schedule; and

generating a new random schedule with the same initiation interval if the random schedule is evaluated to be infeasible.

13. The method of claim 12 , wherein the step of evaluating feasibility of the random schedule comprises:

confirming that a total number of unique nodes including one or more routing nodes scheduled within a modulo timeslot of a plurality of modulo timeslots of the CGRA schedule is less than or equal to a number of processing elements of the CGRA unit scheduled within the modulo timeslot.

14. The method of claim 12 , further comprising:

increasing the initiation interval after A random schedules have been generated for a current value of the initiation interval.

15. The method of claim 9 , wherein the upper bound modulo timeslot for each node of the plurality of nodes of the data flow graph is determined by identifying a Resource-Constrained As Late As Possible timeslot through a bottom-up depth-first search approach starting from nodes of the plurality of nodes that do not have any outgoing edges.

16. The method of claim 9 , further comprising:

determining the lower bound modulo timeslot for each node of the plurality of nodes of the data flow graph by identifying a Resource-Constrained As Soon As Possible timeslot through a top-down, depth-first search approach starting from nodes of the plurality of nodes that do not have any incoming edges.

17. A method, comprising:

generating a random schedule for mapping onto a coarse-grained reconfigurable architecture (CGRA) unit that schedules a node of a plurality of nodes of a data flow graph expressive of an operation of a computational loop to a random timeslot between a lower bound modulo timeslot and an upper bound modulo timeslot with respect to an initiation interval value;

evaluating a feasibility of the random schedule with respect to resource usage;

generating a new random schedule upon infeasible evaluation of the random schedule; and

increasing the initiation interval after A random schedules have been generated for a current value of the initiation interval.

18. The method of claim 17 , further comprising:

mapping the random schedule onto the CGRA unit upon feasible evaluation of the random schedule.

19. The method of claim 17 , wherein the step of evaluating feasibility of the random schedule comprises:

confirming that a total number of unique nodes including one or more routing nodes scheduled within a modulo timeslot of a plurality of modulo timeslots of the random schedule is less than or equal to a number of processing elements of the CGRA unit scheduled within the modulo timeslot.

20. The method of claim 19 , wherein the step of generating a random schedule further comprises:

scheduling a node of the plurality of nodes at a randomly selected modulo timeslot between the lower bound modulo timeslot and the upper bound modulo timeslot;

consecutively displacing one or more nodes that have resource conflicts with a current schedule operation;

updating the lower bound modulo timeslot and the upper bound modulo timeslot for the node based on the current schedule operation;

displacing one or more previously-scheduled nodes having dependence conflicts with the current schedule operation; and

adding one or more displaced nodes to a queue of unscheduled nodes.