隨著製程的不斷進步，單一晶片中可以包含越來越多的電晶體，為了降低設計的複雜度，現在的晶片往往採用階層式 (hierarchical) 的設計，或者重覆使用各種不同的矽智財(Intellectual Property, IP) 來建構系統，這使得平面規劃 (floorplan) 在實體設計 (physical design)中變得越來越重要。最近由於消費性電子產品的普及，發展低功耗的晶片已經成為晶片設計中的重要議題，隨著晶片中的模塊區塊越來越多，晶片中的功率密度 (power density) 更勝於以往，這使得系統晶片中的動態功耗 (dynamic power) 及漏電流功耗(leakage power) 等問題也越來越嚴重，因此許多用來降低功耗消耗的方法已相繼被提出，其中的多重電壓源(Multiple Supply Voltage, MSV) 是用來解決此問題最有效的技術之一。相較於傳統平面規劃的問題，多重電壓源平面規劃的問題更為困難。為了降低晶片中電壓源繞線的複雜度，並且減少插入電壓位準移位器(Level-Shifter)的困難，使用相同電壓源的模塊必須儘量擺放於鄰近的區域，形成一個電壓島。然而過大的電壓島卻又可能使得平面規劃難以實行，並且還會增加晶片設計上的成本，因此，為了能夠同時減少訊號線的繞線線長及考量電壓島內的電壓下降 (voltage drop) 問題，本論文提出一個數學分析的方式，在平面規劃的同時將使用同一電源域的模塊劃適當的區分至多個電壓島中，除此之外，本方法還可以考慮固定框架的限制。實驗結果顯示，我們提出的方法在處理固定框架多重電壓島的平面規劃時，可以獲得不錯的結果。

SUMMARY

Due to prevailing of portable devices, low-power has become an important issue in VLSI design. A system with Multiple Supply Voltages (MSV) is a popular technique to reduce dynamic power. However, this makes floorplanning more complex. For facility of power planning and reducing complexity of inserting level-shifters, a chip has to be divided into several islands properly. This makes voltage-island driven floorplanning become more important than ever. However, a too large voltage island may increase difficulty in floorplanning and deteriorate wirelength. In order to consider signal wirelength and IR-drop at the same time, this thesis proposes an analytical based approach to divide modules in a voltage domain into several voltage-islands during floorplanning. Besides, fixed-outline constraint is considered. The experimental results show our work obtains better result than other approaches.

INTRODUCTION

As design technologies advance, more and more intellectual properties (IPs)
can be integrated into a chip, which makes floorplanning become more important
than ever. Since chip outline is determined before floorplanning in the practical design flow, a floorplanner should have the ability to consider this issue. Recently,
due to popularity of portable electronic devices, lower power has become an
important issue in VLSI design. Many approaches have been proposed to resolve
the problem, and Multiple Supply Voltage (MSV for short) is one of the most
effective techniques. Because MSV is able to reduce dynamic power and leakage
power without influencing a chip’s performance, it is widely adopted by industry.
This makes voltage-island driven floorplanning become more important than ever.
Because it has to divide a chip into several islands for facility of power planning,
voltage-island driven floorplanning is more difficult than classical floorplanning.
Most of works adopted the simulated annealing framework to handle the
voltage-island driven floorplanning [13]、[14]、[20]、[23]、[25]、[30] and
[31]. However, when more and more factors are added into its cost function,
the convergence of the program becomes more difficult and it consumes a lot of
time to obtain the result. Recently, Lin and Hung [23] proposed a SKB-tree
representation to handle this problem. To simplify complexity of power planning
in the later stage, they constrain modules in the same voltage domain have to be
placed into one single island. However, wirelength and IR-drop may suffer from
this additional placement constraint. In order to get balance of these factors,
voltage-island driven floorplanning needs to partition modules in a voltage domain
into various voltage islands and consider the fixed-outline constraint at the same
time.

FLOORPLANNING CONSIDERING VOLTAGE ISLANDS

We apply a hierarchical approach to handle this problem. Please see Fig.
1 for the flow. In the first stage, modules in a voltage domain are partitioned
into various voltage islands and their initial locations are determined. Although
power planning becomes easier if the modules in each voltage domain are placed
together, it may lead to longer wirelength because of this strict placement con-
straint. In order to obtain better results, modules in a power domain have better
to be divided into several islands. After number of voltage islands and member in each voltage island are determined, their shapes and locations of voltage islands
are determined by applying Lin et al. [3]’s algorithm if each voltage island is
considered as a soft module. Next, the shapes and locations of modules inside
each voltage island are decided by applying the algorithm [3] again. In order to
get better wirelength, pins of nets crossing different voltage islands are attached
to the boundary of a voltage island based on relative locations of voltage island.

RESULTS AND DISCUSSION

Our floorplanner was implemented by the C++ programming language on
the Intel Xeonr 2.4GHz Linux workstation with 4GB memory. The wirelength
was estimated by half-parameter wire-length (HPWL). The aspect ratio of a soft
module is ranged from 1/3 to 3 and the aspect ratio for each chip outline is 1
and the whitespace is 10%. Besides, the I/O pads of each circuit are scaled to
chip outline. We performed voltage-island driven floorplanning with the fixed-
outline constraint based on GSRC benchmark [38]. The voltage assignment of
modules is based on the results of SKB-tree [23]. To show the effectiveness
and efficiency of our methodology, we compare our work with SKB-tree based approach. Since SKB-tree based approach does not consider the fixed-outline
constraint, we modified their codes to add the constraint into the cost function
of the simulated annealing framework.
Table 1 shows the comparison results for SKB-tree and our approaches for
GSRC benchmarks. The first column gives the names of all benchmarks. Columns
2-4 shows HPWL for signals, maximal power length, and runtime for SKB-tree
based approach while our results are shown in columns 5-7. The table shows
that our approach achieves better HPWL and maximal power length compared
to SKB-tree based approach. Besides, our approach is faster than SKB-tree based
approach.

CONCLUSION

Low-power has become an important issue in VLSI design and voltage-island
driven floorplanning has attracted more attention. Although this problem has
been discussed by previous work, rare papers emphasize the importance of the
fixed-outline constraint. By proper dividing a voltage domain into several voltage-
islands, we can consider signal wirelength and IR-drop at the same time. The experimental results have demonstrated that our approach can obtains better
result than SKB-tree based approach.

[1] S. N. Adya and I. L. Markov, “Fixed-outline floorplanning through better
local search,” in Proc. ICCD, pp. 328-334, 2001.
[2] S. N. Adya and I. L. Markov, “Fixed-outline floorplanning: Enabling hier-
archical design,” IEEE Trans. on VLSI Systems, vol 11(6), pp. 1120-1135,
Dec. 2003.
[3] K.-C. Chan, J.-M. Lin, C.-J Hsu, “A flexible fixed-outline floorplanning
methodology for mixed-size modules,” in Proc. ASP-DAC, pp. 435-440,
Jan. 2013.
[4] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-Trees: a new
representation for non-slicing floorplans,” in Proc. DAC, pp. 458-463, 2000.
[5] T.-C. Chen, Y.-W. Chang and S.-C. Lin, “IMF: Interconnect-driven mul-
tilevel floorplanning for large-scale building-module designs,” in Proc. ICCAD
, pp. 159-164, 2005.
[6] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, “NTU-
place3: An analytical placer for large-scale mixed-size designs with pre-
placed blocks and density constraints,” IEEE Trans. on CAD, vol. 27(7),
pp. 1228-1240, Jul. 2008
[7] R. L. S. Ching, E. F. Y. Young, K. C. K. Leung, and C. Chu, “Post-
placement voltage island generation,” in Proc. ICCAD, pp. 641-646, 2006.
[8] J. Cong, M. Romesis, and J. Shinnerl. “Fast floorplanning by look-ahead
enabled recursive bipartitioning,” IEEE Trans. on CAD, vol. 25(9), pp.
1719-1732, Sep. 2006.
[9] P.-N. Guo, C.-K. Cheng, and T. Yoshimura, “An O-Tree representation
of non-slicing floorplan and its applications,” in Proc. DAC, pp. 268-273,
1999.
[10] O. He, S. Dong, J. Bian, S. Goto, and C.-K. Cheng, “A novel fixed-outline
floorplanner with zero deadspace for hierarchical design,” in Proc. ICCAD,
pp. 16-23, 2008.
[11] W. Naylor, “Non-Linear Optimization System and Method forWire Length
and Delay Optimization for an Automatic Electric Circuit Placer,” U.S.
Patent 6301693, 2001.
[12] X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu,
“Corner Block List: An effective and efficient topological representation of
non-slicing floorplan,” in Proc. ICCAD, pp. 8-12, 2000.
[13] J. Hu, Y. Shin, N. Dhanwada, and R. Marculescu, “Architecting voltage
islands in core-based system-on-a-chip designs,” in Proc. ISLPED, pp. 180-
185, 2004.
[14] W.-L. Hung, G. M. Link, Y. Xie, N. Vijaykrishnan, N. Dhanwada and J.
Conner, “Temperature-aware voltage islands architecting in system-on-chip
design,” in Proc. ICCD, pp. 689-696, 2005.
[15] A. B. Kahng, “Classical floorplanning harmful?,” in Proc. ISPD, pp. 207-
213, 2000.
[16] A. B. Kahng and Q.Wang, “Implementation and extensibility of an analytic
placer,” IEEE Trans. on CAD, vol. 24(5), pp. 734V747, May 2005.
[17] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel hyper-
graph partitioning: applications in VLSI domain,” IEEE Trans. on VLSI
Systems, vol. 7(1), pp. 69-79, Mar. 1999.
[18] M.-C. Kim, D.-J. Lee, and I. L. Markov, “SimPL: An effective placement
algorithm”, IEEE Trans. on CAD, vol.31(1), pp. 50-60, Jan. 2012.
[19] M. Kuwano and Y. Takashima, “Stable-LSE based analytical placement
with overlap removable length”, in Proc. SASIMI, pp. 115-120, 2010.
[20] W.-P. Lee, H.-Y. Liu, and Y.-W. Chang, “Voltage island aware floorplan-
ning for power and timing optimization,” in Proc. ICCAD, pp. 389-394,
2006.
[21] W.-P. Lee, H.-Y. Liu and Y.-W. Chang, “An ILP algorithm for post-
floorplanning voltage-island generation considering power-network plan-
ning,” in Proc. ICCAD, pp. 650-655, 2007.
[22] J.-M. Lin and Y.-W. Chang, “TCG: A transitive closure graph-based rep-
resentation for non-slicing floorplans,” in Proc. DAC, pp. 764-769, 2001.
[23] J.-M. Lin and Z.-X. Hung. “SKB-tree: A fixed-outline driven representation
for modern floorplanning problems.” IEEE Trans. on VLSI Systems, vol.
20(3), pp. 473-484, Mar. 2012.
[24] C. Luo, M. F. Anjos, and A. Vannelli, “Large-scale fixed-outline floorplan-
ning design using convex optimization Techniques,” in Proc. ASP-DAC, pp.
198-203, 2008.
[25] Q. Ma and E. F. Y. Young, “Multivoltage floorplan design”, IEEE Trans.
on CAD, vol. 29(4), pp. 607-617, Apr. 2010.
[26] W.-K. Mak and J.-W. Chen, “Voltage island generation under performance
requirement for SoC designs,” in Proc. ASP-DAC, pp. 798-803, 2007.
[27] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle-packing
based module placement,” in Proc. ICCAD, pp. 472-479, 1995.
[28] S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, “Module placement
on BSG-structure and IC layout applications,” in Proc. ICCAD, pp. 484-
491, 1996.
[29] R. H. J. M. Otten, “Automatic floorplan design,” in Proc. DAC, pp. 261-
267, 1982.
[30] Z. Qian and E. F. Y. Young, “Multi-voltage floorplan design with optimal
voltage assignment,” in Proc. ISPD, pp. 13-18, 2009.
[31] D. Sengupta and R. Saleh, “Application-driven floorplan-aware voltage is-
land design,” in Proc. DAC, pp. 155-160, 2008.
[32] D. F.Wong, and C.-L. Liu, “A new algorithm for floorplan design,” in Proc.
DAC, pp. 101-107, 1986.
[33] H. Wu, I.-M. Liu, D. F. Wong, and Y. Wang, “Post-placement voltage
island generation under performance requirement,” in Proc. ICCAD, pp.
309-316, 2005.
[34] H.Wu, D. F.Wong, and I.-M. Liu, “Timing-constrained and voltage-island-
aware voltage assignment,” in Proc. DAC, pp. 429-432, 2006.
[35] J. Z. Yan and C. Chu, “DeFer: Deferred decision making enabled fixed-
outline floorplanning algorithm,” IEEE Trans. on CAD, vol. 29(3), pp.
119-130, 2010.
[36] H. Zhou and J. Wang., “ACG - Adjacent constraint graph for general floor-
plans,” in Proc. ICCD, pp. 572-575, 2004.
[37] Y. Zhan, Y. Feng and S. Sapatnekar. “A fixed-die floorplanning algorithm
using an analytical approach,” in Proc. ASP-DAC, pp. 771-776, 2006.
[38] GSRC Floorplan Benchmarks Available:
http://vlsicad.eecs.umich.edu/BK/GSRCbench/
[39] HB Floorplan Benchmarks Available: http://cadlab.cs.ucla.edu/cpmo/HBsuite.html