双层二维网格结构间的Wromhole路由算法

二维网格结构由于其较好的可扩展性而被越来越广泛地应用，因此对于二维网格结构多处理机间的数据通信，寻找一个好的路由算法也越来越重要。以Intel公司的Option Red机器为背景，分析了双层二维网格结构多处理机间的通信机制，并且针对该实际结构，根据单层二维网格结构中以Wormhole原理为基础的Unicast自适应路由算法，提出了适用于双层二维网格结构的无死锁的Wormhole路由算法。根据该算法得出的数据传输路径是无死锁的最短传输路径。     

基于Wormhole路由的二维Mesh上的并行k-选择

由于二维网孔机器的结构简单、规整,易于ＶＬＳＩ实现,使得它不仅成为许多理论研究的基础模型,而且还是许多并行机所采用的互连结构．Ｗｏｒｍ ｈｏｌｅ 路由技术的采用改进了二维网孔机器的通信能力．该文在带有Ｗｏｒｍ ｈｏｌｅ 路由技术的ｎ×ｎ 二维网孔机器上提出了一个时间复杂度为Ｏ（ｌｏｇ２ｎｌｏｇｌｏｇｎ）的并行ｋ－选择算法,改进了该问题在Ｓｔｏｒｅ－ａｎｄ－Ｆｏｒｗ ａｒｄ 路由技术下的时间复杂度下界Ｏ（ｎ）．据已掌握的资料,该算法为最早的、非总线连接的二维网孔机器上的、时间复杂度为对数的多项式级的ｋ－选择算法．     

实现图形打印的二维网格存储结构

介绍为打印一帧反映一昼夜（２４小时）供回水温随时间变化的曲（折）线而采用一种二维网格式数据存储结构，运用该结构较好地解决了输出曲线图形，纵坐标（温度）横坐标（时间）三者间的匹配关系，文中还给出了使用这种存储结构时其寻址公式的推导方法并简要介绍了图形生成的基本过程，该方法已在实际软件设计中得到应用。     

基于二维协调空间的网格工作流调度算法研究

传统的网格工作流模型中分布式工作流管理器之间没有合作,因此可能发生源调度冲突问题,另外,在现有的工作流调度算法中,参与工作流调度的工作流管理器依托于集中或半集中的层次式的资源信息服务体系,导致系统的扩展性差.为了解决这些问题,在文中,提出了一个分布式的协同工作流调度算法.该算法基于二维协调空间来管理网格中的工作流管理器.二维协调空间负责资源发现和协调调度等功能.该算法不仅可以避免性能瓶颈,而且可以增强系统的可扩展性和自主性.     

XML路由算法分类研究

目前,由于网络上存在海量的XML信息,针对XML格式数据的过滤及信息的选择性分发成为当前网络通信研究的重点。如何利用大量XPath查询表达式来构造具有高效性和扩展性的XML过滤器,以匹配持续到来的XML文件流,是XML路由算法研究的核心。本文首先介绍XML路由模型,然后对XML路由算法进行分类比较,在此基础上对典型XML路由算法进行归纳总结,最后展望XML路由算法的应用前景。     

二维自适应有限元网格生成

自适应有限元网格生成是基于误差估计，自动进行有限元网格优化的一种策略。本文提出了一种基于单元误差估计的二维自适应有限元网格生成算法，并讨论了其实现过程。     

一种基于双层进化结构的网格任务调度算法

在网格计算中,任务调度是一个重要的组成部分,并被证明为NP完全问题,以启发式方法求解较为适合。针对网格环境异构、分布等特点,本文运用遗传算法原理,结合高度分层排序,提出了一种基于双层进化结构的网格任务调度算法。模拟实验结果表明,在网格异构环境下,本算法优于其它几种算法。     

一种公平接入的QoS路由算法

主要讨论了在网络负荷较重情况下带宽需求不同的连接公平接入问题,给出了ＱｏＳ路由的最小代价函数并提出一种公平接入的ＱｏＳ路由算法,同时给出了验证算法效益的网络效益函数,最后是实验仿真结果。     

HPMR系统KV路由算法设计

提出一种针对HPMR系统的KV路由算法。HPMR系统是MapReduce模型的一个实现,改进了MapReduce模型以适应高性能计算的需求。HPMR的KV路由算法生成KV路由表,所有数据的收发动作将依据该路由表进行。KV路由算法产生的KV路由表直接决定HPMR系统在通信阶段的时间开销。实验结果表明,该KV路由算法产生的KV路由表可以提高HPMR系统的通信性能。     

基于LSOT的高速IP路由查找算法

由于因特网速度不断提高、网络流量不断增加、路由表规模不断扩大，IP路由查找已经成为制约路由器性能的重要原因，因而受到广泛重视。目前人们已经提出几种算法用于解决IP路由查找问题，但均不能完全满足核心路由器的要求。该文提出一种基于LSOT的IP路由查找方法，它使用可变大小段表和偏移量表，能适应SRAM和FPGA芯片内存储器容量的变化，具有查找速度高、更新时间快、存储代价低、易于实现等特点，使用FPGA设计能满足10Gbps端口速率核心路由器环境的要求，使用ASIC设计能满足40Gbps端口速率核心路由器环境的要求。     

改进型量子蚁群算法求解QoS单播路由

针对遗传以及蚁群算法在求解QoS单播路由问题时收敛速度慢和易于陷入局部最优的问题。采用量子蚁群算法求解QoS单播路由,采用量子旋转门实现蚂蚁的移动,用量子非门来实现蚂蚁位置的变异,同时为了确保算法不陷于局部最优,对量子蚁群算法做了改进,并进行了对比实验。实验表明该算法不但克服了遗传以及蚁群算法的易限于局部最优解的缺陷,在收敛速度上也优于相关算法,能较好地解决QoS单播路由问题。     

基于GIS技术的双层PCB布线的空间剖分算法

双层印制电路板(PCB)通常空间结构及布线线形复杂、约束规则众多,而常用PCB空间结构简单、布线线形单一,不能有效利用PCB的空间关系及拓扑信息引导布线规划。为弥补以前工作的不足,提出一种基于GIS(geographic information system)技术的空间剖分算法,首先利用空间距离与几何要素拓扑关系进行分组预处理,然后引入矢栅一体化模型构建复杂空间及属性约束下的网络模型,基于该网络模型提取区域基准线并利用空间缓冲区技术得到空间剖分结果,从而引导布线规划。实验结果表明,该算法能够在满足所有设计规则的情况下实现100%的布线连通率,同时有效利用布线空间资源;提出的算法布线线形接近人工布线,对于实现复杂场景与多约束下的双层PCB自动化布线具有实际意义。     

基于生长竞争蚁群算法的QoS路由算法*

为解决多约束QoS单播路由问题,提出一种基于改进蚁群算法的QoS单播路多目标算法。该算法引入生长竞争机制,使算法尽可能向Pareto最优靠近。实验结果表明,该算法是可行和有效的,能够在资源预留的基础上较好地满足用户对带宽和时延的要求。     

PRDT（2，1）架构的NoC系统容错路由算法

链路和节点的故障会导致网络中许多节点无法相互通讯,因此容错性是NoC系统设计中的一个重要问题。基于一种新的NoC网络拓扑结构PRDT（2,1）,提出一种PRDT（2,1）容错路由算法以及相应的节点失效算法。节点失效算法通过使较少数量的无故障节点失效来构造矩形故障区域,PRDT（2,1）容错路由算法仅使用了最小数量的虚拟通道并提供足够的自适应性以实现无死锁容错路由。只要故障区域没有断开网络,这一算法能够保证路由的连通性。算法在不同故障率的PRDT（2,1）网络中仿真,结果显示这一算法具有良好的平滑降级使用特性。     

一种基于模糊塔的QoS单播路由选择算法

综合考虑用户服务质量QoS需求和网络提供方收益的单播路由算法．给定用户请求类别和收费原则,通过建立网络提供方收益模型来确定针对每一类请求的概率收益．在此基础上,利用模糊塔,求出两网络节点之间既满足用户服务质量需求又试图最大化网络提供方概率收益的路由。仿真结果表明,算法是可行的和有效的。     

P2P经典路由算法的改进

为改善P2P经典路由算法中存在的某些不足之处,通过对对象定位算法和节点加入、删除算法的改进,改善了路由成功率和减少了网络开销,从而提高了Internt资源的利用率。     

Making-a-stop: A new bufferless routing algorithm for on-chip network

In the deep submicron regime, the power and area consumed by router buffers in network-on-chip (NoC) have become a primary concern. With buffers elimination, bufferless routing is emerging as a promising solution to provide power-and-area efficiency for NoC. In this paper, we present a new bufferless routing algorithm that can be coupled with any topology. The proposed routing algorithm is based on the concept of making-a-stop (MaS), aiming to deadlock and livelock freedom in wormhole-switched NoC. Performance evaluation is carried out by using a flit-level, cycle-accurate network simulator under synthetic traffic scenarios. Simulation results indicate that the proposed routing algorithm yields an improvement over the recent bufferless routing algorithm in average latency, power consumption, and area overhead by up to 10%, 9%, and 80%, respectively.     

蜂窝网络上的路由算法*

主要研究蜂窝网络上的无死锁单播路由算法和一对全的广播路由算法。基于蜂窝网络的砖形画法,利用二维网络维序路由的基本思想和两个虚拟网络实现了无死锁的最短单播路由算法,并证明了算法的无死锁性。然后基于这个单播路由算法和线列上的广播算法,用软件实现了蜂窝网络上一对全的广播路由算法,经过简单比较得出该广播算法比以往的算法在通信效率上有了极大的提高。     

对路由表结构和查找算法的研究

随着网络流量的指数性增长,每秒能够传输10G以上比特的光纤骨干网络大量投入使用,但是大部分骨干路由器无法相应达到每秒转发百万个分组的高速,成为网络瓶颈。分组转发性能由多种因素决定,其中路由查找算法是关键。综述了近年来在路由表数据结构和查找算法的研究方面的最新进展,并对一种较先进的转发表结构进行了重点分析。     

虫洞路由芯片的伸缩缓冲区设计与实现

虫洞路由交换机制由于延迟时间短,对路由芯片缓冲区容量要求小等特点,被广泛应用在机群交换网络的路由芯片中。但阻塞时占用整个传送路径,会使网络吞吐率下降,此外,刹车问题的存在,会限制数据传送速率。该文提出了用伸缩缓冲区技术解决虫洞路由芯片刹车问题的方法,并已在DawningUX8路由芯片中实现,应用结果表明既可以很好地解决刹车问题,也可以提高网络性能。