臺灣博碩士論文加值系統

With the technology process going into nanometer regime, the interconnect delay is a crucial determining factor of circuit performance in modern VSLI designs. Buffer insertion is one of the effective technique to improve the circuit performance. We explore two different problems related to buffer insertion in ASIC and FPGA designs in this thesis.

In modern ASIC designs, a large number of buffers need to be inserted to a large number of nets to improve performance and/or signal integrity. These buffers increase the power consumption and occupy silicon area. So it is important to avoid over-buffering. Buffering spaces are more limited in the denser regions of a layout. Thus it is also necessary to reserve the more premium buffering spaces in the denser regions until they are absolutely needed during physical synthesis. We present a buffer insertion algorithm with consideration of both power dissipation and design density under a given timing constraint for ASIC designs. We propose two formulations for this multi-objective problem and a heuristic solver using Lagrangian relaxation technique.

In FPGAs, signals passing through a long wire do not always exit at the end of the wire. Therefore, the expected delay other than end to end delay of the long wire should be
optimized. We adopt a dynamic programming based approach to insert buffers to minimize the expected delay for FPGA designs and a Lagrangian relaxation based method to achieve
low power and timing closure.

Experiments for ASIC buffering show that our method can significantly improve the overall design density while achieving low power to obtain better timing closure. The
experiments for FPGA buffering show that our method can improve the expected delay by up to 17% compared to the buffered interconnect which only considers end to end delay
optimization.

With the technology process going into nanometer regime, the interconnect delay is a crucial determining factor of circuit performance in modern VSLI designs. Buffer insertion is one of the effective technique to improve the circuit performance. We explore two different problems related to buffer insertion in ASIC and FPGA designs in this thesis.

In modern ASIC designs, a large number of buffers need to be inserted to a large number of nets to improve performance and/or signal integrity. These buffers increase the power consumption and occupy silicon area. So it is important to avoid over-buffering. Buffering spaces are more limited in the denser regions of a layout. Thus it is also necessary to reserve the more premium buffering spaces in the denser regions until they are absolutely needed during physical synthesis. We present a buffer insertion algorithm with consideration of both power dissipation and design density under a given timing constraint for ASIC designs. We propose two formulations for this multi-objective problem and a heuristic solver using Lagrangian relaxation technique.

In FPGAs, signals passing through a long wire do not always exit at the end of the wire. Therefore, the expected delay other than end to end delay of the long wire should be
optimized. We adopt a dynamic programming based approach to insert buffers to minimize the expected delay for FPGA designs and a Lagrangian relaxation based method to achieve
low power and timing closure.

Experiments for ASIC buffering show that our method can significantly improve the overall design density while achieving low power to obtain better timing closure. The
experiments for FPGA buffering show that our method can improve the expected delay by up to 17% compared to the buffered interconnect which only considers end to end delay
optimization.

Acknowledge : i
Abstract : ii
Content : iii
List of Figures : v
List of Tables : vii
1 Introduction 1
1.1 Design Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 ASIC Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 FPGA Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 ASIC Buffering 6
2.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Strategy One Formulation . . . . . . . . . . . . . . . . . . . . . . 8
2.1.2 Strategy Two Formulation . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Lagrangian Relaxation and Heuristic Solver . . . . . . . . . . . . . . . . . 10
iii
2.2.1 Lagrangian Relaxation of Strategy One Formulation . . . . . . . . 11
2.2.2 Lagrangian Relaxation of Strategy Two Formulation . . . . . . . . 12
2.2.3 PDBI : The Heuristic Solver . . . . . . . . . . . . . . . . . . . . . 13
Wire segmentation for determining buffer candidate locations . . . 14
Minimize Lagrangian Relaxtion Function . . . . . . . . . . . . . . 17
Update of Lagrangian Multiplier . . . . . . . . . . . . . . . . . . . 18
2.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 FPGA Buffering 28
3.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 DP for Expected Delay Minimization . . . . . . . . . . . . . . . . . . . . 31
3.3 Lagrangian Relaxation Method for Power Minimization . . . . . . . . . . . 34
3.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4 Conclusion 43
Reference 44

[1] C. J. Alpert and A. Devgan,“Wire segmenting for improved buffer insertion”, In Proc.
of IEEE/ACM Design Automation Conference, pp.588-593, 1997
[2] C. J. Alpert, J. Hu, S. Sapatnekar, and P. Villarrubia, “A practical methodology for
early buffer and wire resource allocation”, In Proc. of IEEE/ACM Design Automation
Conference, pp.189-195, 2001
[3] C. J. Alpert, M. Hrkic, and S. T. Quay, “A fast algorithm for identifying good buffer
insertion candidate locations”, In Proc. of ACM International Symposium on Physical
Design, pp.47-52, 2004
[4] H. B. Bakoglu,“Circuits, Interconnects, and Packaging for VLSI”, Addison-Wesley,
1990
[5] C. P. Chen, Y. P. Chen, and D. F.Wong, “Optimal wire-sizing formula under the Elmore
delay model”. In Proc. ACM/IEEE Design Automation Conf., pp.487-490, 1996.
[6] C. P. Chen and D. F. Wong. “A fast algorithm for optimal wire-sizing under Elmore
delay model”. In Proc. of International Symposium on Circuits and Systems, volume 4,
pp.412-415, 1996.
44
[7] C. C. N. Chu and D. F. Wong, “A new approach to simultaneous buffer insertion and
wire sizing”, In Proc. of IEEE International Conference on Computer-Aided Design,
pp.614-621, 1997
[8] C. C. N. Chu and D. F. Wong, “Closed Form Solution to Simultaneous Buffer Insertion/
Sizing and Wire Sizing”, In Proc. of International Symposium on Physical Design,
pp.192-197, 1997.
[9] C. C. N. Chu and D. F. Wong. “A quadratic programming approach to simultaneous
buffer insertion/sizing and wire sizing”. IEEE Trans. on Computer-Aided Design 18, 6
(June.), pp.787-798. 1999
[10] The international technology roadmap for semiconductors
[11] E. K. P. Chong and S. H. Zak, “An introduction to optimization”, Wiley interscience,
2001
[12] J. Cong and C. K. Koh. “Simultaneous buffer and wire sizing for performance and
power optimization”. In Proc. of Intl. Symp. on Low Power Electronics and Design,
pp.271-276, August 1996.
[13] J. Cong, T. Kong, and D. Z. Pan, “Buffer block planning for interconnect-driven
floorplanning”, In Proc. of IEEE International Conference on Computer Aided Design,
pp.358-363, 1999
[14] S. Dhar and M. A. Franklin. 1991. “Optimum buffer circuits for driving long uniform
lines”. IEEE J. Solid-State Circ. 26, 1 (Jan.), pp. 32-40.
45
[15] A. B. Kahg, S. Muddu, E. Sarto, and R. Sharma, “Interconnect tuning strategies for
high-performance ICs”, In Proc. of Conference on Design Automation and Test in Europe,
pp.471-478, 1998.
[16] J. Lillis, C. K. Cheng, and T. T. Y. Lin, “Optimal wire sizing and buffer insertion for
low power and a generalized delay model”, In Proc. of IEEE International Conference
on Computer Aided Design, pp.138-143, 1995
[17] I-M. Liu, A. Aziz, and D. F. Wong, “Meeting delay constraints in DSM by minimal
repeater insertion”, In Proc. of Conference on Design Automation and Test in Europe,
pp.436-440, 2000
[18] G. Lemieux, E. Lee, M. Tom and A. Yu, “Directional and single driver wires in FPGA
interconnect”, In Proc. of International Conference on Field-Programmable Technology,
pp.41.48, 2004
[19] D. Lewis, E. Ahmed and etc, “The stratix II logic and routing architecture”, In Proc.
of International Symposium on Field-Programmable Gate Arrays, pp.14-20, 2005
[20] Z. Li and W. Shi, “An O(mn) time algorithm for optimal buffer insertion of nets with
m sinks”, In Proc. of Asia and South Pacific Design Automation Conference, pp.320-
325, 2006
[21] E. Lee, G. Lemieux, S. Mirabbasi, “Interconnect driver design for long wires
in field programmable gate arrays”, In Proc. of International Conference on Field-
Programmable Technology, pp.89-96, 2006
46
[22] N. Menezes, R. Baklick, and L. T. Pileggi. ”A sequential quadratic programming
approach to concurrent gate and wire sizing“. In Proc. of IEEE International Conference
on Computer-Aided Design, pp.144-151, 1995.
[23] A. Nemirovsky and D. Yudin, “Informational complexity and efficient methods for
solution of convex extremal problems”, Wiley and Sons, New York, 1983
[24] Y. Peng and X. Liu, “Freeze: Engineering a fast repeater insertion solver for power
minimization using the ellipsoid method”, In Proc. of IEEE/ACM Design Automation
Conference, pp.813-818, 2005
[25] W. Shi and Zhuo Li, “An O(nlogn) time algorithm for optimal buffer insertion”, In
Proc. IEEE/ACM Design Automation Conference, pp.580-585, 2003
[26] P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick, “Repeater scaling and its
impact on CAD”, IEEE Trans. on Computer Aided Design, 23(4):451-463, Apr. 2004
[27] X. Tang and D. F. Wong, “Planning buffer locations by network flows”, In Proc. of
ACM International Symposium on Physical Design, pp.180-185, 2000.
[28] L. P. P. P. van Ginneken,“Buffer placement in distributed RC-tree networks for minimal
Elmore delay”, In Proc. of IEEE International Symposium on Circuits and Systems,
pp.865-868, 1990
[29] F. Y. Young, C. C. N. Chu, W. S. Luk, and Y. C. Wong, “Floorplan area minimization
using lagrangian relaxation”, In Proc. of ACM International Symposium on Physical
Design, pp.174179, 2000