Enabling exact delay synthesis

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.

Published in:
Proceedings of the 36th IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
Presented at:
36th IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Irvine, California, USA, November 13-16, 2017
Nov 16 2017
ERC Cybercare 669354 / Grant 2016016 United States-Israel Binational Science Foundation

Note: The status of this file is: EPFL only

 Record created 2018-01-09, last modified 2020-04-20

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)