公开(公告)号：CN1558350A

公开(公告)日：2004-12-29

申请号：CN200410000098.7

申请日：2004-01-14

Applicant: 清华大学

Inventor： 洪先龙 ,  经彤 ,  杨旸 ,  朱祺

IPC: G06F17/50

Abstract: 4－几何结构下O(nlogn)的斯坦纳树方法属于ICCAD技术领域，其特征在于：首先在4－几何结构下构造出4－几何结构生成图，然后基于该生成图构造出所求点集对应的最小生成树，再利用生成图的性质，分别设计4－几何结构边替换方法和三点组方法，分别结合最小生成树和边替换或三点组方法而得到斯坦纳树。它具有比O(n2)低的复杂度，在构造斯坦纳树的效率也高。

公开(公告)号：CN1540554A

公开(公告)日：2004-10-27

申请号：CN200310103046.8

申请日：2003-10-31

Applicant: 清华大学

Inventor： 洪先龙 ,  经彤 ,  许静宇 ,  杨旸

IPC: G06F17/50

Abstract: 标准单元总体布线时障碍下时延驱动直角斯坦纳树方法属于集成电路标准单元总体布线设计领域，其特征在于：它针对每个线网的顶点集合，进行子集合的划分；再利用自己提出的对顶点集合进行遍历后得到的顶点两两连接的关系求解最小时延树的时延公式进行时延计算，对于有障碍的路径利用自己改进的适用于非规则网格的Rubin方法先寻找有障碍的两点间最短距离后再计算时延；由此得到符合时延最小的目标斯坦纳树的顶点连接关系；把顶点集合自底向上逐步连接成最后的目标斯坦纳树。它同时考虑了障碍和时延的最小化，直接适应了集成电路设计对电性能的需求，它能处理多端点线网或有复杂障碍的线网。

公开(公告)号：CN1150481C

公开(公告)日：2004-05-19

申请号：CN02100354.8

申请日：2002-01-15

Applicant: 清华大学

Inventor： 洪先龙 ,  经彤 ,  鲍海云 ,  蔡懿慈 ,  许静宇

IPC: G06F17/50

Abstract: 基于关键网络技术优化时延的标准单元总体布线方法，含有优化布线拥挤的步骤，其特征在于：在生成总体布线图，不受容量、时延等任何约束的条件下构造长度最短的初始布线树，再优化布线拥挤等公知技术基础上，提出了关键引脚、关键边的概念，据此构造出由关键引脚的和关键边的集合，各条有向边的权值、虚拟的源点和汇点构成的关键网络，用最大流与最小割的关系，从最小割的一组边中，重构其所对应线网的布线树，从而缩短关键网络中从虚拟的源点到汇点的总时延。最后用给定的时延约束数据组与优化的时延相比，通过迭代得出一组满足优化目标的全部线网的布线树。它及时准确反映当前对总时延影响最大的子网络，避免时延优化的盲目性，提高优化效率。