技术领域

本发明涉及一种电源集群构建算法，特别是设计一种应用于大规模多电压域芯片上的电源集群构建算法。

背景技术

文献“Kose S,Friedman E G.Distributed On-Chip Power Delivery[J].IEEEJournal on Emerging&Selected Topics in Circuits&Systems,2012,2(4):704-713.”公开了一种片上电源集群构建算法。其核心思想为：

将电源和去耦电容位置的确定转换为最优设施选址问题。由于电源位置影响整体电源集群的电源压降、响应时间等性能，可以将这些性能作为参数建立一个数学函数。从而将电源最优位置的确定转换为对该函数最优化的线性问题。

该算法实现较为简单，但存在以下缺点：

1、线性最优求解消耗的计算资源随电路节点规模迅速增长。若电压域太多(如：100个以上)，整个算法要求的计算存储资源和计算时间太多，甚至无法实现。因此，可处理的电路规模有限。

2、该算法执行时，必须确定电源和去耦电容的数量。在此基础上，才能得到各个电源的最优位置。

发明内容

要解决的技术问题

为了克服现有算法可处理电路规模有限和只能在特定电源数量下运行的不足，本发明提供一种可自动根据实际电路负载情况计算得到电源数量，并且消耗计算资源较少的片上电源集群构建算法。

技术方案

一种高效快速的电源集群构建方法，其特征在于将芯片上所有负载的坐标位置、负载电流值作为输入文件A；步骤如下：

步骤1：在输入文件A中查找负载电流最大的电路节点，记录其坐标位置，作为当前电压域的第一个负载节点；

步骤2：计算输入文件A中其他负载节点与当前电压域的第一个负载节点的距离，然后按照由近及远排序并依次遍历；判断是否满足以下条件：

1)当前电压域内所有节点的负载电流之和是否小于稳压器能提供的最大输出电流；

2)与电流最大负载点的物理距离是否小于规定的最大距离；

若满足，则按照距离最大负载节点物理位置的远近，将满足条件的节点依次纳入到当前电压域中，并从总负载文件A中将其删除；若不满足，则终止当前电压域的扩展；

步骤3：对输入文件A中剩余的负载节点重复步骤1-2，直至输入文件A为空，即所有负载点都划分到电压域内；

步骤4：在已生成的各个电压域内，分别运行粒子群算法查找电源最优位置，具体为：初始化粒子群的位置坐标，按照当前粒子群中最优粒子位置和当前粒子的最优位置进行位置更新；计算目标函数，其组成为所有负载和电源之间的静态压降，若目标函数更优则选取当前位置为最优，否则，舍弃；经过多次迭代后，得到最终粒子位置，即电源位置；将结果输出到文件B中。

有益效果

本发明提出的一种应用于大规模多电压域芯片上的电源集群构建方法，能够根据实际负载分布情况，自动得到需要的电源数量。可处理的电路规模大幅度提高，负载点数目可达到105以上。电源最优位置的搜索算法处理的电路规模较小，因此极大的降低了对计算资源和计算时间的要求。

附图说明

图1是本发明以大负载节点为中心逐步扩展电压域示意图。

图2是本发明电源集群构建算法流程图。

具体实施方式

现结合实施例、附图对本发明作进一步描述：

本发明中的片上电源集群结构为：所有负载节点都划分到相应的电压域内，且只能属于一个电压域。每个电压域内由一个稳压器提供电源。构建算法分为两步进行：电压域划分、电源最优位置搜索。电压域划分算法采用大负载节点逐步扩展方式。如图1所示，以当前负载节点中负载电流最大节点为中心，按照距离的远近，将其周围邻居节点纳入同一个电压域内。直至达到稳压器能提供的最大电流时，当前电压域的扩展才结束。重复该过程，直至所有负载节点都划分到电压域内。电源最优位置搜索算法基于粒子群算法进行构造。通过多次迭代得到电源的最优x，y坐标。

本发明的具体算法流程如图2所示。算法执行之前，需要统计芯片上所有负载的坐标位置、负载电流值作为输入文件A。第一步，查找负载电流最大的电路节点，记录其坐标位置，作为当前电压域的第一个负载节点。第二步，计算文件A中其他负载节点与该节点的距离，然后排序并依次遍历。判断是否满足以下条件：1、当前电压域内所有节点的负载电流之和是否小于稳压器能提供的最大输出电流。2、与最大负载点的物理距离是否小于规定的最大距离。若满足，则按照距离最大负载节点物理位置的远近，将附近节点依次纳入到当前电压域中，并从总负载文件A中将其删除。若不满足，则终止当前电压域的扩展。重复该过程，直至输入文件A为空，即所有负载点都划分到电压域内。第三步，在已生成的各个电压域内，分别运行粒子群算法查找电源最优位置。具体为：初始化粒子群的位置坐标。按照当前粒子群中最优粒子位置和当前粒子的最优位置进行位置更新。计算目标函数，其组成为所有负载和电源之间的静态压降。若目标函数更优则选取当前位置为最优。否则，舍弃。经过多次迭代后，得到最终粒子位置，即电源位置。将结果输出到文件B中。

本发明首先将芯片上的所有负载点按照其所需电压及相对位置划分到相应的电压域内。然后在每个电压域内基于粒子群算法得到电源的最优位置。单个电压域的构建采用以大负载电流节点为中心向周边邻居节点逐步扩展方式。当电压域内的负载电流总和大于稳压器所能提供的电流范围后，则停止扩展。然后在剩下负载点中找到最大负载节点，重复单个电压域的构建方式直至所有电路节点都划分到电压域内。最后，采用粒子群算法分别在每个电压域内得到电源的最优位置。粒子群算法类似于遗传算法，但不需要进行交叉和变异操作，其具有实现简单、收敛速度快等优点。非常适合用来搜索解空间中的最优解。算法在较少迭代次数后，就可以得到相对较好的可用解。

采用大电流负载节点逐步扩展方式进行电压域的划分，然后在每个电压域内单独进行粒子群算法得到每个电源的最优位置。可以自动得到较优的电源数量，降低了算法对计算资源和计算时间的要求，极大的提高了可处理电路的规模和速度。

以大电流负载节点为中心逐步扩展建立电压域，在每个电压域内进行粒子群算法得到每个电源的最优位置。

将负载节点的x、y坐标和负载电流值作为输入文件，查找当前负载中所需电流最大的节点。然后计算它和其他节点的距离进行排序。从最近电路节点依次判断当前节点是否满足可纳入电压域的条件。若满足则将邻近节点纳入当前电压域，并在输入文件中删除。不满足，则停止当前电压域的扩展。重复该操作，直至输入文件为空。最后在每个电压域内分别运行粒子群算法得到电源最优位置并输出。