关于线性选择算法及其并行化

本文对线性选择算法在比较算法类中给出了基于中值序列而设计的任何改进算法的复杂度下界;从应用的角度对子序列进行有关技术处理,并对递归参量进行动态选择,给出了线性选择算法的实用性改进,并对这一改进算法在共享存储的SIMD机器上给出了并行化。     

基于聚类的环形kNN算法

传统k最近邻算法kNN在数据分类中具有广泛的应用,但该算法具有较多的冗余计算,致使处理高维数据时花费较多的计算时间。同时,基于地标点谱聚类的分类算法(LC-kNN和RC-kNN)中距离当前测试点的最近邻点存在部分缺失,导致其准确率降低。针对上述问题,提出一种基于聚类的环形k最近邻算法。提出的算法在聚类算法的基础上,首先将训练集中相似度较高的数据点聚成一个簇,然后以当前测试点为中心设置一个环形过滤器,最后通过kNN算法对过滤器中的点进行分类,其中聚类算法可以根据实际情况自由选择。算法性能已在UCI数据库中6组公开数据集上进行了实验测试,实验结果表明:AkNN_E与AkNN_H算法比kNN算法在计算量上平均减少51%,而在准确率上比LC-kNN和RC-kNN算法平均提高3%。此外,当数据在10 000维的情况下该算法仍然有效。     

多核片上系统的高效软硬件划分及调度算法

软硬件划分与调度是软硬件协同设计的关键环节,是经典的组合优化问题。本文针对调度与软硬件划分问题提出一种高效的启发式算法。调度算法根据任务的出度及软件计算时间对任务赋予不同的优先级,出度越大,优先级越高,出度相同的情况下,软件计算时间越大,优先级越高。划分算法首先寻找关键路径,然后将关键路径上具有最高受益面积比的任务交由硬件去实现。每次迭代更新当前关键路径的调度长度及剩余硬件面积。继续循环,直到剩余的硬件面积不再满足关键路径上的任何一个软件任务所需的硬件面积的要求为止,这样使得硬件面积的使用率比较高。实验表明,该算法对已有算法的改进可达到38%。     

一类有效的一般并行分枝界限算法

本文针对使用ｐ个处理器选出ｐ个子问题进行并行扩展的一类并行分枝界限算法,提出了一个称作双层立体堆的数据结构,给出了ＰＲＡＭ－ＣＲＥＷ模型上的并行分枝界限算法。假定在状态空间树上扩展一个结点最多生成ｒ个子结点,本文提出的并行算法最多使用ｒ个处理器,其运行时间为Ｏ（（ｒ／ｌｏｇｒ）ｈｌｏｇｈ＋ｒｈ）。对于ｌｏｇｈ〈ｒ〈ｈ,在系数因子ｌｏｇｈ／ｌｏｇｒ的范围内,以及对于ｌｏｇｈ〉ｒ,在系数因子ｒ／ｌｏｇ     

蜂窝网络中用户移动参数对越界率的影响

越界率是衡量无线蜂窝网络性能的重要指标之一.主要考察用户移动模型中3个要素(速度、方向和蜂窝小区的信号覆盖范围)对用户越界率的影响.这种影响的检测是分别在简单移动模型和支持突发事件影响的移动模型上进行多组实验所得的,分别画出了两种移动模型下用户最大速度、最小速度以及平均速度的变化、BS的信号覆盖范围和用户移动方向改变频率与用户越界率之间的曲线图.通过对比两种不同移动模型下的实验数据,发现用户的越界率与用户的移动速度和BS的信号覆盖范围关系较大,而用户移动方向的改变频率对越界率的影响相对较弱.     

Mobile robot path planning based on adaptive bacterial foraging algorithm

The utilization of biomimicry of bacterial foraging strategy was considered to develop an adaptive control strategy for mobile robot, and a bacterial foraging approach was proposed for robot path planning. In the proposed model, robot that mimics the behavior of bacteria is able to determine an optimal collision-free path between a start and a target point in the environment surrounded by obstacles. In the simulation, two test scenarios of static environment with different number obstacles were adopted to evaluate the performance of the proposed method. Simulation results show that the robot which reflects the bacterial foraging behavior can adapt to complex environments in the planned trajectories with both satisfactory accuracy and stability.     

Torus网络自适应容错路由算法

在应用于大规模并行计算机的互连网络的设计中,容错问题是其中的一个关键问题和难点问题。提出了一种基于Torus虫孔交换网络的容错路由算法,这一算法使用了矩形故障模型,无论故障区域大小多少和如何分布,算法始终是无死锁的,而且具有足够的自适应性,只要故障节点没有断开网络的连接,算法就能够通过选路使消息绕过故障区域,保持路由的连通性。同时,算法仅需要使用3个额外的虚拟通道。最后算法在不同故障率的Torus网络中进行了仿真实验,结果显示这一算法具有良好的平滑降级使用的特性。     

容错处理器阵列的并行重构及VHDL实现

网格连接的处理器阵列是一种应用广泛的高性能体系结构,而容错处理器阵列的重构技术是近年来的研究热点之一.现有的研究多数集中在串行重构算法上,忽视了该结构重构时内在的可并行性.本文根据阵列结构的特点设计了一种基于VHDL语言的重构算法,该算法从第一行的各个无故障处理器单元同时向下选路,具有潜在的并行性,.实验结果表明,与现有的串行算法相比,本文提出的并行算法同样能够生成最大规模的目标阵列并且当物理阵列大小为48×48,本文提出的并行算法加速重构将近20倍.     

具有可控冗余度的虚拟机容错分配算法

在现代基于虚拟化的数据中心中,虚拟机分配是实现云中资源有效调度的首要考虑。已经证明对数据结点分配虚拟机并考虑虚拟机之间的通信延迟,使得最大通信延迟最小的问题是NP-hard问题。目前鲜有在数据中心网络虚拟机分配问题上考虑其安全性和可靠性的研究。针对虚拟机分配中的容错技术,提出了一种具有可控虚拟机冗余度的启发式分配算法。算法以最大通信延迟最小化为优化目标,在可利用的虚拟机集合中通过构造可控冗余度的团来分配处理数据结点。实验结果表明,在Tree、VL2、Fat-tree和BCube四种常用的网络结构中,提出的启发式算法能提供0-200%之间任意冗余度。同时,在冗余度介于0~40%时,虚拟机与数据结点的匹配时间平均降低了67.1%,并且算法运行时间平均降低了12.8%。