图形处理器上CSB~+-树索引的并行构建算法

为提高缓存敏感CSB+-树索引的操作效率,在图形处理器(GPU)上研究CSB+-树的并行构建和查询性能.通过分析索引树内部节点的每一键与对应叶子节点的映射关系,提出了一种一次性并行构建CSB+-树所有内部节点键值的无锁并行算法,以最大并行度来快速构建索引树.该算法通过设计GPU平台上支持CSB+-树的索引数据任意伸缩的动态数组来解决GPU上不能动态分配显存空间的问题,通过在索引内部节点的边界增加填充位来减少线程块的线程分支数,从而提高CSB+-树的查询效率.实验结果表明,文中所提算法的运行时间比基于单个节点和基于树层的并行算法分别提高了31.0和1.4倍.     

基于OpenCL的图像灰度化并行算法研究

随着图像数据量的增加,传统单核处理器或多处理器结构的计算方式已无法满足图像灰度化实时处理需求.该文利用图像处理器(GPU)在异构并行计算的优势,提出了基于开放式计算语言(OpenCL)的图像灰度化并行算法.通过分析加权平均图像灰度化数据处理的并行性,对任务进行了层次化分解,设计了2级并行的并行算法并映射到“CPU+GPU”异构计算平台上.实验结果显示:图像灰度化并行算法在OpenCL架构下NVIDIA GPU计算平台上相比串行算法、多核CPU并行算法和CUDA并行算法的性能分别获得了27.04倍、4.96倍和1.21倍的加速比.该文提出的并行优化方法的有效性和性能可移植性得到了验证.     

CPU+GPU异构并行的矩阵转置算法研究

针对当前算法优化研究一般局限于单一硬件平台、很难实现在不同平台上高效运行的问题,利用图形处理器(GPU)提出了基于开放式计算语言(OpenCL)的矩阵转置并行算法.通过矩阵子块粗粒度并行、矩阵元素细粒度并行、工作项与数据的空间映射和本地存储器优化方法的应用,使矩阵转置算法在GPU计算平台上的性能提高了12倍.实验结果表明,与基于CPU的串行算法、基于开放多处理(OpenMP)并行算法和基于统一计算设备架构(CUDA)并行算法性能相比,矩阵转置并行算法在OpenCL架构下NVIDIA GPU计算平台上分别获得了12.26,2.23和1.50的加速比.该算法不仅性能高,而且实现了在不同计算平台间的性能移植.     

内存数据库索引研究

内存数据库将数据存储在内存中进行操作,与基于磁盘的数据库相比在性能上得到提升,但是由于MMDB与DRDB的性能瓶颈的差异,用于DRDB的B+树索引算法已经不再适用于MMDB。为适应内存数据库的性能,T树,CSS树,CSB+树等索引算法相继被提出,但是这些算法没有考虑到TLB失效会影响索引的性能。本文通过对CSB+树进行改进,得到一种更适用于内存数据库的索引算法。实验证明,该索引结构可以降低TLB失配,提升处理器缓存的利用率,提高查询效率。     

基于GPU的PCA人脸识别系统设计

针对实际人脸识别系统需要满足实时性的应用需要,探讨了在图形处理器(GPU)硬件架构基础上的基于主成分分析(PCA)人脸识别系统设计与实现.结合统一计算设备架构(CUDA)的计算平台,通过将算法中耗时长、适合并行的部分过程映射到GPU上并行执行改进系统的加速实现.实验结果表明:相对于基于CPU平台的串行实现,基于GPU的实现在整体上能够获得约5倍的加速,而两个执行并行的模块能分别获得最大20倍和30倍的加速.     

用于光线跟踪的高并行度表面积启发式(SAH)KD树构建

提出一种用于光线跟踪的SAH-KD树构建方法,解决当前KD树并行算法并行度不高且效率低的问题.算法首先对所有图元包围盒在三个维度按坐标轴左值排序,得到三维上有序的包围盒索引.然后使用层次遍历构建KD树,根据每个节点包围盒选择要划分的维度,并在当前层生成所有节点在该维度下的候选划分点序列.最后计算每个节点的空间树,在GPU中计算每个候选点的SAH值,选择每个节点的最小SAH值点进行划分.实验中采用4个常用场景进行测试算法性能,并同时比较了当前高效串行与并行算法,结果证明本文提出的算法在生成同等质量KD树的情况下达到对比串行方法4~6倍以及对比并行方法的1.3~1.5倍的计算速度,并且能在线程数成倍增加时达到相近倍数的加速比.     

并行查询中的索引并行化技术

提出一种新的索引并行化技术，利用多处理机来提高建立在B树结构上的索引性能，并提出了一种改进的B树结构－FALNB树，基于该树结构，以大结点B树方式在多个处理机上分布索引数据，通过动态调整算法快速进行调整，取得很好的负载平衡效果，给出了时间分析模型，实验结果显示FALNB树能加快查询响应速度，对海量数据的索引有良好性能。     

一种分布式后缀树构造与匹配算法

提出一种基于消息传递模式的分布式后缀树构造算法(DPSTG)及相应的并行匹配算法.DPSTG算法按不同的字符将原始字符串的后缀树分解成若干个子后缀树后由多个处理器并行构造.处理器间通过消息传递方式连接各个子后缀树,匹配时首先将要查找的字符串分割成若干不同首字符的子字符串,然后在构造相应首字符子后缀树的处理器上实现多个子字符串的并行匹配.理论分析表明DPSTG算法的时间复杂度要优于现有的大多数后缀树并行生成算法.模拟实验结果表明DPSTG算法的并行加速比随着待处理字符串的长度增加而提高.     

Storm平台非关键路径电压调控节能策略

针对流式大数据计算平台的高能耗问题,提出一种基于Storm平台的非关键路径电压调控节能策略.首先根据数据流处理特点建立有向无环图、关键路径及电压调节模型,确定位于拓扑执行非关键路径上的工作节点CPU使用率及数据传输量阈值;其次根据拓扑执行非关键路径上工作节点的不同情况,对工作节点内存电压进行调节,当工作节点的CPU使用率及数据传输量低于阈值时降低其内存电压,当工作节点CPU使用率及数据传输量高于阈值时则升高其内存电压,由工作节点内存电压确定系统功率;最后通过评估性能与能耗的关系验证算法的可行性.实验结果表明,系统实施节能策略后比原系统降低了约34.5%的能耗,且位于拓扑执行非关键路径上的节点越多节能效果越好.     

Co-OLAP:CPU&GPU混合平台上面向星形模型基准的协同OLAP（英文）

当前GPU(图形处理器),即使是中端服务器配置的中端GPU也拥有强大的并行计算能力.不同于近期的研究成果,中端服务器可能配置有几块高端CPU和一块中端GPU,GPU能够提供额外的计算能力而不是提供比CPU更加强大的计算能力.本文以中端工作站上的CoOLAP(协同OLAP)为中心,描述如何使中端GPU与强大的CPU协同以及如何在计算均衡的异构平台上分布数据和计算以使Co-OLAP模型简单而高效.根据实际的配置,基于内存容量,GPU显存容量,数据集模式和订制的AIR(数组地址引用)算法提出了最大高性能数据分布模型.CoOLAP模型将数据划分为驻留于内存和GPU显存的数据集,OLAP计算也划分为CPU和GPU端的自适应计算负载来最小化CPU和GPU内存之间的数据传输代价.实验结果显示,在SF=20的SSB(星形模型基准)测试中,两块至强六核处理器的性能略优于一块NVIDA Quadra 5 000GPU(352个cuda核心)的处理性能,Co-OLAP模型可以将负载均衡分布在异构计算平台并使每个平台简单而高效.     

Co-OLAP:CPU&GPU混合平台上面向星形模型基准的协同OLAP

当前GPU(图形处理器),即使是中端服务器配置的中端GPU也拥有强大的并行计算能力.不同于近期的研究成果,中端服务器可能配置有几块高端CPU和一块中端GPU,GPU能够提供额外的计算能力而不是提供比CPU更加强大的计算能力.本文以中端工作站上的Co-OLAP(协同OLAP)为中心,描述如何使中端GPU与强大的CPU协同以及如何在计算均衡的异构平台上分布数据和计算以使Co-OLAP模型简单而高效.根据实际的配置,基于内存容量,GPU显存容量,数据集模式和订制的AIR(数组地址引用)算法提出了最大高性能数据分布模型.Co-OLAP模型将数据划分为驻留于内存和GPU显存的数据集,OLAP计算也划分为CPU和GPU端的自适应计算负载来最小化CPU和GPU内存之间的数据传输代价.实验结果显示,在SF=20的SSB(星形模型基准)测试中,两块至强六核处理器的性能略优于一块NVIDA Quadra 5 000GPU(352个cuda核心)的处理性能,Co-OLAP模型可以将负载均衡分布在异构计算平台并使每个平台简单而高效.     

基于双核构架的ABNF字符串模式匹配处理器

在字符串模式匹配专用处理器的基础上,设计了一种双核构架的ABNF字符串模式匹配处理器.该处理器的两个内核通过任务调度模块进行耦合,以并行方式或流水线方式协同工作,目的在于减少遍历ABNF规则树的回溯情况和程序执行的分支情况,提高处理器的访存效率.该方案在可编程逻辑器件(FPGA)上进行了功能验证,结果表明,这种双核构架的设计方法能够有效地提高字符串模式匹配处理的并行程度.     

基于CUDA的并行碰撞检测算法研究

碰撞检测是计算机图形仿真中的关键问题之一。尽管研究人员提出了许多优秀的碰撞检测算法,但是随着仿真场景规模的增大,在单处理器上实现的碰撞检测算法已经难以达到实时性的要求。因此,当前研究的核心问题是如何提高碰撞检测的速度。在对已有算法研究分析的基础上,提出了一种基于层次包围盒的并行碰撞检测算法。该算法的核心思想是用多处理器并行遍历层次树以避免单处理器需要两棵树相互遍历的情况,并提出以并行的方式生成层次包围盒树来进一步提高算法效率。结合CUDA平台提供的并行计算解决方案,整个算法在图形处理器上得以实现。结果表明,该算法显著地提高了碰撞检测的速度,满足实时性的需求。     

多GPU节点下的NAMD测试与分析

运用大规模分子动力学并行开源代码NAMD测试了深腾7000GGPU集群的性能.在配备有Teslac1060与双路4核CPU的节点上,分别对烟草花病毒(STMV),血脂蛋白(ApoA1)与Tiny这3类分子进行了单节点与多节点的测试.测试结果表明:GPU相较于CPU能获得平均2至8倍性能提升,可为大规模分子的模拟提供高性价比的解决方案.然而,多节点下GPU的利用率却有所降低,其并行扩展性能也受到一定限制.另外,一些重要的分子结构构建的指标,如范德华力静止点的值也在一定程度上影响着模拟性能.     

面向CPU+GPU异构计算的SIFT

依据图形处理器(GPU)计算特点和任务划分的特点,提出主从模型的CPU+GPU异构计算的处理模式.通过分析和定义问题中的并行化数据结构,描述计算任务到统一计算设备架构(CUDA)的映射机制,把问题或算法划分成多个子任务,并对划分的子任务给出合理的调度算法.结果表明,在GeForce GTX 285上实现的尺度不变特征变换(SIFT)并行算法相比CPU上的串行算法速度提升了近30倍.     

基于GPU的大规模基因片段并行匹配的方法

后缀树和后缀数组广泛用于生物信息学领域中,特别是通过启发式算法在对DNA基因片段进行匹配的阶段.本文提出了在GPU的平台下,利用多核和超多核体系构成的后缀树以及后缀数组并行匹配大规模基因片段,从而加速基因搜索匹配过程.相对于后缀树,后缀数组二分搜素算法具有内存占用少,缓存使用率高等优点.在GPU的性能评估中,后缀数组执行效率明显超过后缀树,后缀数组占用的空间仅为后缀树的20%~30%.相对于CPU的串行实现,后缀树组达到了约99倍的加速比.实验结果表明在基因片段匹配的过程中,基于GPU的后缀数组二分搜索是一种高效且实用的方法.     

基于spark框架的DBSCAN文本聚类算法

针对DBSCAN算法性能上的瓶颈以及内存和I/O上的消耗严重,提出了一种大数据计算框架的并行聚类方案.选用Spark计算框架对DBSCAN算法进行并行化改进,利用SNN相似度图解决DBSCAN算法对高维数据密度定义模糊的问题,并且将DBSCAN算法运行在spark计算平台上,缓解了内存的不足.实验结果证明,该解决方案相对于单机的DBSCAN算法,聚类精度没有下降,并且通过横向的添加节点增加了运行内存,在缓解内存紧张的前提下降低了算法运行时间,和基于Hadoop的DBSCAN算法相比也有较好的加速比.     

基于GPU加速的全源对最短路径并行算法

针对最短路径算法处理大规模数据集低效的问题，提出了基于图形处理器（Graphics Processing Unit,GPU）加速的全源对最短路径并行算法.首先通过优化矩阵乘法算法实现了在工作组内和组间进行并行运算数据，然后减少了非规则行造成的工作项分支，最后降低了工作项对邻接矩阵计算条带存储资源的访问延时.实验结果表明，与基于AMD Ryzen5 1600X CPU的串行算法、基于开放多处理（Open Multi-Processing, OpenMP）并行算法和基于统一计算设备架构（Compute Unified Device Architecture, CUDA）并行算法相比，最短路径并行算法在开放式计算语言（Open Computing Language, OpenCL）架构下NVIDIA GeForce GTX 1 070计算平台上分别获得了196.35、36.76和2.25倍的加速比，验证了提出的并行优化方法的有效性和性能可移植性.     

移动环境下Huffman索引树在多信道广播中的应用研究

移动计算环境中,为使移动客户能有效地从广播信道中获取数据,该文在多信道广播中提出了基于Huffman树的索引模型,并提出了基于Huffman索引树的索引节点组织方式.最后对Huffman索引树进行了性能分析和比较,表明该模式能有效的提高移动数据广播的性能.     

冷冻电镜三维重构在CPU-GPU系统中的并行性

为了有效地发掘和利用异构系统在应用和体系结构上的并行性,以冷冻电镜三维重构为例展示如何利用应用程序潜在的并行性.通过分析重构计算所有的并行性,实现了将动态自适应的划分算法用于任务在异构系统上高效的分发.在曙光星云系统的部分节点系统(32节点)上评估并行化的程序性能.实验证明:多层次的并行化是CPU与GPU异构系统上开发并行性的有效模式;CPU-GPU混合程序在给定问题规模上相对单纯CPU程序获得2.4倍加速比.