Patent ID: 7415681

Claim:
A system for improved optimal mapping of LUT based FPGAs comprising: a Directed Acyclic Graph (DAG) representation of a network to be mapped including a plurality of nodes v, a sorter performing a sort on said DAG representation to reduce its complexity, a Dependency Definer that determines a dependency variable dv of each node v in the DAG, a Reconvergent Path Locator (RPL) that determines from transitive fan-ins of each said node v whether reconvergent paths exist and if so updates the dependency variable dv of that node v to reflect the existence of the reconvergent paths, a Priority Determiner (PD) that determines a priority of all child nodes of each node v, a Node Sorter (NS) that sorts a list of child nodes in descending order of priority, a Mapper (M) that assigns LUT's to the child nodes starting at a beginning of said sorted list until the node dependency variable dv is less than one plus a number of inputs to the LUT, an Assignor (A) that assigns an LUT to each output node in the DAG.