This work presents a method for global routing (GR) to minimize power associated with global nets. We consider routing in designs with multiple supply voltages. Level converters are added to nets that connect driver cells to sink cells of higher supply voltage and are modeled as additional terminals of the nets during GR. Given an initial GR solution obtained with the objective of minimizing wirelength, we propose a GR method to detour nets to further save the power of global nets. When detouring routes via this procedure, overflow is not increased, and the increase in wirelength is bounded. The power saving opportunities include (1) reducing the area capacitance of the routes by detouring from the higher metal layers to the lower ones, (2) reducing the coupling capacitance between adjacent routes by distributing the congestion, and (3) considering different power weights for each segment of a routed net with level converters (to capture its corresponding supply voltage and activity factor). We present a mathematical formulation to capture these power saving opportunities and solve it using integer programming techniques. In our simulations, we show considerable saving in a power metric for GR, without any wirelength degradation. 1. Introduction Power consumption is a primary design objective in many application domains. Dynamic power still remains the dominant portion of the overall power spectrum. Design with multisupply voltage (MSV) allows significant reduction in dynamic power by taking advantage of its quadratic dependence on the supply voltage. Dynamic power is dissipated in combinational and sequential logic cells, clock network, and the (remaining) local and global nets. We refer to the latter as the signal power. The signal power can take a significant portion of the dynamic power spectrum. For example, the contribution of the signal power is reported to be around 30% of dynamic power for a 45？nm high-performance microprocessor synthesized using a structured data paths design style and about 18% of the overall power spectrum [1]. The signals are complex structures in nanometer technologies that span over many metal layers. The power of a route segment depends on its width, metal layer, and spacing relative to its adjacent parallel-running routes. These factors determine the area, fringe, and coupling capacitances which impact power. Furthermore, in MSV designs, the power of a routed net depends on its corresponding supply voltage. For example, a route will have lower power if all its terminal cells have (the same) lower supply voltage. If a
References
[1]
R. S. Shelar and M. Patyra, “Impact of local interconnects on timing and power in a high performance processor,” in ACM International Symposium on Physical Design, pp. 145–152, 2010.
[2]
R. L. S. Ching, E. F. Y. Young, K. C. K. Leung, and C. C. N. Chu, “Post-placement voltage island generation,” in Proceedings of the International Conference on Computer-Aided Design (ICCAD '06), pp. 641–646, November 2006.
[3]
L. Guo, Y. Cai, Q. Zhou, and X. Hong, “Logic and layout aware voltage island generation for low power design,” in Proceedings of the Asia and South Pacific Design Automation Conference, pp. 666–671, January 2007.
[4]
H. Shojaei, T.-H. Wu, A. Davoodi, and T. Basten, “A Pareto-algebraic framework for signal power optimization in global routing,” in Proceedings of the 16th ACM/IEEE International Symposium on Low-Power Electronics and Design (ISLPED '10), pp. 407–412, August 2010.
[5]
W.-H. Liu, Y.-L. Li, and K.-Y. Chao, “High-quality global routing for multiple dynamic supply voltage designs,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD '11), pp. 263–269, November 2011.
[6]
T.-H. Wu, A. Davoodi, and J. T. Linderoth, “GRIP: scalable 3D global routing using integer programming,” in Proceedings of the 46th ACM/IEEE Design Automation Conference (DAC '09), pp. 320–325, July 2009.
[7]
Nangate 45？nm open cell library, 2008, http://www.nangate.com/.
[8]
C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, and P. H. Vance, “Branch-and-price: column generation for solving huge integer programs,” Operations Research, vol. 46, no. 3, pp. 316–329, 1998.
[9]
D. G. J？rgensen and M. Meyling, “A branch-and-price algorithm for switch-box routing,” Networks, vol. 40, no. 1, pp. 13–26, 2002.
[10]
G. Dantzig and P. Wolfe, “Decomposition principle for linear programs,” Operations Research, vol. 8, pp. 101–111, 1960.
[11]
Y.-J. Chang, Y.-T. Lee, and T.-C. Wang, “NTHU-route 2.0: a fast and stable global router,” in Proceedings of the International Conference on Computer-Aided Design (ICCAD '08), pp. 338–343, November 2008.
[12]
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959.
[13]
M. Pan and C. C. N. Chu, “FastRoute 2.0: a high-quality and efficient global router,” in Proceedings of the Asia and South Pacific Design Automation Conference, pp. 250–255, January 2007.
[14]
J. A. Roy and I. L. Markov, “High-performance routing at the nanometer scale,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 6, pp. 1066–1077, 2008.
[15]
“ISPD 2008 global routing contest and benchmark suite,” http://www.sigda.org/ispd2008/contests/ispd08rc.html.
[16]
T.-H. Wu, A. Davoodi, and J. T. Linderoth, “A parallel integer programming approach to global routing,” in Proceedings of the 47th Design Automation Conference (DAC '10), pp. 194–199, June 2010.
[17]
ISPD 2006 placement contest and benchmark suite.
[18]
CPLEX Optimization, Using the CPLEX Callable Library, Version 9, Incline Village, Nev, USA, 2005.
[19]
M. J. Litzkow, M. Livny, and M. W. Mutka, “Condor—a hunter of idle workstations,” in Proceedings of the 8th International Conference on Distributed Computing Systems, pp. 104–111, 1998.
