Matlab辅助集设计-最大不相交子集

Matlab辅助集成电路设计算法

摘要

在超大规模集成电路（VLSI）布线问题中的一个约束条件就是要使线路最短。旅行商问题（TSP）——判断是否存在一条路线可以让赶集的商人跑遍所有城市且都只去一次——就是一个NP 完全问题的教科书例子，生成解需要花费大量的时间，但很容易检测一个解是否正确。该文章实现自动寻找最大不相交子集路径。

1、MATLAB

1.MATLAB软件简介

20世纪70年代，美国新墨西哥大学计算机科学系主任Cleve Moler为了减轻学生编程的负担，用FORTRAN编写了最早的MATLAB。1984年由Little 、 Moler 、 Steve Bangert 、合作成立了的MathWorks公司正式吧MATLAB推向市场。MATLAB是一种商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。

MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。

MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且MATLAB也吸收了像Maple等软件的优点，使MATLAB成为一个强大的数学软件。在新的版本中也加入了对C，FORTRAN，C++，JAVA的支持。

2.MATLAB的优势及特点

1)编程环境

MATLAB由一系列工具组成。这些工具方便用户使用MATLAB的函数和文件，其中许多工具采用的是图形用户界面。包括MATLAB桌面和命令窗口、历史命令窗口、编辑器和调试器、路径搜索和用于用户浏览帮助、工作空间、文件的浏览器。随着MATLAB的商业化以及软件本身的不断升级，MATLAB的用户界面也越来越精致，更加接近Windows的标准界面，人机交互性更强，操作更简单。而且新版本的MATLAB提供了完整的联机查询、帮助系统，极大的方便了用户的使用。简单的编程环境提供了比较完备的调试系统，程序不必经过编译就可以直接运行，而且能够及时地报告出现的错误及进行出错原因分析。

2)简单易用

Matlab是一个高级的矩阵/阵列语言，它包含控制语句、函数、数据结构、输入和输出和面向对象编程特点。用户可以在命令窗口中将输入语句与执行命令同步，也可以先编写好一个较大的复杂的应用程序（M文件）后再一起运行。新版本的MATLAB语言是基于最为流行的C++语言基础上的，因此语法特征与C++语言极为相似，而且更加简单，更加符合科技人员对数学表达式的书写格式。使之更利于非计算机专业的科技人员使用。而且这种语言可移植性好、可拓展性极强，这也是MATLAB能够深入到科学研究及工程计算各个领域的重要原因。

3)强处理能力

MATLAB是一个包含大量计算算法的集合。其拥有600多个工程中要用到的数学运算函数，可以方便的实现用户所需的各种计算功能。函数中所使用的算法都是科研和工程计算中的最新研究成果，而且经过了各种优化和容错处理。在通常情况下，可以用它来代替底层编程语言，如C和C++ 。在计算要求相同的情况下，使用MATLAB的编程工作量会大大减少。MATLAB的这些函数集包括从最简单最基本的函数到诸如矩阵，特征向量、快速傅立叶变换的复杂函数。函数所能解决的问题其大致包括矩阵运算和线性方程组的求解、微分方程及偏微分方程的组的求解、符号运算、傅立叶变换和数据的统计分析、工程中的优化问题、稀疏矩阵运算、复数的各种运算、三角函数和其他初等数学运算、多维数组操作以及建模动态仿真等。

2、超大规模集成电路设计概论

1.大规模集成电路设计周期

大规模集成电路设计周期分为以下几个步骤：系统规范说明、功能设计、逻辑设计、电路设计、物理设计、设计验证、制造、封装和测试。

3.物理设计

1)物理设计

物理设计即版图设计，是VLSI（大规模集成电路设计）设计中最费时的一步。物理设计要把每个元件的电路表示转换为几何表示，同时，元件间连接的线网也被转换成几何连线图形。物理设计的输入是电路的元件说明和网表，其输出是设计好的版图，即根据电路和工艺要求完成芯片上单元或功能块的安置，实现它们之间所需要的互连。它要把每个元件的电路表示转换成几何表示，同时，元件问的连线也要被转换成几何连线图形。

8)布图规划和布局算法

布图规划和布局算法的目标是最小化芯片的面积，同时满足其它约束如模块间的完全互连等。布局完成之后将进入线网布线阶段。线网布线一般划分为总体布线和详细布线这两个布线过程，总体如线确定一个线网的大致走线，它将各网合理地分配到各靠线区域中，以确保尽可能离的布通率；详细布线则最终产生线网在芯片上的实际走线，以及生成各线网的几何版图。压缩的任务是从各个向上压缩芯片的版图以期将芯片的总面积减小。布图规划和布局算法的目标是最小化芯片的面积，同时满足其它约束如模块间的完全互连等。布局完成之后将进入线网布线阶段。线网布线一般划分为总体布线和详细布线这两个布线过程，总体如线确定一个线网的大致走线，它将各网合理地分配到各靠线区域中，以确保尽可能离的布通率；详细布线则最终产生线网在芯片上的实际走线，以及生成各线网的几何版图。压缩的任务是从各个向上压缩芯片的版图以期将芯片的总面积减小。

9)布线算法

布线过程是物理设计中布局之后的重要步骤，布局确定了模块在芯片上的位置和模块上各引脚的位置，并通过网表提供了各引脚间的互连信息。

大多数VLSI 布图问题在算法上都可归结于图论问题，因此图论算法在布图中有着广泛的应用。而多VLSI 布线设计中的布线问题都是与一个特殊图上的最短路径(ShortestPath，SP)有关的问题。因此，最短路径算法在布线中有重要地位。

在计算机科学的很多领域中都会出现查找最短路径的问题。比如，在超大规模集成电路（VLSI）布线问题中的一个约束条件就是要使线路最短。旅行商问题（TSP）——判断是否存在一条路线可以让赶集的商人跑遍所有城市且都只去一次——就是一个NP 完全问题的教科书例子，生成解需要花费大量的时间，但很容易检测一个解是否正确。下面介绍一种算法——动态规划算法

3、动态规划算法

1、主题：

在一块电路板的上、下两端分别有n个接线柱。然后上下两端的接线柱分别两两有连线，现在要在这个连线之中找出最大不相交的子集。

1、问题描述：

我们用一个行向量x（i）来表示这两端的线路，例如

x = 6 1 7 4 9 5 8 3 10 2

即x（1）=6，则第一行第一个点连接到第二行的第六个点。

观察数列可以得出一个规律，从左往右按顺序，只要后面的数比前面的数大，直线就不会相交了。因此，想要找到最大不相交直线的子集，只要找出从左往右最大递增数列就好了。

例如上面的例子，最大不相交数列是x(1) x(4) x(5) x(8) x(10)，即对应的值是 2，4，6，7，9。

这个2，4，6，7，9就是那个从左到右最大递增数列，也就是我们要找的最大不相交子集。

data =

2 4 6 7 9

1)算法思路：

找出所有的可能性，找出子集数量最多的那个。

例如首先在x(1)之后的数列中找出所有比x(1)大的数，再在所有比x（1）大的数中找出后面所有比数本身大的数；然后再从x（2）开始重复x（1）的操作

这里我画图来说明

第一行是初始，第二行是比第一行对应两线元素大的数(这里的图不完整，按照上面的数列画的)

(Word画出来然后截图的)

然后到最后就看哪个深度最深，就找出那个深度最深的以个行列就行了

10)算法具体实现

我分成了三个function来写biggest_sub，pocess_juzhen，find_bigger；

1、其中biggest_sub是主函数，里面调用x(1,:)=randperm(10);生成随机线路序列，还有负责画图，一个是整体图，一个是最大子集图，然后还调用find_bigger找到比当前数大的数，调用pocess_juzhen对调用find_bigger之后生成的数据矩阵count_out进行处理，提取最终子集数据

2、find_bigger完整函数是[r1_out,r2_out,count_out,r_type_num]=find_bigger(r1,r2,count,x)

这个算法的核心在于这个矩阵count_out的数据存储，我们定义一个矩阵第一行是全部是1，一共有n+1列，前面n列是关于x向量的，最后地n+1个是个标志位。

直接句个例子说明一下会清晰一点（n=10，矩阵有11列）

1 1 1 1 1 1 1 1 1 1 1

0 0 1 0 1 0 1 0 1 0 1

0 0 1 1 1 1 1 1 1 1 2

0 0 0 0 1 0 1 0 1 0 3

0 0 0 0 1 1 1 0 1 0 4

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 1 0 1 0 6

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 1 0 8

0 0 0 0 0 0 0 0 0 0 9

0 0 0 0 0 0 0 0 0 0 10

0 0 0 0 1 0 1 0 1 0 3

这是矩阵的片段，从第而列开始分析，第二列最后一个数字是1，说明这一列是以x(1)为开始，找出所有比x（1）大的数字如果比他大，则该元素位置显示1，否则显示0，如x（1）=6，x（2）=1，所以第二行第二个数是0，x（3）=7，比x（1）大，所以矩阵count_out(2，3)=1，以此类推；最后一列的数字是起始位，也就是所有的比较都是和x（这位元素数值）比较的。

输入参数r1是输入的矩阵中，上次新增的矩阵数据的起始行，r2是输入的矩阵中，上次新增的矩阵数据的最后一行,count是输入矩阵,x是输入的向量数据。

输出参量r1_out是输出矩阵相对于输出是新增的数据的起始行，r2_out是输出矩阵相对于输出是新增的数据的末行,count_out输出矩阵,r_type_num是每一次输出中的数据分类，开始时候是想通过这个数据对矩阵处理的，但后来找到比它优越的方法就把它抛弃了，这里我暂时不想删掉，就先留着吧

3、pocess_juzhen是对输出矩阵的数据提取[pre_r,flag]=pocess_juzhen(r_in,count_out)，例如对下面的矩阵处理，从最后一行的矩阵看起，0 0 0 0 0 0 0 0 0 0 9，最后一个9，那就找它之前的行之中的第9列，哪个是1，就选出那一行，再提取那一行的最后一列的数字，0 0 0 0 0 0 0 0 1 0 7，我们这里找到是7，然后再找它前面的行之中第7列的数是1的那行0 0 0 0 0 0 1 0 1 0 6；最后是6，再找它前面的行之中第6列的数是1的那行0 0 0 0 1 1 1 0 1 0 4，在找它前面的行之中第4列的数0 0 1 1 1 1 1 1 1 1 2

这里为了方便我们就只找一种而已，当然，也可以找到很多种，所有的数据都在矩阵里头了，只有对矩阵分析得比较具体就可以找出所有的子集。

4、MATLAB代码实现

1.MATLAB源程序代码

biggest_sub.m文件

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%主函数 %%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function biggest_sub()

%x(1,:)=[1:20];

x(1,:)=randperm(50);

%x=[6 1 7 4 9 5 8 3 10 2]

figure(1);

[r,q]=size(x);

for i=1:q

a=[x(i),i];

y=[2,4];

plot(a, y, '-rs','MarkerSize',10);

hold on;

end

%调用find_bigger，调用足够多的次数就行了

count=ones(1,q+1);

[r1_out,r2_out,count_out,r_type_num]=find_bigger(1,1,count,x);

[r1_out,r2_out,count_out,r_type_num]=find_bigger(r1_out,r2_out,count_out,x);

[r1_out,r2_out,count_out,r_type_num]=find_bigger(r1_out,r2_out,count_out,x);

[r1_out,r2_out,count_out,r_type_num]=find_bigger(r1_out,r2_out,count_out,x);

[r1_out,r2_out,count_out,r_type_num]=find_bigger(r1_out,r2_out,count_out,x);

[r1_out,r2_out,count_out,r_type_num]=find_bigger(r1_out,r2_out,count_out,x);

[r1_out,r2_out,count_out,r_type_num]=find_bigger(r1_out,r2_out,count_out,x);

[r,s]=size(count_out);

last_d=count_out(r,s);

data_diverse(1)=last_d;

pre_r=r;

for i=2:100

%调用pocess_juzhen对矩阵进行处理，把结果存到data_diverse里面

[pre_r,flag]=pocess_juzhen(pre_r,count_out);

if flag==1

data_diverse(i)=count_out(pre_r,s);

else

if flag==0

break

end

end

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%对data_diverse数据倒过来，画出输出结果图%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

[data_diverse_r,data_diverse_q]=size(data_diverse);

for i=1:data_diverse_q

data(i)=data_diverse(data_diverse_q-i+1);

end

figure(2);

for i=1:data_diverse_q

a=[x(data(i)),data(i)];

y=[2,4];

plot(a, y, '-rs','MarkerSize',10);

hold on;

end

b=data;

find_bigger.m文件

function [r1_out,r2_out,count_out,r_type_num]=find_bigger(r1,r2,count,x)

[x_r,x_q]=size(x);

count_out=count;

r_num_per_count_r=0;

r_type_num=0;

for i=r1:r2

r_type_num(i-r1+1)=sum(count(i,1:x_q));

end

for count_r=r1:r2

l_subsc=sum(count(count_r,1:x_q));

subsc=find(count(count_r,1:x_q));

for i=1:l_subsc

for j=(i+1):l_subsc

if x(subsc(i))

count_out(r2+r_num_per_count_r+i,subsc(j))=1;

else

count_out(r2+r_num_per_count_r+i,subsc(j))=0;

end

end

count_out(r2+r_num_per_count_r+i,x_q+1)=subsc(i);

%每完成一个插入一行2向量

% count_out(r2+r_num_per_count_r+i+1,:)=2

end

r_num_per_count_r=r_num_per_count_r+l_subsc-1;

end

r1_out=r2+1;

[temp1,temp2]=size(count_out);

r2_out=temp1;

pocess_juzhen.m文件

function [pre_r,flag]=pocess_juzhen(r_in,count_out)

[r,s]=size(count_out);

last_d=count_out(r_in,s);

pre_r=0;

flag=0;

%pre_num=1;

for i=1:r_in-1

if count_out(r_in-i+1,last_d)==1

pre_r=r_in-i+1;

flag=1;

break

end

end

4.MATLAB仿真结果

N=10的组合

x =

6 1 7 4 9 5 8 3 10 2

count_out =

1 1 1 1 1 1 1 1 1 1 1

0 0 1 0 1 0 1 0 1 0 1

0 0 1 1 1 1 1 1 1 1 2

0 0 0 0 1 0 1 0 1 0 3

0 0 0 0 1 1 1 0 1 0 4

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 1 0 1 0 6

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 1 0 8

0 0 0 0 0 0 0 0 0 0 9

0 0 0 0 0 0 0 0 0 0 10

0 0 0 0 1 0 1 0 1 0 3

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 1 0 1 0 1 0 3

0 0 0 0 1 1 1 0 1 0 4

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 1 0 1 0 6

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 1 0 8

0 0 0 0 0 0 0 0 0 0 9

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 1 0 1 0 6

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 0 0 9

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 1 0 5

0 0 0 0 0 0 1 0 1 0 6

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 0 0 9

0 0 0 0 0 0 0 0 1 0 7

0 0 0 0 0 0 0 0 0 0 9

data =

2 4 6 7 9

N=30的组合

x=

Columns 1 through 21

9 2 1 29 22 6 25 11 15 23 17 13 10 30 21 8 14 3 27 7 16

Columns 22 through 30

18 19 20 4 12 26 24 5 28

data =

3 6 8 12 17 21 22 23 24 28 30

输出矩阵是359*3=太大这里截取片段

size(count_out)

ans =

2359 31

Count_out=

…………

0 0 0 0 0 1 1 0 1 24

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 1 1 0 1 24

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 1 1 0 1 24

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 1 1 0 1 24

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 0 0 0 1 27

0 0 0 0 0 0 0 0 1 28

0 0 0 0 0 0 0 0 0 30

N=50的情况

x =

Columns 1 through 16

44 31 11 15 21 19 46 41 30 4 42 16 28 17 9 8

Columns 17 through 32

50 34 5 45 23 33 49 3 2 40 36 37 6 22 7 18

Columns 33 through 48

29 48 25 20 32 24 14 39 38 12 43 27 26 35 13 1

Columns 49 through 50

47 10

data =

10 19 29 31 32 36 38 45 46 49

5、总结

当前集成电路产业正在由亚微米工艺向深亚微米工艺不断推进，集成电路工艺技术的不断发展冲击着VLSI CAD技术，这就要求集成电路物理设计研究人员根据目前的工艺技术不断改进布局布线、逻辑综合及验证工具，开发出更加适合VLSI产业发展的物理设计算法。

为满足当前和今后集成电路工艺技术不断发展所提出的高性能芯片和SOC芯片设计。为此，在VLSI电路物理设计中的应用中，最短路径、动态规划算法能够解决VLSI物理设计中最基本的问题。

在MATLAB的使用过程中，MATLAB强大的程序函数量和矩阵计算功能大大提高了整体算法的研究速度，在实现电路系统的功能时，可在MATLAB中进行算法测试，可以更好的理解算法的精髓，提高电路系统移植的高效性。