高维环网上的一种可扩展的全交换算法

全交换在并行计算领域中有着大量而且重要的应用,例如FFT和矩阵运算等.本文提出了一种适合环网结构的全交换算法.算法中采用了新的网络划分技术及通信模式,使高维环网上全交换算法的通信量的主项达到了理论下限,这是已知的其他相关算法未能达到的,且其启动次数与通信量均优于现有的其他同类算法.本文所述的算法并不要求环网每一维上的处理器结点数目是2的方幂或某一个数的平方.最后,该算法简单规范,易于硬件高效实现.     

一种面向数据密集型应用的并行程序执行模型

随着各领域需要处理的数据量越来越大,数据密集型应用也变得越来越被重视.该文提出一种包含数据访存层次和访存冲突等信息的新并行程序执行模型PSRAM(h).针对数据密集型应用以访存为主的特点,PSRAM(h)模型将程序执行时间简化为访存时间,通过分析各程序子段的访存层次和数量来预测串行程序的执行时间,进而通过使用各线程执行时间的最大值来预测并行程序的执行时间.使用PSRAM(h)模型下对最典型的数据密集型应用矩阵向量乘进行分析,在龙芯3A处理器和Intel Xeon E5520处理器两个平台上的测试结果表明,PSRAM(h)模型分析结果与实测结果大部分情况下误差小于20%.由此可见,针对数据密集型应用,PSRAM(h)不但可以给出程序执行时间的下限,还可以有效的预测程序的执行时间.     

Internet自治系统级拓扑发现系统的研究与实现

Internet由多个自治系统相互连接而成，AS间的互联结构体现了Internet的宏观结构。研究AS间的连接关系可以辅助分析网络特性。该文研究了Internet AS级拓扑发现，实现了一个Internet AS级拓扑发现系统。该系统分析BGP路由表得到Internet AS级拓扑并直观显示出来。分析了AS级拓扑的度分布属性，分析结果显示生成的拓扑具有幂律分布特性。     

静态博弈模型下的无线传感器网络MAC地址分配算法

针对传感器网络地址分配过程中为了避免地址冲突而导致通信能耗较大的问题,提出了一种基于静态博弈模型的MAC地址分配算法MAAS.该算法将传感器节点看作博弈模型中的决策者,通过使模型达到纳什平衡来解决节点的MAC地址分配问题.在进行地址分配时,MAAS利用博弈模型中每个决策者可根据其邻居节点信息独立进行决策的性质,避免了节点在地址分配过程中发送大量的交互信息.实验结果表明,MAAS在保证较低冲突率的同时降低了地址分配过程中的通信消耗.     

一种规则集快速压缩算法

实际应用中的规则集表现出很强的聚集特性,针对这一特性提出一种规则集快速压缩算法.快速压缩算法是一个由粗到细的先分类再合并压缩的过程,首先通过使用Hash函数将提取的规则信息散列并以散列值作为查找关键字构建二叉查找树实现粗略分类,然后在树结点对应的Hash函数冲突列表中逐条比较完成精确分类,最后合并冲突列表中的规则实现压缩.实验结果表明,与逐条规则逐个域比较的简单压缩方法相比,快速压缩算法在保持较高压缩率的前提下,能够将压缩时间平均减少90%以上.     

一种严格非阻塞Clos型波分复用光置换网络

波分复用光交换网络设计中的一个重要问题是如何在提供完全连接能力的同时保持最低的硬件代价.这里采用波长交换原理,提出一种能同时完成空间交换和波长转换的交叉开关,并将其作为基本模块构造出严格非阻塞Clos型波分复用光置换网络.与现有网络相比,该网络不需要额外的波长转换级,减小了信号衰减;降低了整体硬件代价,在空间交换代价和波长转换代价之间取得了很好的平衡,并具有较好的扩展性.     

基于Omega网的新型自路由多播网络

介绍了一种新型的基于Omega网构造的多播网络模型FiO,由1个Omega-1网和4个Omega网串连，并适当改变中间连接方式构成，其硬件代价为O(5/2N log N). 同时，本文在FiO网络模型上提出了一种对换设置找中间状态的自路由方法实现多源点多播，算法初始设置时间为O(N)，通信时间达到(logN). 由于Omega网本身的构造简单, 所以该网络有利于硬件集成，同时在处理多播能力上较以前的网络模型也有显著提高，所以该网络有较好的实用价值和发展潜力.     

一种递归构造的合成BANYAN网络

该文提出了一种新的多路径多级互连网络——递归构造的合成BANYAN网络,网络由若干级3×3的开关组成.通过增加中间链路,解决了在已有的由Seo和Feng提出的合成BANYAN网上不能实现所有置换的问题.该网络无需复杂的数值计算,通过二进制操作就可以很容易的产生路由标志,得到更多的路径,从而大大提高了路由成功率和容错能力.该文中还给出了路由算法,并提出通过设置标识开关性能的标志位,使在路由时选取正确的路由标志,提前避开不起作用的开关,达到"预容错"的目的.     

一种基于局部能量消耗最优的分簇协议

在无线传感器网络中,先确定簇头分布方式、后考虑网络能量消耗的分簇方式降低了网络能量消耗的有效性.针对减小能耗问题,提出了一种基于局部能量消耗最优的非均匀分簇协议.在该协议中,各区域根据与基站的距离安排簇头分布,折中簇头能量消耗,使得簇内所有节点的平均能量消耗最小.仿真结果表明,相比现有的分簇协议,协议生成的簇头数稳定集中并且将网络生命期延长了20.7%到43.9%.这说明按照最小化簇内节点平均能量消耗的原则安排簇头分布,可以有效减少和均衡网络中节点的能量消耗.     

基于前缀的片上网络容错源路由算法

为克服片上网络链路永久性错误带来的路由问题,提出一种基于前缀的片上网络容错源路由算法PFTSR。该算法适用于二维mesh片上网络,采用预测路径并根据反馈信息调整路径的方法进行路由探测。在仿真平台NIRGAM上进行仿真,实验结果表明,与传统片上网络容错源路由算法SRN相比,PFTSR极大降低了片上系统的功耗,并且在大多数情况下能减少探测到第一条路径的时间。