基于3、4-几何结构的互连算法研究

互连结构(on-chip interconnect architecture)是集成电路布线的形式化基础。目前，互连线已成为影响电路性能的决定因素。若继续采用现有基于直角(rectilinear)互连结构的Steiner树构造算法进行互连线性能优化，其优化能力受到限制。本项目将研究基于以3、4-几何结构(3、4-geometry)为代表的非直角互连结构的互连算法，试图以基于全新互连结构的互连算法作为突破途径实现高性能的集成电路。该项目的主要研究内容包括：研究适合3、4-几何结构的Steiner树构造算法(包括考虑线长、有障碍、性能驱动等情况)；通过比较分析3、4-几何结构，研究非直角互连及布线的合适发展方向；研究基于3、4-几何结构的总体布线算法。该项研究将引起布图领域算法的更新；同时，对于诸如计算机网络、交通等其他领域布线、设计问题以及NP-Hard问题的研究也具有理论价值。