Home

Multi-Valued Logic Synthesis

Boolean Technology Mapping

Berkeley Language and Automata Manipulation

Combinational Verification

Physically-Aware Synthesis

Download Software

People / Contact

introduction

Technology mapping is the process of expressing a given boolean network in terms of library gates (for standard cells) or look-up tables (for FPGAs). MVSIS has technology mappers for both standard cells and FPGAs. The core mapping algorithm in both cases uses boolean matching which is superior to structural matching for large and complex libraries, leading to better quality results.

motivation: structural bias

Since the final mapping is derived from the technology independent netlist by local re-writes, the quality of the initial netlist determines to a large extent the quality of the final mapping. To mitigate this structural bias the new mapper introduces supergates and choice nodes.

supergates

A supergate is a virtual gate built from a set of real library gates. By having these larger gates, the mapper can look deeper into the circuit, thus producing better results. This is because the mapper is constrained by the fact that there is a correspondence in the mapped netlist and the initial netlist at the gate boundaries. By mapping with larger gates, these constraints are relaxed, leading to better quality.

choice nodes

Choice nodes in the initial netlist specificy different structural implementations and serve as an efficient way of encoding multiple netlists in one. The choices can be added in a number of ways such as by

  • algebraic re-writing like the Lehman Watanabe mapper
  • combining netlists from different scripts
  • combining netlists at different stages of the same script (this is useful since synthesis scripts are often heuristic, and there is no guarantee that the final netlist is overall the best netlist for mapping).

publications

  1. S. Chatterjee, A. Mishchenko, R. Brayton, T. Kam and X. Wang, "Reducing Structural Bias in Technology Mapping," To appear in IWLS 05. (PDF)
  2. A. Mishchenko, S. Chatterjee, M. Ciesielski and R. Brayton, "An Integrated Technology Mapping Environment," To appear in IWLS 05. (PDF)

Contact 
©2002-2018 U.C. Regents