[1] Hao Jie, Ma Hong, Peng Silong,. Recursive bisection placement algorithm with the predicted wirelength [J]. Journal of Southeast University (English Edition), 2008, 24 (4): 462-467. [doi:10.3969/j.issn.1003-7985.2008.04.013]

Copy

Recursive bisection placement algorithm with the predicted wirelength()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

24

Issue:

2008 4

Page:

462-467

Research Field:

Computer Science and Engineering

Publishing date:

2008-12-30

Info

Title:

Recursive bisection placement algorithm with the predicted wirelength

Author(s):

Hao Jie;  Ma Hong;  Peng Silong

National ASIC Design Engineering Center, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China

Keywords:

hierarchy;  interconnect;  placement;  VLSI circuit;  wirelength prediction

PACS:

TP391.72

DOI:

10.3969/j.issn.1003-7985.2008.04.013

Abstract:

To obtain a better placement result, a partitioning-based placement algorithm with wirelength prediction called HJ-Pl is presented.A new method is proposed to estimate proximity of interconnects in a netlist, which is capable of predicting not only short interconnects but long interconnects accurately.The predicted wirelength is embedded into the partitioning tool of bisection-based global placement, which can guide our placement towards a solution with shorter interconnects.In addition, the timing objective can be handled within the algorithm by minimizing the critical path delay.Experimental results show that, compared to Capo10.5, mPL6, and NTUplace, HJ-Pl outperforms these placers in terms of wirelength and run time.The improvements in terms of average wirelength over Capo10.5, mPL6 and NPUplace are 13%, 3%, and 9% with only 19%, 91%, and 99% of their runtime, respectively.By integrating the predicted wirelength-driven clustering into Capo10.5, the placer is able to reduce average wirelength by 3%.The timing-driven HJ-Pl can reduce the critical path delay by 23%.

References:

[1] Adya S N, Markov I L.Combinatorial techniques for mixed-size placement[J].ACM Transactions on Design Automation of Electronic Systems, 2005, 10(1):58-90.
[2] Doll K, Johannes F M, Antreich K J.Iterative placement improvement by network flow methods [J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994, 13(10):1189-1200.
[3] Roy J A, Papa D A, Ng A N, et al.Satisfying whitespace requirements in top-down placement[C]//Proc of International Symposium on Physical Design.San Jose, California, USA:IEEE Press, 2006:206-208.
[4] Wang M, Yang X, Sarrafzadeh M.Dragon 2000:fast standard-cell placement for large circuits[C]//Proc of the International Conference on Computer-Aided Design.San Jose, California, USA, 2000:260-263.
[5] Vygen J.Algorithms for large-scale flat placement[C]//Proc of Design Automation Conference.Anaheim, California, USA, 1997:746-751.
[6] Chan T, Cong J, Joseph R, et al.mPL6:enhanced multilevel mixed-size placement[C]//Proc of International Symposium on Physical Design.San Jose, California, USA, 2006:212-214.
[7] Donath W E.Placement and average interconnection lengths of computer logic[J].IEEE Transactions on Circuits and Systems, 1979, 26(4):272-277.
[8] Caldwell A E, Kahng A B, Mantik S, et al.On wire length estimations for row-based placement[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999, 18(9):1265-1278.
[9] Balachandran S, Bhatia D.A priori wirelength interconnect estimation based on circuit characteristics[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(7):1054-1065.
[10] Hu B, Malgorzata Marck-Sadowaka.Wire length prediction based clustering and its application in placement[C]//Proc of Design Automation Conference.Anaheim, California, USA, 2003:800-805.
[11] Liu Q, Malgorzata Marck-Sadowaka.Semi-individual wire-length prediction with application to logic synthesis[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(4):611-624.
[12] Fiduccia C M, Mattheyses R M.A linear-time heuristic for improving network partitions[C]//Proc of Design Automation Conference.Las Vegas, Nevada, USA, 1982:175-181.
[13] Chen Tung-Chieh, Hsu Tien-Chang, Jiang Zhe-Wei, et al.NTUplace:a ratio-partitioning-based placement algorithm for large-scale mixed-size designs[C]//Proc of International Symposium on Physical Design.San Francisco, California, USA, 2005:236-238.

Memo

Memo:

Biographies: Hao Jie(1981—), male, graduate;Peng Silong(corresponding author), male, doctor, professor, silong.peng@ia.ac.cn.
Foundation item: The National Key Project of Scientific and Technical Supporting Programs(No.2006BAK07B04).
Citation: Hao Jie, Ma Hong, Peng Silong.Recursive bisection placement algorithm with the predicted wirelength[J].Journal of Southeast University(English Edition), 2008, 24(4):462-467.

Common functions