用于片上网络的一种不规则拓扑结构生成方法属于片上互连网络设计领域，其特征在于，含有以下步骤：把描述片上网络应用的通信图中的节点分成很多小集合，每个集合中的所有节点用一个边缘路由器连接后形成新的节点，从而形成新的有向通信图；对新的有向通信图继续进行集合划分，直到不能形成一个新的集合，或者节点数目小于或等于5为止；再根据最终形成的通信图的节点数目确定核心网络路由器数目并生成核心网络；缩减冗余的边缘路由器简化网络。本发明具有再满足具体应用的通信要求下，面积小、通信功耗低的优点。
1.用于片上网络的一种不规则拓扑结构生成方法，其特征在于，所述不规则拓扑结构是在计算机上先后按以下步骤生成的：步骤(1).把描述具体应用的有向通信图输入计算机，其中：节点表示单芯片中所集成的各个IP核，带权重的边表示各IP核之间的业务量，同时设置一个路由器端口所能承受的最大业务量并清空集合缓存库，所述集合是指满足以下条件的有向通信图的节点组合：该集合内部各个节点向集合外其他各个节点传输的业务量的总和不会超过一个路由器端口所能承受的最大业务量，该集合外部各个节点向集合内部每个节点传输的业务量的总和不会超过一个路由器端口所能承受的最大业务量，每个集合里的节点数目至多不超过4个；各个路由器的端口至多为5个，其中路由器包括核心网络路由器和边缘路由器，每个节点最多连接到一个路由器的端口，并且初始化可能构成集合的节点组合数目N，其中n为所输入的有向通信图的节点数目，且令i＝1；
步骤(2).判断第i个可能构成集合的节点组合Pi是否满足成为一个集合的条件：若：满足成为一个集合的条件，则转步骤(3)，
步骤(3).判断集合缓存库里是否存在一个或多个集合D，使得 或若：不存在，则转到步骤(4)，
若：存在某些集合D，使得 则删除这些集合D后转步骤(4)，若：存在某些集合D，使得 则转到步骤(5)；
步骤(4).判断Pi是否与集合缓存库中的某些集合D存在交集：若：不存在交集，则转到步骤(5)，
若：存在交集，则对交集部分进行重新分配，使得这些重新分配后的集合仍然满足集合的条件且它们的外界通信量总和最小，然后把重新分配后得到的新集合存入集合缓存库中去替换重新分配前的集合，转步骤(5)；
步骤(6).判断集合缓存库中的集合数目是否大于5：
若：集合数目大于5，则把集合缓存库中的每个集合中的所有节点用一个边缘路由器连接成一个新的大节点，形成新的有向通信图，清空集合缓存库，再根据新的有向通信图的节点数目更新N值，令i＝1，返回步骤(2)，若：集合数目不大于5，则集合划分结束，把集合缓存库中的每个集合的所有节点用一个边缘路由器连接成一个新的大节点，形成最终的有向通信图，转步骤(7)，若：没有集合，则集合划分结算并转步骤(7)；
步骤(7).根据最终通信图的节点数Q，确定核心网络路由器数目，生成核心网络：若：Q≤5，则核心网络路由器数目为1，然后把Q个节点直接连接到一个核心网络路由器上，并结束该步骤，若：Q＞5，则核心网络路由器数目等于Q，然后把Q个核心网络路由器连成一个环，再把Q个节点分别连到Q个核心网络路由器上，接着分配路由路径，并在保证每个核心网络路由器的端口数不超过5的条件下通过添加核心网络路由器端口和链路来满足通信要求。
2.根据权利要求1所述的用于片上网络的一种不规则拓扑结构生成方法，其特征在于，在所述步骤(7)之后，增加一个步骤(8)：步骤(8).删除冗余的边缘路由器，简化网络：
其中，p为删除之前某边缘路由器的本地端口数，k为删除之前某边缘路由器的网络接口所连接的路由器F的端口数，则，删除该边缘路由器，并把与该边缘路由器本地端口相连的节点直接连接到路由器F上，使其端口数为k+p-1。
3.根据权利要求1所述的用于片上网络的一种不规则拓扑结构生成方法，其特征在于，在步骤(4)中，若多种分配方式均能使这些集合的外界通信量的总和达到最小，则选择能使这些集合的外界通信量大小最接近的分配方式。
用于片上网络的一种不规则拓扑结构生成方法
技术领域
[0001] 本发明属于集成电路设计、尤其涉及片上互连网络设计领域。
背景技术
[0002] 集成电路一直按照摩尔定律推进，单芯片所集成的IP(Intellectual Property)核数目越来越多，传统的基于总线的片上互连结构已经在带宽、功耗、可靠性、扩展性等方面表现出越来越多的局限性，片上通信已经取代计算成为集成电路设计的瓶颈。片上网络(Network-on-Chip，NoC)作为集成电路设计领域的一项关键技术，用于解决芯片规模增大所带来的片上互连问题。片上网络主要由路由器、网络接口和物理链路构成。
[0003] 拓扑结构是片上网络研究的一个热点问题，该方面的研究可以分成规则拓扑结构的研究和非规则拓扑结构的研究。规则型结构具有重用性；不规则型结构是针对具体的应用设计的结构，虽然能够提供更好的通信性能，但是不具有可重用性。在拓扑结构研究中，具体应用被抽象为一个有向通信图，IP核被抽象为有向通信图的节点，而IP核之间的业务量被抽象为带权重的有向通信图的边。目前，在不规则拓扑结构的研究中仍没有很好解决的一个问题就是设计自动化问题，即如何根据具体的有向通信图生成最优或较优的非规则拓扑。
发明内容
[0004] 本发明的目的是为片上网络提供一种不规则拓扑结构生成方法，该方法能根据具体的应用生成较优的不规则拓扑结构。
[0005] 该方法的基本思想是将描述具体应用的有向通信图的节点分成很多小集合。所谓集合，就是满足以下条件的有向通信图的节点的组合：1)集合内部各个节点向集合外其他各个节点传输的业务量的总和不会超过一个路由器端口所能承受的最大业务量，该集合外部各个节点向集合内部每个节点传输的业务量的总和不会超过一个路由器端口所能承受的最大业务量，由于一个节点最多连接到一个路由器端口，因此路由器端口所能承受的最大业务量至少应大于任意一个节点的向其他所有节点传输的业务量的总和，也至少应该大于所有其它节点向某节点传输的业务量的总和；2)考虑到路由器设计的复杂度，各路由器的端口数不能超过5，因此一个集合里的节点数目不能超过4。属于同一个集合的所有节点被连接到同一个边缘路由器上。该方法可以分为三个步骤：1)把描述片上网络应用的通信图中的节点分成很多小集合，每个集合中的所有节点用一个边缘路由器连接后形成新的节点，从而形成新的有向通信图；对新的有向通信图继续进行集合划分，直到不能形成一个新的集合，或者节点数目小于或等于5为止。2)根据最终形成的通信图的节点数目确定核心网络路由器数目并生成核心网络。3)缩减冗余的边缘路由器简化网络。
[0006] 在描述本发明的具体步骤前，我们先定义五个概念：1)构成集合A的所有节点都称为集合A的元素。2)如果两个集合存在共同的元素，则称两个集合存在交集。3)如果集合B中的所有元素属于集合A且A中存在元素不属于B，则称集合A包含集合B，表示为否则称集合A不包含集合B，表示为 4)一个集合中的各个节点与集合外的每个节点之间的通信量的总和称为该集合的外界通信量。5)对于边缘路由器，连接有向通信图节点的端口称为本地端口，其它端口称为网络端口，一个边缘路由器可以有多个本地端口但只有一个网络端口。假定某有向通信图的节点数目为n，则所有可能构成集合的节点组合的数目为
[0007]
[0008] 本发明的特征在于：所述方法是在计算机上先后按以下步骤依次实现的：
[0009] 步骤(1).将描述应用的通信图输入计算机(包括通信图的节点数和任意节点到任意其它节点的业务量)，设置路由器端口所能承受的最大业务量，清空集合缓存库，初始化N并令i＝1；
[0010] 步骤(2).判断第i个可能构成集合的节点组合Pi是否满足成为一个集合的条件；如果满足成为一个集合的条件，则转到步骤(3)；如果不满足成为一个集合的条件，则转到步骤(5)；
[0011] 步骤(3).判断集合缓存库里是否存在一个或多个集合D，使得 或 如果不存在，则转到步骤(4)；如果存在某些集合D使得 则删除这些集合D后转到步骤
(4)；如果存在某些集合D使得 则转到步骤(5)；
[0012] 步骤(4).判断Pi是否与集合缓存库中的某些集合存在交集；如果不存在交集，则转到步骤(5)；如果存在交集，则对存在交集的集合的交集部分进行重新分配，使得这些集合仍然是集合且它们的外界通信量的总和最小；如果多种分配方式均能使这些集合的外界通信量的总和达到最小，则选择能使这些集合的外界通信量大小最接近的分配方式；最后将分配后得到的新集合存入集合缓存库中替换分配前的集合并转到步骤(5)；
[0013] 步骤(5).i自加1，然后判断i是否等于N+1；如果i不等于N+1，则跳转到步骤(2)；如果i等于N+1，则转到步骤(6)；
[0014] 步骤(6).判断集合缓存库中是否有集合以及集合数目是否大于5；如果有集合且集合数目大于5，则把集合缓存库中的每个集合中的所有节点用一个边缘路由器连接成一个新的大节点，形成新的通信图，清空集合缓存库，根据新的通信图更新N，令i＝1并跳转到步骤(2)；如果有集合但集合数目不大于5，则集合划分结束，把集合缓存库中的每个集合中的所有节点用一个边缘路由器连接成一个新的大节点，形成新的通信图并跳转到步骤(7)；如果没有集合，则集合划分结束并转到步骤(7)；
[0015] 步骤(7).根据最终通信图的节点数Q，确定核心网络路由器数目，生成核心网络：若：Q≤5，则核心网络路由器数目为1，然后把Q个节点直接连接到一个核心网络路由器上，由上面的定义可知，每个节点输入和输出的总业务量都小于一个路由器端口所能承受的业务量，因此所生成的核心网络满足通信要求，于是结束该步骤；若：Q＞5，则核心网络路由器数目等于Q，然后把Q个核心网络路由器连成一个环，再把Q个节点分别连到Q个核心网络路由器上，接着分配路由路径，并在保证每个核心网络路由器的端口数不超过5的条件下通过添加核心网络路由器端口和链路来满足通信要求。
[0016] 步骤(8).删除冗余的边缘路由器，简化网络；假定p为删除之前某边缘路由器E的本地端口数，k为删除之前边缘路由器E的网络接口所连接的路由器F的端口数，如果k+p≤6，则删除边缘路由器E，并把与边缘路由器E本地端口相连的节点直接连接到路由器F上，使其端口数为k+p-1，刚好满足不超过5的条件。由上述方法简化后的网络，仍然满足通信要求，解释如下：在路由器F中，对于与被删除的边缘路由器E本地端口相连的节点相连的端口，由节点的定义可知经过这些路由器端口的业务量不会超过一个路由器端口所能承受的业务量；对于其它端口，由于在删除边缘路由器E前后，经过这些端口的业务量不变，因此这些端口的业务量仍然不会超过一个路由器端口所能承受的业务量。
[0017] 该方法有如下优点：1)满足应用的通信性能要求；2)多个IP核接在同一个路由器，能很好节省路由器的数目，从而减小了实现面积；3)多个IP核接在同一个路由器，有效缩短了通信路径长度，从而减小通信功耗。例如，对于MPEG 4解码器，该方法生成的片上网络拓扑结构只需要4个路由器，路由器的总端口数目为18，很好节省了片上网络的实现面积。
附图说明
[0018] 图1.该不规则拓扑结构生成方法的软件流程框图
[0019] 图2.MPEG 4解码器通信图。
[0020] 图3.集合划分后形成的新的通信图。
[0021] 图4.生成的初步拓扑结构。
[0022] 图5.生成的最终拓扑结构。
具体实施方式
[0023] 在描述具体实施方式以前，我们先定义五个概念：1)构成集合A的所有节点都称为集合A的元素。2)如果两个集合存在共同的元素，则称两个集合存在交集。3)如果集合B中的所有元素属于集合A且A中存在元素不属于B，则称集合A包含集合B，表示为否则称集合A不包含集合B，表示为 4)一个集合中的各个节点与集合外的每个节点
之间的通信量的总和称为该集合的外界通信量。5)对于边缘路由器，连接有向通信图节点的端口称为本地端口，其它端口称为网络端口，一个边缘路由器可以有多个本地端口但只有一个网络端口。假定某有向通信图的节点数目为n，则所有可能构成集合的节点组合的数目为
[0024]
[0025] 该方法在计算机上运行，实现该方法的软件流程框图如图1所示。描述如下：
[0026] 步骤(1).将描述应用的通信图输入计算机(包括通信图的节点数和任意节点到任意其它节点的业务量)，设置路由器端口所能承受的最大业务量，清空集合缓存库，初始化N并令i＝1；
[0027] 步骤(2).判断第i个可能构成集合的节点组合Pi是否满足成为一个集合的条件；如果满足成为一个集合的条件，则转到步骤(3)；如果不满足成为一个集合的条件，则转到步骤(5)；
[0028] 步骤(3).判断集合缓存库里是否存在一个或多个集合D，使得 或 如果不存在，则转到步骤(4)；如果存在某些集合D使得 则删除这些集合D后转到步骤
(4)；
[0029] 如果存在某些集合D使得 则转到步骤(5)；
[0030] 步骤(4).判断Pi是否与集合缓存库中的某些集合存在交集；如果不存在交集，则转到步骤(5)；如果存在交集，则对存在交集的集合的交集部分进行重新分配，使得这些集合仍然是集合且它们的外界通信量的总和最小；如果多种分配方式均能使这些集合的外界通信量的总和达到最小，则选择能使这些集合的外界通信量大小最接近的分配方式；最后将分配后得到的新集合存入集合缓存库中替换分配前的集合并转到步骤(5)；
[0031] 步骤(5).i自加1，然后判断i是否等于N+1；如果i不等于N+1，则跳转到步骤(2)；如果i等于N+1，则转到步骤(6)；
[0032] 步骤(6).判断集合缓存库中是否有集合以及集合数目是否大于5；如果有集合且集合数目大于5，则把集合缓存库中的每个集合中的所有节点用一个边缘路由器连接成一个新的大节点，形成新的通信图，清空集合缓存库，根据新的通信图更新N，令i＝1并跳转到步骤(2)；如果有集合但集合数目不大于5，则集合划分结束，把集合缓存库中的每个集合中的所有节点用一个边缘路由器连接成一个新的大节点，形成新的通信图并跳转到步骤(7)；如果没有集合，则集合划分结束并转到步骤(7)；
[0033] 步骤(7).根据最终通信图的节点数Q，确定核心网络路由器数目，生成核心网络：若：Q≤5，则核心网络路由器数目为1，然后把Q个节点直接连接到一个核心网络路由器上，由上面的定义可知，每个节点输入和输出的总业务量都小于一个路由器端口所能承受的业务量，因此所生成的核心网络满足通信要求，于是结束该步骤；若：Q＞5，则核心网络路由器数目等于Q，然后把Q个核心网络路由器连成一个环，再把Q个节点分别连到Q个核心网络路由器上，接着分配路由路径，并在保证每个核心网络路由器的端口数不超过5的条件下通过添加核心网络路由器端口和链路来满足通信要求。
[0034] 步骤(8).删除冗余的边缘路由器，简化网络；假定p为删除之前某边缘路由器E的本地端口数，k为删除之前边缘路由器E的网络接口所连接的路由器F的端口数，如果k+p≤6，则删除边缘路由器E，并把与边缘路由器E本地端口相连的节点直接连接到路由器F上，使其端口数为k+p-1，刚好满足不超过5的条件。由上述方法简化后的网络，仍然满足通信要求，解释如下：在路由器F中，对于与被删除的边缘路由器E本地端口相连的节点相连的端口，由节点的定义可知经过这些路由器端口的业务量不会超过一个路由器端口所能承受的业务量；对于其它端口，由于在删除边缘路由器E前后，经过这些端口的业务量不变，因此这些端口的业务量仍然不会超过一个路由器端口所能承受的业务量。
[0035] 下面给出一个MPEG 4解码器的片上网络拓扑结构生成例子。MPEG 4解码器的通信图如图2所示，假定路由器所有端口的最大允许通信量为1793(刚好等于“meml”节点的向其他所有节点传输的业务量的总和)。其拓扑结构生成过程描述如下：首先将MPEG 4解码器的通信图输入计算机，然后根据上述步骤(1)到步骤(5)进行集合划分后得到四个集合，分别是：{“meml”、“upsp”}，{“cpu”、“mem2”、“rast”}，{“vu”、“dsp”、“au”}和{“bab”、“mem3”、“risc”、“idct”}；由于集合数目小于5，则集合划分结束，把四个集合分布用四个边缘路由器连接成四个新的大节点，形成的最终通信图如图3所示。由于最终通信图的顶点数目Q为4，则核心网络路由器数目为1，将最终通信图的四个节点用一个核心网络路由器进行连接，得到初步拓扑结构(如图4所示)；接着，删除冗余的边缘路由器，得到最终拓扑结构(如图5所示)。对于MPEG 4解码器，该方法生成的片上网络拓扑结构只需要4个路由器，路由器的总端口数目为18，很好节省了片上网络的实现面积。
