用于片上网络的一种不规则拓扑结构生成方法

摘要

用于片上网络的一种不规则拓扑结构生成方法属于片上互连网络设计领域，其特征在于，含有以下步骤：把描述片上网络应用的通信图中的节点分成很多小集合，每个集合中的所有节点用一个边缘路由器连接后形成新的节点，从而形成新的有向通信图；对新的有向通信图继续进行集合划分，直到不能形成一个新的集合，或者节点数目小于或等于5为止；再根据最终形成的通信图的节点数目确定核心网络路由器数目并生成核心网络；缩减冗余的边缘路由器简化网络。本发明具有再满足具体应用的通信要求下，面积小、通信功耗低的优点。

主权项

1.用于片上网络的一种不规则拓扑结构生成方法，其特征在于，所述不规则拓扑结构是在计算机上先后按以下步骤生成的：步骤(1).把描述具体应用的有向通信图输入计算机，其中：节点表示单芯片中所集成的各个IP核，带权重的边表示各IP核之间的业务量，同时设置一个路由器端口所能承受的最大业务量并清空集合缓存库，所述集合是指满足以下条件的有向通信图的节点组合：该集合内部各个节点向集合外其他各个节点传输的业务量的总和不会超过一个路由器端口所能承受的最大业务量，该集合外部各个节点向集合内部每个节点传输的业务量的总和不会超过一个路由器端口所能承受的最大业务量，每个集合里的节点数目至多不超过4个；各个路由器的端口至多为5个，其中路由器包括核心网络路由器和边缘路由器，每个节点最多连接到一个路由器的端口，并且初始化可能构成集合的节点组合数目N，其中n为所输入的有向通信图的节点数目，且令i＝1；步骤(2).判断第i个可能构成集合的节点组合P_i是否满足成为一个集合的条件：若：满足成为一个集合的条件，则转步骤(3)，若：未满足成为一个集合的条件，则转步骤(5)；步骤(3).判断集合缓存库里是否存在一个或多个集合D，使得或若：不存在，则转到步骤(4)，若：存在某些集合D，使得则删除这些集合D后转步骤(4)，若：存在某些集合D，使得则转到步骤(5)；步骤(4).判断P_i是否与集合缓存库中的某些集合D存在交集：若：不存在交集，则转到步骤(5)，若：存在交集，则对交集部分进行重新分配，使得这些重新分配后的集合仍然满足集合的条件且它们的外界通信量总和最小，然后把重新分配后得到的新集合存入集合缓存库中去替换重新分配前的集合，转步骤(5)；步骤(5).使i+1，判断是否等于N+1；若：不等于N+1，则返回步骤(2)，若：等于N+1，则转步骤(6)；步骤(6).判断集合缓存库中的集合数目是否大于5：若：集合数目大于5，则把集合缓存库中的每个集合中的所有节点用一个边缘路由器连接成一个新的大节点，形成新的有向通信图，清空集合缓存库，再根据新的有向通信图的节点数目更新N值，令i＝1，返回步骤(2)，若：集合数目不大于5，则集合划分结束，把集合缓存库中的每个集合的所有节点用一个边缘路由器连接成一个新的大节点，形成最终的有向通信图，转步骤(7)，若：没有集合，则集合划分结算并转步骤(7)；步骤(7).根据最终通信图的节点数Q，确定核心网络路由器数目，生成核心网络：若：Q≤5，则核心网络路由器数目为1，然后把Q个节点直接连接到一个核心网络路由器上，并结束该步骤，若：Q＞5，则核心网络路由器数目等于Q，然后把Q个核心网络路由器连成一个环，再把Q个节点分别连到Q个核心网络路由器上，接着分配路由路径，并在保证每个核心网络路由器的端口数不超过5的条件下通过添加核心网络路由器端口和链路来满足通信要求。