基于现代硬件的并行内存排序方法综述

研究了现代硬件上的并行内存排序方法,对其研究现状与进展进行了综述.首先简要阐述了经典排序算法以及排序网络的优缺点,分析其并行优化的适用性,然后从现代CPU处理器设备(多核、配备大内存)、图形处理器(GPU)、现场可编程逻辑门阵列(FPGA)等新型处理器设备介绍现有排序方法的研究成果.处理器设备的架构不同,对排序算法的优化策略也不同,现代CPU主要利用线程的本地存储层次优化数据在存储单元中的排列,以减少访存次数及减少访存缺失,同时利用单指令多数据流技术(SIMD),以提高算法的数据级并行度;GPU则需要将多个线程组织成线程块,依靠共享内存提高线程块的访存速度,而在线程块内则使用单指令多线程(SIMT)技术提高线程的执行效率;FPGA则更靠近于硬件底层,受到自身的资源限制,FPGA的优化策略主要依靠硬件描述语言或高级综合语言优化电路的设计,提高资源利用率的同时增加FPGA的吞吐量.现有的成果表明,GPU的并行内存排序性能优于CPU端上的并行内存排序性能.作者最后对未来的研究方向进行了展望.

无线Mesh骨干网络拓扑优化算法研究

针对无线Mesh骨干网络网关部署及其网络拓扑优化问题,提出一种基于Delaunay图形的无线Mesh骨干网络拓扑优化算法.算法首先根据Delaunay图形的特点,利用网络节点位置信息快速找到网关部署节点;然后依据网络中传输距离与节点度之间的关系对网络拓扑进行链路优化,通过减少传输距离过长、能耗较高的无线链路和限定路由节点上的定向天线数量上限,提高网络传输成功率,解决进行定向天线WMN网络部署后产生的新干扰和能耗浪费问题.仿真实验结果表明,优化后的网络拓扑结构实现了网关数量较少、路由节点至网关节点传输距离较短的优化目标,降低了部署费用和干扰,改善了网络性能.

基于紧密中心性的无线mesh骨干网网关部署

将定向天线和Delaunay图应用于无线mesh骨干网络的网关部署,提出了基于紧密中心性的无线mesh骨干网络网关部署算法。根据已知的mesh路由器和网关的最大流通量对网络进行划分,形成Delaunay子图,在划分的子图中根据欧几里德距离找出距离中心点最近的3个节点,形成候选网关集,在候选网关集中选择到其他节点总路径最短的节点作为网关的部署位置,将每个子图的网关位置输出。仿真结果表明,根据网关最大流通量进行合理网络划分后,算法能最小化网络的网关数量,由mesh路由器到网关的总路径长度优于随机算法。