A convex programming solution for gate-sizing with pipelining constraints. (English) Zbl 1497.94200
Summary: This paper proposes a novel geometric programming based formulation to solve a gate-sizing and retiming problem in the context of circuit optimization. The gate-sizing aspect of the problem involves continuous variables while the retiming problem involves the placement of registers in the circuit and can be naturally modeled using discrete variables. Our formulation is solved using first-order convex programming. We show promising experimental results on industrial circuits. We also investigate formally the computational complexity of the problem. To our knowledge, this is the first effort that solves this problem in a single optimization framework.
MSC:
| 94C11 | Switching theory, applications of Boolean algebras to circuits and networks |
| 90C25 | Convex programming |
| 90C90 | Applications of mathematical programming |
Software:
TILOSReferences:
| [1] | Boyd, S.; Kim, S-J; Patil, D.; Horowitz, M., Digital circuit optimization via geometric programming, Oper Res, 53, 6, 899-932 (2005) · Zbl 1165.90655 · doi:10.1287/opre.1050.0254 |
| [2] | Butnariu, D.; Censor, Y.; Gurfil, P.; Hadar, E., On the behavior of subgradient projections methods for convex feasibility problems in euclidean spaces, SIAM J Optim, 19, 2, 786-807 (2008) · Zbl 1161.49033 · doi:10.1137/070689127 |
| [3] | Chuang W, Sapatnekar SS, Hajj IN (1993) A unified algorithm for gate sizing and clock skew optimization to minimize sequential circuit area. In: International conference on computer-aided design |
| [4] | Coudert O (1997) Gate sizing for constrained delay/power/area optimization. IEEE Trans VLSI, pp 465-472 |
| [5] | DePierro AR, Iusem AN (1985) A simultaneous projections method for linear inequalities. Linear Algebra Appl, pp 243-253 · Zbl 0552.65051 |
| [6] | Fishburn J, Dunlop A (1985) Tilos: a posynomial programming approach to transistor sizing. In: IEEE international conference on computer-aided design, pp 326-328 |
| [7] | Fishburn JP (1990) Clock skew optimization. IEEE Trans Comput |
| [8] | Hurst A, Mischenko A, Brayton RK(2007) Minimizing implementation costs with end-to-end retiming. In: International workshop on logic sysnthesis |
| [9] | Jaggi M (2011) Convex optimization without projection steps. arXiv preprint arxiv:1108.1170 |
| [10] | Joshi, S.; Boyd, S., An efficient method for lareg-scale gate sizing, IEEE Trans Circuits Syst-I, 55, 2760-2773 (2008) · doi:10.1109/TCSI.2008.920087 |
| [11] | Kondamadugula, S.; Naidu, SR, Variation-aware parameter based analog yield optimization methods, Analog Integr Circ Sig Process, 99, 123-132 (2019) · doi:10.1007/s10470-018-1319-x |
| [12] | Leiserson CE, Saxe JB (1983) Optimizing synchronous systems. J VLSI Comput Syst, pp 41-67 · Zbl 0532.94015 |
| [13] | Leiserson, CE; Saxe, JB, Retiming synchronous systems, Algorithmica, 6, 1, 5-35 (1991) · Zbl 0708.94025 · doi:10.1007/BF01759032 |
| [14] | Li WN (1993) Strongly np-hard discrete gate sizing problems. In: IEEE international conference on computer design |
| [15] | Naidu SR (2015) Geometric programming formulation for gate sizing with pipelining constraints. In: Proceedings of the international conference on VLSI design, pp 452-457 |
| [16] | Purushothaman A, Parikh CD (2015) A new delay model and geometric programming-based design automation for latched comparators. Circuits Syst Signal Process, pp 2749-2764 |
| [17] | Rajeswari P, Shekar G, Devi S, Purushothaman A (2018) Geometric programming based power optimization and design automation for a digitally controlled pulse width modulator. Circuits Syst Signal Process, pp 4049-4064 |
| [18] | Roy S, Liu D, Singh J, Um J, Pan DZ (2016) Osfa: a new paradigm of aging aware gate-sizing for power/performance optimizations under multiple operating conditions. IEEE Trans Comput-Aided Des Integr Circuits Syst |
| [19] | Sabet MA, Ghavami B, Raji M (2017) A scalable solution to soft error tolerant circuit design using partitioning-based gate sizing. IEEE Trans Reliab |
| [20] | Satyamurthy H, Sapatnekar SS, Fishburn JP (1998) Speeding up pipelined circuits through a combination of gate sizing and clock skew optimization. IEEE Trans Comput-Aided Des Integr Circuits Syst |
| [21] | Sutherland, I.; Sproull, B.; Harris, D., Logical effort: designing fast CMOS circuits (1999), San Francisco: Morgan-Kaufmann, San Francisco |
| [22] | Wang J, Das D, Zhou H(2009) Gate sizing by lagrangian relaxation revisited. IEEE Trans Comput-Aided Des Integr Circuits Syst, pp 1071-1084 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
