Placement Method Based On A Sorted Operation Unit Graph For An Iterative Placement And Routing On A Reconfigurable Processor

1 . A method of operating a placer and router for an iterative placement and routing of a sorted operation unit graph on a reconfigurable processor, comprising:

receiving an architectural specification of the reconfigurable processor;

receiving the sorted operation unit graph having an ordered sequence of nodes and edges that interconnect nodes in the ordered sequence of nodes;

repeating as long as the ordered sequence of nodes comprises at least one unassigned node:

in order of the ordered sequence of nodes, retrieving a first unassigned node from the ordered sequence of nodes as a current node;

determining a starting location on the reconfigurable processor for performing a search of candidate locations on the reconfigurable processor that are suitable for placing the current node;

determining candidate locations on the reconfigurable processor for placing the current node based on the starting location;

for each candidate location of the candidate locations, determining a valuation associated with placing the current node at the candidate location;

selecting among the candidate locations a target location with an associated valuation that satisfies a predetermined criterion;

assigning the current node to the target location; and

assigning edges that connect the current node with already assigned nodes of the ordered sequence of nodes to physical links and switches of the reconfigurable processor.

2 . The method of claim 1 , wherein the reconfigurable processor comprises arrays of coarse-grained reconfigurable (CGR) units.

3 . The method of claim 1 , wherein determining a starting location on the reconfigurable processor further comprises:

determining a location of a most recently assigned node of the already assigned nodes as the starting location on the reconfigurable processor;

determining a location of one of the already assigned nodes as the starting location on the reconfigurable processor, wherein an edge with a highest bandwidth requirement connects the current node with the one of the already assigned nodes; or

determining a location with a minimum gravitational pull that the current node experiences through connections with the already assigned nodes as the starting location on the reconfigurable processor, wherein connections with a higher bandwidth requirement exert a higher attraction force than connections with a lower bandwidth requirement.

4 . The method of claim 1 , wherein determining candidate locations on the reconfigurable processor for placing the current node based on the starting location further comprises:

determining a predetermined number of suitable candidate locations as the candidate locations by searching starting from the starting location and with increasing distance to the starting location, wherein a suitable candidate location of the predetermined number of suitable candidate locations includes circuitry that is unassigned and able to implement the current node.

5 . The method of claim 4 , wherein determining a predetermined number of suitable candidate locations as the candidate locations by searching starting from the starting location and with increasing distance to the starting location further comprises:

moving from the starting location in direction of a location of an already assigned node of the already assigned nodes, wherein the already assigned node has a connection with a highest bandwidth requirement with the current node among all connections that the current node has with the already assigned nodes.

6 . The method of claim 4 , wherein determining a predetermined number of suitable candidate locations as the candidate locations by searching starting from the starting location and with increasing distance to the starting location further comprises:

iteratively moving with increasing distance from the starting location in a same row, a same column, and diagonally.

7 . The method of claim 1 , wherein determining the valuation associated with placing the current node at the candidate location further comprises:

determining the valuation based on interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes.

8 . The method of claim 7 , wherein determining the valuation based on interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes further comprises:

determining a total Manhattan distance of all interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes;

determining a total Manhattan distance of all interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes weighted with associated bandwidth requirements;

determining a number of switches required for connecting the current node with the already assigned nodes; or

determining a channel usage required for connecting the current node with the already assigned nodes.

9 . The method of claim 1 , wherein determining the valuation associated with placing the current node at the candidate location further comprises:

determining a weighted sum of two or more criteria associated with placing the current node at the candidate location.

10 . The method of claim 1 , wherein determining the valuation associated with placing the current node at the candidate location further comprises:

determining a first criterion associated with placing the current node at the candidate location; and

determining a second criterion associated with placing the current node at the candidate location for breaking ties between two candidate locations of the candidate locations that have a same first criterion.

11 . The method of claim 1 , further comprising:

determining whether the current node is a critical node.

12 . The method of claim 11 , further comprising:

in response to determining that the current node is a critical node:

determining a first predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location; and

for each one of the first predetermined number of candidate locations, determining a second predetermined number of candidate locations on the reconfigurable processor for placing unplaced neighbors of the current node.

13 . The method of claim 11 , further comprising:

in response to determining that the current node is a critical node: determining a first predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location; and

in response to determining that the current node is not a critical node: determining a second predetermined number of candidate locations on the reconfigurable processor for placing the current node based on the starting location, wherein the second predetermined number of candidate locations is smaller than the first predetermined number of candidate locations.

14 . The method of claim 11 , wherein determining whether the current node is a critical node further comprises:

determining whether an edge with a relative bandwidth requirement above a predetermined threshold connects the current node with an already assigned node of the already assigned nodes, or

determining whether the current node has more than a predetermined number of neighbor nodes.

15 . A placer and router for an iterative placement and routing of a sorted operation unit graph on a reconfigurable processor, wherein the placer and router is configured to:

receive an architectural specification of the reconfigurable processor;

receive the sorted operation unit graph having an ordered sequence of nodes and edges that interconnect nodes in the ordered sequence of nodes;

repeat as long as the ordered sequence of nodes comprises at least one unassigned node:

in order of the ordered sequence of nodes, retrieve a first unassigned node from the ordered sequence of nodes as a current node;

determine a starting location on the reconfigurable processor for performing a search of candidate locations on the reconfigurable processor that are suitable for placing the current node;

determine candidate locations on the reconfigurable processor for placing the current node based on the starting location;

for each candidate location of the candidate locations, determine a valuation associated with placing the current node at the candidate location;

select among the candidate locations a target location with an associated valuation that satisfies a predetermined criterion;

assign the current node to the target location; and

assign edges that connect the current node with already assigned nodes of the ordered sequence of nodes to physical links and switches of the reconfigurable processor.

16 . The placer and router of claim 15 , wherein the placer and router, for determining a starting location on the reconfigurable processor, is further configured to:

determine a location of a most recently assigned node of the already assigned nodes as the starting location on the reconfigurable processor;

determine a location of one of the already assigned nodes as the starting location on the reconfigurable processor, wherein an edge with a highest bandwidth requirement connects the current node with the one of the already assigned nodes; or

determine a location with a minimum gravitational pull that the current node experiences through connections with the already assigned nodes as the starting location on the reconfigurable processor, wherein connections with a higher bandwidth requirement exert a higher attraction force than connections with a lower bandwidth requirement.

17 . The placer and router of claim 15 , wherein the placer and router, for determining candidate locations on the reconfigurable processor for placing the current node based on the starting location, is further configured to:

determine a predetermined number of suitable candidate locations as the candidate locations by searching starting from the starting location and with increasing distance to the starting location, wherein a suitable candidate location of the predetermined number of suitable candidate locations includes circuitry that is unassigned and able to implement the current node.

18 . The placer and router of claim 15 , wherein the placer and router, for determining the valuation associated with placing the current node at the candidate location, is further configured to:

determine the valuation based on interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes.

19 . The placer and router of claim 18 , wherein the placer and router, for determining the valuation based on interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes, is further configured to:

determine a total Manhattan distance of all interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes;

determine a total Manhattan distance of all interconnection resources of the reconfigurable processor that are required for connecting the current node with the already assigned nodes weighted with associated bandwidth requirements;

determine a number of switches required for connecting the current node with the already assigned nodes; or

determine a channel usage required for connecting the current node with the already assigned nodes.

20 . A non-transitory computer-readable storage medium including instructions that, when executed by a processing unit, cause the processing unit to operate a placer and router for an iterative placement and routing of a sorted operation unit graph on a reconfigurable processor, the instructions comprising:

receiving an architectural specification of the reconfigurable processor;

receiving the sorted operation unit graph having an ordered sequence of nodes and edges that interconnect nodes in the ordered sequence of nodes;

repeating as long as the ordered sequence of nodes comprises at least one unassigned node:

in order of the ordered sequence of nodes, retrieving a first unassigned node from the ordered sequence of nodes as a current node;

determining a starting location on the reconfigurable processor for performing a search of candidate locations on the reconfigurable processor that are suitable for placing the current node;

determining candidate locations on the reconfigurable processor for placing the current node based on the starting location;

for each candidate location of the candidate locations, determining a valuation associated with placing the current node at the candidate location;

selecting among the candidate locations a target location with an associated valuation that satisfies a predetermined criterion;

assigning the current node to the target location; and

assigning edges that connect the current node with already assigned nodes of the ordered sequence of nodes to physical links and switches of the reconfigurable processor.