期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于贪心随机自适应搜索的电路划分改进算法 被引量：4

Improved GRASP based circuit partitioning algorithm
下载PDF
导出
摘要 为提高基于迭代改进的传统电路划分算法的划分质量,提出了一种基于贪心随机自适应搜索过程(greedyrandomized adaptive search procedure,GRASP)的电路划分改进算法.GRASP由构造阶段和局部搜索阶段组成,能够快速构造较好的初始划分.在其构造阶段引入启发式子集选择策略,并与高效搜索技术Path-Relinking相结合,在各个局部最优解之间建立路径,从而有效搜索了局部最优解空间.实验结果表明,该算法与基本GRASP相比,能在合理的时间范围内改进解的质量,获得更好的划分结果.在获得的最小划分上,改进程度最大达到33.3%;而在平均划分上,最大达到27.4%. An improved circuit partitioning algorithm based on the greedy randomized adaptive search procedure （GRASP） was presented to improve the circuit partitioning quality of traditional iterative improvement-based algorithms. GRASP consisted of a construction phase and a local search phase and could construct good initial partitions quickly. In the construction phase, a heuristic strategy was introduced to select clusters. A very efficient searching technique called Path-Relinking was integrated into the GRASP iterative process to build paths among local optimal solutions and effectively explore the local optimal solution space. The experimental results indicated that compared to the basic GRASP, the modified algorithm improved the solution quality in a reasonable period, and obtained better partition. The minimum cut-size reached 33.3% while the average cut-size was up to 27.4%.
作者 詹青青 朱文兴
机构地区 福州大学数学与计算机科学学院 福州大学离散数学与理论计算机科学研究中心
出处 《浙江大学学报（工学版）》 EI CAS CSCD 北大核心 2007年第10期1679-1683,共5页 Journal of Zhejiang University：Engineering Science
基金 福建省自然科学基金资助项目(2006J0030)
关键词 电路划分 贪心随机自适应搜索过程 启发式策略 PATH-RELINKING circuit partitioning greedy randomized adaptive search procedure （GRASP） heuristic strategy Path-Relinking
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献5

  • 1ALPERT J,KAHNG A B.Recent direction in netlist partitioning:a survey[J].Integration-the VLSI Journal,1995,19(1):1-93.
  • 2AREIBI S M.GRASP:an effective constructive technique for VLSI circuit partitioning[C]//Proceedings of the 1999 IEEE Canadian Conference on Electrical and Computer Engineering.[S.l.]:IEEE,1999:462 -467.
  • 3南国芳,李敏强,寇纪淞.基于F-M算法的电路划分新方法[J].天津大学学报（自然科学与工程技术版）,2004,37(6):549-552. 被引量：1
  • 4BOESE K,KAHNG A,MUDDU S.A new adaptive multi-start technique for combinatorial global optimizations[J].Operations Research Letters,1994,16:101-113.
  • 5RESENDE M G C,RIBEIRO C.GRASP and path-relinking:recent advances and applications[C]//TOSHIHIDE I,YASUNARI Y,eds.Proceedings of the Fifth Metaheuristics International Conference.[S.l.]:[s.n.],2003:T6-1-T6-6.

二级参考文献9

  • 1Sait S M, Youssef H.VLSI physical design automation: theory and practice [A].In: IEEE Press [C].Piscataway, NJ:1995.
  • 2Fiduccia C M, Mattheyses R M.A linear-time heuristic for improving network partitions[A].In:19th Design Automation Conference [C].Las Vegas: 1982,175-181.
  • 3Krishnamurthy B.An improved min-cut algorithm for partitioning VLSI networks [J].IEEE Tran Computers, 1984, C-33:438-446.
  • 4Sanchis L A.Multi-way network partitioning [J].IEEE Trans Computers, 1989, C-38:62-81.
  • 5Dutta S, Deng W.A probability-based approach to VLSI circuit partitioning [A].In: Proc Design Automation Conf[C].Minnesota: 1996,100-105.
  • 6Eem C K, Chong J W.An efficient iterative improvement technique for VLSI circuit partitioning using hybrid bucket structures[A].In: Design Automation Conference [C].New Orleans, LA: 1999,73-76.
  • 7Patkar S B, Narayanan H.An effcient practical heuristic for good ratio-cut partitioning [A].In: VLSI Design [C].Indiana :2003,64-69.
  • 8Areibi S, Thompson M.A new model for macrocell partitioning[A].In:16th International Conference on Computers and Their Applications[C].Washington: 2001.
  • 9Allam M W, Vannelli A, Elmasry M I.A clustering algorithm for circuit partitioning [J].Electrical and Computer Engineering, 1997 (1) :25-28.

同被引文献30

  • 1南国芳,李敏强,寇纪淞.电路划分问题的算法研究与计算机实现[J].计算机工程,2004,30(13):15-17. 被引量：2
  • 2Fiduccia C M, Mattheyses R M. A linear time heuristic for improving network partitions [ C ]//Proceedings of the ACM/IEEE Design Automation Conference. New Jersey: IEEE Press, 1982:175 -181.
  • 3Krishnamurthy B. An improved min -cut algorithm for partitioning VI_SI networks [ J ]. IEEE Transactions on Computers, 1984., 33(5) : 438 -446.
  • 4Sanchis L A. Multiple- way network partitioning[ J]. IEEE Transactions on Computers, 1989, 38( 1 ) : 62 -81.
  • 5Areibi S, Vannelli A. Efficient hybrid search techniques for circuit partitioning[ C ]//IEEE 4th World Muhiconferenee on Circuits, Systems, Communications and Computers. Athens : [ s. n. ], 2000.
  • 6Areibi S M. GRASP: an effective constructive technique for VLSI circuit partitioning[ C]//Proceedings of the IEEE Canadian Conference on Electrical and Computer Engineering. Edmonton: [ s. n. ], 1999:462 -467.
  • 7Li J, Behjat L, Kennings A. Net- cluster: a net- reduction- based clustering preprocessing algorithm for partitioning and placement[J]. IEEE Transactions on CAD of Integrated Circuits and Systems, 2007, 26(4) : 669-679.
  • 8Selvakkumaran N, Karypis G. Multiobjective hypergraph - partitioning algorithms for cut and maximum subdomain - degree minimization [ J ]. IEEE Transactions on CAD of Integrated Circuits and Systems, 2006, 25 (3) : 504 - 517.
  • 9Trifunovic A, Knottenbeh W J. Parallel multilevel algorithms for hypergraph partitioning [ J ]. Journal of Parallel and Distributed Computing, 2008, 68:563-581.
  • 10Resende M G C, Ribeiro C C. GRASP and path -relinking: recent advances and applications [ C ]//Toshihide Ibaraki, Yasunail Yoshitomi. Proceedings of the Fifth Metaheuristics International Conference. Kyoto: [ s. n. ], 2003 : T6 - 1 - T6 - 6.

引证文献4

二级引证文献15

浙江大学学报（工学版）
2007年 第10期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部