Mapping programmable logic devices
View Patent ↗Methods and systems improve mapping of LUT based FPGAs. In some embodiments, a topological sort is performed on a network to be mapped, whereby the network is represented as a Directed Acyclic Graph. The system locates feasible reconvergent paths existing from transitive fan-ins of individual nodes using a Reconvergent Path Locator for replicating fan-outs of the nodes in the DAG, and therefore improves the number of LUTs and the time consumed in the mapping process.
1. A method for mapping look-up table (LUT) based field programmable gate arrays (FPGAs), the method comprising:
representing a network to be mapped using a Directed Acyclic Graph (DAG), the DAG including a plurality of nodes v;
traversing individual nodes v in the DAG;
computing a dependency variable dv for individual traversed nodes v using an input and output of the traversed node v;
assigning a LUT to a traversed node v if at least one of the following conditions is satisfied:
if its dv>k, with k representing a number of LUT inputs;
if its dv>1 and a number of fanouts from that traversed node v is >2; or
if a number of fanouts from that traversed node v is >3; and
configuring an FPGA using an assigned LUT.
2. The method as recited in claim 1 , wherein the assigning if the dv>k condition is satisfied comprises:
identifying child nodes c from the traversed node v;
prioritizing the child nodes; and
assigning a LUT to the child note c of traversed node v unless its dv<k+1.
3. The method as recited in claim 2 , wherein the prioritizing comprises generating a priority for the child nodes based at least in part on the fan-outs of the nodes of the DAG.
4. The method as recited in claim 1 , wherein computing a dependency variable dv for individual traversed nodes v comprises:
determining whether k reconvergent paths exist from transitive fan-ins of the traversed node v; and
if so, updating the dv of that node v to account for the determined reconvergent paths.
5. The method as recited in claim 1 , wherein assigning a LUT to a traversed node v is performed after all nodes v have been traversed and the dependency variable dv has been computed for each traversed node v.
6. A method for mapping of look-up table (LUT) based field programmable gate arrays (FPGAs), the method comprising:
representing a network to be mapped using a Directed Acyclic Graph (DAG), the DAG including a plurality of nodes v;
traversing individual nodes v in the DAG;
computing a dependency variable dv for individual traversed nodes v using an input and output of the traversed node v;
identifying nodes whose dependency variable dv is >k, with k representing a number of LUT inputs;
assigning to each identified node a LUT if either of the following conditions is satisfied:
if its dv>1 and a number of fanouts from that identified node is >2; or
if a number of fanouts from that identified node is >3; and
configuring an FPGA using an assigned LUT.
7. The method as recited in claim 6 , wherein the representing comprises topologically sorting the network in the DAG.
8. The method as recited in claim 6 , wherein computing a dependency variable dv for individual traversed nodes v comprises:
determining whether k reconvergent paths exist from transitive fan-ins of the traversed node v; and
if so, updating the dv of that node v to account for the determined reconvergent paths.
9. The method as recited in claim 6 , wherein the assigning comprises:
identifying child nodes c from the traversed node v;
prioritizing the child nodes; and
assigning a LUT to the child node c of traversed node v unless its dv<k+1.
10. The method as recited in claim 6 , wherein assigning a LUT to a traversed node v is performed after all nodes v have been traversed and the dependency variable dv has been computed for each traversed node v.
11. One or more non-transitory computer-readable storage media having computer-readable instructions thereon which, when executed by a computer, implement a method for mapping look-up table (LUT) based field programmable gate arrays (FPGAs), the method comprising:
representing a network to be mapped using a Directed Acyclic Graph (DAG), the DAG including a plurality of nodes v;
traversing individual nodes v in the DAG;
computing a dependency variable dv for individual traversed nodes v using an input and output of the traversed node v; and
assigning a LUT to a traversed node v if at least one of the following conditions is satisfied:
if its dv>k, with k representing a number of LUT inputs;
if its dv>1 and a number of fanouts from that traversed node v is >2; or
if a number of fanouts from that traversed node v is >3.
12. One or more non-transitory computer-readable storage media as recited in claim 11 , wherein the assigning if the dv>k condition is satisfied comprises:
identifying child nodes c from the traversed node v;
prioritizing the child nodes; and
assigning a LUT to the child node c of traversed node v unless its dv<k+1.
13. One or more non-transitory computer-readable storage media as recited in claim 12 , wherein the prioritizing comprises generating a priority for the child nodes based at least in part on the fan-outs of the nodes of the DAG.
14. One or more non-transitory computer-readable storage media as recited in claim 11 , wherein computing a dependency variable dv for individual traversed nodes v comprises:
determining whether k reconvergent paths exist from transitive fan-ins of the traversed node v; and
if so, updating the dv of that node v to account for the determined reconvergent paths.
15. One or more non-transitory computer-readable storage media as recited in claim 11 , wherein assigning a LUT to a traversed node v is performed after all nodes v have been traversed and the dependency variable dv has been computed for each traversed node v.
16. One or more non-transitory computer-readable storage media having computer-readable instructions thereon which, when executed by a computer, implement operations for mapping look-up table (LUT) based field programmable gate arrays (FPGAs), the operations comprising:
representing a network to be mapped usin Directed Acyclic Graph (DAG), the DAG including a plurality of nodes v;
traversing individual nodes v in the DAG;
computing a dependency variable dv for individual traversed nodes v using an input and output of the traversed node v;
identifying nodes whose dependency variable dv is >k, with k representing a number of LUT inputs; and
assigning to each identified node a LUT if either of the following conditions is satisfied;
if its dv>1 and a number of fanouts from that identified node is >2; or
if a number of fanouts from that identified node is >3.
17. One or more non-transitory computer-readable storage media as recited in claim 16 , wherein the representing comprises topologically sorting the network in the DAG.
18. One or more non-transitory computer-readable storage media as recited in claim 16 , wherein computing the dependency variable dv for individual traversed nodes v comprises:
determining whether k reconvergent paths exist from transitive fan-ins of the traversed node v; and
if so, updating the dv of that node v to account for the determined reconvergent paths.
19. One or more non-transitory computer-readable storage media as recited in claim 16 , wherein the assigning comprises:
identifying child nodes c from the traversed node v;
prioritizing the child nodes; and
assigning a LUT to the child node c of traversed node v unless its dv<k+1.
20. One or more non-transitory computer-readable storage media as recited in claim 16 , wherein assigning a LUT to a traversed node v is performed after nodes v have been traversed and the dependency variable dv has been computed for each traversed node v.