| 主权项 |
一种集成网络器件的多电压片上网络芯片的布图规划方法，其特征在于，给定初始的模块信息，互连信息以及给定的电压值，根据电压值将所有模块划分至不同的电压岛，随后在岛内生成网络器件并将网络器件的规划与布图规划一起处理，求解最优的布图结果，在计算机中依次按以下几个步骤实现：步骤(1)，读入模块信息，包括模块总数n，模块大小，模块的供电电压值，各模块在供电电压值下的功耗，以及模块之间的通信量；步骤(2)，根据输入的模块信息，划分电压岛，步骤如下：步骤(2.1)根据各模块的电压值，将电压值相同的模块分配到同一个集合中；每个集合作为一个电压岛；步骤(2.2)，根据步骤(1)中的模块间的通信信息，为每个电压岛生成一张岛内的通信图，图中的每个节点都对应一个模块，节点编号与模块编号相同，图中的边表示相邻模块之间有通信，边上的权值代表通信量；步骤(3)，对于每个电压岛，根据该电压岛的通信图，配置相应的转换器，步骤如下：步骤(3.1)，假定第k个电压岛通信图G<sub>k</sub>中的节点数为n<sub>k</sub>，通过边权均衡的最小割划分算法将所有节点划分为i个集合，划分步骤如下：步骤(3.1.1)，将G<sub>k</sub>中节点编号、节点对应的权值，节点之间的边以及边权值输入到最小割划分算法程序中，设定划分集合的数量为i；步骤(3.1.2)，将边权值作为划分的代价输入到最小割划分算法的程序中，运行程序，得到i个集合，记录每个集合中节点的编号以及模块的编号；步骤(3.2)，将划分集合的数量i从2到n<sub>k</sub>变化，记录下每个i下的划分方案以及集合间的通信总量，步骤(3.3)，选择通信总量最小的i，并将其对应的划分方案作为电压岛k的最终划分结果，步骤(3.4)，根据步骤(3.3)的划分结果，为每个划分后的集合分配一个转换器，集合中的模块共享同一个转换器；步骤(4)，从步骤(3)得到模块对应的转换器，将转换器看作是一种特殊的模块，与原有模块一起进行两阶段的布图规划，步骤如下：步骤(4.1)设定布图规划的目标代价函数，表示为：Cost＝α·Area+β·VIArea+γ·wirelength+λ·ratio 公式(9)Area表示布图的面积；VIArea表示所有电压岛边框面积总和；wirelength表示芯片互连的总线长，ratio表示布图结果的长宽比；参数a,β,γ和λ用于权衡各个因素之间的权值，且a+β+γ+λ＝1，步骤(4.2)，选取合适的布图表示方法CBL，基于模拟退火算法，进行两阶段的布图规划，步骤如下：步骤(4.2.1)，布图表示方法是指布图规划阶段的数据结构，选定布图表示方法后，将转换器看为一种特殊的模块，加入到布图表示方法中的模块列表中；步骤(4.2.2)，在模拟退火过程中，将扰动部分分为混合扰动和特殊扰动两个阶段：步骤(4.2.2.1)，进行混合扰动，即特殊模块与原有模块统一按照设定的温度范围进行扰动，需要满足以下所有条件：退火温度大于设定的阈值T_threthold，新方案拒绝率低于设定的阈值reject_ratio并且空白区面积比大于设定的阈值ds_ratio；其中，T_threthold，reject_ratio和ds_ratio都是用户定义的阈值；步骤(4.2.2.2)，一旦上述条件之一没有满足，则进行特殊扰动，即单独对特殊模块进行扰动；步骤(4.2.3)，使用步骤(4.2.1)中的布图表示方法，根据步骤(4.2.2)的扰动方法，运行模块退火算法，得到布图结果；步骤(5)，在布图规划结束后，通过最小代价最大流算法实现网络接口的分配，步骤如下：步骤(5.1)，将步骤(4.2.3)得到的布图结果中的所有空白区划分为大小相同的网格，网格的尺寸与网络接口的尺寸相同；步骤(5.2)，按照如下方法建立最小代价最大流模型：在网络图加入一个源节点s和一个汇聚节点t，n个模块节点以及m个所有可达的空白区网格节点；边有三种，分别是：源节点s到每个模块节点网络接口的边，容量设为1，边权设为0；每个网格节点g<sub>j</sub>与t的边，容量设为1，边权设为0；每个模块网络接口到可达网格g<sub>j</sub>的边，容量设为1，边权设为w<sub>ij</sub>，其中w<sub>ij</sub>表示网格g<sub>j</sub>到网络接口的距离；步骤(5.3)，以s为源点，以t为汇点，求解步骤(5.2)所述的最小代价最大流模型，求得模块对应的网络接口最优的网格位置。 |
