Timing-aware power-optimal ordering of signals

ABSTRACT

A computationally efficient technique for reducing interconnect active power in VLSI systems is presented. Power reduction is accomplished by simultaneous wire spacing and net ordering, such that cross-capacitances between wires are optimally shared. The existence of a unique power-optimal wire order within a bundle is proven, and a method to construct this order is derived. The optimal order of wires depends only on the activity factors of the underlying signals; hence, it can be performed prior to spacing optimization. By using this order of wires, optimality of the combined solution is guaranteed (as compared with any other ordering and spacing of the wires). Timing-aware power optimization is enabled by simultaneously considering timing criticality weights and activity factors for the signals. The proposed algorithm has been applied to various interconnect layouts, including wire bundles from high-end microprocessor circuits in 65 nm technology. Interconnect power reduction of 17% on average has been observed in such bundles.

REFERENCES

• 1: Arif Ishaq Abou-Seido , Brian Nowak, Fitted Elmore Delay: A Simple and Accurate Interconnect Delay Model, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.422, September 16-18, 2002
• 2: Ravishankar Arunachalam , Emrah Acar , Sani R. Nassif, Optimal shielding/spacing metrics for low power design, Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI'03), p.167, February 20-21, 2003
• 3: Barke, E. 1988. Line-to-ground capacitance calculation for VLSI—A comparison. IEEE Trans. Computer--Aided Des. VLSI, 7, 2, 295--298.
• 4: L. Benini , G. De Micheli , E. Macii , D. Sciuto , C. Silvano, Address bus encoding techniques for system-level power optimization, Proceedings of the conference on Design, automation and test in Europe, p.861-867, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 5: D. Bertozzi , L. Benini , G. de Micheli, Low Power Error Resilient Encoding for On-Chip Data Buses, Proceedings of the conference on Design, automation and test in Europe, p.102, March 04-08, 2002
• 6: Boese, K. D., Kahng, A. B., McCoy, B. A., and Robins, G. 1993. Fidelity and near-optimality of elmore-based routing constructions. Dig. Technical Paper ICCAD, pp. 81--84.
• 7: Cha, M., Lyuh, C., and Kim, K. 2006. Low power bus encoding with crosstalk delay elimination. IEE Proceedings: Computers and Digital Techiques 153, 2, 93--100.
• 8: Pinhong Chen , Desmond A. Kirkpatrick , Kurt Keutzer, Miller factor for gate-level coupling delay calculation, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 9: Cong, J., He, L., Koh, C. K., and Pan, Z. 2001. Interconnect sizing and spacing with consideration of coupling capacitance. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 20, 9, 1164--1169.
• 10: Maged Ghoneima , Yehea Ismail, Delayed line bus scheme: a low-power bus scheme for coupled on-chip buses, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013257]
• 11: Puneet Gupta , Andrew B. Kahng, Wire Swizzling to Reduce Delay Uncertainty Due to Capacitive Coupling, Proceedings of the 17th International Conference on VLSI Design, p.431, January 05-09, 2004
• 12: Cheng-Ta Hsieh , Massoud Pedram, Architectural power optimization by bus splitting, Proceedings of the conference on Design, automation and test in Europe, p.612-616, March 27-30, 2000, Paris, France [doi>10.1145/343647.343869]
• 13: ITRS report, 2005. Available online http://www.itrs.net/reports.html
• 14: Jhang, K., Ha, S., and John, C. 1994. A segment rearrangement approach to channel routing under the crosstalk constraints. In Proceedings of the Asia-Pacific Conference on Circuits and Systems, 536--541.
• 15: Andrew B. Kahng , Kei Masuko , Sudhakar Muddu, Analytical delay models for VLSI interconnects under ramp input, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.30-36, November 10-14, 1996, San Jose, California, United States
• 16: A. B. Kahng , S. Muddu , E. Sarto , R. Sharma, Interconnect tuning strategies for high-performance ICs, Proceedings of the conference on Design, automation and test in Europe, p.471-478, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 17: Ki Wook Kim , Kwang Hyun Baek , Naresh Shanbhag , C. L. Liu , Sung Mo Kang, Coupling-driven signal encoding scheme for low-power interface design, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 18: Chun-Gi Lyuh , Taewhan Kim , Ki-Wook Kim, Coupling-aware high-level interconnect synthesis for low power, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.609-613, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774662]
• 19: Enrico Macii , Massimo Poncino , Sabino Salerno, Combining wire swapping and spacing for low-power deep-submicron buses, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764859]
• 20: Nir Magen , Avinoam Kolodny , Uri Weiser , Nachum Shamir, Interconnect-power dissipation in a microprocessor, Proceedings of the 2004 international workshop on System level interconnect prediction, February 14-15, 2004, Paris, France [doi>10.1145/966747.966750]
• 21: Moiseev, K., Wimer, S., and Kolodny, A. 2006. Timing optimization of interconnect by simultaneous net-ordering, wire sizing and spacing. In Proceedings of IEEE International Symposium on Circuits and Systems, IEEE Computer Society Press, Los Alamitos, CA, 329--332.
• 22: Konstantin Moiseev , Shmuel Wimer , Avinoam Kolodny, On optimal ordering of signals in parallel wire bundles, Integration, the VLSI Journal, v.41 n.2, p.253-268, February, 2008 [doi>10.1016/j.vlsi.2007.06.002]
• 23: Mui, M. L., Benerjee, K., and Mehortra, A. 2004. A global interconnect optimization scheme for nanometer scale VLSI with implications for latency, bandwidth, and power dissipation. IEEE Trans. Elect. Dev. 51, 2, 195--203.
• 24: Naroska, E., Ruan, S.-J., and Schwiegelshohn, U. 2005. An efficient algorithm for simultaneous wire permutation, inversion, and spacing. In Proceedings of International Symposium on Circuits and Systems, 109--112.
• 25: Sapatnekar, S. S. 1996. Wire sizing as a convex optimization problem: Exploring the area delay tradeoff. IEEE Trans. Comput.-Aided Design of Integrated Circuits and Systems 15, 8, 1001--1011.
• 26: Li Shang , Li-Shiuan Peh , Niraj K. Jha, Power-efficient Interconnection Networks: Dynamic Voltage Scaling with Links, IEEE Computer Architecture Letters, v.1 n.1, p.6, January 2002 [doi>10.1109/L-CA.2002.10]
• 27: Youngsoo Shin , Takayasu Sakurai, Coupling-driven bus design for low-power application-specific systems, Proceedings of the 38th conference on Design automation, p.750-753, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379059]
• 28: Stellari, F. and Lacaita, A. L. 2000. New formulas of interconnect capacitances based on results of conformal mapping method. IEEE Trans. Electron Dev., 222--231.
• 29: Wimer, S., Michaely, S., Moiseev, K., and Kolodny, A. 2006. Optimal bus sizing in migration of processor design. IEEE Trans. Circ. Syst. -- I, 53, 5, 1089--1100.
• 30: Hui Zhang , Varghese George , Jan M. Rabaey, Low-string on-chip signaling techniques: effectiveness and robustness, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.3, p.264-272, June 2000 [doi>10.1109/92.845893]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
Wire ordering, interconnect optimization, power optimization, wire spacing