众核平台上广度优先搜索算法的优化

图算法在多个领域具有重要的应用价值。随着社会信息化程度的提高,需要处理的图数据量越来越大,图算法的性能已成为研究热点。广度优先搜索算法是一种重要的图算法,研究它的性能优化技术可以为其他图算法的性能优化提供借鉴。目前,在新一代Xeon Phi众核处理器上的工作均基于自顶向下算法且没有考虑到非均匀访存(NUMA)对性能的影响。文中以混合广度优先搜索算法为基础,结合NUMA拓扑结构,从任务分配、向量化和数据预处理3个方面展开优化,在Xeon Phi平台上设计并实现了高性能并行广度优先搜索算法。一系列实验结果表明,优化后的算法在不同规模的测试数据上与Graph500官方优化的算法相比取得了50%~145%的性能提升。     

基于广度优先搜索算法的故障隔离矩阵生成方法

相关性矩阵表示故障与测试之间的逻辑关系。隔离矩阵表示在给定的测试顺序下,故障隔离与测试之间的需求关系。测试顺序对诊断费用影响可以通过隔离矩阵进行计算。所以求解隔离矩阵是诊断费用优化的前提。针对相关性矩阵与隔离矩阵易于混淆的问题,以及传统分析方法求解隔离的不足,详述隔离矩阵的概念和生成原理,设计基于广度优先搜索的隔离矩阵生成算法。示例表明,生成算法是可行的和有效的。     

基于广度优先搜索的空间搜索算法

广度优先搜索是图的遍历的一种重要的算法。本文在广度搜索算法的基础上实现空间搜索算法。算法的实现在二维和三维空间同时适用,而且可以根据实际情况及搜索条件在方位和方式上进行调整。该算法还用到了C＋＋标准模板库中的队列。在空间搜索算法实现上本文有较大的参考价值。     

用广度优先搜索算法实现路径搜索

介绍了一种采用广度优先搜索算法实现游戏中路径搜索的方法,并用VC编程实现。     

基于异步自动机的网格广度优先搜索算法

在网格中，经常需要以某个结点源点，构造一棵广度优先生成树来进行广播和聚合通信，现有的广度优先搜索算法都是基于图论的同步式算法，而在异步式的网格系统中不能采用这种算法，在开发国家高性能计算环境的过程中，以异步自动机为基础建立了网格理论模型，在这个模型的基础上实现了一种异步式网格广度优先搜索算法－－GridBFS算法，还证明了，GridBFS算法最终将产生一棵广度优先生成树，并且能够检测到算法的终止。     

树的广度优先搜索算法在VFP中的实现

介绍采用数据表作为存储结构,使用树型控件显示树的结点和层次关系.通过建立表、访问表来实现树的存储和广度优先搜索.     

基于单元树结构的广度优先P2P搜索算法

提出基于单元树结构的广度优先搜索算法UTBFS。将单元树结构生成算法与广度优先算法相结合,阐述UTBFS的实现思路,对其时间复杂度、空间复杂度、可行性、优越性进行分析。实验仿真结果显示,相比于传统的广度优先搜索算法和随机广度优先搜索算法,UTBFS减少了需要转发消息的邻居节点个数和冗余消息,因此性能更优。     

基于权值的广度优先搜索算法在九宫格中的实现

人工智能领域搜索算法有多种方式和应用,本文在盲目的广度优先搜索算法的基础上,提出了基于权值的广度优先搜索算法。利用两种搜索算法,在九宫格问题中进行了实现,通过随机产生一定数目的数据,来对比两种搜索算法的优劣,实验表明,基于权值的广度优先搜索算法搜索更有效,效率更高。     

基于广度优先动态二进制的RFID抗碰撞的搜索算法

射频识别技术(RFID)在超高频段的应用将成为物流商业开发的主流,对于排除阅读器识别多个电子标签发回信号的电磁波干扰,实现快速、准确地信息识别,抗碰撞的搜索算法是最为关键的因素.研究了基于广度优先动态二进制搜索算法,并进一步提出优化方案,从技术上切实提高了射频识别系统的效率.     

基于图形处理器的球面Voronoi图生成算法优化

基于四元三角格网(QTM)之间距离计算与比较的球面Voronoi图生成算法相对于扩张算法具有较高的精度,但由于需要计算并比较每个格网到所有种子点的距离,致使算法效率较低。针对这一问题,利用图形处理器(GPU)并行计算对算法进行实现,然后从GPU共享内存、常量内存、寄存器等三种内存的访问方面进行优化,最后用C++语言和统一计算设备架构(CUDA)开发了实验系统,对优化前后算法的效率进行对比。实验结果表明,不同内存的合理使用能在很大程度上提高算法的效率,且数据规模越大,所获得的加速比越高。     

基于多路径广度优先搜索算法的代谢通路设计与实现

寻找从底物到产物的可行代谢通路是代谢工程设计中的核心环节.针对复杂代谢网络中代谢通路不唯一的情况以及传统K条最短路径(K-Shortest Path,KSP)算法效率低的问题,该文通过对传统KSP算法的优化,引入关键边概念以减少非必要的重复计算;搭建代谢通路设计Web平台,使用并行计算方式提升了算法运算性能.最终,通过...     

基于广度优先遍历加权图生成的启发式图分区

图分区质量极大程度上影响着计算机之间的通信开销和负载平衡, 这对于大规模并行图计算的性能是至关重要的. 然而, 随着图数据规模的越来越大, 图分区算法的执行时间成了一个不可避免的问题. 因此, 研究如何优化图分区算法的执行效率是有必要的. 本文提出了一个基于广度优先遍历加权图生成的启发式图分割方法, 该方法在实现较低的通信代价和较好负载平衡的同时, 只引入了少量的预处理时间开销. 实验结果表明, 本文的划分方法减少了复制因子, 降低通信开销, 并且引入的时间开销较小.     

通用图形处理器缓存子系统性能优化方法综述

随着工艺和制程技术的不断发展以及体系架构的日趋完善,通用图形处理器(general purpose graphics processing units, GPGPU)的并行计算能力得到了很大的提升,其在高性能、高吞吐量等通用计算应用场景的使用越来越广泛.GPGPU通过支持大量线程的并发执行,可以较好地隐藏长延时访存操作,从而获得高并行计算能力.然而,GPGPU在处理计算和访存不规则的应用时,其存储子系统的效率受到很大影响,尤其是片上缓存的争用情况尤为突出,难以及时提供计算操作所需的数据,使得GPGPU的高并行计算能力不能得到充分发挥.解决片上缓存的争用问题、优化缓存子系统的性能,是优化GPGPU性能的主要解决方案之一,也是目前研究GPGPU性能优化的主要热点之一.目前,针对GPGPU缓存子系统的性能优化研究主要集中在线程级并行度(thread level parallelism, TLP)调节、访存顺序调节、数据通量增强、最后一级缓存(last level cache, LLC)优化和基于非易失性存储(non-volatile memory, NVM)的GPGPU缓存新架构设计等5个方面.也从这5个方面重点分析讨论了目前主要的GPGPU缓存子系统性能优化方法,并在最后指出了未来GPGPU缓存子系统优化需要进一步探讨的问题,对GPGPU缓存子系统性能优化的研究有重要意义.     

面向优先车辆感知的交通灯优化控制方法

智慧交通灯控制能够有效地改善道路交通的秩序和效率.在城市交通网络中,具有紧急任务的特殊车辆对于通行效率的要求更高.目前已有的智慧交通灯控制算法通常对路网中的所有车辆一视同仁,没有考虑到特殊车辆的优先性;而传统的控制特殊车辆优先通行的方法基本上都是采用信号抢占的方式,对普通车辆的通行干扰过大.为此,提出一种面向优先车辆感...     

深度优先搜索算法的应用研究

在算法的应用中,深度优先搜索算法在图结构的数据类型中有着广泛的应用,本文设置了两个应用场景,一个是信件能否送达问题,一个是不重复打卡夜跑路线的规划问题,这两个问题都与现实生活息息相关.本文通过对这两个问题的详细分析和解决来说明深度优先搜索算法的各种不同使用场合和方法,同时也分析了在解决问题过程中存在的不足.     

面向移动设备的3D图形处理器设计

提出一种面向移动设备的3D图形处理器的设计方法,从图形算法和硬件架构两个层次进行优化.对图形算法进行C语言的仿真模拟,并设计高效的具有并行和流水线结构的图形处理器架构.该架构采用定点的数据通道,拥有一个可编程的顶点处理器和基于像素块的光栅扫描转换模块,降低电路复杂度的同时提高了整体性能.该设计已经在FPGA上验证,并给出了实验结果.实验结果显示该图形处理器结构可以满足移动设备的图形应用要求,具有可行性.     

面向OpenGL 2.0的图形处理器图像处理单元体系结构

为实现图形处理器的自主可控,设计了面向OpenGL2.0图形处理器图像处理单元的体系结构.首先,确定了图像处理单元的单元结构及工作流程;其次,针对每条所处理的函数设计了数据通路;随后,依据各函数的数据通路和OpenGL规范,整理了各模块的处理函数对照表;最后,实现了其体系结构,并在虚拟仿真和FPGA平台进行了纹理加载/获取、卷积、颜色表、柱状图等功能验证,对纹理加载进行了峰值性能验证,面向FPGA和ASIC进行了代价评估.结果表明,该结构能够实现图像处理单元所规定的系列功能,性能满足设计要求,峰值情况每秒可处理30帧2K×2K图像,实现代价可接受.目前,该图像处理单元已集成到完全自主研发的图形处理器之中.     

面向神威高性能多核处理器的并行编译优化方法

在神威高性能多核服务器上,自动并行化编译系统为识别和申明程序中的并行性,产生的OpenMP程序没有经过充分的优化,其采用简单的fork-join模型,存在大量的并行循环嵌套,导致运行效率低。为提升自动并行化编译系统产生的OpenMP程序的运行效率,提出一种并行域重构优化技术。并行域重构技术通过合并程序中的并行域和扩展嵌套循环中的并行域范围,减少OpenMP程序的并行域数目,降低线程组频繁创建和合并等控制开销,将简单fork-join模型的OpenMP程序转换为性能更为高效的单程序多数据模型的OpenMP程序。实验结果表明,在新一代神威高性能多核服务器SW1621平台上,并行域重构技术在NPB3.3-OMP测试集和SPEC OMP2012测试集上的运行效率分别提高了10.77%和7.94%的,可有效提升自动并行化编译系统OpenMP程序的执行效率。     

搜索算法的常见优化方法

在近年的竞赛中,搜索的地位虽然已明显降低,但难度却有增无减,再加上技巧性越来越强,常常成为拉开选手差距的难题。大家知道,由于搜索是一种通用方法,我们关心的往往不是它的正确性,而是它的时间效率和空间耗费,多数的时候更关心时间效率。这样,时间优化就成为了设计搜索算法的重要环节。本文中我们将结合2001年的两道ACM程序设计竞赛的题目讨论一下搜索算法的几种常见优化方法。