VLSI电路的复杂网络特性

2018-12-25张植莹

电子技术与软件工程 2018年8期

文/张植莹

近几年来，复杂网络受到不同研究领域学者们的广泛关注，复杂性科学得到快速的发展复杂网络系统普遍存在于自然界与人类社会中，如新陈代谢网络、分子结构网络、交通网络、经济技术网络研究现实世界网络的复杂网络特性具有重要的意义，通过发现一类网络的共同特性，可以确定这类网络的核心，从而进行进一步的研究目前，复杂网络的研究热点集中在网络的小世界特性和度分布的统计特性上这些理论为复杂网络的研究奠定了基础。

1 复杂网络统计参量

复杂网络受到多种统计参量的影响，对其功能以及结构的复杂程度有很大的影响，所以要想全方面的分析，就需要对影响电路复杂程度以及电路密集度的影响因素进行分析，主要包括下面几个方面：网络度分布、小世界网络等。

1.1 网络度分布

网络程度分布网络程度分布可以描述为网络中节点程度的概率分布。本节首先介绍节点的度和平均度的定义，然后介绍网络的度分布和累积度分布。网络节点的度是指与某一个节点相连接的所有的边数，每一条边都是组成电路的部分，所以说需要对每一条边进行详细分析和研究，这样才能保证后期运行的过程中避免一些不必要的故障发生。度分布是指电路网络中节点度的概率分布，其可以对电路中的节点进行位置的判断，从而在发生故障的时候进行故障排出，有效的提高故障维修的效率和质量。除了度分布织物，还可以利用累计度分布来描述度的分布情况，它能更加全面的分析一段时间内度的分布情况。

1.2 小世界网络

小世界网络是从完全规则的网络过渡到完全随机的网络。它具有最短的平均最短路径和较高的聚类系数。小世界的判断方法是网络的实际平均路径长度接近同尺度的随机网络，平均聚集系数远大于等大小的随机网络。本节首先介绍平均最短路径的定义和然后介绍了集聚系数的概念。平均最短路径是指网络中两个节点中最短且最简单的路径，寻找到这样一条路径对电路来说是很有必要的，不仅可以节约成本还能简化电路的复杂程度，有效的提高了的网络电路的可操作性。但是在实际中，并不是所有节点之间都有平均最短路径的，所以说需要根据实际情况进行选择，从而保证电路的简约性。集聚系数是指网络中与某一个节点连接的两个节点也互相连接的概率，这也在一定的程度上反映了网络节点的密集程度。

2 实验

小世界网络分为无标度网络、规模网络和单尺度网络的无标度网络的累积分布服从幂律分布，累积尺度网络的分布遵循幂律分布并在尾部截断，网络的累积分布具有快速衰减尾部。

2.1 实验方案

实验采用VLSI参考电路BMHB+Benchmark中的模块包括软模块和硬模块，数量从500到2000，网络数量从5000到60万，最大的模块占电路面积比例09到136之间具体说明IBM-HB+Benchmark电路的特征，该文件包含节点文件，nets文件，pl文件，scl文件，用于节点文件描述模块的宽度和高度;对于网络文件，描述模块在电路中的连接关系;对于pl文件，描述模块在电路中的坐标位置;scl文件，定义了电路中的布线信息。实验平台采用惠普工作站，采用213GHzCPU和4O0GB内存作为测试平台，操作系统为windows7，该工具采用复杂网络专业分析平台Pajek和Matlab实验，将模块作为节点进行基准测试，模块之间的连接为均衡复杂网络中的参考电路首先利用网络的平均最短路径和聚合系数来判断它是否具有小世界特征。基于等效复杂网络模型，得到网络的累积分布，并分析其特点。

2.2 实验结果及分析

通过对等效复杂网络模型的分析和计算，得到基准网络的节点数量（N），平均度数（平均数），平均最短路径数和聚类系数（c）。从数据分析可以看出，最小网络只有915个模块，最大的网络有2339个模块，每个模块的平均值为443523个IBM_HB+，平均范围为12308-969832，不同电路间的平均差值为平均最短路径和聚集系数差异小，d在29605-4007范围内，平均为33542，C在0356l-05125范围内，平均为04187。在此基础上，我们随机生成相同大小的网络（具有相同数量的节点和相同的节点平均值）。随机网络平均最短路径的平均值为2.8614，聚类系数的平均值为0.015，具体而言，基准网络与随机网络的聚类系数的比值范围为11.36-134.7，平均28.51，电路的聚类系数远大于同尺度的随机网络，平均最短路径的比值范围在0.88-1.35之间，平均值为1.17，平均最短路径近似相等。根据小世界网络的条件来看，VLSI电路具有小世界特征

由试验数据可以得出，对复杂电路进行网络特性分析，可以有效的对电路进行全面的分析，判断其故障的原因，从而为后期的维修提供有利的保障，但是在进行分析的时候也需要大量的人力和财力的消耗，所以在进行实验的时候保证实验的安全性和准确性，确保实验的成功率，避免成本的大量浪费。