{ "id": "ep34yyn5pp", "slug": "technology-mapping", "title": "Technology mapping", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.hardware", "label": "Computer hardware", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.hardware" }, { "id": "technology.computing.hardware.hardware-semiconductors", "label": "Semiconductor devices & fabrication", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.hardware.hardware-semiconductors" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing", "label": "Non-geographic · 1946 to 2000: Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" } ] } ], "excerpt": "Technology mapping is the logic synthesis step that converts a technology-independent Boolean network into a netlist of standard-cell or FPGA library gates, optimizing area, delay, or power.", "snippet": "Technology mapping is the logic synthesis step that converts a technology-independent Boolean network into a netlist of standard-cell or FPGA library gates, optimizing area, delay, or power.", "node": "technology.computing.hardware.hardware-semiconductors", "markdown": "# Technology mapping\n\nTechnology mapping is the logic synthesis step that converts a technology-independent [Boolean network](https://www.edgepedia.org/boolean-network) into a netlist of gates drawn from a specific standard-cell or FPGA library, while optimizing an objective such as area, delay, or power. It sits at the end of the synthesis flow: the design has already been optimized as an abstract circuit, and mapping decides which physical gates implement it. In modern flows the input is typically a subject graph, most often an and-inverter graph (AIG), where each node is a two-input AND gate and complemented edges carry negation, and the output is a gate-level netlist built from the target library.[1](https://si2.epfl.ch/demichel/publications/archive/2025/ASPDAC25_Andrea.pdf) • [2](https://arxiv.org/html/2604.26591) For standard-cell design the output gates come from a foundry library; for FPGAs they are k-input [lookup tables](https://www.edgepedia.org/lookup-table) (K-LUTs), each of which can be programmed with any [Boolean function](https://www.edgepedia.org/boolean-function) of its k inputs.[3](https://people.eecs.berkeley.edu/~alanmi/publications/2005/tech05_map.pdf) • [4](https://yosyshq.readthedocs.io/projects/yosys/en/0.41/using%5Fyosys/synthesis/techmap_synth.html)\n\n| Key fact | Detail |\n|---|---|\n| Input / output | A technology-independent subject graph (commonly an AIG) in; a netlist of standard-cell gates or K-LUTs out[1](https://si2.epfl.ch/demichel/publications/archive/2025/ASPDAC25_Andrea.pdf) • [2](https://arxiv.org/html/2604.26591) |\n| Formulation | Covering the subject graph with pattern graphs derived from library gates[5](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf) |\n| Complexity | Tree covering is optimal in linear time by dynamic programming; minimum-area covering of a DAG is NP-hard[5](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf) • [6](https://people.eecs.berkeley.edu/~alanmi/benchmarks/fpga/iccad04_daomap.pdf) |\n| FPGA depth | FlowMap guarantees depth-optimal LUT mapping in polynomial time under the unit delay model[7](https://limsk.ece.gatech.edu/book/papers/flowmap.pdf) |\n| Typical gains | DAOmap is 16.02% better on area and 24.2x faster than CutMap with 5-input LUTs[6](https://people.eecs.berkeley.edu/~alanmi/benchmarks/fpga/iccad04_daomap.pdf); choice-based mapping cuts delay 10% and area 19% at 8x runtime[8](https://blif.org/~satrajit/files/2006_FPGA_Improvements_to_FPGA_Tech_Mapping.pdf) |\n| Tool support | Yosys maps in two phases, RTL cells to internal single-bit cells, then to the target library[4](https://yosyshq.readthedocs.io/projects/yosys/en/0.41/using%5Fyosys/synthesis/techmap_synth.html) |\n\n## How it works\n\nThe problem is covering. The technology-independent circuit and each library gate are decomposed into a common base of simple gates, historically two-input NANDs and inverters; the decomposed circuit is the subject graph and each decomposed library gate is a pattern graph, and mapping means covering the subject graph with pattern graphs at minimum cost.[5](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf) Equivalently, it is choosing a minimum-cost cover of the Boolean network from a library of logic cells, whose core can be formulated as the binate covering (covering problem with conflicting constraints; NP-hard) problem, which is NP-hard.[9](http://www.ecs.umass.edu/ece/labs/vlsicad/ece667/reading/techmap-binate-servit.pdf) The objective is stated over the chosen mapping: area as the sum of gate areas, worst-case delay as the maximum over paths of the summed gate delays, or a weighted combination.[2](https://arxiv.org/html/2604.26591)\n\nThe complexity split explains the algorithms. When the subject graph and pattern graphs are trees, dynamic programming finds an optimal cover in linear time; when the subject graph is a DAG, minimum-area covering is NP-hard.[5](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf) For FPGA LUT mapping the picture differs: because a K-LUT implements any of up to \\( 2^{k} \\) functions of k inputs, tree-based dynamic programming does not transfer directly, and depth minimization instead reduces to computing a minimum-height K-feasible cut at each node, solvable in polynomial time by network flow.[7](https://limsk.ece.gatech.edu/book/papers/flowmap.pdf) The FlowMap labeling recurrence computes optimal depth by dynamic programming over cuts: \\( \\mathrm{depth}(x) = \\min_{X,\\, |X| \\le k} \\max_{x_{i} \\in X} \\left( \\mathrm{depth}(x_{i}) + 1 \\right) \\).[5](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf)\n\n## How it is done\n\nA standard-cell mapper of the cut-based type runs in five steps. First, compute all k-feasible cuts for every node of the AIG. Second, for each cut, assign a formal variable to each node in the cut and compute the node's function in terms of those variables as truth-table bit-vectors. Third, match those functions against library gates using a hash table. Fourth, compute best arrival times in topological order, choosing the minimum-delay gate for each cut. Fifth, select the best covering in reverse topological order.[3](https://people.eecs.berkeley.edu/~alanmi/publications/2005/tech05_map.pdf)\n\nTwo practical refinements matter. The priority cut algorithm bounds runtime by computing only a subset of cuts per node, sorted by the optimization objective, instead of enumerating all feasible cuts; this matters because the number of K-feasible cuts per node can exceed 100 for large K, making exhaustive storage costly.[10](https://www.epfl.ch/labs/lap/wp-content/uploads/2018/05/JiangSep15_ATechnologyMapperForDepthConstrainedFpgaLogicCells_FPL15.pdf) • [8](https://blif.org/~satrajit/files/2006_FPGA_Improvements_to_FPGA_Tech_Mapping.pdf) In Yosys, mapping runs in two phases: RTL cells are first mapped to an internal library of single-bit cells, and that netlist is then transformed into gates from the target technology library.[4](https://yosyshq.readthedocs.io/projects/yosys/en/0.41/using%5Fyosys/synthesis/techmap_synth.html)\n\n## Origin\n\nThe TMS system addressed technology-to-technology mapping between gate array and standard cell logic families, using an intermediate notation called GLN and several forms of rules.[11](https://www.mirrorservice.org/sites/www.bitsavers.org/pdf/ibm/IBM_Journal_of_Research_and_Development/285/ibmrd2805F.pdf) The algorithmic formulation came from Kurt Keutzer's DAGON, published in the Proceedings of the 24th [Design Automation Conference](https://www.edgepedia.org/design-automation-conference) in 1987.[12](https://link.springer.com/rwe/10.1007/978-0-387-30162-4_420) Keutzer observed the similarity between technology mapping and the code optimization problem for programming languages, adapted an existing tree-covering technique from that field, and showed the tree version optimal by dynamic programming while DAG covering for minimum area is NP-hard; the approach soon dominated rule-based methods and became the de facto standard.[5](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf) The FPGA era brought heuristics such as Chortle, based on tree decomposition and bin packing, Xmap, based on an if-then-else DAG representation, and MIS-pga-delay, followed by DAG-Map, reported by K.-C. Chen and colleagues in 1992 in IEEE Design & Test of Computers, which maps the entire Boolean network rather than decomposing it into fan-out-free trees.[7](https://limsk.ece.gatech.edu/book/papers/flowmap.pdf) • [13](https://doi.org/10.1109/54.156154) FlowMap, published by J. Cong and Yuzheng Ding in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems in 1994, then proved depth-optimal LUT mapping polynomial.[14](https://doi.org/10.1109/43.273754)\n\n## Variants\n\nFPGA mappers are categorized by objective: those minimizing the number of LUTs (area), those minimizing delay, meaning the number of LUTs on a longest path, those focused on routability, and those minimizing both area and delay.[15](https://cecs.uci.edu/~papers/compendium94-03/papers/2003/aspdac03/pdffiles/04c_1.pdf) FlowMap guarantees optimal depth under the unit delay model; CutMap extends it to minimize LUT count among depth-optimal solutions; DAOmap keeps the depth guarantee while improving area, and EdgeMap generalizes FlowMap to a weighted-edge delay model.[6](https://people.eecs.berkeley.edu/~alanmi/benchmarks/fpga/iccad04_daomap.pdf) On the standard-cell side, mapping with choices encodes multiple local algebraic decompositions into the subject graph, and supergates, single-output networks of a few library gates treated as one gate, let matching look deeper into the circuit; the key difference from conventional DAG-covering mappers is Boolean matching instead of structural matching.[3](https://people.eecs.berkeley.edu/~alanmi/publications/2005/tech05_map.pdf) Boolean matching exploits Boolean relationships, for example canonical BDD representations, to find more or better matches than structural pattern matching alone.[16](https://nanohub.org/resources/43301/download/2025.04.01-ECE512-L5.09-Raghunathan-annotated.pdf)\n\n## Applications\n\nReported benchmark results show the progression. FlowMap reduces LUT network depth by up to 7% and the number of LUTs by up to 50% compared with three earlier methods.[7](https://limsk.ece.gatech.edu/book/papers/flowmap.pdf) CutMap, tested on MCNC logic synthesis benchmarks, uses 15% fewer K-LUTs than FlowMap at equal depth optimality.[17](https://dl.acm.org/doi/10.1145/201310.201322) DAOmap, compared against CutMap with 5-input LUTs, is 16.02% better on area and runs 24.2x faster on average.[6](https://people.eecs.berkeley.edu/~alanmi/benchmarks/fpga/iccad04_daomap.pdf) Five mapping iterations with choices reduce delay by 10% and area by 19% at 8x runtime, with these improvements available in the ABC package.[8](https://blif.org/~satrajit/files/2006_FPGA_Improvements_to_FPGA_Tech_Mapping.pdf)\n\nSince 2023, machine learning has entered cut selection and library tuning. LEAP, an ICCAD 2024 machine learning-assisted cut sampling strategy that prioritizes high-quality cuts by delay, reduces the number of cuts exposed to the mapper by over 51% compared with ABC, yielding a 2% delay improvement with no area penalty.[18](https://dl.acm.org/doi/10.1145/3676536.3676797) MapTune applies Multi-Armed Bandit and Q-Learning within ABC for design-specific cell selection, achieving an average Area-Delay Product improvement of 22.54% across exploration settings.[19](https://arxiv.org/html/2407.18110) MappingEvolve uses LLMs to evolve core mapping operators, reporting 10.04% area reduction versus ABC and 7.93% versus mockturtle, with 46.6% to 96.0% \\( S_{\\mathrm{overall}} \\) improvement on EPFL benchmarks.[2](https://arxiv.org/html/2604.26591) In open tools, Yosys v0.48 documents the experimental abc_new command, which uses ABC to optimize the design and map it to a target standard cell library.[20](https://yosyshq.readthedocs.io/projects/yosys/en/v0.48/cmd/abc_new.html)\n\n## Limitations and alternatives\n\nThe central limitation is that minimum-area covering of a general DAG is NP-hard, so practical mappers decompose the subject DAG into trees, map each optimally, and glue the results together, sacrificing global optimality; matching against a forest of trees loses the guarantee of a globally optimal solution, although each tree is matched optimally no matter how many levels of logic it contains.[5](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf) • [21](https://doi.org/10.1145/37888.37940) A second limitation is structural bias: the structure of the subject graph, shaped by earlier technology-independent optimization, dictates the structure of the mapped network. Tree- and DAG-covering approaches are fast but sub-optimal for this reason, while Boolean approaches are less structure-dependent but slower.[3](https://people.eecs.berkeley.edu/~alanmi/publications/2005/tech05_map.pdf) Choices and Boolean matching address structural bias, since choices let the mapper select among alternative decompositions rather than inherit one.[3](https://people.eecs.berkeley.edu/~alanmi/publications/2005/tech05_map.pdf) • [16](https://nanohub.org/resources/43301/download/2025.04.01-ECE512-L5.09-Raghunathan-annotated.pdf) A third limitation is the delay model: the strongest optimality results, including optimal DAG covering by dynamic programming, hold under load-independent delay models, and published sources note the assumption without quantifying how inaccurate it is on real libraries. Minimum-area LUT mapping is also NP-hard for k = 4 and k = 5, so even the FPGA area objective lacks polynomial optimal algorithms on DAGs.[5](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf) No published head-to-head benchmark compares mapping with SAT-based exact mapping or direct synthesis, so the practical standing of those alternatives is not settled here.\n\n## References\n\n1. [Mapping (ASPDAC 2025)](https://si2.epfl.ch/demichel/publications/archive/2025/ASPDAC25_Andrea.pdf)\n2. [MappingEvolve: LLM-Driven Code Evolution for Technology Mapping](https://arxiv.org/html/2604.26591)\n3. [Technology Mapping with Boolean Matching, Supergates and Choices](https://people.eecs.berkeley.edu/~alanmi/publications/2005/tech05_map.pdf)\n4. [Technology mapping (Yosys documentation)](https://yosyshq.readthedocs.io/projects/yosys/en/0.41/using%5Fyosys/synthesis/techmap_synth.html)\n5. [Delay-Optimal Technology Mapping by DAG Covering](https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf)\n6. [DAOmap: A Depth-optimal Area Optimization Mapping Algorithm for FPGA Designs](https://people.eecs.berkeley.edu/~alanmi/benchmarks/fpga/iccad04_daomap.pdf)\n7. [FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGAs](https://limsk.ece.gatech.edu/book/papers/flowmap.pdf)\n8. [Improvements to Technology Mapping for LUT-Based FPGAs](https://blif.org/~satrajit/files/2006_FPGA_Improvements_to_FPGA_Tech_Mapping.pdf)\n9. [Technology mapping by binate covering](http://www.ecs.umass.edu/ece/labs/vlsicad/ece667/reading/techmap-binate-servit.pdf)\n10. [A Technology Mapper for Depth-Constrained FPGA Logic Cells](https://www.epfl.ch/labs/lap/wp-content/uploads/2018/05/JiangSep15_ATechnologyMapperForDepthConstrainedFpgaLogicCells_FPL15.pdf)\n11. [Automated Technology Mapping (IBM Journal of Research and Development)](https://www.mirrorservice.org/sites/www.bitsavers.org/pdf/ibm/IBM_Journal_of_Research_and_Development/285/ibmrd2805F.pdf)\n12. [Technology Mapping (Encyclopedia of Computer Science and Engineering)](https://link.springer.com/rwe/10.1007/978-0-387-30162-4_420)\n13. [K.-C. Chen and colleagues (1992). DAG-Map: graph-based FPGA technology mapping for delay optimization. IEEE Design & Test of Computers.](https://doi.org/10.1109/54.156154)\n14. [J. Cong, Yuzheng Ding (1994). FlowMap: an optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.](https://doi.org/10.1109/43.273754)\n15. [Efficient LUT-Based FPGA Technology Mapping for Power Minimization](https://cecs.uci.edu/~papers/compendium94-03/papers/2003/aspdac03/pdffiles/04c_1.pdf)\n16. [Lecture notes: logic synthesis technology mapping approaches (Raghunathan, Purdue ECE 512)](https://nanohub.org/resources/43301/download/2025.04.01-ECE512-L5.09-Raghunathan-annotated.pdf)\n17. [Simultaneous depth and area minimization in LUT-based FPGA mapping (CutMap)](https://dl.acm.org/doi/10.1145/201310.201322)\n18. [LEAP: Learning guided Quality Cut selection for faster Technology Mapping](https://dl.acm.org/doi/10.1145/3676536.3676797)\n19. [MapTune: Advancing ASIC Technology Mapping via Reinforcement Learning Guided Library Tuning](https://arxiv.org/html/2407.18110)\n20. [abc_new, Yosys manual (v0.48)](https://yosyshq.readthedocs.io/projects/yosys/en/v0.48/cmd/abc_new.html)\n21. [DAGON: Technology Binding and Local Optimization by DAG Matching](https://doi.org/10.1145/37888.37940)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Computer hardware › Semiconductor devices & fabrication*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://people.eecs.berkeley.edu/~alanmi/publications/2005/tech05_map.pdf", "https://cecs.uci.edu/~papers/compendium94-03/papers/1998/dac98/pdffiles/22_4.pdf", "https://people.eecs.berkeley.edu/~alanmi/benchmarks/fpga/iccad04_daomap.pdf", "https://cecs.uci.edu/~papers/compendium94-03/papers/2003/aspdac03/pdffiles/04c_1.pdf" ], "url": "https://www.edgepedia.org/technology-mapping", "markdown_url": "https://www.edgepedia.org/technology-mapping.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Technology mapping\", Edgepedia (EdgeChat), https://www.edgepedia.org/technology-mapping. Edgepedia Community License 1.0.", "credit_md": "\"[Technology mapping](https://www.edgepedia.org/technology-mapping)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/technology-mapping](https://www.edgepedia.org/technology-mapping). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Technology mapping\", Edgepedia (EdgeChat), https://www.edgepedia.org/technology-mapping. Edgepedia Community License 1.0.", "speakable": "Technology mapping is the logic synthesis step that converts a technology-independent Boolean network into a netlist of standard-cell or FPGA library gates, optimizing area, delay, or power." }