TY - CPAPER
DO - 10.1109/ICCAD.2017.8203799
AB - Given (i) a Boolean function, (ii) a set of arrival times at the inputs, and (iii) a gate library with associated delay values, the exact delay synthesis problem asks for a circuit implementation which minimizes the arrival time at the output(s). The exact delay synthesis problem, with given input arrival times, relates to computing the communication complexity of a Boolean function, which is an intractable problem. Input arrival times are variable and can take any value, thereby making the exact delay synthesis search space infinite. This paper presents theory and algorithms for exact delay synthesis. We introduce the theory of equioptimizable arrival times, which allows us to partition all arrival time patterns into a finite set of equivalence classes. Thanks to this new theory, we create for the first time exact delay circuit databases covering all Boolean functions up to 5 variables and all possible arrival time patterns. We describe further arrival time compression techniques which enable the creation of larger databases. We propose an enhanced delay synthesis flow capable of dealing with large circuits, combining exact delay logic rewriting and Boolean optimization techniques, attaining unprecedented results. We improve 9/10 of the best known results in the EPFL arithmetic delay synthesis competition, outperforming previous best results up to 3×. Embedded in a commercial EDA flow for ASICs, our exact delay synthesis techniques reduce the total negative slack by 12.17%, after physical implementation, at negligible area and runtime costs.
T1 - Enabling exact delay synthesis
DA - 2017-11-16
AU - Amarù, Luca
AU - Soeken, Mathias
AU - Vuillod, Patrick
AU - Luo, Jiong
AU - Mishchenko, Alan
AU - Gaillardon, Pierre-Emmanuel
AU - Olson, Janet
AU - Brayton, Robert
AU - De Micheli, Giovanni
JF - Proceedings of the 36th IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
PB - IEEE
N1 - ERC Cybercare 669354 / Grant 2016016 United States-Israel Binational Science Foundation
ID - 233721
SN - 978-1-5386-3093-8
UR - http://infoscience.epfl.ch/record/233721/files/2017_iccad.pdf
ER -