基于混合离散粒子群优化的轨道分配算法

doi:10.16451/j.cnki.issn1003-6059.201908009

摘要
图/表
参考文献(26)
相关文章 (2)

全文: PDF (819 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要

现有的轨道分配工作大多忽略局部线网问题,并且容易陷入局部极值.为此,文中基于离散粒子群优化、遗传操作和基于协商的精炼策略,综合考虑局部线网、重叠冲突、线长和障碍物,提出轨道分配算法.算法抽象局部线网,构建对应的线段模型.为了扩大种群多样性,混合遗传操作以提高全局搜索效率.同时,设计简单高效的适应度函数.最后,使用基于协商的精炼策略进一步减少线段重叠.实验表明文中算法的有效性,该算法可以获得较佳的重叠代价指标优化值,减少关键布线区域的拥挤情况.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	郭文忠
	陈晓华
	刘耿耿
	陈国龙

关键词 ：轨道分配, 超大规模集成电路, 离散粒子群优化, 局部线网, 遗传算子

Abstract：

Most of the existing track allocation works neglect the local nets problem, and are prone to fall into the local extremums. Based on discrete particle swarm optimization, genetic operation and negotiation-based refining strategy, a track assignment algorithm is proposed by considering local nets, overlapping conflict, wirelength and blockages. The algorithm abstracts local nets and constructs the corresponding model of segments. To expand population diversity, hybrid genetic operation is incorporated to improve the efficiency of global search. At the same time, a simple and efficient fitness function is designed. Finally, the negotiation-based refining strategy is exploited to further reduce the overlap of segments. The experimental results indicate the effectiveness of the proposed algorithm. The algorithm can obtain better overlapping cost index optimization value and reduce the congestion in the key routing area.

Key words： Track Assignment Very Large Scale Integration Discrete Particle Swarm Optimization Local Nets Genetic Operator

收稿日期: 2019-05-13

ZTFLH:

TP 301

基金资助:

国家自然科学基金项目(No.61877010,11501114)、福建省自然科学基金项目(No.2019J01243)

通讯作者: 刘耿耿(通讯作者),博士,副教授,主要研究方向为计算智能及其应用.E-mail:liu_genggeng@126.com.

作者简介: 郭文忠,博士,教授,主要研究方向为计算智能及其应用.E-mail:guowenzhong@fzu.edu.cn.陈晓华,硕士研究生,主要研究方向为EDA设计算法.E-mail:sherryhchen@163.com.陈国龙,博士,教授,主要研究方向为人工智能、网络信息安全.E-mail:fzucgl@163.com.

引用本文:

郭文忠, 陈晓华, 刘耿耿, 陈国龙. 基于混合离散粒子群优化的轨道分配算法[J]. 模式识别与人工智能, 2019, 32(8): 758-770. GUO Wenzhong, CHEN Xiaohua, LIU Genggeng, CHEN Guolong. Track Assignment Algorithm Based on Hybrid Discrete Particle Swarm Optimization. , 2019, 32(8): 758-770.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.201908009 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2019/V32/I8/758

[1] 徐宁,洪先龙.超大规模集成电路物理设计理论与算法.北京:清华大学出版社, 2009.
(XU N, HONG X L. Very Large Scale Integration Physical Design Theory and Method. Beijing, China: Tsinghua University Press, 2009.)
[2] CHO M, XIANG H, PURI R, et al. Track Routing and Optimization for Yield. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(5): 872-882.
[3] GAO X, MACCHIARLO L. Track Routing Optimizing Timing and Yield // Proc of the 16th Asia and South Pacific Design Automation Conference. Washington, USA: IEEE, 2011: 627-632.
[4] CHANG Y N, LI Y L, LIN W T, et al. Non-slicing Floorplanning Based Crosstalk Reduction on Gridless Track Assignment for a Gridless Routing System with Fast Pseudo-Tile Extraction // Proc of the ACM Interntaional Symposium on Physical Design. New York, USA: ACM, 2008: 134-141.
[5] BATTERYWALA S, SHENOY N, NICHOLLS W, et al. Track Assignment: A Desirable Intermediate Step between Global Routing and Detailed Routing // Proc of the IEEE/ACM International Conference on Computer Aided Design. Washington, USA: IEEE, 2002: 59-66.
[6] LAI B T, LI T H, CHEN T C. Native-Conflict-Avoiding Track Routing for Double Patterning Technology // Proc of the IEEE International SOC Conference. Washington, USA: IEEE, 2012. 381-386.
[7] WONG M P, LIU W H, WANG T C. Negotiation-Based Track Assignment Considering Local Nets // Proc of the 21st Asia and South Pacific Design Automation Conference(ASP-DAC). Washington, USA: IEEE, 2016: 378-383.
[8] 郭文忠,陈国龙.一种求解多目标最小生成树问题的有效离散粒子群优化算法.模式识别与人工智能, 2009, 22(4): 597-604.
(GUO W Z, CHEN G L. An Efficient Discrete Particle Swarm Optimization Algorithm for Multi-criteria Minimum Spanning Tree. Pa-ttern Recognition and Artificial Intelligence, 2009, 22(4): 597-604.)
[9] MUDJIHARTONO P, JIAMTHAPTHAKSIN R, TANPRASERT T. Parallelized GA-PSO Algorithm for Solving Job Shop Scheduling Problem // Proc of the 2nd International Conference on Science in Information Technology. Washington, USA: IEEE, 2016: 103-108.
[10] 钟一文,蔡荣英.求解二次分配问题的离散粒子群优化算法.自动化学报, 2007, 33(8): 871-874.
(ZHONG Y W, CAI R Y. Discrete Particle Swarm Optimization Algorithm for QAP. Acta Automatica Sinica, 2007, 33(8): 871- 874.)
[11] DU J X, HUANG D S, ZHANG J, et al. Shape Matching Using Fuzzy Discrete Particle Swarm Optimization // Proc of the IEEE Swarm Intelligence Symposium. Washington, USA: IEEE, 2005: 405-408.
[12] SHARMA A, KAPUR R K. Image Enhancement Using Hybrid GSA-Particle Swarm Optimization // Proc of the 2nd International Conference on Contemporary Computing and Informatics. Washington, USA: IEEE, 2016: 698-704.
[13] TOREINI E, MEHRNEJAD M. Clustering Data with Particle Swarm Optimization Using a New Fitness // Proc of the 3rd Conference on Data Mining and Optimization. Washington, USA: IEEE, 2011: 266-270.
[14] WANG C, ZHANG Y, SONG J B, et al. A Novel Optimized SVM Algorithm Based on PSO with Saturation and Mixed Time-Delays for Classification of Oil Pipeline Leak Detection. Systems Science and Control Engineering, 2019, 7(1): 75-88.
[15] PRAKASH A, LAL R K. PSO: An Approach to Multiobjective VLSI Partitioning // Proc of the International Conference on Innovations in Information, Embedded and Communication Systems. Washington, USA: IEEE, 2015. DOI: 10.1109/ICIIECS.2015.7192971.
[16] GUO W Z, LIU G G, CHEN G L, et al. A Hybrid Multi-objective PSO Algorithm with Local Search Strategy for VLSI Partitioning. Frontiers of Computer Science, 2014, 8(2): 203-216.
[17] CHEN G L, GUO W Z, CHEN Y Z. A PSO-Based Intelligent Decision Algorithm for VLSI Floorplanning. Soft Computing, 2010, 14(12): 1329-1337.
[18] SIVARANJANI P, KUMAR A S. Thermal-Aware Non-slicing VLSI Floorplanning Using a Smart Decision-Making PSO-GA Based Hybrid Algorithm. Circuits, Systems, and Signal Processing, 2015, 34(11): 3521-3542.
[19] KARIMI G, AKBARPOUR H, SADEGHZADEH A. Multi Objective Particle Swarm Optimization Based Mixed Size Module Placement in VLSI Circuit Design. Applied Mathematics and Information Sciences, 2015, 9(3): 1485-1492.
[20] LIU G G, HUANG X, GUO W Z, et al. Multilayer Obstacle-Avoiding X-Architecture Steiner Minimal Tree Construction Based on Particle Swarm Optimization. IEEE Transactions on Cybernetics, 2015, 45(5): 1003-1016.
[21] 刘耿耿,陈志盛,郭文忠,等.基于自适应PSO和混合转换策略的X结构Steiner最小树算法.模式识别与人工智能, 2018, 31(5): 398-408.
(LIU G G, CHEN Z S, GUO W Z, et al. Self-adapting PSO Algorithm with Efficient Hybrid Transformation Strategy for X-Architecture Steiner Minimal Tree Construction Algorithm. Pattern Recognition and Artificial Intelligence, 2018, 31(5): 398-408.)
[22] VISWANATHAN N, ALPERT C, SZE C, et al. The DAC 2012 Routability-Driven Placement Contest and Benchmark Suite // Proc of the 49th Annual Design Automation Conference. New York, USA: ACM, 2012: 774-782.
[23] HSU M K, CHEN Y F, HUANG C C, et al. Routability-Driven Placement for Hierarchical Mixed-Size Circuit Designs // Proc of the 50th Annual Design Automation Conference. New York, USA: ACM, 2013. DOI: 10.1145/2463209.2488921.
[24] LIU W H, KAO W C, LI Y L, et al. Multithreaded Collision-Aware Global Routing with Bounded-Length Maze Routing // Proc of the 47th Design Automation Conference. New York, USA: ACM, 2013: 709-722.
[25] KIM M C, HU J, LEE D J, et al. A SimPLR Method for Routabi-lity-Driven Placement // Proc of the International Conference on Computer-Aided Design. Washington, USA: IEEE, 2011: 67-73.
[26] HE X, HUANG T, XIAO L F, et al. Ripple: An Effective Rou-tability-Driven Placer by Iterative Cell Movement // Proc of the IEEE/ACM International Conference on Computer-Aided Design. Washington, USA: IEEE, 2011: 74-79.