doi: 10.7873/DATE.2015.0746

A Universal Macro Block Mapping Scheme for Arithmetic Circuits

Xing Wei1,a, Yi Diao1,b, Tak-Kei Lam1,c and Yu-Liang Wu2

1The Chinese University of Hong Kong, Hong Kong.

2Easy-Logic Technology, Limited, Hong Kong.


A macro block is a functional unit that can be re-used in circuit designs. The problem of general macro block map- ping is to identify such embedded parts, whose I/O signals are unknown, from the netlist that may have been opti- mized in various ways. The mapping results can then be used to ease the functional verification process or for re- placement by more advanced intellectual property (IP) ma- cros. In the past literatures, the mapping problem is mostly limited to the identification of a single adder or multiplier with I/O signals given, which is already NP-hard. How- ever, in today’s typical arithmetic circuits (like digital sig- nal processing (DSP) applications), it is not unusual to have combinations of arithmetic operators implemented as macro blocks for performance gain. To solve this new practical mapping problem, we propose a flow to identify and build a forest of one-bit-adder trees using structural information and formal verification techniques, followed by algorithms that locate macro boundaries and I/O signal orders. Experi- mental results show that our algorithm is highly practical and scalable. It is capable of identifying any combinations of arbitrary adders and multipliers such as (a + b) ×c and a×b+c×d+e×f, where each operand is a multi-bit constant or variable. Most of the benchmarks in ICCAD 2013 CAD Contest [1] can be well handled by our algorithm.

Keywords: Adder, Multiplier, Technology mapping, Arithmetic logic.

Full Text (PDF)