并行算法

摘要： 为满足无线通信中高吞吐、低功耗的要求,并行译码器的结构设计得到了广泛的关注。基于并行Turbo码译码算法,研究了前后向度量计算中的对称性,提出了一种基于前后向合并计算的高效并行Turbo码译码器结构设计方案,并进行现场可编程门阵列(field-programmable gate array,FPGA)实现。结果表明,与已有的并行Turbo码译码器结构相比,本文提出的设计结构使状态度量计算模块的逻辑资源降低50%左右,动态功耗在125 MHz频率下降低5.26%,同时译码性能与并行算法的译码性能接近。

摘要： 随着全球期权市场规模逐年增大,为了满足实时交易、监管和制定决策等需求,计算速度是银行业重点考虑的要素之一。通用图形处理器在解决金融领域大规模数据并行计算问题上发挥着优秀的性能。讨论在局部波动率模型上期权定价蒙特卡罗方法的图形处理单元(graphics processing unit,GPU)并行加速问题,比较使用C++和openACC实现的欧式看涨期权和亚式看涨期权的CPU串行定价程序与GPU并行定价程序之间的时间开销和加速比。测试表明,在搭载了NVIDIA Tesla P100 GPU的计算机上GPU并行算法取得了加速效果。

摘要： 作为一种典型的拉格朗日型无网格数值方法,光滑粒子流体动力学(SPH)方法在模拟自由表面流问题时具有天然优势。但是,该方法计算量大、耗时长,为此提出了一种基于粒子分解的SPH并行算法。该算法将所有粒子平均分配到各个进程进行计算,每个时间步通信仅调用一次发送、接收和广播函数,因此易于实现且可扩展性较好。应用该并行算法对二维溃坝流和三维液滴冲击液膜问题进行数值模拟,结果表明:该并行算法能显著减少模拟所消耗的计算时间,有利于进行三维大规模计算问题的数值模拟;当粒子数大于百万时,最大加速比可达30以上。

摘要： 在中大规模无人机干扰资源调度中,针对现有模型约束条件简单、调度算法适用规模较小的问题,该文提出了带最少任务数约束的资源调度模型,以最大化干扰效益和最小化成本为目标,用层次分析法对效益与成本指标赋权,并设计了一种用精英集加快收敛的改进并行遗传算法。在中等规模和500:500(干扰资源数:目标数)的更大规模仿真实验中,所提算法与遗传算法、非支配排序遗传算法II、修复遗传算法、基于岛屿模型的并行遗传算法和自适应模拟退火遗传禁忌搜索算法的性能相比,能在更短的时长内达到较优的目标函数值。

摘要： 本文研究了Volterra级数模型全解耦辨识算法,提出Volterra级数模型并行辨识算法的设计思想,设计了并行算法。实验和仿真结果表明,该算法能有效减小模型的在线辨识时间,能有效克服Volterra级数模型辨识中的维数灾难问题,且收敛速度快、稳态精度高,有利于实现工程应用。

摘要： 传统的异常数据监测算法依靠单台计算机对异常数据进行识别,识别速度慢,且无法满足对数据处理的精确性要求。针对上述问题,文中构建了Hadoop分布式财务异常数据分析模型。该模型采用Hadoop中的MapReduce框架作为并行计算框架,同时在数据异常检测算法方面引入了邻域关系的LOF算法,有效避免了数据集元素边缘可能会出现误判的情况。数值实验结果表明,文中所提算法的准确率相比其他3种同类算法提升了5%以上,且算法的总运行时间也明显缩短。由此可见,文中所提模型可快速、准确地检测出财务异常数据,保障医疗系统的平稳运行。

摘要： 面向装配信息缺失的复杂几何模型结构分析问题,提出一种适用于任意曲面类型的接触关系并行识别方法。根据模型几何特征自动计算局部容差,采用基于局部容差的三角形碰撞检测技术进行接触识别,有效提升算法精度。利用多线程并行技术,结合包围盒筛选技术和空间划分技术提高识别效率。算法能高效地自动识别数百上千部件模型包含的接触关系。通过对复杂几何模型的测试表明,算法具有高精度、高效率的特点。最后,将接触关系识别的结果应用到实际工程模型的结构分析计算中,进一步验证了算法的有效性。

摘要： 针对使用非结构网格的时域间断伽略金方法在并行计算时通信复杂的问题,提出一种适用于瞬态电磁场大规模并行计算的最小通信周期策略。将进程间点对点通信的拓扑结构映射为通信矩阵,利用通信缓冲区未满时非关联进程的通信互不干扰特性,对互不干扰的进程通信顺序进行排序,将每轮同时进行的通信记为同一个通信周期,重新填充通信矩阵。最小通信周期策略对初始通信矩阵不断递归地取各元素余子式,每次递归结束后即得到一个通信周期中同时进行通信的进程,将这些进程对应的元素排除在下一次递归之外,直到所有初始通信矩阵所有元素排序完毕。最小通信周期策略能够有效降低并行迭代计算过程中的总通信周期数,减少通信过程消耗的时间,从而提升算法的计算效率。与传统策略相比,最小通信策略的通信周期数缩减到3%,并行效率显著提高,计算时间减少。同时,使用该策略在国产超级计算机神威·太湖之光上以8000核组(8000进程,520000核心)进行计算时取得了约70.38%(10倍扩展)的并行效率。

摘要： 为应对由客户的动态需求、大型货车的限行政策及配送时间窗的限制给供应商制定科学配送计划带来的严峻挑战,设计考虑动态度和时间窗的两级车辆路径优化方法。该方法基于客户动态增量概率阈值及动态度构建响应增量需求的车辆路径更新策略;将连续两级车辆路径优化问题映射为由配送中心到中转站和由中转站到客户的两个子网络的带时间窗的车辆路径问题(VRPTW),并在并行模拟退火算法框架下融合Or-opt,2-opt,2-opt*,Swap/shift 4种邻域搜索策略求解VRPTW。用数据案例对模型及算法进行验证,表明所提策略及方法能较好地满足供应商对客户动态需求的响应,且具有良好的鲁棒性。

摘要： 通过构建参考基因组的二级Hash索引,以快速筛选出测序长序列在参考基因组中可能匹配的候选区域;建立测序序列局部索引,以加速测序序列和参考基因组候选区域之间的映射定位;对每个候选区域里的k-mer与测序序列的索引命中进行左右扩展获得比对种子;采用等距离抽样方式对种子抽取多个位置,利用抽样结果建立判断依据来过滤掉那些不可能匹配的种子;建立处理包含“均聚物”类型错误的序列片段全局比对得分方程,并行填补比对骨架的空隙,并采取GPU显存预分配和后释放独立的并行比对策略,以提升序列片段全局并行比对效率.模拟与真实数据的实验结果表明,相较于已有同类的长序列比对并行算法,本文提出的并行算法获得整体上较高的比对敏感度、碱基层次灵敏度和准确度,且可有效处理第3代测序长序列含有的“均聚物”类型错误,显著加速了大规模长序列与参考基因组比对的完成.

摘要： 浅水模型在水利工程、海岸工程和环境工程等领域应用广泛.现有基于有限体积法和近似黎曼算子的浅水模型的时间步长受限于CFL条件,计算效率偏低.针对该类模型实现了主流的加速并行算法,包括基于计算机硬件的OpenMP和CUDA-GPU,以及基于算法本身软件的局部分级时间步长技术(LTS:local time step)和它们之间的组合.应用模型模拟了试验条件下溃决洪水流经建筑物群的过程,得到如下认识:首先,在串行计算条件下,PGI编译器(即CUDA Fortran的编程环境)的计算效率比Intel Fortran编译器低,相差1.5～1.6倍;其次,GPU的加速效果优于Open MP:网格规模越大,优势越明显.再次,如果网格规模较小,OpenMP+LTS可达到和GPU近似的加速效果.最后,GPU+LTS可在单纯GPU并行计算基础上,进一步大幅度提升计算效率.

摘要： 现有的并行矩阵分解算法通常采用对矩阵分块的方法,将互不冲突的分块并行地计算.负载不均衡是同步并行算法中常见的问题——各分块中评分数量差异较大,导致线程阻塞和空等待,降低并行效率.本文提出一种"均衡分块"的方法,通过分别调整行块、列块尺寸均衡评分数的分布,达到方体块评分均衡的目标.以块评分数方差衡量"均衡",从理论上分析和证明了均衡分块的可行性;将均衡分块应用于DSGD和CCD++等并行矩阵分解算法,通过大规模分布式实验,验证了该方法能大大提升并行性能."均衡分块"作为一种普适的负载均衡思想,适用于基于矩阵分块、同步的矩阵分解并行算法,具备广泛的应用价值.

摘要： 在图及其它离散的结构上进行大规模的计算在包括计算生物学、网页搜索及知识发现等众多领域发挥着日益重要的作用.但是,与相对成熟的数值科学计算相比,以图计算为代表的高性能组合计算是一个新兴领域,如何使大规模图计算获得高性能是一个待解决的问题.高性能数值计算的许多方法,特别是针对稀疏矩阵计算的并行算法及数据结构可以为并行图计算提供支撑.本文在Combinatorial BLAS上实现了对同辈压力(Peer Pressure)图聚类的并行优化,将图计算转化为对稀疏矩阵的计算,并基于MPI和MPI+OpenMP两种编程模型分别针对该算法最费时的部分提出相应的并行算法.实验结果表明,在处理规模达到43000亿的由稀疏矩阵表示的超大规模图时,基于线性代数表示的同辈压力图聚类算法在曙光超级计算机上取得了较高的性能表现,良好的可扩展性.其MPI实现在1024个核上获得了76.8％的并行效率;其MPI+OpenMP实现在2048个核上取得了46.4％的并行效率.

摘要： LOBPCG是一种可以被有效并行化的特征值数值解法.本文讨论了在神威太湖之光上优化LOBPCG的方法.首先介绍了适合神威太湖之光架构的两级并行模型,研究了稀疏矩阵-向量积的并行算法的优化技术;提出一种自动调节缓冲区大小方法,从而自动实现最佳程度的通信隐藏;研究了适合不同"形态"输入矩阵的稠密矩阵积在神威太湖之光架构上的并行算法;在1.25亿阶矩阵、最高使用1048576核的特征值求解测试中表现出满意的扩展性.

摘要： Stencil计算是一种科学和工程应用中常见的循环模式,而分块技术是一种提高数据局部性和并行性的强大转换方法.与以往直接对整个迭代空间进行分块的分块技术不同,本文提出了一种新的两层密铺分块的并行算法.首先,利用不同分块密铺数据空间,其次,所有分块沿时间维度的扩展能密铺迭代空间.本文提出的算法有以下优点:(1)最大化并发执行,(2)无冗余计算,(3)简洁的循环条件,(4)适应Stencil不同的尺寸、形状、阶数和边界条件.实验结果表明,对于3d27p Stencil,非周期边界的性能比Pluto高12％,周期边界的比Pochoir最高提升40％.

摘要： 本文基于OpenMP实现了一种基于空腔交叠互斥准则与无锁原子操作的Delaunay三角化增量插点细粒度并行算法.在串行算法的基础上,对点集引入Hilbert排序,使相邻点在几何上亦相邻.引入互斥机制——仅当各空腔无公共单元及公共相邻边时,才可同时插入,据Delaunay局部性准则可保证整个网格都具备Delaunay属性.每个单元用一个原子变量已标记该单元是否被占有,在计算Delaunay空腔时,各线程将试图写入该原子变量,但本竞争机制保证有且仅有一个线程能成功获得该单元的所有权,以保证算法的互斥性.在16核Intel(R)Xeon(R)CPU E5-2640v3@2.60GHz、64GiB内存的平台上的数值实验表明,对于107的点集,该算法在16核下加速比可达7.06倍.

摘要： 多技能模型呼叫中心的座席资源被多个呼叫队列共享形成资源竞争,座席资源的互斥访问导致路由计算的并行程度低,因此互斥方法控制下的多进程系统对座席路由计算的性能难以提升,这成为云呼叫中心扩展能力的瓶颈.对此本文在对呼叫中心路由分配算法与资源竞争模型分析基础上,提出了一种并行的呼叫中心路由方法PCCRM,该方法通过临界资源粒度细化,将互斥范围从全局资源缩小到局部资源,可显著减少了进程间同步造成的延迟,提高了系统多节点并发性能.同时PCCRM引入有序竞争模型来保证该并行方法符合呼叫中心路由算法基本原则,满足功能性要求.实验结果表明PCCRM可以有效提升路由算法的多进程并行程度和系统整体性能.

摘要： 转子瞬态响应分析比临界转速求解、稳态响应分析算法复杂,计算时间长,瞬态响应算法的优化可以缩短计算时长、提高计算精度和计算效率.本文采用Riccati传递矩阵-Wilson-θ法进行转子系统瞬态响应分析,对其算法进行并行化处理以优化算法结构,缩短运算时间.最后通过单转子瞬态分析实例验证该算法的有效性.

摘要： 为加速基于离散纵标方法(SN)的中子输运计算,针对群内迭代研究并实现了PCR(分流再平衡)算法及基于区域分解的并行,并在加速方程求解时进一步耦合了算术多重网格算法.并行PCR算法已集成至JSNT软件,并针对临界和外源计算典型算例验证了算法的正确性和有效性.74亿自由度的国内某商业压水堆压力容器屏蔽计算中,JSNT迭代次数减少3.1倍,总体计算时间减少2.4倍,1024核并行效率达42.8％.

摘要： Jacobi和Gauss-Seidel算法作为线性方程组的求解器,在并行计算领域具有广泛应用,而基于异构众核架构开发其细粒度并行性一直是挑战.最新Top500排名第一位的神威太湖之光超级计算机正是基于异构众核架构,针对这一现状,基于非结构网格提出了面向神威太湖之光超级计算机异构众核架构的块Gauss-Seidel/Jacobi算法,将其作为区域分解算法的子区域求解器.为充分利用神威太湖之光国产SW26010芯片中每个CPE拥有的高速LDM(Local Data Memory),以缓解通信瓶颈,设计了多行块通信打包、计算与通信重叠性能优化策略和忽略非关键元素的低通信复杂性数值优化方法.数值实验结果显示,块Gauss-Seidel/Jacobi算法具有良好的预处理效果,相较于串行Gauss-Seidel算法,预处理过程的加速比最高达到4.16倍.以1040核的测试数据为基准,在处理器核数达到33,280时,块Gauss-Seidel/Jacobi预条件算法的并行效率为61％.

摘要： 本发明涉及一种多智能优化并行算法的机器人路径规划方法，属于机器人技术领域。该方法包括步骤：S1，利用粒子群优化算法的全局搜索能力实现移动机器人的路径规划；S2，以粒子群优化算法为主干，嵌入遗传算法(GA)中的选择、交叉、变异算子以及细菌觅食算法(BFO)中的趋化操作加强局部搜索能力；S3，利用并行策略优化路径，提高机器人的路径规划效率；S4，设计栅格环境地图，用于评定算法的优越性。本发明在复杂多障碍物的环境下，相较于其他算法，多智能优化并行算法弥补了PSO算法的缺陷，局部和整体的搜索能力大幅度提高，路径规划速度快且路径距离短，同时具备更强的鲁棒性。

摘要： 本发明涉及集成电路领域的线程处理方法，具体涉及基于并行算法的集成电路电阻抽取方法，该方法包括以下步骤；步骤一，读取版图信息，根据导体或过孔的坐标以及所属的层，把所有导体存储在对应单元里面；步骤二，首先，建立线程池对每个单元的每个导体层建立一个任务加入线程池；然后，根据用户配置的线程数启动线程，并对每个线程做如下操作：步骤二一，从线程池中取出一个任务；步骤二二，遍历这个任务里面所有导体，在和其他导体或过孔接触的地方创建节点；步骤二三，把创建的节点和节点对应的导体或者过孔返回给主进程；步骤三，所有线程运行至结束，把所有节点保存到导体的里面，并删除重复的节点。

摘要： 本发明公开一种基于OpenMP和CUDA的图像特征提取并行算法，应用于利用内核原型分析算法的图像特征提取，针对图像本身的特点，即在图像处理算法中存在大量矩阵运算，对内核原型分析算法进行了优化。通过在采用FURTHESTSUM算法对内核原型分析算法进行初始化的过程中，使用了OpenMP多线程并行同时结合归约算法对其进行优化，随后在使用投影梯度法更新矩阵的过程中，使用OpenMP和CUDA在GPU中并行执行其中的矩阵乘法运算，使用OpenMP并行执行其中的矩阵减法运算，即通过多线程的计算解决了现有的内核原型分析算法中由于在进行最大值和矩阵运算的计算时使用串行方法计算，导致其计算速度慢，运行效率低等问题。

摘要： 本申请提供基于BCH并行算法和LDPC算法的纠错电路及方法，所述纠错电路包括BCH并行算法电路、LDPC算法电路和模式配置电路，其中，所述BCH并行算法电路，用于并行处理编译码操作过程和数据传输过程；所述LDPC算法电路，用于对数据进行LDPC编译码；所述模式配置电路，用于配置通过所述BCH并行算法电路和/或所述LDPC算法电路进行纠错。本申请实施例的技术方案，可以提高数据吞吐率，以及提高纠错性能。

摘要： 本发明公开了一种基于蚁群优化和遗传算法的粗粒度并行算法，初始化m只蚂蚁的起始城市；蚁群周游一次，将周游结果作为GA的初始种群；蚁群周游一次，计算并记录本次周游具有最短路径的蚂蚁；运行GA的选择算子、GA的杂交算子、GA的变异算子；若迭代过程达到预先设定的迭代条件，计算并输出运行时间，输出最优解。经过大量计算表明，该并行算法的计算速度优于同等串行算法。

摘要： 本发明涉及AI行为网络算法技术领域，公开了一种基于AI人体行为的多层前馈人工神经网络并行算法，包括视频特征码输入层、隐含层、模型激励输出层和Spark底层，所述框架PANN由一个视频特征码输入层，多个隐含层，一个模型激励输出层构成，采用后向传播的误差调整公式，所述视频特征码输入层、隐含层和模型激励输出层之间通过单向的权值网连接，所述Spark底层由Scala语言实现，神经网络的深度与隐含层的数目有关，且与时间长度有关。该基于AI人体行为的多层前馈人工神经网络并行算法，采用神经网络模型的方法，完成人体行为识别的任务，保证了对人体样本行为识别的正确率，并充分提高了系统完成人体在线行为识别任务的能力，运行系统时顺畅。

摘要： 本发明公开了一种加速算法与对向并行算法的机器人路径规划方法，其特征在于，包括：通过机器人的传感器获取机器人周围的环境数据，并使用栅格法对该环境数据进行处理，以得到栅格地图；选取割线将得到的栅格地图分割成相应的条带状的子图，通过并行化处理的方式得到的子图两端割线上的任意两个边界点之间的最短路径，同时从初始位置和目标位置沿着各个子图两端割线上的任意两个边界点之间的最短路径开始对向搜索，一旦搜索到同一割线上的边界点，则停止搜索，并且合并搜索得到的两个对向路径以得到最短路径，并使机器人从初始位置沿着该最短路径向目标位置运动。本发明能够解决现有串行最短路径加速算法的执行效率低的技术问题。

摘要： 本发明公开的基于BDDC区域分解并行算法的粗网格选取方法，属于大规模柔性多体系统并行仿真预测领域。本发明将Deluxe缩放矩阵用于构造广义特征方程系数矩阵，能够有效针对柔性多体系统出现子域界面材料系数跃变的情况；此外，本发明通过计算共有边的二次苏尔补矩阵，凝聚柔性多体系统子域内界面除共有边之外的剩余部分信息，有效针对柔性多体系统出现子域界面材料系数跃变的情况，保证BDDC区域分解并行算法的稳定性，提高对柔性多体系统并行仿真预测效率。本发明能够解决柔性多体系统子域界面材料系数跃变导致的效率低下问题，提高基于BDDC区域分解并行算法对柔性多体系统的并行仿真预测效率，进而解决大规模柔性多体系统并行仿真预测领域相关技术问题。

摘要： 在泛电子领域高速高精度的3D测量系统中关于电路板元素（如丝印，锡膏，孔洞，异物，元件等）识别一直是复杂的问题，由于不同类型的电路板颜色各异，甚至同一类型的电路板都可能出现很大的色差，且电路板表面可能受光照不均匀、材质吸光或反光等因素影响，传统单独基于2D图像信息或3D点云数据的方法都因为各自算法的局限性，无法准确地识别出各元素，且3D点云数据计算量极大，计算效率慢，不能满足实时检测的需求。本发明提出一种结合二维与三维信息精确计算高度的并行算法，通过异构并行运算单元根据2D和3D信息对各元素进行快速准确的识别并精确计算各元素的相对高度，满足设备在线实时检测的需求。

摘要： 本发明涉及集成电路领域的线程处理方法，具体涉及基于并行算法的集成电路电阻抽取方法，该方法包括以下步骤；步骤一，读取版图信息，根据导体或过孔的坐标以及所属的层，把所有导体存储在对应单元里面；步骤二，首先，建立线程池对每个单元的每个导体层建立一个任务加入线程池；然后，根据用户配置的线程数启动线程，并对每个线程做如下操作：步骤二一，从线程池中取出一个任务；步骤二二，遍历这个任务里面所有导体，在和其他导体或过孔接触的地方创建节点；步骤二三，把创建的节点和节点对应的导体或者过孔返回给主进程；步骤三，所有线程运行至结束，把所有节点保存到导体的里面，并删除重复的节点。