Mapping programmable logic devices
AssigneeSicronic Remote KG, LLC
InventorsAjay Tomar, Dhabalendu Samanta
Life of this patent
Estimating the term…
Abstract
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.
Claims20
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.
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.
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.
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.
Dependencies are inferred from the claim text.