||Timing-Aware Physical Design Methodologies for Implementing Low Power Designs
||Department of Electrical Engineering
Clock power reduction
hybrid routing structure
Due to the prevalence of portable electronic products, lower power attracts more attention for circuit designs. However, as technology advances, an SOC design can contain more and more components, which lead to a higher power density. Hence, lower power becomes one of the most important issues in modern VLSI designs. Reducing power consumption not only can enhance battery life but also can avoid performance degradation induced by the overheating problem.
There have been many lower power design techniques proposed to reduce system power consumption. Among these techniques, the multi-bit flip-flop and the power-gated
are considered as the most effective approaches. Although these two methods both can reduce power consumption, they also increase implementation complexity of the physical
design. For instance, we have to replace several single-bit flip-flops by a single multi-bit flip-flop when the multi-bit flip-flop technique is applied to a design. But the timing in an original layout may be affected if an improper set of single-bit flip-flops is selected or a new inserted multi-bit flip-flop is placed at improper location. This will result in performance degradation or even failure in the functionality. Besides, when a power-gated technique is applied to a design, it may cause severe rush current if the turned-on sequence of power
switches or their timing are not properly controlled, and thus the reliability of a system is degraded and the response time is increased.
This dissertation presents two design methodologies which respectively target on implementing multi-bit flip-flops and power-gated techniques in the physical design. Since both of two techniques may induce timing-related issues, our approaches show the methodologies to resolve these problems and make them feasible in real VLSI designs. The experimental results have demonstrated the efficiency and effectiveness of our approaches. For the multi-bit flip-flop technique, our algorithm can achieve power reduction and simultaneously minimize wirelength without violating timing constraint. For the power gated technique, the proposed methodology can avoid occurrence of large rush current; hence, the reliability of a design is maintained.
Abstract (Chinese) I
Table of Contents VII
List of Tables X
List of Figures XI
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Overview of the Dissertation 2
1.2.1. Approach of Power Reduction by Using Multi-Bit Flip-Flops 2
1.2.2. Methodology to Control Turn-On Sequence of Power Switches for Power Gating Designs 3
1.3 Thesis Organization 3
Chapter 2 Background Knowledge 5
2.1 Power consumption in circuit design 5
2.1.1. Dynamic Power 5
2.1.2. Static Power 8
2.2 Low Power Techniques 9
2.2.1. Gate Level Power Optimization 9
2.2.2. Multi-threshold Logics 10
2.2.3. Clock Network Power Saving 10
2.2.4. Power Network Management 12
2.3 Usage of Multi-Bit Flip-Flops in Clock Network 14
2.3.1. Structure 14
2.3.2. Design Concerns 15
2.3.3. Related Work 16
2.4 Power-Gated Design 19
2.4.1. Structure 19
2.4.2. Design Concerns of Rush Current and Wake-Up Time 21
2.4.3. Related Work 22
Chapter 3 Approach of Power Reduction by Using Multi-Bit Flip-Flops 24
3.1 Problem Formulation 24
3.2 Algorithm 26
3.2.1. Placement Space Determination 27
3.2.2. Combination Table Construction 30
3.2.3. Flip-Flop Merging 36
3.3 Computation Complexity Analysis 42
3.4 Experiment Results 43
3.4.1. Performance Comparison with Chang et al.  43
3.4.2. Average-Case Performance 47
3.5 Summary 49
Chapter 4 Methodology to Control Turn-on Sequence of Power Switches for Power Gating Designs 51
4.1 Methodology for Power Switches Turn-on Sequence Determination 51
4.2 Power Network Modeling 54
4.2.1. C1C2 Model with Leakage Resistance 54
4.2.2. Equations for Estimating Voltage 57
4.2.3. Equations for Estimating Rush Current 60
4.3 Algorithm 61
4.3.1. Overview of Algorithm Flow 62
4.3.2. Power Switches Selection 63
4.3.3. Determination of the Depth of Daisy-Chain 64
4.3.4. Construction of Daisy-Chain 68
4.3.5. Construction of Distributed Fishbone 70
4.4 Experiment Results 71
4.4.1. Waveform Comparison with HSPICE Simulation Results 71
4.4.2. Quality of Solutions Generated by ILP Formulation 76
4.4.3. Test Cases Simulation Results 77
4.5 Summary 79
Chapter 5 Conclusions and Future Work 81
5.1 Conclusions 81
5.2 Future Work 82
5.2.1. More Precise Power Network Equivalent Model Formulation 82
5.2.2. Better Routing Structure Exploring 83
5.2.3. Robustness-aware Routing Structure Construction 84
5.2.4. Power Verification Methodology for Low Power Technique Implementation at Early Design Stage 86
Publication List 100
A. Transaction / Journal Papers 100
B. Conference Papers 101
C. Awards 102
 P. Gronowski, W. j. Bowhill, R. P. Preston, M. K. Gowan, and R. L. Allmon, “Highperformance microprocessor design,” IEEE J. Solid-State Circuits, vol. 33, no. 5, pp. 676–686, May 1998.
 W. Hou, D. Liu, and P.-H. Ho, “Automatic register banking for low-power clock trees,” in Proc. Int. Symp. Quality Electron. Design, Mar. 2009, pp. 647–652.
 Y.-T. Shyu, J.-M. Lin, C.-P. Huang, C.-W. Lin, Y.-Z. Lin, and S.-J. Chang, “An effective and efficient approach for power reduction by using multi-bit flip-flops,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 21, no.4, pp. 624–635, Apr. 2013.
 Y.-T. Shyu, J.-M. Lin, C.-C. Lin, C.-P. Huang, and S.-J. Chang, “An efficient and effective methodology to control turn-on sequence of power switches for power gating design,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 35, no. 10, pp. 1730–1743, Oct., 2016.
 N. H. E. Weste, D. Harris, and A. Banerjee, CMOS VLSI Design: A Circuits and Systems Perspective. 3rd ed. Pearson, Boston, MA: Addison Wesley, 2004.
 M. Keating, D. Flynn, R. Aitken, A. Gibbons, and K. Shi, Low Power Methodology Manual: For System-on-Chip Design. New York: Springer, 2007.
 J. Kao, S. Narendra, and A. Chandrakasan, “Subthreshold leakage modeling and reduction techniques,” in Proc. Int. Conf. Comput.-Aided Design, Nov. 2002, pp. 141–148.
 CAO, K.M. et al. “BSIM4 gate leakage model including source-drain partition.” in Int. Electron Devices Meeting Dig. Tech. Papers, Dec. 2000, pp. 815–818.
 L. Benini, and G. D. Micheli, Logic Synthesis for Low Power. in: S. Hassoun, T. Sasao (eds.) Logic Synthesis and Verification, pp. 197–223. Kluwer Academic Publishers
Norwell, MA, USA, 2002.
 K. Roy, and C. Prasad, “Circuit activity based logic synthesis for low power reliable operations,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 1, no. 4, pp. 503–513, Dec. 1993.
 J. Lillis, C.-K. Cheng, and T.-T. Lin, “Optimal wire sizing and buffer insertion for low power and a generalized delay model,” IEEE J. Solid-State Circuits, vol. 31, no.3, pp. 437–447, March, 1996.
 D. Chinnery, Low Power Design Automation, Ph.D. dissertation, Dept. Elect. Eng. Comput. Sci., Univ. California, Berkeley, Berkeley, CA, 2006.
 P. Balasubramanian, C. H. Narayanan, and K. Anantha, “Low power design of digital combinatorial circuits with complementary CMOS logic,” Int. J. Electron. Circuits
Syst., vol. 1, no. 1, pp. 10–18, 2007.
 I. Brzozowski, and A. Kos, “Two-level logic synthesis for low power based on new model of power dissipation,” in Proc. Design Diagnostics Electron. Circuits Syst., Apr. 2007, pp. 139–144.
 U. Narayanan, and C. L. Liu, “Low power logic synthesis for xor based circuits,” in Proc. Int. Conf. Comput.-Aided Design, Nov. 1997, pp. 570–574.
 S. V. Kosonocky, M. Immediato, P. Cottrell, T. Hook, R. Mann, and J. Brown, “Enhanced multi-threshold (MTCMOS) circuits using variable well bias,” in Proc. Int. Symp. Low Power Electron. Design, Aug. 2001, pp. 165–169.
 D. Duarte, V. Narayanan, and M. J. Irwin, “Impact of technology scaling in the clock system power,” in Proc. Comput. Soc. Annu. Symp. VLSI, Apr. 2002, pp. 25–26.
 H. Kawagachi and T. Sakurai, “A reduced clock-swing flip-flop (RCSFF) for 63% clock power reduction,” in Proc. Symp. VLSI Circuits, Jun. 1997, pp. 97–98.
 Y. Cheon, P.-H. Ho, A. B. Kahng, S. Reda, and Q. Wang, “Power-aware placement,” in Proc. Design Automation Conf., Jun. 2005, pp. 795–800.
 Y. Lu, C. N. Sze, X. Hong, Q. Zhou, Y, Cai, L. Huang, and J. Hu, “Register placement for low power clock network,” in Proc. Asia South Pacific Design Automation Conf., Jan. 2005, pp. 588–593.
 I. Vaisband, E.G. Friedman, R. Ginosar, and A. Kolodny, “Low power clock network design,” J. Low Power Electron. Appl., pp. 219–246, May 2011.
 V. Kursun and E. G. Friedman, Multi-Voltages CMOS Circuit Design: John Wiley & Sons Ltd., 2006.
 K. Usami, M. Igarashi, F. Minami, T. Ishikawa, M. Kanazawa, M. Ichida, and K. Nogami, “Automated low-power technique exploiting multiple supply voltages applied
to a media processor,” IEEE J. Solid-State Circuits, vol. 33, no.3, pp. 463–471, Mar. 1998.
 H.-O. Kim, and Y. Shin, “Semicustom design methodology of power gated circuits for low leakage applications,” IEEE Trans. Circuits Syst. II, vol. 54, no. 6, pp. 512–516, June 2007.
 C. Santos, R. Reis, G. Godoi, M. Barros, and F. Duarte, “Multi-bit flip-flop usage impact on physical synthesis,” in Proc. Symp. Integr. Circuits Syst., Aug. 2012, pp. 1–6.
 Y.-T. Chang, C.-C. Hsu, P.-H. Lin, Y.-W. Tsai, and S.-F. Chen, “Post-placement power optimization with multi-bit flip-flops,” in Proc. Int. Conf. Comput.-Aided Design, Nov. 2010, pp. 218–223.
 J.-T. Yan, and Z.-W. Chen, “Construction of constrained multibit flip-flops for clock power reduction,” in Proc. Int. Conf. Green Circuits Syst., June 2010, pp. 675–678.
 S.-H. Wang, Y.-Y. Liang, T.-Y. Kuo, and W.-K. Mak, “Power-driven flip-flop merging and relocation,” in Proc. Int. Symp. Physical Design, Jan. 2011, pp. 107–114.
 S. S.-Y. Liu, C.-J. Lee, and H.-M. Chen, “Agglomerative based flip-flop merging for power optimization,” in Proc. Design Automation Test Europe Conf., July 2012, pp. 1391–1396.
 Iris H.-R. Jiang, C.-L. Chang, and Y.-M. Yang, “INTEGRA: Fast multibit flip-flop clustering for clock power saving,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 31, no. 2, pp. 192–204, Feb. 2012.
 H. Moon, and T. Kim, “Design and allocation of loosely coupled multi-bit flip-flops for power reduction in post-placement optimization,” in Proc. Asia South Pacific Design Automation Conf., Jan. 2016, pp. 268–273.
 C.-C. Tsai, Y. Shi, G. Luo, and I. H.-R. Jiang, “FF-bond: Multi-bit flip-flop bonding at placement,” in Proc. Int. Symp. Physical Design, Jan. 2013, pp. 147–153.
 Mark P.-H. Lin, C.-C. Hsu, and Y.-C. Chen, “Clock-tree aware multibit flip-flop generation during placement for power optimization,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 34, no. 2, pp. 280–292, Feb. 2015.
 Y. Kretchmer, “Using multibit register inference to save area and power,” EE Times Asia, May 2001.
 L. Chen et al., “Using multi-bit flip-flop for clock power saving by design compiler,” in Proc. Synopsys User Group, 2010.
 R. Pokala, R. Feretich, and R. McGuffin, “Physical synthesis for performance optimization,” in Proc. ASIC Conf. Exhibit., Sep. 1992, pp. 34–37.
 V. Khandelwal and A. Srivastava, “Leakage control through fine-grained placement and sizing of sleep transistors,” in Proc. Int. Conf. Comput.-Aided Design, Nov. 2004, pp. 533–536.
 K. Usami et al., “Design and implementation of fine-grain power gating with ground bounce suppression,” in Proc. VLSI Design, 2009, pp. 381–386.
 C. Long and L. He, “Distributed sleep transistor network for power reduction,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 12, no. 9, pp. 937–946, Sep. 2004.
 J. N. Kozhaya and L. A. Bakir, “An electrically robust method for placing power gating switches in voltage islands,” in Proc. Custom Integrated Circuits Conf., Oct. 2004, pp. 321–324.
 L. K. Yong and C. K. Ung, “Power density aware power gate placement optimization,” in Proc. Asia. Symp. Quality Electron. Design, Aug. 2010, pp. 38–42.
 C. Hwang, C. Kang, and M. Pedram, “Gate sizing and replication to minimize the effects of virtual ground parasitic resistances in MTCMOS designs,” in Proc. Int. Symp. Quality Electron. Design, Mar. 2006, pp. 741–746.
 J. Kao, A. Chandrakasan, and D. Antoniadis, “Transistor sizing issues and tool for multi-threshold CMOS technology,” in Proc. Design Automation Conf., Jun. 1997, pp. 409–414.
 J. Kao, S. Narendra, and A. Chandrakasan, “MTCMOS hierarchical sizing based on mutual exclusive discharge patterns,” in Proc. Design Automation Conf., Jun. 1998, pp. 495–500.
 S. Kim, S. V. Kosonocky, and D. R. Knebel, “Understanding and minimizing ground bounce during mode transition of power gating structures,” in Proc. Int. Symp. Low Power Electron. Design, Aug. 2003, pp. 22–25.
 S. Paik, S. Kim, and Y. Shin, “Wakeup synthesis and its buffered tree construction for power gating circuit designs,” in Proc. Int. Symp. Low Power Electron. Design, Aug. 2010, pp. 413–418.
 S.-H. Chen, Y.-L. Lin, and M. C.-T. Chao, “Power-up sequence control for MTCMOS designs,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 21, no. 3, pp. 413–423, Mar. 2013.
 Y.-T. Chen, D.-C. Juan, M.-C. Lee, and S.-C. Chang, “An efficient wake-up schedule during power mode transition considering spurious glitches phenomenon,” in Proc. Int. Conf. Comput.-Aided Design, Nov. 2007, pp. 779–782.
 Y. Lee, D.-K. Jeong, and T. Kim, “Simultaneous control of power/ground current, wakeup time and transistor overhead in power gated circuits,” in Proc. Int. Conf. Comput.-Aided Design, Nov. 2008, pp. 169–172.
 A. Davoodi and A. Srivastava, “Wake-up protocols for controlling current surges in MTCMOS-based technology,” in Proc. Asia South Pacific Design Automation Conf.,
Jan. 2005, pp. 868–871.
 H. Jiang and M. Marek-Sadowska, “Power gating scheduling for power/ground noise reduction,” in Proc. Design Automation Conf., Jun. 2008, pp. 980–985.
 T.-M. Tseng, M. C.-T. Chao, C.-P. Lu, and C.-H. Lo, “Power-switch routing for coarsegrain MTCMOS technologies,” in Proc. Int. Conf. Comput.-Aided Design, Nov. 2009, pp. 39–46.
 Faraday® Technology Corporation, http://www.faraday-tech.com/tw/
 Datasheet Synopsys. [Online]. Available: http://www.synopsys.com/home.aspx,
accessed Feb. 2016.
 Datasheet Synopsys. [Online]. Available: http://www.synopsys.com/implementationand-
signoff/signoff/primerail.html, accessed January 2017.
 Datasheet Synopsys. [Online]. Available: https://www.synopsys.com/-
 J. G. Fijnvandraat, S. H. M. J. Houben, E. J. W. ter Maten, and J. M. F. Peters, “Time domain analog circuit simulation,” J. Computational and Applied Mathematics, vol. 185, no. 2, pp. 441–459, Jan. 2006.
 V. Sreekumar and S. Ravichandran, “Impact of leakage and short circuit current in rush current analysis of power gated domains,” in Proc. SoutheastCon, Apr. 2010, pp. 41–44.
 S. Kose and E. G. Friedman, “Fast Algorithm for Power Grid analysis Based on Effective Resistance,” in Proc. IEEE Int. Symp. Circuits Syst., pp. 3661–3664, May
 G. Venezian, “On the Resistance between Two Points on a Grid,” American J. Physics, Vol. 62, no. 11, pp. 1000–1004, Nov. 1994.
 H. Qian, and S. S. Sapatnekar, “Hierarchical Random-Walk Algorithms for Power Grid Analysis,” in Proc. Asia South Pacific Design Automation Conf., pp. 499–504, Jan.
 J. N. Kozhaya, S. R. Nassif, and F. N. Najm, “A Multigrid-Like Technique for Power Grid Analysis,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 21, no. 10, pp. 1148–1160, Oct. 2002.
 W. Huang, S. Ghosh, S. Velusamy, K. Sankaranarayanan, K. Skadron, and M. R. Stan, “HotSpot: A copact thermal modeling methodology for early-stage VLSI design,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 14, no. 5, pp. 501–513, Mar. 2006.
 C. Lasance, H. Vinke, H. Rosten, and K.-L. Weiner, “A novel approach for the thermal characterization of electronic parts,” in Proc. IEEE Semi-Therm Symp., Aug. 1995, pp. 1–9.
 M. Agarwal, V. Balakrishnan, A. Bhuyan, K. Kim, B. C. Paul, W. Wang, B. Yang, Y. Cao, and S. Mitra, “Optimized circuit failure prediction for aging: Practicality and promise,” in Proc. Int. Test Conf., Oct. 2008, pp. 1–10.
 M. Omana, D. Rossi, N. Bosio, and C. Metra, “Low cost nbti degradation detection and masking approaches,” IEEE Trans. Computers, vol. 62, no.3, pp. 496–509, Mar. 2013.
 D. Rossi, V. Tenentes, S. Khursheed, and B. M. Al-Hashimi, “NBTI and Leakage Aware Sleep Transistor Design for Reliable and Energy Efficient Power Gating,” in Proc.
European Test Symp., Jul. 2015, pp. 1–6.