芯片级布图规划中的缓冲器规划算法.pdfVIP

中国科学E辑信息科学2004，34(8)：869—881 芯片级布图规划中的缓冲器规划算法木 陈 松” 洪先龙 董社勤 马昱春蔡懿慈 (清华大学计算机科学与技术系，北京100084) Chung—KuanCheng of (UniversityCalifornia，SanDiego，USA) 顾 钧 (香港科技大学计算机科学与技术系，香港) 摘要 文中对纳米技术下，互连驱动的芯片级布图规划问题中的缓冲器规划 局中的空白区是指在布局中不被任何电路模块占用的闲置区域；该算法充分利 用布局中的空白区插入缓冲器．在基于拓扑的布图规划表示中，可以把电路模块 和空白区相关联，在相应区域内移动一些电路模块就可以达到重分布空白区的 目的．在进行空白区重分布的过程中，给定布局的总面积和拓扑结构将维持不变． 通过重分布布局中的空白区，可以增加满足时延约束的线网数目；实验证实，满 足时延约束的线网数的增长率平均达到9％． 关键词 缓冲器规划 空白区 重分布布图规划 VLSI角模块序列 随着超大规模集成电路(VLSI)的不断发展，纳米技术和高频技术的应用，互 连的设计与优化成为决定系统性能、成本和可靠性的关键问题．为了确保电路设 计的时序特性，在设计的流程中，互连的设计应该尽早加以考虑．在过去lO年里， 人们已经研究出了多种互连优化技术，例如拓扑的构造，缓冲器插入，器件尺寸 的优化，线宽和线间距的优化，以及上述各种优化技术的组合应用．在文献[1】中 2004—03—13收稿，2004．06—07收修改稿 目(CCR．0096383)与“八六三”国家高技术研究发展计划(2002AAIZl460)资助项目 4+E-mail：chensoo@mails．tsinghua．edu．ca 。 SCIENCEINCHINASer．EInformationSciences 中国科学E辑信息科学 第34卷 对这些互连优化技术进行了全面的概述． 模型下，长连线的时延与线长的平方成比例增长，而利用缓冲器插入技术，可以 控制连线的时延与线长呈线性增长关系．为满足时延约束，需要插入的缓冲器数 km 目随工艺尺寸的减小而持续增长．例如，在70nm工艺下【21，总线长估计为10 硅资源，所以在设计过程中，缓冲器应该尽早规划．近年来，缓冲器规划问题受 到广泛的关注，人们已经提出了很多缓冲器规划的方法，但是由于缓冲器规划问 题本身的复杂性，无法将其有效地集成到布图规划过程中，因此基本上将其作为 布图规划的后处理过程． Cong等【34】引入了可行区域(feasible 缓冲器模块；缓冲器的可行区域是指在满足线网的目标延时的条件下，缓冲器可 基础上引入了独立可行区域的概念，同时试图优化布线拥挤度；缓冲器模块都被 器的情况下，提出了求解最优解的算法，同样模块间的空白区域用来插入缓冲器． o]用多商品流的方法，将缓冲器分配到预先已存在的缓冲器模块． Dragan等【91 Alpert等[1 块内部也允许插入缓冲器，因此这种方法会使插入缓冲器的点分布在布局的各 通道插入的布图规划系统，用于基于总线的微处理器设计． 布局中的空白区是指在布局中不被任何电路模块占用的闲置区域．在有较 目标的惟一选择．作为布图规划的后处理过程，缓冲器规划一定是在布图规划较 优解(即较为紧凑的布图)的基础上进行；因而其空白区一定有了确定的位置、大 小和数量．目前所有相关研究基本是在这个限定的前提下进行缓冲器规划．如何 突破这一限定的前提，使布线阶段确定具体的缓冲器数目和位置时能有更好的 布图规划和缓冲器规划的结果作为开始，不外两种解决方案，一种是在布图规划 阶段有意增加空白区，另一种就是改变现有空白区的分布．前一种方法很难实现， 因为无法在布图规划过程中