基于多核并行的海量数据序列模式挖掘*

为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行序列模式挖掘算法。该算法采用数据并行与任务并行相结合的策略,在各处理器核生成局部序列模式后,再与其他处理器核协同,以最终获得所有的全局序列模式。算法通过并行局部归约技术消除了局部序列的重复生成与计算,并可结合静态与动态任务分配机制解决处理器的负载不均衡问题。理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。     

多核同时多线程处理器的线程调度器设计

多核同时多线程处理器(SMT_PAAG)是用于图形、图像及数字信号处理的一种多核处理器。基于这种处理器提出了一种硬件线程调度器,该调度器采用同时多线程技术,最多可同时执行四个线程,支持八个线程阻塞模式下的快速上下文切换。这样避免了因阻塞带来的等待问题,能够有效提高处理器的工作效率和资源利用率。通过在处理器上运行图形处理算法进行性能评测。结果表明,SMT-PAAG处理器通过挖掘指令级并行和线程级并行,将处理器的性能提高了69.25%。     

嵌入式ARM多核处理器并行化方法的研究

随着嵌入式处理器技术的不断发展以及人们对嵌入式设备性能的要求越来越高,嵌入式处理器由单核时代进入多核时代。然而,传统嵌入式系统软件开发方法还是基于单核模式,并没有利用嵌入式多核处理器多核并行化的特点,没有充分发挥嵌入式多核处理器的性能。虽然在PC平台上,多核并行化方法相对更成熟,但嵌入式多核处理器在处理器数目、Cache以及总线等方面有很大不同,嵌入式平台多核并行化并不能借助PC平台的实践方法,因此基于嵌入式平台研究多核并行化的方法是很有意义的。     

分布环境中的并行频繁模式挖掘算法

频繁模式的并行挖掘算法是数据挖掘中重要的研究课题。目前已经提出的并行算法大多是基于Apriori或基于FP-tree。由于两者的固有局限性,而且在计算过程中需要多次同步,因而具有较低的性能。文章提出了一种基于分布数据库的并行挖掘算法。该算法尽可能地让每个处理器独立地挖掘,每个处理器基于前缀树采用深度优先搜索的策略挖掘局部频繁模式集,并通过相关性质尽量减少候选全局频繁模式的规模,减少网络的通信量和同步次数以提高挖掘效率。     

基于GPU的位并行多模式串匹配研究

图形处理器(GPU)具有较强的单一运算能力及高度并行的体系结构。根据上述特点,选择基于位并行技术的多模式串匹配算法M-BNDM,将其移植到GPU上加以实现和优化。通过对需要处理的数据进行预处理,将串匹配的过程简化为更适合CUDA计算数据的位操作。对基于CUDA架构的并行串匹配算法的性能影响因子进行分析。实验结果表明,与同等CPU算法相比,该算法能够获得约十几倍的加速比。     

一种有效的并行序列模式挖掘算法

为解决共享存储的并行计算环境下挖掘序列模式时存在的处理器负载不平衡及缺少有效剪枝策略的问题,提出采用动态任务分配的办法来平衡处理器之间的工作负载,利用并行局部剪枝技术消除投影数据库的重复生成与计算以提高挖掘效率。设计一种基于共享存储SMP系统的并行序列模式挖掘算法PFSPAN。算法分析和实验结果表明,PFSPAN能够有效地挖掘序列模式。     

面向多核处理器的视频编码并行加速算法综述

视频编码算法复杂度的提高,对处理器性能提出了更高的需求,多核处理器为媒体数据处理提供了有力的平台。分析了视频编码标准算法的特点,总结视频编码加速的方法,按照对称多核处理器、不对称多核处理器以及混合式多核处理器的分类,介绍基于多核处理器的并行视频编码设计方法以及典型例子;总结基于多核处理器进行视频编码设计可能遇到的问题,并指出了未来的研究方向。     

一种挖掘多核处理器存储级并行的算法

多核处理器中,各个处理器核之间可以并发地进行外部存储访问,提供不同于单处理器的存储级并行(memory level parallelism)能力.不规则应用中的循环,传统的并行方法难以识别其并行性,不能充分利用多核处理器存储级并行能力和并行计算能力.对基于软件开发多核处理器存储级并行进行了讨论,提出一种前瞻并行多线程算法LLSM(loop level speculative mssultithreading).LLSM对不规则应用中的循环进行并行化,在多核处理器上的测试数据表明:该算法能够有效地挖掘多核处理器的存储级并行能力和计算能力,同时指出多核环境下存储级并行计算公式需要考虑线程同步开销.     

基于以太网的TMS320C6713并行系统设计

在某大型测试系统的设计中,为了实现多只处理器问灵活的数据交换及并行处理,提出了基于Ethernet的多处理器并行系统设计;通过FPGA实现了以太网交换机的介质无关接口与处理器同步串口的接口转换,从而实现了处理器接收和发送网络数据．在此基础上实现了多处理器的并行数据处理。为实现高效的对多处理器系统的开发调试,提出了基于Ethernet的多处理器网络调试方案,最后对系统的可扩展性进行了分析。     

基于可重构处理器的并行优化算法

为挖掘可重构处理器的内在并行性,需要编译器通过分析程序的并行性来决定可重构处理器硬件最好的执行模式。为此,提出一种基于可重构处理器的并行优化算法。将有向无环图的并行计算部分映射到可重构处理器上,对任务实现3个不同层次的并行性(指令级并行、循环级并行、线程级并行)。测试结果表明,该算法使得可重构处理器在处理任务时比未用并行优化算法的性能提升1.2倍左右。     

并行I/O技术在气候数值模式中的应用研究

在气候变化数值模拟工作中,气候数值模式运行效率主要受到计算效率和I/O效率的共同影响。目前,模式计算部分已经基本实现并行,计算效率显著提升。随着气候数值模式时空分辨率的提高,对I/O效率的需求也不断增加,数据并行I/O技术已经成为提高模式整体运行效率的有效方法之一。文中深入分析了BCC_AGCM模式串行I/O算法及NetCDF数据结构特点,采用基于MPI-IO的高层I/O库对模式I/O算法进行并行优化,优化后可支持多类气象要素并行输出,输出效率明显提升。为我国应对气候变化数值模式的运行效率优化工作,进行了有益的技术探索和积累。     

基于闪存的混合存储系统缓冲区管理算法

由于基于闪存的混合存储系统充分利用了闪存的高速随机读和磁盘的快速顺序写的特性,近年来已经成为了数据库管理系统的二级存储层的高效存储模式,但其I/O访问开销是一个继续提高存储性能的瓶颈.为了降低混合存储系统的I/O访问开销,提出了一种自适应缓冲区管理算法DLSB.该算法根据数据页的逻辑代价和物理代价进行自适应的数据域选择;并在选择的数据域中,比较闪存队列和磁盘队列容量的实际值与理想值来确定数据页的置换,达到了提高I/O访问效率的目的.实验结果表明,该算法有效且可行,显著降低了混合存储系统的I/O访问开销.     

一种改进的Apriori算法

针对Apriori算法对数据库的扫描次数过多、系统的I/O负载大和产生大量的无关中间项集等弊端,提出了一种改进的Apriori算法。该算法通过加入用户兴趣项,减少候选项集的产生;打破了传统的算法实现步骤减少了数据库的扫描次数,降低了系统I/O负载;构建了用户兴趣度模型增加了算法生成强关联规则的可读性,提高了算法的效率。实验表明,改进的Apriori算法能有效地提高运行速度和效率。     

地理栅格数据的并行访问方法研究

在海量地理栅格数据处理中,数据I/O性能是影响处理算法程序整体性能的关键。目前针对地理栅格数据 I/O优化问题的研究成果还很有限,通过对并行程序中的数据I/O模式进行深入分析,结合栅格数据逻辑模型和物理 模型的特点,提出了面向地理栅格数据的并行I/O框架;基于消息传递模型,实现了4种并行访问方法。实验证明,并 行访问方法优于传统的串行访问方法和分时多进程访问方法。该研究成果可以提高并行栅格处理程序的I/()访问效 率,进而提高其整体并行性能。     

MapReduce连接查询的I/O代价研究

数据的指数级增长给数据管理和分析带来了严峻的挑战.连接查询是数据分析中一种常用运算,而MapReduce是一种用于大规模数据集并行处理的编程模型,研究基于MapReduce的连接查询代价评估和查询优化,有着学术意义和应用价值.MapReduce连接查询算法的性能主要取决于I/O代价(包括本地和网络I/O),而I/O代价与数据集以及连接运算的特征参数相关,通过对二元连接的I/O代价评估可以优化多元连接执行计划.基于此,首先提出了二元连接查询的I/O代价模型;随后,对现有二元连接算法进行形式化定义和简单扩展,归纳出6种基于MapReduce连接查询算法,并通过算法白盒分析定义它们的I/O代价函数;最后,提出一种多元连接最优执行计划的选择算法.通过实验表明I/O代价模型的正确性且能够准确地反映算法的性能优劣.     

Performance Evaluation of a Parallel Pipeline Computational Model for Space-Time Adaptive Processing

This paper presents further results on the design and implementation of various optimizations based on our earlier work of developing a parallel pipelined model for the computational intensive applications that have multiple processing tasks. Performance evaluation of this model was done by using a real-time airborne radar application that employs a Space-Time Adaptive Processing (STAP) algorithm. This paper focuses on the following four issues: (1) The tradeoffs between increasing the throughput and reducing the latency are examined in more detail when allocating processors among different processing tasks. (2) A multi-threaded design is incorporated into the pipeline model and implemented on a massively parallel computer with symmetric multi-processor nodes, which shows enhanced performance. (3) The disk I/O is incorporated into the parallel pipeline to study its effect on performance in which two I/O task designs have been implemented: embedding I/O in the pipeline or having a separate I/O task. By using a double buffering approach together with the asynchronous I/O, the overall pipeline performance scales well as the number of processors increases. (4) From the comparison of the two I/O implementations, it is discovered that the latency may be improved when merging multiple tasks into a single task. The effect of reorganizing the task structure of the pipeline is discussed in detail. All the performance results shown in this work demonstrate the linear scalability the parallel pipeline model can achieve using a production radar application. Although this paper focuses on the implementation of the parallel pipeline model and uses the results from a STAP application to support the claims of the discovered properties for this pipeline, this model is also applicable to many other types of applications with similar computational characteristics.     

大规模虚拟地形数据多线程异步调度算法

为了实现大规模虚拟地形环境的实时绘制,提出一种海量地形数据实时调度算法。本文算法基于传统四叉树结构对地形数据进行组织和索引。在此基础上,运用Hilbert填充曲线对数据进行存储优化。然后设计基于I/O完成端口（I/O Completion Port,IOCP）的异步机制,结合多线程技术实现了I/O操作及数据加卸载的合理运作。最后,选取单线程同步I/O算法与本文算法进行实验对比。结果表明,本文算法具有高效的数据调度性能,可以满足大规模地形实时绘制的需求。     

全球谱模式T213L31在PC机群系统上的并行实现

本文研究以PC作为结点的Linux机群系统上实现全球谱模式T213L31并行计算的方法,给出了谱模式的三维置换并行算法和半拉格朗日时间积分格式的按需通讯并行实现方法,同时提出了适合于机群系统的并行I/O实现。该实现在由四个双CPU结点组成的Linux机群环境下取得了良好的运行效果。     

面向SoC的系统级并行划分方法

为缩短复杂SoC系统的设计周期,降低系统设计的复杂性,提出了一种SoC系统级的并行划分方法.引入带有信号激活率和输入输出延时的过程模型图,为SoC系统构建模型.设计一启发式算法对该过程模型图进行并行划分,同时,该算法能解决有环图的划分问题.通过大量的实验证明,划分结果同要求吻合,说明该划分方法是可行、有效的.     

基于SR-IOV的IO虚拟化技术

虚拟技术经过多年的发展,CPU虚拟化与内存虚拟化均已成熟,而I/O虚拟化方面却未出现大的变化,成为当前虚拟技术性能提高的瓶颈。近期Intel公司提出的SR-IOV技术通过在硬件层增加虚拟支持,与原有I/O虚拟化中采用的Passthrough技术相结合,极大的提高了物理设备的使用效率和客户域的I/O性能。文章在总结虚拟技术中采用过的I/O模型基础上,分析了SR-IOV技术的实现和特点。