Dominator-Based Technology Mapping System

Cut enumeration, as the crucial and most time-consuming step of technology mapping, is to prepare candidate cuts for cut selection. Traditional methods for cut enumeration are to compute all the candidate cuts for each logic gate and then find a depth-optimal mapping solution. The algorithm DMAP in the thesis adopts the most efficient Boolean logic representation found so far: Reduced Ordered Binary Decision Diagram (ROBDD). Based on the structural characteristics and various dominators, including arithmetic dominators (0-dominator, 1-dominator, x-dominator) and Boolean operators (generalized dominator and generalized x-dominator), DMAP can produce less cuts efficiently and effectively. Also, the thesis presents some heuristics approaches. Compared to state-of-the-art technology mapper ABC, our proposed mapping algorithm offers up to 3x average runtime reduction with negligible area penalty.