• 北大核心期刊(《中文核心期刊要目总览》2017版)
  • 中国科技核心期刊(中国科技论文统计源期刊)
  • JST 日本科学技术振兴机构数据库(日)收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

VLSI详细布线算法研究进展

屈通 盖天洋 王书涵 苏晓菁 粟雅娟 韦亚一

屈通, 盖天洋, 王书涵, 苏晓菁, 粟雅娟, 韦亚一. VLSI详细布线算法研究进展[J]. 微电子学与计算机, 2021, 38(11): 1-6. doi: 10.19304/J.ISSN1000-7180.2021.0030
引用本文: 屈通, 盖天洋, 王书涵, 苏晓菁, 粟雅娟, 韦亚一. VLSI详细布线算法研究进展[J]. 微电子学与计算机, 2021, 38(11): 1-6. doi: 10.19304/J.ISSN1000-7180.2021.0030
QU Tong, GAI Tianyang, WANG Shuhan, SU Xiaojing, SU Yajuan, WEI Yayi. Research progress of VLSI detailed routing algorithm[J]. Microelectronics & Computer, 2021, 38(11): 1-6. doi: 10.19304/J.ISSN1000-7180.2021.0030
Citation: QU Tong, GAI Tianyang, WANG Shuhan, SU Xiaojing, SU Yajuan, WEI Yayi. Research progress of VLSI detailed routing algorithm[J]. Microelectronics & Computer, 2021, 38(11): 1-6. doi: 10.19304/J.ISSN1000-7180.2021.0030

VLSI详细布线算法研究进展

doi: 10.19304/J.ISSN1000-7180.2021.0030
基金项目: 

国家自然科学基金 61874002

北京市自然科学基金 4182021

国家重点研发计划 2019YFB2205005

详细信息
    作者简介:

    屈通  男,(1996-),硕士.研究方向为设计与工艺联合优化

    盖天洋  男,(1994-),博士研究生.研究方向为设计与工艺联合优化

    王书涵  男,(1997-),硕士研究生.研究方向为设计与工艺联合优化

    苏晓菁  女,(1989-),博士,助理研究员.研究方向为设计与工艺联合优化、良率提升和计算光刻

    韦亚一  男(1965-),博士,研究员.研究方向为先导光刻工艺

    通讯作者:

    粟雅娟(通讯作者)  女,(1975-),博士,研究员.研究方向为设计工艺协同优化、低功耗器件建模、二维器件与CMOS集成、应用于逻辑电路的MEMS/NEMS开关器件等. E-mail: suyajuan@ime.ac.cn

  • 中图分类号: TN47

Research progress of VLSI detailed routing algorithm

  • 摘要:

    超大规模集成电路(VLSI)中的详细布线是物理设计中一个重要且具有挑战性的环节.在这一阶段,所有导线的路径都会被确定下来,布线的优劣直接关系到芯片的面积和性能,路径搜索是布线中最为耗时的步骤之一.本文介绍了基于网格的布线模型,将布线问题抽象为一个图搜索问题或者多商品流问题;总结了迷宫搜索算法、A*算法、整数线性规划(ILP)算法和并行加速算法在路径搜索中的应用和针对设计约束作出的优化,结合在布线器中应用情况分析其优劣;总结回顾了基于机器学习求解算法的研究进展,分析了存在的问题,并对详细布线算法的发展趋势做了展望.分析表明,A*算法在布线质量、稳定性和速度等方面的综合性能较其他算法更为优异,其难点在于设计合理的布线排序策略和图模型.强化学习具有巨大的研究潜力,目前的研究仅在规模较小的设计中测试,仍需要进一步改进和探索.

     

  • 图 1  详细布线的3D网格图[4]

    图 2  划分子区域的示意图

    表  1  布线器比较

    布线器 算法 竞赛/约束 线网规模
    MANA[3] MANA 线端距离/最小线长 12k
    Du[6] Dijkstra SID 16k
    Ding[7] Dijkstra SIM 12k
    DSAR[8] A* DSA 22k
    MCFRoute[10] ILP ISPD05/14 255k/158k
    DRAPS[2] A* ISPD18 182k
    Sun[12] 协商 ISPD18 182k
    TritonRoute[11] MILP ISPD18 (1st) 182k
    TritonRoute[17] A* ISPD18/19 182k/889k
    Dr.CU[4, 5] Dijkstra ISPD18 (2nd)/ISPD19 (1st) 182k/889k
    Alpha-PD-Router[16] A*/RL RL <25
    Liao[14](全局布线器) RL RL 50
    下载: 导出CSV
  • [1] SOUKUP J. Fast maze router[C]//15th Design Automation Conference. Las Vegas, NV, USA: IEEE, 1978. DOI: 10.1109/DAC.1978.1585154.
    [2] GONCALVES S M M, ROSA L S, MARQUES F S. DRAPS: A design rule aware path search algorithm for detailed routing[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2020, 67(7): 1239-1243. DOI: 10.1109/TCSII.2019.2937893.
    [3] CHANG F Y, TSAY R S, MAK W K, et al. MANA: A shortest path maze algorithm under separation and minimum length nanometer rules[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32(10): 1557-1568. DOI: 10.1109/TCAD.2013.2265878.
    [4] CHEN G J, PUI CW, LI H C, et al. Dr. CU: detailed routing by sparse grid graph and minimum-area-captured path search[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(9): 1902-1915. DOI: 10.1109/TCAD.2019.2927542.
    [5] LI H C, CHEN G J, JIANG B T, et al. Dr. CU 2.0: a scalable detailed routing framework with correct-by-construction design rule satisfaction[C]//2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). Westminster, CO, USA: IEEE, 2019: 1-7. DOI: 10.1109/ICCAD45719.2019.8942074.
    [6] DU Y L, MA Q, SONG H, et al. Spacer-is-dielectric-compliant detailed routing for self-aligned double patterning lithography[C]//Proceedings of the 50th Annual Design Automation Conference on-DAC′13. Austin, Texas: ACM Press, 2013: 1-6. DOI: 10.1145/2463209.2488848.
    [7] DING Y X, CHU C, MAK W K. Detailed routing for spacer-is-metal type self-aligned double/quadruple patterning lithography[C]//Proceedings of the 52nd Annual Design Automation Conference on-DAC′15. San Francisco, California: ACM Press, 2015: 1-6. DOI: 10.1145/2744769.2744821.
    [8] OU J J, YU B, XU X Q, et al. DSAR: DSA aware routing with simultaneous DSA guiding pattern and double patterning assignment[C]//Proceedings of the 2017 ACM on International Symposium on Physical Design-ISPD′17. Portland, Oregon, USA: ACM Press, 2017: 91-98. DOI: 10.1145/3036669.3036677.
    [9] JIA X T, CAI Y C, ZHOU Q, et al. MCFRoute: A detailed router based on multi-commodity flow method[C]//2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Jose California: ACM, 2014: 397-404. DOI: 10.5555/2691365.2691446.
    [10] JIA X T, CAI Y C, ZHOU Q, et al. A multicommodity flow-based detailed router with efficient acceleration techniques[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(1): 217-230. DOI: 10.1109/TCAD.2017.2693270.
    [11] KAHNG A B, WANG L T, XU B Q. TritonRoute: an initial detailed router for advanced VLSI technologies[C]//2018 IEEE/ACM International Conference on Computer-Aided Design. San Diego, CA, USA: ACM, 2018: 1-8. DOI: 10.1145/3240765.3240766.
    [12] SUN F K, CHEN H, CHEN C Y, et al. A multithreaded initial detailed routing algorithm considering global routing guides[C]//2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Diego, CA, USA: IEEE, 2018. DOI: 10.1145/3240765.3240777.
    [13] QI Z D, CAI Y C, ZHOU Q. Accurate prediction of detailed routing congestion using supervised data learning[C]//2014 IEEE 32nd International Conference on Computer Design (ICCD). Seoul, Korea (South): IEEE, 2014: 97-103. DOI: 10.1109/ICCD.2014.6974668.
    [14] LIAO H G, ZHANG W T, DONG X L, et al. A deep reinforcement learning approach for global routing[J]. Journal of Mechanical Design, 2020, 142(6): 061701. DOI: 10.1115/1.4045044.
    [15] LIAO H G, DONG Q Y, DONG X L, et al. Attention routing: track-assignment detailed routing using attention-based reinforcement learning[C]//ASME 2020 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. [s. l. ]: ASME, 2020. DOI: 10.1115/DETC2020-22219.
    [16] GANDHI U, BUSTANY I, SWARTZ W, et al. A reinforcement learning-based framework for solving physical design routing problem in the absence of large test sets[C]//2019 ACM/IEEE 1st Workshop on Machine Learning for CAD (MLCAD). Canmore, AB, Canada: IEEE, 2019: 1-6. DOI: 10.1109/MLCAD48534.2019.9142109.
    [17] KAHNG A B, WANG L T, XU B Q. TritonRoute: the open-source detailed router[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 40(3): 547-559. DOI: 10.1109/TCAD.2020.3003234.
  • 加载中
图(2) / 表(1)
计量
  • 文章访问数:  302
  • HTML全文浏览量:  196
  • PDF下载量:  70
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-01-06
  • 修回日期:  2021-02-26

目录

    /

    返回文章
    返回