11.4 Logic Synthesis: the Faithful, the Approximate and the Stochastic
Date: Thursday 12 March 2015
Time: 14:00 - 15:30
Location / Room: Chartreuse
Chair:
Alex Yakovlev, University of Newcastle, GB
Co-Chair:
Mohamed Sabry, Stanford University, US
Logic synthesis is evolving from traditional frameworks with fully-defined Boolean functions to account for the flexibilities afforded by observability don't cares, to generate smaller circuits through approximation and improve power-performance tradeoffs by taming stochastic computation.
| Time | Label | Presentation Title Authors |
|---|---|---|
| 14:00 | 11.4.1 | A NEW APPROXIMATE ADDER WITH LOW RELATIVE ERROR AND CORRECT SIGN CALCULATION Speakers: Junjun Hu1 and Weikang Qian2 1Shanghai Jiao Tong University, CN; 2Shanghai Jiao Tong University (SJTU), CN Abstract Conventional precise adders need long delay and large power consumption to obtain accurate results. However, in recognition of the error tolerance of some applications such as multimedia processing and machine learning, a few recent works proposed approximate adders that generate inaccurate results occasionally to reduce the delay and power consumption. However, existing approximate adders rarely control the relative error and the potential sign error of the calculation results. In this paper, we propose a novel approximate adder that exploits the generate signals for carry speculation. Furthermore, we introduce a very low-cost error reduction module to effectively control the maximal relative error and a low-overhead sign correction module to fix the sign errors. Compared to the conventional adders, our adder is up to 4.3x faster and saves 47% power for a 32-bit addition. Compared to the existing approximate adders, our adder significantly reduces the maximal relative error and ensures correct sign calculation with comparable area, delay, and power consumption. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 14:30 | 11.4.2 | TOWARDS BINARY CIRCUIT MODELS THAT FAITHFULLY CAPTURE PHYSICAL SOLVABILITY Speakers: Matthias Fuegger1, Robert Najvirt1, Thomas Nowak2 and Ulrich Schmid1 1TU Wien, AT; 2École Normale Supérieure, FR Abstract In contrast to analog models, binary circuit models are high-level abstractions that play an important role in assessing the correctness and performance characteristics of digital circuit designs: (i) modern circuit design relies on fast digital timing simulation tools and, hence, on binary-valued circuit models that faithfully model signal propagation, even throughout a complex design, and (ii) binary circuit models provide a level of abstraction that is amenable to formal correctness proofs. A mandatory feature of any such model is the ability to trace glitches and other short pulses precisely as they occur in physical circuits, as their presence may affect a circuit's correctness and its performance characteristics. Unfortunately, it was recently proved [Függer et al., ASYNC'13] that none of the existing binary-valued circuit models proposed so far, including the two most commonly used pure and inertial delay channels and any other bounded single-history channel, is realistic in the following sense: For the simple Short-Pulse Filtration (SPF) problem, which is related to a circuit's ability to suppress a single glitch, they showed that every bounded single-history channel either contradicts the unsolvability of SPF in bounded time or the solvability of SPF in unbounded time in physical circuits, i.e., no existing model correctly captures physical solvability with respect to glitch propagation. We propose a binary circuit model, based on so-called involution channels, which do not suffer from this deficiency. In sharp contrast to what is possible with all the existing models, they allow to solve the SPF problem precisely when this is possible in physical circuits. To the best of our knowledge, our involution channel model is hence the very first binary circuit model that realistically models glitch propagation, which makes it a promising candidate for developing more accurate tools for simulation and formal verification of digital circuits. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 15:00 | 11.4.3 | A COUPLING AREA REDUCTION TECHNIQUE APPLYING ODC SHIFTING Speakers: Yi Diao1, Tak-Kei Lam2, Xing Wei1 and Yu-Liang Wu2 1The Chinese University of Hong Kong, CN; 2The Chinese University of Hong Kong, HK Abstract Circuit size reduction is a basic problem in today's integrated circuit (IC) design. Besides yielding a smaller area, reducing circuit size can also provide advantages in many operations throughout the design flow, including technology mapping, verification and place-and-route. In recent years, some node based logic synthesis algorithms have been proposed for this purpose. Node Addition and Removal (NAR) and Observability Don't Cares (ODCs) based node merging were found to be quite effective in reducing the number of nodes in a netlist. However, both methods do not address the effect of re-distributing ODCs and the results are virtually fixed after one iteration run. We study the implications of redistributing ODCs and propose a node-based and wire-based coupling synthesis scheme that can effectively find better solutions with the application of ODC shifting operations. Experimental results show that this approach can produce area reductions nearly double of the pure node-based algorithms. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 15:15 | 11.4.4 | A GENERAL DESIGN OF STOCHASTIC CIRCUIT AND ITS SYNTHESIS Speakers: Zheng Zhao and Weikang Qian, Shanghai Jiao Tong University (SJTU), CN Abstract Stochastic computing (SC) is an unconventional paradigm to realize arithmetic computation, where real values are encoded as stochastic bit streams. Compared with conventional computation on binary radix encoding, SC can perform arithmetic computation with very simple circuits. It also has strong tolerance to soft errors. In this paper, we introduce a general design of combinational circuit for stochastic computing, together with its analysis. We further show a synthesis method that can implement arbitrary arithmetic functions with the proposed design. The experimental results demonstrated that compared with the previous methods, our approach produces a circuit with much smaller area and delay. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 15:30 | IP5-12, 647 | SUBHUNTER: A HIGH-PERFORMANCE AND SCALABLE SUB-CIRCUIT RECOGNITION METHOD WITH PRüFER-ENCODING Speakers: Hong-Yan Su, Chih-Hao Hsu and Yih-Lang Li, National Chiao Tung University, TW Abstract Sub-circuit recognition (SR) is a problem of recognizing sub-circuits within a given circuit and is a fundamental component in simulation, verification and testing of computer-aided design. The SR problem can be formulated as subgraph isomorphism problem. Performance of previous works is not scalable as the complexities of modern designs increase. In this paper we propose a novel Prüfer-encoding based SR algorithm that performs scalable and high-performance sub-circuit matching. Several techniques including tree structure partition, tree cutting and circuit graph encoding are proposed herein to decompose the SR problem into several small sub-sequence matching problems. A pre-filtering strategy is applied before matching to remove the sub-circuits that are not likely to be matched. A fast branch and bound approach is developed to identify all the sub-circuits within the given circuit. Experimental results show that SubHunter can achieve better performance than SubGemini and detect all the sub-circuits as well. As the circuit size increases, we can also achieve near linear runtime growth that outperforms the exponential growth for SubGemini, showing the scalability of the proposed algorithm. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 15:31 | IP5-13, 87 | TIMING VERIFICATION FOR ADAPTIVE INTEGRATED CIRCUITS Speakers: Rohit Kumar1, Bing Li2, Yiren Shen1, Ulf Schlichtmann2 and Jiang Hu1 1Texas A&M University, College Station, US; 2Technische Universität München, DE Abstract An adaptive circuit can perform built-in self-detection of timing variations and accordingly adjust itself to avoid timing violations. Compared with conventional over-design approach, adaptive circuit design is conceptually advantageous in terms of power-efficiency. Although the advantage has been witnessed in numerous previous works including test chips, adaptive design is far from being widely used in practice. A key reason is the lack of corresponding timing veri fication support. We develop new timing analysis techniques to fi ll this void. A main challenge is the large runtime complexity due to numerous adaptivity configurations. We propose several pruning and reduction techniques and apply them in conjunction with statistical static timing analysis (SSTA). The proposed method is validated on benchmark circuits including the recent ISPD'13 suite, which has circuit as large as 150K gates. The results show that our method can achieve orders of magnitude speedup over Monte Carlo simulation with about the same accuracy. It is also several times faster than an exhaustive application of SSTA. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 15:32 | IP5-14, 1045 | A ROBUST APPROACH FOR PROCESS VARIATION AWARE MASK OPTIMIZATION Speakers: Jian Kuang, Wing-Kai Chow and Evangeline Young, The Chinese University of Hong Kong, HK Abstract As the minimum feature size continues to shrink, whereas the wavelength of light used for lithography remains constant, Resolution Enhancement Techniques are widely used to optimize mask, so as to improve the subwavelength printability. Besides correcting for error between the printed image and target shape, a mask optimization method also needs to consider process variation. In this paper, a robust mask optimization approach is proposed to optimize the process window as well as the Edge Placement Error (EPE) of the printed image. Experiments results on the public benchmarks are encouraging. Download Paper (PDF; Only available from the DATE venue WiFi) |
| 15:30 | End of session Coffee Break in Exhibition Area Coffee Break in Exhibition AreaOn all conference days (Tuesday to Thursday), coffee and tea will be served during the coffee breaks at the below-mentioned times in the exhibition area. Lunch BreakOn Tuesday and Wednesday, lunch boxes will be served in front of the session room Salle Oisans and in the exhibition area for fully registered delegates (a voucher will be given upon registration on-site). On Thursday, lunch will be served in Room Les Ecrins (for fully registered conference delegates only). Tuesday, March 10, 2015Coffee Break 10:30 - 11:30 Lunch Break 13:00 - 14:30; Keynote session from 13:20 - 14:20 (Room Oisans) sponsored by Mentor Graphics Coffee Break 16:00 - 17:00 Wednesday, March 11, 2015Coffee Break 10:00 - 11:00 Lunch Break 12:30 - 14:30, Keynote lectures from 12:50 - 14:20 (Room Oisans) Coffee Break 16:00 - 17:00 Thursday, March 12, 2015Coffee Break 10:00 - 11:00 Lunch Break 12:30 - 14:00, Keynote lecture from 13:20 - 13:50 Coffee Break 15:30 - 16:00 |
Visit us at DATE 2015
