In this paper, clustering for the circuit placement problem is examined from the perspective of wire length contribution from groups of nets. First, the final wire length data of groups of nets with different degrees are extracted and studied. It is illustrated that nets with high-degree contribute a high percentage to the total wire length. To remedy this problem, a clustering algorithm for placement is proposed that focuses on clustering nets with high-degree. This new clustering algorithm is implemented as a preprocessing step in the placement stage. ICCAD04 benchmark circuits abstracted from IBM are used to validate the placement quality by using four academic placers with and without the proposed preprocessing step. Experiments show that the overall placement results can be improved by up to 5%.
References
1.
NamG.AlpertC. J.VillarrubiaP.WinterB., and YildizM., The ISPD2005 placement contest and benchmark suite, in Proc. ISPD, 2005, pp. 216–219.
2.
NamG., ISPD 2006 placement contest: Benchmark suite and results, in Proc. ISPD, 2006, p. 167.
3.
AlpertC. J.HuangD., and KahngA. B., Multilevel circuit partitioning, IEEE Trans. on CAD, vol. 17, no. 8, pp. 655–667, 1998.
4.
KarypisG. and KumarV., Multilevel k-way hypergraph partitioning, in Proc. DAC, 1999, pp. 343–348.
5.
CaldwellA. E.KahngA. B., and MarkovI. L., Improved algorithms for hypergraph bipartitioning, in Proc. ASPDAC, 2000, pp. 661–666.
6.
AlpertC.KahngA.NamG. J.RedaS., and VillarrubiaP., A semi- persistent clustering technique for VLSI circuit placement, in Proc. ISPD, 2005, pp. 200–207.
7.
HuB. and Marek-SadowskaM., Fine granularity clustering for large scale placement problems, in Proc. ISPD, 2003, pp. 67–74.
8.
CongJ. and LimS., Edge separability-based circuit clustering with application to multilevel circuit partitioning, IEEE Trans. on CAD, vol. 23, no. 3, pp. 346–357, 2004.
9.
LiJ.BehjatL., and HuangJ., An effective clustering algorithm for mixed- size placement, in Proc. ISPD, 2007, pp. 111–118.
10.
ChangC. C.CongJ.RomesisM., and XieM., Optimality and scalability study of existing placement algorithms, IEEE Trans. on CAD, vol. 23, no. 4, pp. 537–549, 2004.
11.
LiuQ. and Marek-SadowskaM., A study of netlist structure and place- ment efficiency, in IEEE Trans. on CAD, vol. 24, no. 5, May 2005, pp. 762–772.
12.
TaghaviT.YangX., and SarrafzadehM., Dragon2005: Large-scale mixed sized placement tool, in Proc. ISPD, 2005, pp. 245–247.
13.
AdyaS.ChaturvediS.RoyJ.PapaD., and MarkovI., Unification of partitioning, floorplanning and placement, in Proc. ICCAD, 2004, pp. 550–557.
14.
KirkpatrickS.GelattC. D., and VecchiM. P., Optimization by simulated annealing, Science, no. 220, pp. 671–680, 1983.
15.
RoyJ.PapaD.AdyaS.ChanH.NgA.LuF., and MarkovI., Capo: Robust and scalable open-source min-cut floorplacer, in Proc. ISPD, 2005, pp. 224–226.
16.
AgnihotriA.OnoS., and MaddenP., Recursive bisection placement: Fengshui 5.0 implementation details, in Proc. ISPD, 2005, pp. 230–232.
17.
HuangJ.LiJ.RakaiL., and BehjatL., Wirelength based clustering technique for vlsi physical design, in CCECE, 2007, pp. 655–658.
18.
BehjatL.LiJ.RakaiL., and HuangJ., Two clustering preprocessing techniques for large-scale circuits, in Proc. ISCAS, May 2007, pp. 1057–1060.
19.
BodapatiS. and NajmF. N., Prelayout estimation of individual wire lengths, IEEE Trans. on VLSI, vol. 9, no. 6, pp. 943–958, Dec 2001.
20.
HeinekenH. T. and MalyW., Standard cell interconnect length prediction from structural circuit attributes, in Proc. CICC, 1996, pp. 167–170.
21.
LiJ.BehjatL., and RakaiL., Clustering algorithms for circuit partitioning and placement problems, in 18th ECCTD, 2007, pp. 547–550.
22.
ChanT. F.CongJ.RomesisM.ShinnerlJ. R.SzeK., and XieM., mPL6: Enhanced multilevel mixed-size placement, in Proc. ISPD, 2006, pp. 212–214.
23.
ChenT. C.JiangZ. W.HsuT.ChenH. C., and ChangY. W., A high-quality mixed-size analytical placer considering preplaced blocks and density constraints, in Proc. ICCAD, 2006, pp. 187–192.
24.
KahngA. B. and RobinsG., A new class of iterative steiner tree heuristics with good performance, IEEE Trans. on CAD, vol. 11, no. 7, pp. 893–902, July 1992.
