| Title | MIXSyn: An Efficient Logic Synthesis Methodology for Mixed XOR-AND/OR Dominated Circuits |
| Author | *Luca Amarú, Pierre-Emmanuel Gaillardon, Giovanni De Micheli (Integrated Systems Laboratory, Ecole Polytechnique Federale de Lausanne, Switzerland) |
| Page | pp. 133 - 138 |
| Keyword | Logic Synthesis, XOR-intensive, Library-free Technology Mapping, Ambipolar Transistors |
| Abstract | We present a new logic synthesis methodology, called MIXSyn, that produces area-efficient results for mixed XOR-AND/OR dominated logic functions. MIXSyn is a two step synthesis process. The first step is a hybrid logic optimization that enables selective and distinct optimization of AND/OR and XOR-intensive portions of the logic circuit. The second step is a library-free technology mapping that enhances design flexibility with a tractable computational cost. MIXSyn has been tested on a set of large MCNC benchmarks. Experimental results indicate that MIXSyn produces CMOS circuits with 18.0% and 9.2% fewer devices, on the average, with respect to state-of-art academic and commercial synthesis tools, respectively. MIXSyn is also capable to exploit the opportunity of novel XOR implementations offered by the use of double-gate ambipolar devices. Experimental results show that MIXSyn can reduce the number of ambipolar transistors by 20.9% and 15.3%, on the average, with respect to state-of-art academic and commercial synthesis tools, respectively. |
| Slides |
| Title | Optimizing Multi-level Combinational Circuits for Generating Random Bits |
| Author | Chen Wang, *Weikang Qian (Shanghai Jiao Tong University, China) |
| Page | pp. 139 - 144 |
| Keyword | logic synthesis, random bit generation, probabilistic computation |
| Abstract | Random bits are an important construct in many applications, such as hardware-based implementation of probabilistic algorithms and weighted random testing. One approach in generating random bits with required probabilities is to synthesize combinational circuits that transform a set of source probabilities into target probabilities. In [1], the authors proposed a greedy algorithm that synthesizes circuits in the form of a gate chain to approximate target probabilities. However, since this approach only considers circuits of such a special form, the resulting circuits are not satisfactory both in terms of the approximation error and the circuit depth. In this paper, we propose a new algorithm to synthesize combinational circuits for generating random bits. Compared to the previous one, our approach greatly enlarges the search space. Also, we apply a linear property of probabilistic logic computation and an iterative local search method to increase the efficiency of our algorithm. Experimental results comparing the approximation error and the depth of the circuits synthesized by our method to those of the circuits produced by the previous approach demonstrate the superiority of our method. |
| Slides |
| Title | Improving the Mapping of Reversible Circuits to Quantum Circuits Using Multiple Target Lines |
| Author | *Robert Wille, Mathias Soeken, Christian Otterstedt, Rolf Drechsler (University of Bremen, Germany) |
| Page | pp. 145 - 150 |
| Keyword | quantum, reversible, synthesis, optimization, circuits |
| Abstract | The efficient synthesis of quantum circuits is an active research area. Since many of the known quantum algorithms include a large Boolean component (e.g. the database in the Grover search algorithm), quantum circuits are commonly synthesized in a two-stage approach. First, the desired function is realized as a reversible circuit making use of existing synthesis methods for this domain. Afterwards, each reversible gate is mapped to a functionally equivalent quantum gate cascade.
In this paper, we propose an improved mapping of reversible circuits to quantum circuits which exploits a certain structure of many reversible circuits. In fact, it can be observed that reversible circuits are often composed of similar gates which only differ in the position of their target lines. We introduce an extension of reversible gates which allow multiple target lines in a single gate. This enables a significantly cheaper mapping to quantum circuits. Experiments show that considering multiple target lines leads to improvements of up to 85% in the resulting quantum cost. |
| Slides |