运用于VLSI中的新型网表—距离聚类分割技术

摘要

自从大规模集成电路进入百万门级别设计之后，超大规模集成电路的设计就成为一项工序繁琐、耗时长久的电子设计过程。因此，减小设计的复杂度及缩短设计周期成为了制约VLSI设计的重要瓶颈之一。 为了解决这一瓶颈问题，诸多的方法被加入到VLSI设计的整个过程当中，其中尤其以布局过程中的改进作为重点研究的突破口。一种比较常见的方法就是在布局前期处理过程中进行器件聚类处理，从而减少了所需处理的器件数量及认证周期。这种方式已经被广泛的运用到百万门级别以上的大规模集成电路布局设计当中。 但是，传统的布局聚类方法往往只考虑到布局方式的一种特性，如：网表，局部相关度，树型结构图等等。无法吸收更多的全局信息来进行聚类处理，丧失了大量布局信息，因此所产生的布局结果不甚完备，为后期精布局、布线带来先天性的不足。有很大的改进空间。 本论文提出的新方法是基于多种布局参数作为聚类的考虑因素，以物理距离作为聚类依据的方法。而且最后的实验数据结果也为今后的研究者提供了更多通过物理参数的引入、进一步对全局变量进行控制的可能性。本论文的创新之处在于提出了一种多参数布局聚类的新方式，这对聚类布局向更快、更好的方向发展起到了重要的作用。 新方法的关键技术有以下几个： 1.多参数比单参数更利于聚类的依据是什么? 2.如何寻找相关程度较高的两种或者多种参数作为聚类的依据? 3.如何在原有的聚类布局研究平台中引入多参数聚类? 4.多参数聚类的适应度如何? 5.多参数到底比单参数或者无聚类布局提高了多少性能? 在研究过程中，首先利用过去的研究成果，并提出了有效物理距离聚类这一个概念作为聚类依据，并完成了对物理距离理论上及算法上的详细研究，且有效的定义了实际测量的物理距离及布局板的元素位置参量，然后在实际操作中引入物理距离及过去研究中的网表到聚类处理中，从而完成了新方法的实现。最后的实验利用了传统的网表参量、新引入的物理距离参量和一部分的元素面积参量相互的组合作为整体的聚类依据。最终的实验结果表明，新方法大大提高了聚类分割布局的各种性能参数，对于某些布局实验数据性能提高值达到了70％多，而且对于不同的数据库都有一定程度的提高。另外，在实验测试中，还利用了一些其他具体的布局方式产生的中间结果作为聚类的测试数据之一，目的是为了进一步地测试新方法对各种数据的适应度。测试结果也比较理想。 实验结果表明，多参数聚类布局将会成为百万门级别预布局当中的一种全新方法而得到推广及改进。当然整个实验中还存在着各种各样的疑问有待解决，本实验室也会对此进行一定的深入研究及后期跟踪改进。

目录

文摘

英文文摘

声明

第一章 简介

1.1 研究背景

1.1.1 版图设计的重要性

1.1.2 布局方式划分

1.2 聚类技术的引入

1.2.1 聚类技术的发展

1.2.2 网表聚类技术

1.3 新想法的提出

1.4 章节安排

第二章LU分解矩阵解法运用于二次规划布局

2.1 大规模集成电路的二次规划布局

2.1.1 网表中的元素超图

2.1.2 二次规划布局

2.1.3 线性方程组

2.2 LU分解运用于二次规划布局

2.2.1 线性方程组的传统分解解法

2.2.2 线性方程组的LU分解解法

2.2.3 LU分解解法的优势

2.2.4 实验结果

第三章多层超图分割运用于大规模集成电路布局

3.1 一些相关的定义及术语

3.2 多层超图分割

3.2.1 分层聚类过程

3.2.2 顶层分割(top-level partitioning)

3.2.3 精分割与逆聚类处理

3.3 hMETiS：一种超图分割算法包

第四章 网表聚类技术运用于大规模集成电路布局

4.1 聚类技术的分类

4.2 网表聚类技术

4.2.1 网表数据的结构

4.2.2 网表聚类技术的步骤

4.3 Best-Choice algorithm

4.3.1 聚类超图与树型结构

4.3.2 Best-Choice algotithm原理

第五章物理距离聚类运用于大规模集成电路布局

5.1 基本概念

5.1.1 如何定义两个元素间的距离

5.1.2 如何减少分割度

5.1.3 如何完成其他的聚类步骤

5.2 距离聚类的算法描述

第六章实验及其结果

6.1 新聚类方案提出

6.2 实验

6.2.1 实验环境

6.2.2 输入数据

6.2.3 输出文件

6.3 实验结果

6.3.1 实验一

6.3.2 实验二

6.3.3 实验三

第七章结论及今后工作

参考文献

附录

作者在攻读硕士学位期间公开发表的论文及申请专利

作者在攻读硕士学位期间所参加的项目

致 谢