用于片上网络的一种基于学习的自适应容错方法

专利名称：用于片上网络的一种基于学习的自适应容错方法
技术领域：
本发明属于集成电路设计、尤其涉及片上互连网络设计领域。
背景技术：
集成电路一直按照摩尔定律推进，单芯片所集成的智能IP (Intellectual Property) 块数目越来越多，传统的基于总线的片上互连结构已经在带宽、功耗、可靠性、扩展性等方 面表现出越来越多的局限性，片上通信已经取代计算成为集成电路设计的瓶颈。片上网络 (Network-on-Chip， NoC)作为集成电路设计领域的一项关键技术，用于解决芯片规模增大 所带来的片上互连问题。随着工艺的发展，芯片的电源电压和晶体管的阈值越来越低，串扰越来越严重，因此器 件和互连线也变得越来越不可靠，在电路级保证数据传输的可靠信已经越来越难，而且代价 也越来越大。因此，研究者们开始关注通过引入检错和纠错编码等容错方法保证数据传输的 可靠性。考虑到片上网络的资源有限性， 一般采用较简单的容错方法，常见的有1)端到端 的错误重传容错方法；2)端到端的纠错与错误重传相结合的混合容错方法。然而，上述两种 方法都只是在某些情况下性能较优错误重传容错方法在错误概率较低的情况下性能较优； 混合容错方法在多数错误图样能通过纠错恢复的情况下性能较优。而且，对于一个成型的片 上网络，往往不同路径有不同的错误情况，如果采用单一的容错方案，都将导致某些路径的 性能恶化。因此，必须研究更优的容错方法。发明内容本发明的目的是为片上网络提供一种更优的基于学习的自适应容错方法。 本发明的特征在于所述方法是在网络接口上先后按以下步骤依次实现的 步骤(1).初始化步骤(1.1).建立片上网络，确定采用的纠错编码和检错编码，从而确定混合容错方 法中的编码效率&和错误重传容错方法中的编码效率&;步骤(1.2).所述片上网络的所有网络接口中的容错方法选择器向片上网络的每条路 径重复发送设定的已知序列；步骤(1.3).所述片上网络的所有网络接口中的容错方法选择器计算接收到的每条路 径的序列的总的比特数并和发出的序列进行对比，根据对比结果计算每条路径的错误比特数和上述所选纠错编码不能纠正的错误比特数，从而确定每条路径的信道错误概率p和在有错 条件下所选纠错编码不能纠正的错误概率《，其中p = &， g = &，并保存，K是所述容错『 W方法选择器所接收到的某条路径的总的比特数目，^是该路径的错误比特数目，『2是上述所 选纠错编码不能纠错的该路径的错误比特数目；步骤(1.4).将由步骤(1.3)所确定的每条路径的p和《存在容错方法选择器中；步骤(2).所述网络接口中的发送模块对从智能IP块输入的数据按下述方式处理后送往 所述路由器步骤(2.1).从所述智能IP块输入的数据首先经过打包器将数据打包；然后经过检错 码编码器根据步骤(1. 1)所确定的检错编码在数据包尾部加入检错监督码元后送往容错方法 选择器；歩骤(2.2).容错方法选择器根据上述步骤所确定的p、《、yt,和&，比较p和A^的大小，决定数据包是否经过纠错码编码器；如果^<7^^，容错方法选择器选择错误重 传方法，则在数据包最前面添加容错方法标志位"0"，并直接将数据包送往或门电路；否则，如果;^^^，容错方法选择器选择的是混合容错方法，则在数据包最前面添加容错方法标志位"1"并将数据包送往纠错码编码器，纠错码编码器根据步骤(1.1)所确定的纠错编码在数据包尾部加入纠错监督码元后将数据包送往或门电路；步骤(2.3).所述或门电路将到达的数据相或后送往所述路由器；步骤(3).所述网络接口中的接收模块对从所述路由器输入数据包依次经过以下步骤处 理后送往所述智能IP块步骤(3.1).从所述路由器输入的数据包首先经过分离器将采用不同容错方法的数据 包分离，如果数据包的容错方法标志位为"0"，表示数据包采用的是错误重传方法，则分离 器将该数据包直接送往检错码解码器进行检错；如果数据包的容错方法标志位为"1"，表示 数据包采用的是混合容错方法，则分离器将数据包送往纠错码解码器进行纠错并去掉纠错码 监督码元后送往检错码解码器进行检错；步骤(3.2).所述检错码解码器对到达的数据包进行检错，如果数据包中仍然存在错 误，则把错误标志信号置位为"1",通知目的智能IP块发送重传请求；如果数据包中不存在 错误，则去掉数据包尾部的检错码监督码元并把错误标志信号设置为"0"，然后将数据送往 解包器解包后送往目的智能IP块；仿真表明，与端到端的错误重传方法和混合容错方法相比，基于学习的自适用容错方法 在增加少量的实现面积的情况下很大程度上提高了片上网络的吞吐量、减少传输延迟和通信 功耗。


图1.网络接口示意图。图2.从智能IP块向路由器发送数据的过程。 图3.从路由器向智能IP块传输数据的过程。
具体实施方式
该方法首先对端到端的错误重传方法和混合容错方法进行分析和推导，得出一条容错方 法选择公式，通过该公式，我们可以选择出实现无错传输所需的冗余比特较少的容错方法。 然后，在片上网络建立以后，由容错方法选择器向每条链路发送已知序列，我们称这过程为学习，根据学习结果和前面推导的公式，容错方法选择器为不同路径选择出较优的(实现无 错传输所需的冗余比特较少的)容错方法。下面介绍我们对端到端的错误重传方法和混合容错方法的分析和推导过程。推导之前， 我们先进行如下定义1) 码长为w。2) 编码效率"每个码中的信息比特数为丄，于是力=#4，特别的，假定、和4分别是 错误重传容错方法中的编码效率和每个码字中的信息比特数，/^和A分别是混合容错方法中 的编码效率和每个码字中的信息比特数，那么我们有，4=w.、， A^w人。3) p为信道错误概率，g为有错误的条件下，混合容错方法中不能纠错(必须重传)的条件概率。因此在错误重传方法中，重传概率^等于/>，在混合容错方法中，重传概率/i等于p."7 。4) r为需要传输的总的信息比特数'同时，我们假定1)重传请求在控制通道中传输，与数据传输相独立；2)重传请求的 传输不会出现错误。下面对错误重传方法的冗余比特数进行推导在错误重传方法中，为了使一个码字正确的传到目的地所必须传输的所有的比特数目的 均值。]可以通过下面式子进行计算5那么，要把r个比特正确的传输到目的地所必须传输的所有比特数目的均值fi[7;]能由下 面式子计算得到朴f楊rw r<formula>formula see original document page 6</formula><formula>formula see original document page 6</formula>混合容错方法冗余比特数推导类似的，在混合容错方法中，为了使一个码字正确的传到目的地所必须传输的所有的比特数目的均值]可以通过下面式子进行计算:那么，要把T个比特正确的传输到目的地所必须传输的所有比特数目的均值E[Tn]能由下面式子计算得到那么，要把T个比特正确的传输到目的地所必须传输的冗余比特数的均值E[t;。]为:显然，当<formula>formula see original document page 7</formula>,错误重传方法性能将优于混合容错方法，反之则反。<formula>formula see original document page 7</formula>,也就是说，当<formula>formula see original document page 7</formula>,错误重传方法性能将优于混合容错方法，反之，当<formula>formula see original document page 7</formula>,混合容错方法性能优于错误重传方法。式中，Kd和Kk与选择的检测和纠错编码有关，p由信道特性决定，由信道特性和所选的纠错编码的纠错能力共同决定。支持基于学习的自适应容错方法的网络接口实现框图如图1所示，主要包括发送模块和 接收模块两大模块。发送模块由打包器、容错方法选择器、检错码编码器、纠错码编码器和或门电路组成；接收模块由分离器、纠错码解码器、检错码解码器和解包器组成。 该方法具体工作过程描述如下 步骤(1).初始化步骤(1.1).建立片上网络，确定采用的纠错编码和检错编码，从而确定混合容错方 法中的编码效率、和错误重传容错方法中的编码效率、；步骤(1.2).所述片上网络的所有所述网络接口中的容错方法选择器向片上网络的每 条路径重复发送特定已知序列；步骤(1.3).所述片上网络的所有网络接口中的容错方法选择器计算接收到的每条路 径的序列的总的比特数并和发出的序列进行对比，根据对比结果计算每条路径的错误比特数和上述所选纠错编码不能纠正的错误比特数，从而确定每条路径的信道错误概率p和在有错 条件下所选纠错编码不能纠正的错误概率《，其中p=^， 9 = ^,并保存，,是所述容错『 ^方法选择器所接收到的某条路径的总的比特数目，^是该路径的错误比特数目，^是上述所 选纠错编码不能纠错的该路径的错误比特数目；步骤(1.4).将由步骤(1.3)所确定的每条路径的p和9存在容错方法选择器中；步骤(2).如图2所示，所述网络接口中的发送模块对从智能IP块输入的数据按下述方 式处理后送往所述路由器步骤(2. 1).从所述智能IP块输入的数据首先经过打包器将数据打包；然后经过检错 码编码器根据步骤(1. 1)所确定的检错编码在数据包尾部加入检错监督码元后送往容错方法 选择器；步骤(2.2).容错方法选择器根据上述步骤所确定的p、 9、 ^和&，比较; 和7^^的大小，决定数据包是否经过纠错码编码器；如果^<^=^，容错方法选择器选择错误重 传方法，则在数据包最前面添加容错方法标志位"0"，并直接将数据包送往或门电路；否则，如果;^^^，容错方法选择器选择的是混合容错方法，则在数据包最前面添加容错方法标志位"1"并将数据包送往纠错码编码器，纠错码编码器根据步骤(1.1)所确定的纠错编码在数据包尾部加入纠错监督码元后将数据包送往或门电路；步骤(2.3).所述或门电路将到达的数据相或后送往所述路由器；步骤(3).如图3所示，所述网络接口中的接收模块对从所述路由器输入数据包依次经 过以下步骤处理后送往所述智能IP块步骤(3.1).从所述路由器输入的数据包首先经过分离器将采用不同容错方法的数据 包分离，如果数据包的容错方法标志位为"0"，表示数据包采用的是错误重传方法，则分离器将该数据包直接送往检错码解码器进行检错；如果数据包的容错方法标志位为"1"，表示 数据包采用的是混合容错方法，则分离器将数据包送往纠错码解码器进行纠错并去掉纠错码 监督码元后送往检错码解码器进行检错；步骤(3.2).所述检错码解码器对到达的数据包进行检错，如果数据包中仍然存在错 误，则把错误标志信号置位为"1"，通知目的智能IP块发送重传请求；如果数据包中不存在 错误，则去掉数据包尾部的检错码监督码元并把错误标志信号设置为"0"，后将数据送往解 包器解包后送往目的智能IP块。
权利要求
1.用于片上网络的一种基于学习的自适应容错方法，其特征在于，所述方法是在片上网络的各智能IP块的发送端和接收端依次分别按以下步骤实现的发送端步骤(1).在片上网络的网络接口的发送模块上，设有打包器、检错码编码器、容错方法选择器、纠错码编码器，以及或门电路，其中，打包器、检错码编码器、容错方法选择器依次串接，而容错方法选择器的两输出端一个与或门电路的第一输入端经过纠错码编码器后相连，而另一个与或门电路的第二输入端直接相连，或门电路的输出送往路由器；步骤(2).初始化步骤(2.1).确定采用的纠错编码和检错编码，以及混合容错方法中的编码效率kh和错误重传容错方法中的编码效率kd；步骤(2.2).所述容错方法选择器向片上网络的每条路径重复发送设定的已知序列；步骤(2.3).所述容错方法选择器计算接收到的每条路径的序列的总的比特数并和发出的序列进行对比，根据对比结果计算每条路径的错误比特数和上述所选纠错编码不能纠正的错误比特数，从而确定每条路径的信道错误概率p和在有错条件下所选纠错编码不能纠正的错误概率q，其中
2. 根据权利要求l所述的用于片上网络的一种基于学习的自适应容错方法，其特征在于，在所述错误重传方法中，要把r个比特正确地传输到目的所必须传输的冗余比特数的均值
3. 根据权利要求l所述的用于片上网络的一种基于学习的自适应容错方法，其特征在于，在 所述混合容错方法中，要把r个比特正确地传输到目的所必须传输的冗余比特数的均值L"」hJ V(i-m)
全文摘要
用于片上网络的一种基于学习的自适应容错方法属于片上互连网络领域，其特征在于，在发送和接收端上分别设立发送和接收模块，在发送模块中，根据容错方法选择器向片上网络每条路径发送的已知序列和接收到的序列，计算出每条路径信道错误概率p和在有错时所设纠错编码不能纠正的错误概率q。对于智能IP块输入的数据，先经过检错码编码器编码，再通过比较p和k_d-k_h/k_d-k_h·q的大小来决定选择错误重传方法或混合容错方法，从而决定是否经过纠错码编码器；而在接收端则反之，根据数据包中的容错标志位决定是否经过纠错编码解码器，然后通过检错码解码器对数据包进行检错决定数据包是否需要重传。本发明提高了片上网络的吞吐量，减少了传输延迟和通信功耗。
文档编号H04L1/16GK101267280SQ20081010440
公开日2008年9月17日 申请日期2008年4月18日 优先权日2008年4月18日
发明者曾烈光, 林世俊, 厉 苏, 苏海波, 金德鹏, 雪 陈 申请人:清华大学