Date: Thursday 28 March 2019
Time: 16:00 - 17:30
Location / Room: Room 2
Chair:
Jordi Cortadella, University Politecnica de Catalunya, ES
Co-Chair:
Tiziano Villa, University of Verona, IT
The recent progress in logic synthesis is presented in this session. The research targets new emerging applications of synthesis and extends the current computing limits of logic synthesis. The first paper introduces an approximate synthesis algorithm for realizing a logic function on a lattice using Boolean satisfiability. The second paper presents a scalable Boolean optimization flow including enhancements to difference-based resubstitution, AIG optimization and kerneling. The third paper improves exact logic synthesis techniques and integrates them into a scalable generic logic rewriting algorithm. The fourth paper proposes a polynomial-time algorithm for computing the closest symmetric approximation for a Boolean function.
| Time | Label | Presentation Title Authors |
|---|---|---|
| 16:00 | 12.2.1 | A SATISFIABILITY-BASED APPROXIMATE ALGORITHM FOR LOGIC SYNTHESIS USING SWITCHING LATTICES Speaker: Levent Aksoy, Istabul Technical University, TR Authors: Levent Aksoy and Mustafa Altun, Istanbul Technical University, TR Abstract In recent years the realization of a logic function on two-dimensional arrays of four-terminal switches, called switching lattices, has attracted considerable interest. Exact and approximate methods have been proposed for the problem of synthesizing Boolean functions on switching lattices with minimum size, called lattice synthesis (LS) problem. However, the exact method can only handle relatively small instances and the approximate methods may find solutions that are far from the optimum. This paper introduces an approximate algorithm, called JANUS, that formalizes the problem of realizing a logic function on a given lattice, called lattice mapping (LM) problem, as a satisfiability problem and explores the search space of the LS problem in a dichotomic search manner, solving LM problems for possible lattice candidates. This paper also presents three methods to improve the initial upper bound and an efficient way to realize multiple logic functions on a single lattice. Experimental results show that JANUS can find solutions very close to the minimum in a reasonable time and obtain better results than the existing approximate methods. The solutions of JANUS can also be better than those of the exact method, which cannot be determined to be optimal due to the given time limit, where the maximum gain on the number of switches reaches up to 25%. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 16:30 | 12.2.2 | SCALABLE BOOLEAN METHODS IN A MODERN SYNTHESIS FLOW Speaker: Eleonora Testa, EPFL, CH Authors: Eleonora Testa1, Luca Amaru2, Mathias Soeken1, Alan Mishchenko3, Patrick Vuillod2, Jiong Luo2, Christopher Casares2, Pierre-Emmanuel Gaillardon4 and Giovanni De Micheli5 1EPFL, CH; 2Synopsys Inc., US; 3UC Berkeley, US; 4University of Utah, US; 5École Polytechnique Fédérale de Lausanne (EPFL), CH Abstract With the continuous push to improve Quality of Results (QoR) in Electronic Design Automation (EDA), Boolean methods in logic synthesis have been recently drawing the attention of researchers. Boolean methods achieve better QoR than algebraic methods but require higher computational cost. In this paper, the Scalable Boolean Method (SBM) framework is presented. The SBM consists of 4 optimization engines designed to be scalable in a modern synthesis flow. The first presented engine is a generalized resubstitution framework based on computing, and implementing, the Boolean difference between two nodes. The second consists of a gradient-based AIG optimization, while the third one is based on heterogeneous elimination for kerneling. The last proposed engine is a revisiting of Maximum Set of Permissible Functions (MSPF) computation with BDDs. Altogether, the SBM framework enables promising synthesis results. We improve 12 of the best known area results in the EPFL synthesis competition. Embedded in a commercial EDA flow for state-of-the-art ASICs, the new Boolean methods enable - 2.20% combinational area savings and -5.99% total negative slack reduction, after physical implementation, at contained runtime cost. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 17:00 | 12.2.3 | ON-THE-FLY AND DAG-AWARE: REWRITING BOOLEAN NETWORKS WITH EXACT SYNTHESIS Speaker: Heinz Riener, EPFL, CH Authors: Heinz Riener1, Winston Haaswijk1, Alan Mishchenko2, Giovanni De Micheli1 and Mathias Soeken1 1EPFL, CH; 2UC Berkeley, US Abstract The paper presents a generalization of DAG-aware AIG rewriting for k-feasible Boolean networks, whose nodes are k-input lookup tables (k-LUTs). We introduce a DAG-aware rewriting algorithm, called cut rewriting, that uses exact synthesis to compute replace- ments on the fly. Cut rewriting pre-computes a large number of possible replacement candidates, but instead of eagerly rewriting the Boolean network, stores the replacements in a conflict graph. Heuristic optimization is used to determine a best, maximal subset of replacements that can be simultaneously applied to the Boolean network. We have implemented cut rewriting and have optimized 3- LUT mapped Boolean networks obtained from the ISCAS and EPFL combinational benchmark suites. For 3-LUT networks, experiments show that we achieve an average size improvement of 5.58% and up to 40.19% after state-of-the-art Boolean rewriting techniques were applied until saturation. Similarly, for 4-LUT networks, we obtain an average improvement of 4.04% and up to 12.60%. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 17:15 | 12.2.4 | APPROXIMATE LOGIC SYNTHESIS BY SYMMETRIZATION Speaker: Anna Bernasconi, Universita, IT Authors: Anna Bernasconi1, Valentina Ciriani2 and Tiziano Villa3 1Università di Pisa, IT; 2Università degli Studi di Milano, IT; 3Dipartimento d'Informatica, Università di Verona, IT Abstract Approximate synthesis is a recent trend in logic synthesis that changes some outputs of a logic specification to take advantage of error tolerance of some applications and reduce complexity and consumption of the final implementation. We propose a new approach to approximate synthesis of combinational logic where we derive its closest symmetric approximation, i.e., the symmetric function obtained by injecting the minimum number of errors in the original function. Since BDDs of totally symmetric functions are quite compact, this approach is particularly convenient for BDD-based implementations, such as networks of MUXes directly mapped from BDDs. Our contribution is twofold: first we propose a polynomial algorithm for computing the closest symmetric approximation of an incompletely specified Boolean function with an unbounded number of errors; then we discuss strategies to achieve partial symmetrization of the original specification while satisfying given error bounds. Experimental results on classical and new benchmarks confirm the efficacy of the proposed approach. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 17:30 | End of session | |