NoC中基于路径树的无冲突测试调度方法

在复用片上网络(No C)架构作为测试访问机制对No C内嵌核进行测试时,如果有多个I/O接口并行测试就容易发生资源的冲突.为了解决多区域并行测试的资源冲突问题,提出一种无链路冲突的测试调度方法.首先使用分区算法将网络划分多个区域,然后使用链路分配算法对节点建立路径树来查找可连通路径,最后全局考虑各个区域的连通路径来分配链路使所有区域都连通,从而避免资源冲突、减少测试时间、保证测试可靠性.实验结果表明,相对于基准对象,该方法可减少测试时间14.13%~52.62%,比已有算法的测试时间最多减少了16.42%,是一种较优的无冲突测试调度方法.     

基于图形处理器的并行方体计算

方体(cube)计算是数据仓库和联机分析处理(Online analytical processing,OLAP)领域的核心问题,如何提高方体计算性能获得了学术界和工业界的广泛关注,但目前大部分方体算法都没有考虑最新的处理器架构.近年来,处理器从单一计算核心进化为多个或许多个计算核心,如多核CPU、图形处理器(Graphic Processing Units, GPU)等.为了充分利用现代处理器的多核资源,该文提出了基于GPU的并行方体算法GPU-Cubing,算法采用自底向上、广度优先的划分策略,每次并行完成一个cuboid的计算并输出;在计算cuboid过程中多个分区同步处理,分区内多线程并行.GPU-Cubing算法适合GPU体系结构,并行度高.与BUC算法相比,基于真实数据集的完全方体计算可以获得一个数量级以上的加速比,冰山方体获得至少2倍以上的加速.     

最小共享干扰--负荷平衡QoS路由算法

文中将链路共享、负荷均衡性以非线性路径长度的统一形式纳入QoS寻径决策中,并以"最短路径优先"为准则,提出一种QoS路由算法,该算法能选择合适路径、能调节链路共享、能平衡网络负荷,优化网络整体性能.     

基于直径为2的摩尔图网络的并行矩阵乘算法

提出了一个并行矩阵乘算法IPBPMM(Interconnected Processor-Based Parallel Matrix Multiplication).该算法运行在以五角形、Petersen图和Hoffman-Singleton图等直径为2的摩尔图(满足n=d2+1,n为节点数,d为度)为拓扑结构的由n个独立处理器构成的机群并行计算环境中.与基于二维环绕网孔阵列拓扑结构的Cannon和Fox等并行矩阵乘法算法相比较,IPBPMM算法通信开销较小,加速比更高,同时还具有矩阵分块可随机分布在各个节点中,无需事先按一定规律装入各节点中的特点.同时IPBPMM算法也能很好地扩充到由多个直径为2的摩尔图为拓扑结构组合构成的并行计算环境中,且随着网络的扩大,算法的并行加速比更高.     

一种基于QoS度量的Pareto并行路由寻优方法

动态QoS路由是基于每个流计算的,为了优化动态QoSR请求中状态的时变性和控制滞后性,快速寻找满足多个约束的可行路径,提出一种基于OoS度量的Pareto子集并行路由预计算方法(QPAS).方法实现了并行状态收集和路由计算,求得满足路由请求约束可行路径的Pareto子集并综合选择合适的转发路由,仿真结果验证了QPAS的计算效率和有效性.QPAS可用于解决有限节点网络的复杂QoS路由等网络传输控制中的实际问题.     

一种挖掘多核处理器存储级并行的算法

多核处理器中,各个处理器核之间可以并发地进行外部存储访问,提供不同于单处理器的存储级并行(memory level parallelism)能力.不规则应用中的循环,传统的并行方法难以识别其并行性,不能充分利用多核处理器存储级并行能力和并行计算能力.对基于软件开发多核处理器存储级并行进行了讨论,提出一种前瞻并行多线程算法LLSM(loop level speculative mssultithreading).LLSM对不规则应用中的循环进行并行化,在多核处理器上的测试数据表明:该算法能够有效地挖掘多核处理器的存储级并行能力和计算能力,同时指出多核环境下存储级并行计算公式需要考虑线程同步开销.     

多重循环的软件流水：比较和提高

循环并行化是并行编译的核心问题之一。许多科学计算程序的大部分执行时间花费在循环上，有效开发循环中的并行性将提高整个程序的执行效率。多重循环最为常见，因此并行化多重循环具有重要的理论和现实意义。现代处理器中硬件资源迅速增长，也使得在整个多维循环空间中开发并行性成为必要。目前大多数软件流水算法只对最内层循环，仅有少数的算法对多重循环进行软件流水，本文介绍几种多重循环的软件流水算法，比较它们之间的相似与不同之处，为编译器实现中算法的选择提供了指导。     

基于遗传算法实现并行路径的自适应流量工程

研究实现动态并行路径的集中式流量工程,利用遗传算法提出流量优化算法,基于网络拥塞信息动态精简优化对象,基于网络链路利用率动态确定并行路径的采用,同时给出在并行路径间可行、简洁的流量分配方案简化算法的进化选择。仿真结果验证了提出的算法简化了解空间、降低了复杂度、提高了收敛速度,可同时确保优化性能。     

蚁群算法解决TSP问题的并行化研究与实现

蚁群算法在处理大规模TSP(Traveling Salesman Problem)问题时耗时较长,为了解决这一不足,给出一种基于多核环境下的并行优化算法.采用OpenMp并行优化技术对蚁群算法中最为耗时的循环迭代和循环赋值部分进行改进,减少其运算时间,同时利用粗粒度并行策略和PC机多核的优势将具有一定规模的小蚁群分配到对应的处理器上,使其并行执行,并且在适当时机让各处理器上的蚁群进行相互间的通信.通过实验证明,改进后的并行蚁群算法程序执行时间明显缩短,执行效率显著提高.由此可见,改进后的并行蚁群算法是可行有效的.     

一种快速规避拥塞的路由算法

为了平衡网络负载,优化网络资源使用,路由算法必须具备快速规避拥塞的能力.文章借鉴了最短路径算法和蚂蚁算法,在拥塞出现以后,分别以拥塞链路的相邻两端节点为中心、以一个事先设定的路径优劣评价函数为标准,通过两组寻路蚂蚁,逐渐增大网络搜索范围,各自独立寻找绕开拥塞链路到达对方的最优相向路径.直到上述找到的相向路径中途相遇(节点集中出现相同的节点),则意味着算法成功找到了绕开了拥塞链路新路径,算法结束.经仿真证明,该算法由于充分地利用了拥塞前的QoS路由信息,加上具体寻路过程利用了蚂蚁算法的并发性,明显节省了QoS路由搜索时间,有效地规避了网络拥塞,提高了网络服务能力.     

多QoS约束的层次多播路由算法框架

为了解决网络路由的扩展性问题。大型网络通常被划分成若干个不同的域。拓扑聚集是对这些域的拓扑状态信息进行汇总的过程。在拓扑聚集的基础上，QoS层次多播路由算法用来构造满足QoS要求的域闻多播树。现有的QoS层次多播路由算法在其拓扑聚集和路径计算的过程中都只考虑了存在两个QoS特征值的情况。本文提出了一种具有多QoS约束的层次多播路由算法框架HMRMQ（Hierarchical Multicast Routing with Multiple QoS constraints），此算法框架不仅为基于多QoS特征值的拓扑状态聚集和状态信息表示提供了新的方法，而且提出了一种适应于多QoS约束的层次多播路由新算法。我们提出的状态信息表示法和拓扑聚集算法都具有很好的扩展性，分布式的路由算法也便于某些安全性策略的实施。理论分析和实验结果不仅证明了HMRMQ的正确性和有效性，同时也表明了HMRMQ在网络路由的扩展性、路由成功率、网络代价以及报文负载等方面都具有良好的性能。     

IPv6单播QoS路由实现的障碍和潜能

基于IPv6及其主流的OSPFv3路由协议,分析IPv6实现单播QoS路由可能遇到的障碍,如现有IPv4 QoS路由机制的实用性缺陷、多QoS度量表达困难和洪泛更新开销大。利用IPv6的简化报头、流概念、流量类型和流标签域支持QoS路由的潜能。     

基于网络处理器的路由交换方案

网络处理器是新一代网络设备的核心器件，基于网络处理器的路由器交换机开发是一个热点。由于ASIC和通用CPU各自的局限无法满足日益增长的网络流量和业务的需求，从而出现了网络处理器，网络处理器一般是由通用处理器作为控制CPU，多个转发引擎并行处理分组以隐藏访问I／O设备的延时，并通过协处理器来加速路由查找、CRC计算等功能。通过分析网络处理器的体系结构并依据当前网络处理器发展的实际情况提出了几种基于网络处理器设计的路由交换系统方案，并分析了各种方案的特点及应用场合。     

基于软件的网络处理器的路由高速缓存算法研究

路由器需要以较低的代价灵活、高速地实现路由查找这一基本功能.为网络处理器设计了一种基于软件的路由查找高速缓存算法.网络处理器片上高速存储器中的一部分空间被划分出来,由指令代码来维护一个路由查找结果缓存表.通过选择合适的哈希函数,平衡表项之间的冲突并刷新复杂度,该算法可以缩短路由查找的延迟,减少多处理单元对存储器总线的竞争,为其他网络应用提供更多的处理时间.基于真实网络流量的实验表明,即便每个处理单元中仅有少量表项,网络处理器的吞吐量仍然可以得到有效的提升.     

基于服务质量的多媒体通信初始路由建立算法的研究

基于服务质量的路由选择机制是从根本上提供分布式多媒体应用所需的服务质量保证的重要手段之一。该文提出了两种基于服务质量的多媒体通信初始路由建立算法。一种算法支持在两个通信方之间建立基于服务质量的初始路由,既可以作为点对点多媒体通信的基于服务质量的路由选择／初始路由建立算法,也可以作为初始成员为两个的多媒体动态组通信的基于服务质量的初始路由建立算法,另一种算法支持在多个通信方之间建立基于服务质量的初始路由,既可以作为多媒体静态组通信的基于服务质量的路由选择／初始路由建立算法,也可以作为初始成员为多个的多媒体动态组通信的基于服务质量的初始路由建立算法,文中还探讨了这两种算法的正确性。     

Tourism Route Recommendation Based on A Multi-Objective Evolutionary Algorithm Using Two-Stage Decomposition and Pareto Layering

Tourism route planning is widely applied in the smart tourism field. The Pareto-optimal front obtained by the traditional multi-objective evolutionary algorithm exhibits long tails, sharp peaks and disconnected regions problems, which leads to uneven distribution and weak diversity of optimization solutions of tourism routes. Inspired by these limitations, we propose a multi-objective evolutionary algorithm for tourism route recommendation (MOTRR) with two-stage and Pareto layering based on decomposition. The method decomposes the multi-objective problem into several subproblems, and improves the distribution of solutions through a two-stage method. The crowding degree mechanism between extreme and intermediate populations is used in the two-stage method. The neighborhood is determined according to the weight of the subproblem for crossover mutation. Finally, Pareto layering is used to improve the updating efficiency and population diversity of the solution. The two-stage method is combined with the Pareto layering structure, which not only maintains the distribution and diversity of the algorithm, but also avoids the same solutions. Compared with several classical benchmark algorithms, the experimental results demonstrate competitive advantages on five test functions, hypervolume (HV) and inverted generational distance (IGD) metrics. Using the experimental results of real scenic spot datasets from two famous tourism social networking sites with vast amounts of users and large-scale online comments in Beijing, our proposed algorithm shows better distribution. It proves that the tourism routes recommended by our proposed algorithm have better distribution and diversity, so that the recommended routes can better meet the personalized needs of tourists.      

一个优化的IP-DiffServ端到端定量QoS管理机制

提出了一个IP-DiffServ网络的端到端定量QoS管理机制。它基于用户在市场上评估行为,提出了一个选择方案的优化度评估公式,从用户的利益出发,提出了一个基于最大优化度原则的QoS分割算法。它不但可以为用户的业务或业务应用提供端到端的定量QoS保证,还可以提高它们的性能价格比。实验结果很好地验证了该协商机制的优点。     

用PSO优化基于QoS的WSN路由协议

在过去的10年中,提供服务质量(QoS)保证的路由协议很好的用在了有线网络中,随着无线传感网络(WSN)的广泛使用,就需要考虑如何在无线传感网络中实现QoS的效率.很多QoS度量值都需要被考虑,如数据包时延、带宽效率、能量消耗等.同时QoS也受路由的影响,由于路由解空间随着网络的规模变大而呈指数级的增长,研究路由协议算法的效率就成为一个必然.在研究了智能粒子群最优算法(PSO)后,提出了一个基于PSO的路由算法,不仅考虑了QoS的需求同时也有一个不错的搜索能力.仿真结果表明,与一些典型QoS常规机制比较基于粒子群最优路由算法是有效的.     

一种基于改进蚁群优化的QoS路由算法

蚁群优化（Ant Colony Optimization,AC0）是一种新型的分布式仿生优化算法,可有效地用来解决组合优化问题,而网络路由优化问题则正是组合优化问题当中的一种。因此,本文首先分析了常用路由算法与蚁群优化的基本原理,根据网络路由优化问题与蚁群优化算法的许多匹配特性,提出了一种基于改进蚁群优化的QoS路由算法（Route Algorithm based on Improved Ant Colony Optimlzation,RAIAC0）。最后,通过实验分析,对其可行性进行了证明。