7.4 Advances in Logic Synthesis

Time	Label	Presentation Title Authors
14:30	7.4.1	AN ALGORITHM TO FIND OPTIMUM SUPPORT-REDUCING DECOMPOSITIONS FOR INDEX GENERATION FUNCTIONS. Speaker: Tsutomu Sasao, Meiji University, JP Authors: Tsutomu Sasao, Kyu Matsuura and Yukihiro Iguchi, Meiji University, JP Abstract Index generation functions are useful for pattern matching, and routers in the internet, etc.. This paper presents an algorithm to find support-reducing decompositions for index generation functions. Let n be the number of the input variables, and let s be the number of bound variables. Then, the exhaustive search for finding an optimum support-reducing decomposition requires to check ${n choose s}$ combinations. We found a special property of index generation functions that drastically reduces this search space. With this property, we developed a fast algorithm to find an exact optimum solution.For a given number of bound variables, it finds a decomposition with the fewest rails. Experimental results up to n=60 and s=33 are shown. Download Paper (PDF; Only available from the DATE venue WiFi)
15:00	7.4.2	TAKING ONE-TO-ONE MAPPINGS FOR GRANTED: ADVANCED LOGIC DESIGN OF ENCODER CIRCUITS Speaker: Robert Wille, Johannes Kepler University, Linz, AT Authors: Alwin Zulehner¹ and Robert Wille² ¹Johannes Kepler University, AT; ²Johannes Kepler University Linz, AT Abstract Encoders play an important role in many areas such as memory addressing, data demultiplexing, or for interconnect solutions. However, design solutions for the automatic synthesis of corresponding circuits suffer from various drawbacks, e.g. they are often not scalable, do not exploit the full degree of freedom, or are applicable to realize certain codes only. All these problems are caused by the fact that existing design solutions have to explicitly guarantee a one-to-one mapping. In this work, we propose an alternative design approach which relies on dedicated description means for both, the specification of an encoder as well as its circuit. Based on that, synthesis can be conducted without the need to explicitly take care of guaranteeing one-to-one mappings. Experiments show that this indeed overcomes the drawbacks of current design solutions and leads to an improvement in the resulting number of gates by up to 92%. Download Paper (PDF; Only available from the DATE venue WiFi)
15:30	7.4.3	ANALYSIS OF SHORT-CIRCUIT CONDITIONS IN LOGIC CIRCUITS Speaker: João Afonso, INESC-ID, PT Authors: João Pedro¹ and Jose Monteiro² ¹INESC-ID, PT; ²INESC-ID, IST, U Lisboa, PT Abstract This paper offers a novel approach for the analysis of input conditions that cause a short-circuit in a logic circuit, that is, that create a direct path from the power supply to ground. We model the logic circuit as a graph where edges represent transistors which are either open or closed, function of the input conditions. From this graph we derive a Quantified Boolean Formula (QBF) problem whose solution identifies the existence of a valid input combination that creates a path in the graph between the pair of nodes that represent the power source and ground, without ever enumerating all input combinations. We build the QBF problem incrementally, minimising the number of active nodes and hence of possible states. In the end, we obtain a relatively simple CNF expression, function only of the circuit inputs, that is handled by a generic SAT solver. We present results that demonstrate the practical applicability of our method on circuit instances that are intractable by alternative methods. Download Paper (PDF; Only available from the DATE venue WiFi)
15:45	7.4.4	BUSY MAN'S SYNTHESIS: COMBINATIONAL DELAY OPTIMIZATION WITH SAT Speaker: Mathias Soeken, EPFL, CH Authors: Mathias Soeken¹, Giovanni De Micheli¹ and Alan Mishchenko² ¹EPFL, CH; ²UC Berkeley, US Abstract Boolean SAT solving can be used to find a minimum-size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival times and the maximum depth. After integration into a depth-optimizing mapping algorithm, the proposed SAT formulation can be used to perform logic rewriting to reduce the logic depth of a network. It is shown that to be effective the logic rewriting algorithm requires (i) a fast SAT formulation and (ii) heuristics to quickly determine whether the given delay constraints are feasible for a given function. The proposed algorithm is more versatile than previous algorithms, which is confirmed by the experimental results. Download Paper (PDF; Only available from the DATE venue WiFi)
16:00	IP3-13, 799	TECHNOLOGY MAPPING WITH ALL SPIN LOGIC Speaker: Azadeh Davoodi, University of Wisconsin - Madison, US Authors: Boyu Zhang¹ and Azadeh Davoodi² ¹University of Wisconsin-Madison, US; ²University of Wisconsin - Madison, US Abstract This work is the first to propose a technology mapping algorithm for All Spin Logic (ASL) device. The ASL device is the most actively-pursed one among spintronics devices which themselves fall under emerging post-CMOS nano-technologies. We identify the shortcomings of directly applying the classical technology mapping with ASL devices, and propose techniques to extend the classical procedure to handle these shortcomings. Our results show that our ASL-aware technology mapping algorithm can achieve on-average 9.15% and up to 27.27% improvement in delay (when optimizing delay) with slight improvement in area, compared to the solution generated by classical technology mapping. In a broader sense, our results show the need for developing circuit-level CAD tools that are aware of and optimized for emerging technologies in order to better assess their promise as we move to the post-CMOS era. Download Paper (PDF; Only available from the DATE venue WiFi)
16:01	IP3-14, 734	A NEW METHOD TO IDENTIFY THRESHOLD LOGIC FUNCTIONS Speaker: Spyros Tragoudas, Southern Illinois University Carbondale, US Authors: Seyed Nima Mozaffari, Spyros Tragoudas and Themistoklis Haniotakis, Southern Illinois University, US Abstract An Integer Linear Programming based method to identify current mode threshold logic functions is presented. The approach minimizes the transistor count and benefits from a generalized definition of threshold logic functions. Process variations are taken into consideration. Experimental results show that many more functions can be implemented with predetermined hardware overhead, and the hardware requirement of a large percentage of existing threshold functions is reduced. Download Paper (PDF; Only available from the DATE venue WiFi)
16:00		End of session Coffee Break in 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. Tuesday, March 28, 2017 Coffee Break 10:30 - 11:30 Coffee Break 16:00 - 17:00 Wednesday, March 29, 2017 Coffee Break 10:00 - 11:00 Coffee Break 16:00 - 17:00 Thursday, March 30, 2017 Coffee Break 10:00 - 11:00 Coffee Break 15:30 - 16:00

Time

Label

Presentation Title
Authors

14:30

7.4.1

AN ALGORITHM TO FIND OPTIMUM SUPPORT-REDUCING DECOMPOSITIONS FOR INDEX GENERATION FUNCTIONS.
Speaker:
Tsutomu Sasao, Meiji University, JP
Authors:
Tsutomu Sasao, Kyu Matsuura and Yukihiro Iguchi, Meiji University, JP
Abstract
Index generation functions are useful for pattern matching, and routers in the internet, etc.. This paper presents an algorithm to find support-reducing decompositions for index generation functions. Let n be the number of the input variables, and let s be the number of bound variables. Then, the exhaustive search for finding an optimum support-reducing decomposition requires to check ${n choose s}$ combinations. We found a special property of index generation functions that drastically reduces this search space. With this property, we developed a fast algorithm to find an exact optimum solution.For a given number of bound variables, it finds a decomposition with the fewest rails. Experimental results up to n=60 and s=33 are shown.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:00

7.4.2

TAKING ONE-TO-ONE MAPPINGS FOR GRANTED: ADVANCED LOGIC DESIGN OF ENCODER CIRCUITS
Speaker:
Robert Wille, Johannes Kepler University, Linz, AT
Authors:
Alwin Zulehner¹ and Robert Wille²
¹Johannes Kepler University, AT; ²Johannes Kepler University Linz, AT
Abstract
Encoders play an important role in many areas such as memory addressing, data demultiplexing, or for interconnect solutions. However, design solutions for the automatic synthesis of corresponding circuits suffer from various drawbacks, e.g. they are often not scalable, do not exploit the full degree of freedom, or are applicable to realize certain codes only. All these problems are caused by the fact that existing design solutions have to explicitly guarantee a one-to-one mapping. In this work, we propose an alternative design approach which relies on dedicated description means for both, the specification of an encoder as well as its circuit. Based on that, synthesis can be conducted without the need to explicitly take care of guaranteeing one-to-one mappings. Experiments show that this indeed overcomes the drawbacks of current design solutions and leads to an improvement in the resulting number of gates by up to 92%.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:30

7.4.3

ANALYSIS OF SHORT-CIRCUIT CONDITIONS IN LOGIC CIRCUITS
Speaker:
João Afonso, INESC-ID, PT
Authors:
João Pedro¹ and Jose Monteiro²
¹INESC-ID, PT; ²INESC-ID, IST, U Lisboa, PT
Abstract
This paper offers a novel approach for the analysis of input conditions that cause a short-circuit in a logic circuit, that is, that create a direct path from the power supply to ground. We model the logic circuit as a graph where edges represent transistors which are either open or closed, function of the input conditions. From this graph we derive a Quantified Boolean Formula (QBF) problem whose solution identifies the existence of a valid input combination that creates a path in the graph between the pair of nodes that represent the power source and ground, without ever enumerating all input combinations. We build the QBF problem incrementally, minimising the number of active nodes and hence of possible states. In the end, we obtain a relatively simple CNF expression, function only of the circuit inputs, that is handled by a generic SAT solver. We present results that demonstrate the practical applicability of our method on circuit instances that are intractable by alternative methods.
Download Paper (PDF; Only available from the DATE venue WiFi)

15:45

7.4.4

BUSY MAN'S SYNTHESIS: COMBINATIONAL DELAY OPTIMIZATION WITH SAT
Speaker:
Mathias Soeken, EPFL, CH
Authors:
Mathias Soeken¹, Giovanni De Micheli¹ and Alan Mishchenko²
¹EPFL, CH; ²UC Berkeley, US
Abstract
Boolean SAT solving can be used to find a minimum-size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival times and the maximum depth. After integration into a depth-optimizing mapping algorithm, the proposed SAT formulation can be used to perform logic rewriting to reduce the logic depth of a network. It is shown that to be effective the logic rewriting algorithm requires (i) a fast SAT formulation and (ii) heuristics to quickly determine whether the given delay constraints are feasible for a given function. The proposed algorithm is more versatile than previous algorithms, which is confirmed by the experimental results.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:00

IP3-13, 799

TECHNOLOGY MAPPING WITH ALL SPIN LOGIC
Speaker:
Azadeh Davoodi, University of Wisconsin - Madison, US
Authors:
Boyu Zhang¹ and Azadeh Davoodi²
¹University of Wisconsin-Madison, US; ²University of Wisconsin - Madison, US
Abstract
This work is the first to propose a technology mapping algorithm for All Spin Logic (ASL) device. The ASL device is the most actively-pursed one among spintronics devices which themselves fall under emerging post-CMOS nano-technologies. We identify the shortcomings of directly applying the classical technology mapping with ASL devices, and propose techniques to extend the classical procedure to handle these shortcomings. Our results show that our ASL-aware technology mapping algorithm can achieve on-average 9.15% and up to 27.27% improvement in delay (when optimizing delay) with slight improvement in area, compared to the solution generated by classical technology mapping. In a broader sense, our results show the need for developing circuit-level CAD tools that are aware of and optimized for emerging technologies in order to better assess their promise as we move to the post-CMOS era.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:01

IP3-14, 734

A NEW METHOD TO IDENTIFY THRESHOLD LOGIC FUNCTIONS
Speaker:
Spyros Tragoudas, Southern Illinois University Carbondale, US
Authors:
Seyed Nima Mozaffari, Spyros Tragoudas and Themistoklis Haniotakis, Southern Illinois University, US
Abstract
An Integer Linear Programming based method to identify current mode threshold logic functions is presented. The approach minimizes the transistor count and benefits from a generalized definition of threshold logic functions. Process variations are taken into consideration. Experimental results show that many more functions can be implemented with predetermined hardware overhead, and the hardware requirement of a large percentage of existing threshold functions is reduced.
Download Paper (PDF; Only available from the DATE venue WiFi)

16:00

End of session
Coffee Break in 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.

Tuesday, March 28, 2017