We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 25 Issue 5
August  2010
Turn off MathJax
Article Contents
Abstract
References
Hui Dai, Qiang Zhou, Ji-Nian Bian. Multilevel Optimization for Large-Scale Hierarchical FPGA Placement[J]. Journal of Computer Science and Technology, 2010, 25(5): 1083-1091. DOI: 10.1007/s11390-010-1085-4
Citation: Hui Dai, Qiang Zhou, Ji-Nian Bian. Multilevel Optimization for Large-Scale Hierarchical FPGA Placement[J]. Journal of Computer Science and Technology, 2010, 25(5): 1083-1091. DOI: 10.1007/s11390-010-1085-4
shu

Multilevel Optimization for Large-Scale Hierarchical FPGA Placement

Funds: This work is supported by the National Natural Science Foundation of China under Grant Nos. 60876026 and 60833004.
More Information
  • Author Bio:

    Qiang Zhou received the B.S. degree in computer science and technology from University of Science and Technology of China in 1983, the M.S. degree in computer science and technology from Tsinghua University in 1986, and the Ph.D. degree in control theory and control engineering from Chinese University of Mining and Technology in 2002. He has been an associate professor in the Department of Computer Science and Technology, Tsinghua University, Beijing, China. His research interests include EDA and VLSI layout theory and algorithms.

    Ji-Nian Bian graduated from Tsinghua University, China in 1970. Since 1999, he has been a professor in the Department of Computer Science and Technology, Tsinghua University, China. He was a visiting scholar in Kyoto University and in Kyushu University, Japan in 1999. He joined several national developing projects on VLSI CAD systems including the PANDA VLSI CAD system. His research interests include logic-level and high-level design specification, simulation and verification, synthesis and DA systems.

  • Received Date: November 01, 2009
  • Revised Date: June 03, 2010
  • Published Date: August 31, 2010
    Abstract
  • This paper proposes a multilevel placer targeted at hierarchical FPGA (Field Programmable Gate Array) devices. The placer is based on multilevel optimization method which combines the multilevel bottom-up clustering process and top-down placement process into a V-cycle. It provides superior wirelength results over a known heuristic high-quality placement tool on a set of large circuits, when restricted to a short run time. For example, it can generate a placement result for a circuit with 5000 4-LUTs (4-Input Look Up Tables) in 70 seconds, almost 30% decrease of wirelength compared with than the heuristic implementation that takes over 500 seconds. We have verified our algorithm yields good quality-time tradeoff results as a low-temperature simulated annealing refinement process can only improve the result by an average of 1.11% at the cost of over 25-fold runtime.
    • FullText(HTML)
    • References (26)
  • [1]
    Callahan T J, Chong P, Dehon A et al. Fast module mapping and placement for datapaths in FPGA. In Proc. the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays, Monterey, USA, Feb. 22-24, 1998, pp.123-132.
    [2]
    Sankar T, Rose J. Trading quality for compile time: Ultra-fast placement for FPGA. In Proc. the 1999 ACM/SIGDA Seventh International Symposium on Field Programmable Gate Arrays, Monterey, USA, Feb. 21-23, 1999, pp.157-166.
    [3]
    Maidee P, Ababei C, Bazargan K. Fast timing-driven partitioning-based placement for island style FPGA. In Proc. the 40th Conference on Design Automation, Monterey, USA, Feb. 23-25, 2003, pp.598-603.
    [4]
    Wang Y H, Zhou Q, Bian J N et al. VPH: Versatile routability-driven place algorithm for hierarchical FPGAs based on VPR. In Proc. IEEE Int. Conf. Comput. Aided Des. Comput. Graph., Beijing, China, Oct. 15-18, 2007, pp.349-354. (in Chinese)
    [5]
    Zhou F, Tong J R, Tang P S. Placement with time constraints for FPGA design. Journal of Computer-Aided Design and Computer Graphics, 1999, 11(4): 304-308. (in Chinese)
    [6]
    Yang M, Lai J M, Tang P S et al. LowTARP: A novel low temperature alternating refinement placer. Journal of Computer-Aided Design and Computer Graphics, 2007, 19(6): 692-697. (in Chinese)
    [7]
    Shen X Y, Zhou X H. An offline placement algorithm for reconfigurable computing systems. Journal of University of Science and Technology of China, 2008, 38(10): 1194-1201. (in Chinese)
    [8]
    Atoofian E, Navabi Z. A test approach for look-up table based FPGAs. Journal of Computer Science and Technology, 2006, 21(1): 144-146.
    [9]
    Wrightion M G, DeHon A M. Hardware-assisted simulated annealing with application for fast FPGA placement. In Proc. the 2003 ACM/SIGDA Eleventh International Symposium on Field Programmable Gate Arrays, Monterey, USA, Feb. 23-25, 2003, pp.33-42.
    [10]
    Chan P K, Wong D F. Parallel placement for field-programmable gate arrays. In Proc. the 2003 ACM/SIGDA Eleventh International Symposium on Field Programmable Gate Arrays, Monterey, USA, Feb. 23-25, 2003, pp.43-50.
    [11]
    Chang C C, Cong J, Pan Z et al. Multilevel global placement with congestion control. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 2003, 22(4): 395-409.
    [12]
    Chan T, Cong J, Sze K. Multilevel generalized force-directed method for circuit placement. In Proc. the 2005 International Symposium on Physical Design, San Francisco, USA, Apr.3-6, 2005, pp.185-192.
    [13]
    Chan T, Cong J, Shinnerl J R et al. Multi-Scale Optimization in VLSI Physical Design Automation. Springer Publishers, 2004.
    [14]
    Chen D, Cong J, Pan P. FPGA design automation: A survey. Foundations and Trends in Electronic Design Automation, 2006, 1(3): 195-330.
    [15]
    Hutton M, Adibsamii K, Leaver A, Timing-driven placement for hierarchical programmable logic devices. In Proc. the 2001 ACM/SIGDA Ninth International Symposium on Field Programmable Gate Arrays, Monterey, USA, Feb. 11-13, 2001, pp.3-11.
    [16]
    Amir B D, Ron S, Zohar Y. Clustering gene expression patterns. Journal of Computational Biology, 1999, 6(3/4): 281-297.
    [17]
    Hartuv E, Schmitt A, Lange J et al. An algorithm for clustering cDNAs for gene express analysis. In Proc. the Third Annual International Conference on Computational Molecular Biology, Lyon, France, Apr. 11-14, 1999, pp.188-197.
    [18]
    Tsu W et al. HSRA: High Speed, Hierarchical synchronous reconfigurable array. In Proc. the 1999 ACM/SIGDA Seventh International Symposium on Field Programmable Gate Arrays, Monterey, USA, Feb. 21-23, 1999, pp.125-134.
    [19]
    Lai Y, Wang P. Hierarchical interconnection structures for field programmable gate arrays. IEEE Transactions on VLSI Systems, 1997, 5(2): 186-196.
    [20]
    Aggarwal A, Lewis D. Routing architectures for hierarchical field programmable gate arrays. In Proc. 1994 IEEE. Int. Conf. Computer Design, Cambridge, USA, Oct. 10-12, 1994, pp.475-478.
    [21]
    Senouci S A, Amoura A, Krupnova H et al. Timing driven floorplanning on programmable hierarchical targets. In Proc. the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays, Monterey, USA, Feb. 22-24, 1998, pp.85-92.
    [22]
    Angelo device datasheet. Agate Logic Inc., Feb. 2009.
    [23]
    Charney H R, Plato D L. Efficient partitioning of components. In Proc. the Fifth Annual Design Automation Workshop, Washington DC, USA, July 15-18, 1968. 16-0-16-21
    [24]
    Hanan M, Kurtzberg J M. A review of the placement and quadratic assignment problems. SIAM Review, 1972, 14(2): 324-342.
    [25]
    Donath W E. Logic Partitioning. Physical Design Automation of VLSI Systems, Benjamin/Cummings, 1988, pp.65-86.
    [26]
    Betz V, Rose J. VPR: A new packing, placement and routing tool for FPGA research. In Proc. the 7th International Workshop on Field-Programmable Logic and Applications, London, UK, Sept. 1-3, 1997, pp.213-222.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (56) PDF downloads (2325) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return