7.3 Advances in Logic Synthesis and Technology Mapping

Time	Label	Presentation Title Authors
14:30	7.3.1	IMPROVEMENTS TO BOOLEAN RESYNTHESIS Speaker: Mathias Soeken, EPFL, CH Authors: Luca Amaru¹, Mathias Soeken², Patrick Vuillod³, Jiong Luo¹, Alan Mishchenko⁴, Janet Olson¹, Robert Brayton⁴ and Giovanni De Micheli² ¹Synopsys Inc., US; ²Integrated System Laboratory – EPFL, CH; ³Synopsys Inc., FR; ⁴UC Berkeley, US Abstract Boolean resynthesis techniques are increasingly used in electronic design automation, to improve quality of results where algebraic methods hit local minima. Boolean methods rely on complete functional properties of a logic circuit, eventually including don't cares. In order to gather such properties, computationally expensive engines are required, e.g., truth tables, SAT and BDDs, which in turn determine the scalability of Boolean resynthesis. In this paper, we present theoretical and practical improvements to Boolean resynthesis, enabling more optimization opportunities to be found at the same, or smaller, runtime cost than state-of-the-art methods. Our contributions include: (i) a theory of Boolean filtering, to drastically reduce the number of gates processed and still retain all possible optimization opportunities, (ii) a weaker notion of maximum set of permissible functions, which can be computed efficiently via truth tables, (iii) a parallel package for truth table computation tailored to speedup Boolean methods, (iv) a generalized refactoring engine which supports multiple representation forms and (v) a practical Boolean resynthesis flow, which combines the techniques proposed so far. Using our Boolean resynthesis on the EPFL benchmarks, we improve 9 of the best known area results in the synthesis competition. Embedded in a commercial EDA flow for ASICs, our Boolean resynthesis flow reduces the area by 2.67%, and total negative slack by 5.48%, after physical implementation, at negligible runtime cost. Download Paper (PDF; Only available from the DATE venue WiFi)
15:00	7.3.2	LOGIC OPTIMIZATION WITH CONSIDERING BOOLEAN RELATIONS Speaker: Chia-Cheng Wu, National Tsing Hua University, TW Authors: Tung-Yuan Lee¹, Chia-Cheng Wu¹, Chia-Chun Lin¹, Yung-Chih Chen² and Chun-Yao Wang³ ¹National Tsing Hua University, TW; ²Yuan Ze University, TW; ³Dept. CS, National Tsing Hua University, TW Abstract Boolean Relation (BR) is a many-to-many mapping between two domains. Logic optimization considering BR can exploit the potential flexibility existed in logic networks to minimize the circuits. In this paper, we present a logic optimization approach considering BR. The approach identifies a proper sub-circuit and locally changes its functionality by solving the corresponding BR in the sub-circuit without altering the overall functionality of the circuit. We conducted experiments on a set of MCNC benchmarks that cannot be further optimized by resyn2 script in ABC. The experimental results show that the node counts of these benchmarks can be further reduced. Additionally, when we apply our approach followed by the resyn2 script repeatedly, we can obtain 6.11% improvements in average. Download Paper (PDF; Only available from the DATE venue WiFi)
15:30	7.3.3	TECHNOLOGY MAPPING FLOW FOR EMERGING RECONFIGURABLE SILICON NANOWIRE TRANSISTORS Speaker: Shubham Rai, Chair For Processor Design, CFAED, Technische Universität Dresden, Dresden, DE Authors: Shubham Rai, Michael Raitza and Akash Kumar, Technische Universität Dresden, DE Abstract Efficient circuit designs can make use of ambipolar nature of silicon nanowire (SiNW) over CMOS. Conventional circuit Design-Flow fails to use this inherent functional flexibility as CMOS based mapping considers a single logical output from logic gates. To address this, we propose an area-optimized technology mapping which uses this innate reconfigurability, offered by SiNW transistors for efficient circuit designs. To enable this objective, we use higher order functions (HOF) to encapsulate this extended functionality. Additionally, the electrical properties of SiNW allow us to take advantage of the available inverted forms of fan-ins for additional savings of area for XOR logic family. Experimental results using our technology mapping shows that area of SiNW based logic design is less by an average of 18:38% as compared to CMOS flow for complete mcnc benchmarks suite. Further, we evaluate our flow for both reconfigurability-aware and static layout for SiNW based logic gates. The whole flow including the new SiNW based genlib and the modified ABC tool is made available under open source license to enable further research for any kind of emerging ambipolar transistors. Download Paper (PDF; Only available from the DATE venue WiFi)
15:45	7.3.4	EFFICIENT SYNTHESIS OF APPROXIMATE THRESHOLD LOGIC CIRCUITS WITH AN ERROR RATE GUARANTEE Speaker: Chia-Chun Lin, National Tsing Hua University, TW Authors: Yung-An Lai¹, Chia-Chun Lin¹, Chia-Cheng Wu¹, Yung-Chih Chen² and Chun-Yao Wang³ ¹National Tsing Hua University, TW; ²Yuan Ze University, TW; ³Dept. CS, National Tsing Hua University, TW Abstract Recently, Threshold logic attracts a lot of attention due to the advances of its physical implementation and the strong binding to neural networks. Approximate computing is a new design paradigm that focuses on error-tolerant applications, e.g., machine learning or pattern recognition. In this paper, we integrate threshold logic with approximate computing and propose a synthesis algorithm to obtain cost-efficient approximate threshold logic circuits with an error rate guarantee. We conduct experiments on IWLS 2005 benchmarks. The experimental results show that the proposed algorithm can efficiently explore the approximability of each benchmark. For a 5% error rate constraint, the circuit cost can be reduced by up to 65%, and 22.8% on average. Compared with a naive method, our approach has a speedup of 2.42 under a 5% error rate constraint. Download Paper (PDF; Only available from the DATE venue WiFi)
16:00	IP3-9, 367	APPROXIMATE HARDWARE GENERATION USING SYMBOLIC COMPUTER ALGEBRA EMPLOYING GRöBNER BASIS Speaker: Saman Fröhlich, DFKI GmbH, DE Authors: Saman Froehlich¹, Daniel Grosse² and Rolf Drechsler² ¹Cyber-Physical Systems, DFKI GmbH, DE; ²University of Bremen/DFKI GmbH, DE Abstract Many applications are inherently error tolerant. Approximate Computing is an emerging design paradigm, which gives the opportunity to make use of this error tolerance, by trading off accuracy for performance. The behavior of a circuit can be defined at an arithmetic level, by describing the input and output relation as a polynomial. Symbolic Computer Algebra (SCA) has been employed to verify that a given circuit netlist matches the behavior specified at the arithmetic level. In this paper, we present a method that relaxes the exactness requirement of the implementation. We propose a heuristic method to generate an approximation for a given netlist and use SCA to ensure that the result is within application-specific bounds for given error-metrics. In addition, our approach allows for automatic generation of approximate hardware wrt. applicationspecific input probabilities. To the best of our knowledge taking input probabilities, which are known for many practical applications, into account has not been considered before. We employ the proposed approach to generate approximate adders and show that the results outperform state-of-the-art, handcrafted approximate hardware. Download Paper (PDF; Only available from the DATE venue WiFi)
16:01	IP3-10, 600	RECONFIGURABLE IMPLEMENTATION OF $GF(2^M)$ BIT-PARALLEL MULTIPLIERS Speaker and Author: José L. Imaña, Complutense University of Madrid, ES Abstract Hardware implementations of arithmetic operations over binary finite fields $GF(2^m)$ are widely used in several important applications, such as cryptography, digital signal processing and error-control codes. In this paper, efficient reconfigurable implementations of bit-parallel canonical basis multipliers over binary fields generated by type II irreducible pentanomials $f(y) = y^m + y^{n+2} + y^{n+1} + y^n +1$ are presented. These pentanomials are important because all five binary fields recommended by NIST for ECDSA can be constructed using such polynomials. In this work, a new approach for $GF(2^m)$ multiplication based on type II pentanomials is given and several post-place and route implementation results in Xilinx Artix-7 FPGA are reported. Experimental results show that the proposed multiplier implementations improve the area$imes$time parameter when compared with similar multipliers found in the literature. Download Paper (PDF; Only available from the DATE venue WiFi)
16:00		End of session Coffee Break in Exhibition Area Coffee Breaks in the Exhibition Area On 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 (Terrace Level of the ICCD). Lunch Breaks (Großer Saal + Saal 1) On all conference days (Tuesday to Thursday), a seated lunch (lunch buffet) will be offered in the rooms "Großer Saal" and "Saal 1" (Saal Level of the ICCD) to fully registered conference delegates only. There will be badge control at the entrance to the lunch break area. Tuesday, March 20, 2018 Coffee Break 10:30 - 11:30 Lunch Break 13:00 - 14:30 Awards Presentation and Keynote Lecture in "Saal 2" 13:50 - 14:20 Coffee Break 16:00 - 17:00 Wednesday, March 21, 2018 Coffee Break 10:00 - 11:00 Lunch Break 12:30 - 14:30 Awards Presentation and Keynote Lecture in "Saal 2" 13:30 - 14:20 Coffee Break 16:00 - 17:00 Thursday, March 22, 2018 Coffee Break 10:00 - 11:00 Lunch Break 12:30 - 14:00 Keynote Lecture in "Saal 2" 13:20 - 13:50 Coffee Break 15:30 - 16:00

Time

Label

Presentation Title
Authors

14:30

7.3.1

IMPROVEMENTS TO BOOLEAN RESYNTHESIS
Speaker:
Mathias Soeken, EPFL, CH
Authors:
Luca Amaru¹, Mathias Soeken², Patrick Vuillod³, Jiong Luo¹, Alan Mishchenko⁴, Janet Olson¹, Robert Brayton⁴ and Giovanni De Micheli²
¹Synopsys Inc., US; ²Integrated System Laboratory – EPFL, CH; ³Synopsys Inc., FR; ⁴UC Berkeley, US
Abstract
Boolean resynthesis techniques are increasingly used in electronic design automation, to improve quality of results where algebraic methods hit local minima. Boolean methods rely on complete functional properties of a logic circuit, eventually including don't cares. In order to gather such properties, computationally expensive engines are required, e.g., truth tables, SAT and BDDs, which in turn determine the scalability of Boolean resynthesis. In this paper, we present theoretical and practical improvements to Boolean resynthesis, enabling more optimization opportunities to be found at the same, or smaller, runtime cost than state-of-the-art methods. Our contributions include: (i) a theory of Boolean filtering, to drastically reduce the number of gates processed and still retain all possible optimization opportunities, (ii) a weaker notion of maximum set of permissible functions, which can be computed efficiently via truth tables, (iii) a parallel package for truth table computation tailored to speedup Boolean methods, (iv) a generalized refactoring engine which supports multiple representation forms and (v) a practical Boolean resynthesis flow, which combines the techniques proposed so far. Using our Boolean resynthesis on the EPFL benchmarks, we improve 9 of the best known area results in the synthesis competition. Embedded in a commercial EDA flow for ASICs, our Boolean resynthesis flow reduces the area by 2.67%, and total negative slack by 5.48%, after physical implementation, at negligible runtime cost.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:00

7.3.2

LOGIC OPTIMIZATION WITH CONSIDERING BOOLEAN RELATIONS
Speaker:
Chia-Cheng Wu, National Tsing Hua University, TW
Authors:
Tung-Yuan Lee¹, Chia-Cheng Wu¹, Chia-Chun Lin¹, Yung-Chih Chen² and Chun-Yao Wang³
¹National Tsing Hua University, TW; ²Yuan Ze University, TW; ³Dept. CS, National Tsing Hua University, TW
Abstract
Boolean Relation (BR) is a many-to-many mapping between two domains. Logic optimization considering BR can exploit the potential flexibility existed in logic networks to minimize the circuits. In this paper, we present a logic optimization approach considering BR. The approach identifies a proper sub-circuit and locally changes its functionality by solving the corresponding BR in the sub-circuit without altering the overall functionality of the circuit. We conducted experiments on a set of MCNC benchmarks that cannot be further optimized by resyn2 script in ABC. The experimental results show that the node counts of these benchmarks can be further reduced. Additionally, when we apply our approach followed by the resyn2 script repeatedly, we can obtain 6.11% improvements in average.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:30

7.3.3

TECHNOLOGY MAPPING FLOW FOR EMERGING RECONFIGURABLE SILICON NANOWIRE TRANSISTORS
Speaker:
Shubham Rai, Chair For Processor Design, CFAED, Technische Universität Dresden, Dresden, DE
Authors:
Shubham Rai, Michael Raitza and Akash Kumar, Technische Universität Dresden, DE
Abstract
Efficient circuit designs can make use of ambipolar nature of silicon nanowire (SiNW) over CMOS. Conventional circuit Design-Flow fails to use this inherent functional flexibility as CMOS based mapping considers a single logical output from logic gates. To address this, we propose an area-optimized technology mapping which uses this innate reconfigurability, offered by SiNW transistors for efficient circuit designs. To enable this objective, we use higher order functions (HOF) to encapsulate this extended functionality. Additionally, the electrical properties of SiNW allow us to take advantage of the available inverted forms of fan-ins for additional savings of area for XOR logic family. Experimental results using our technology mapping shows that area of SiNW based logic design is less by an average of 18:38% as compared to CMOS flow for complete mcnc benchmarks suite. Further, we evaluate our flow for both reconfigurability-aware and static layout for SiNW based logic gates. The whole flow including the new SiNW based genlib and the modified ABC tool is made available under open source license to enable further research for any kind of emerging ambipolar transistors.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:45

7.3.4

EFFICIENT SYNTHESIS OF APPROXIMATE THRESHOLD LOGIC CIRCUITS WITH AN ERROR RATE GUARANTEE
Speaker:
Chia-Chun Lin, National Tsing Hua University, TW
Authors:
Yung-An Lai¹, Chia-Chun Lin¹, Chia-Cheng Wu¹, Yung-Chih Chen² and Chun-Yao Wang³
¹National Tsing Hua University, TW; ²Yuan Ze University, TW; ³Dept. CS, National Tsing Hua University, TW
Abstract
Recently, Threshold logic attracts a lot of attention due to the advances of its physical implementation and the strong binding to neural networks. Approximate computing is a new design paradigm that focuses on error-tolerant applications, e.g., machine learning or pattern recognition. In this paper, we integrate threshold logic with approximate computing and propose a synthesis algorithm to obtain cost-efficient approximate threshold logic circuits with an error rate guarantee. We conduct experiments on IWLS 2005 benchmarks. The experimental results show that the proposed algorithm can efficiently explore the approximability of each benchmark. For a 5% error rate constraint, the circuit cost can be reduced by up to 65%, and 22.8% on average. Compared with a naive method, our approach has a speedup of 2.42 under a 5% error rate constraint.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:00

IP3-9, 367

APPROXIMATE HARDWARE GENERATION USING SYMBOLIC COMPUTER ALGEBRA EMPLOYING GRöBNER BASIS
Speaker:
Saman Fröhlich, DFKI GmbH, DE
Authors:
Saman Froehlich¹, Daniel Grosse² and Rolf Drechsler²
¹Cyber-Physical Systems, DFKI GmbH, DE; ²University of Bremen/DFKI GmbH, DE
Abstract
Many applications are inherently error tolerant. Approximate Computing is an emerging design paradigm, which gives the opportunity to make use of this error tolerance, by trading off accuracy for performance. The behavior of a circuit can be defined at an arithmetic level, by describing the input and output relation as a polynomial. Symbolic Computer Algebra (SCA) has been employed to verify that a given circuit netlist matches the behavior specified at the arithmetic level. In this paper, we present a method that relaxes the exactness requirement of the implementation. We propose a heuristic method to generate an approximation for a given netlist and use SCA to ensure that the result is within application-specific bounds for given error-metrics. In addition, our approach allows for automatic generation of approximate hardware wrt. applicationspecific input probabilities. To the best of our knowledge taking input probabilities, which are known for many practical applications, into account has not been considered before. We employ the proposed approach to generate approximate adders and show that the results outperform state-of-the-art, handcrafted approximate hardware.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:01

IP3-10, 600

RECONFIGURABLE IMPLEMENTATION OF $GF(2^M)$ BIT-PARALLEL MULTIPLIERS
Speaker and Author:
José L. Imaña, Complutense University of Madrid, ES
Abstract
Hardware implementations of arithmetic operations over binary finite fields $GF(2^m)$ are widely used in several important applications, such as cryptography, digital signal processing and error-control codes. In this paper, efficient reconfigurable implementations of bit-parallel canonical basis multipliers over binary fields generated by type II irreducible pentanomials $f(y) = y^m + y^{n+2} + y^{n+1} + y^n +1$ are presented. These pentanomials are important because all five binary fields recommended by NIST for ECDSA can be constructed using such polynomials. In this work, a new approach for $GF(2^m)$ multiplication based on type II pentanomials is given and several post-place and route implementation results in Xilinx Artix-7 FPGA are reported. Experimental results show that the proposed multiplier implementations improve the area$imes$time parameter when compared with similar multipliers found in the literature.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:00

End of session
Coffee Break in Exhibition Area

Coffee Breaks in the Exhibition Area

On 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 (Terrace Level of the ICCD).

Lunch Breaks (Großer Saal + Saal 1)

On all conference days (Tuesday to Thursday), a seated lunch (lunch buffet) will be offered in the rooms "Großer Saal" and "Saal 1" (Saal Level of the ICCD) to fully registered conference delegates only. There will be badge control at the entrance to the lunch break area.

Tuesday, March 20, 2018