基于GPU的多层次并行QR分解算法研究

QR分解作为一个基本计算模块,广泛应用在图像处理、信号处理、通信工程等众多领域.传统的并行QR分解算法只能挖掘计算过程中的数据级并行.在分析快速Givens Rotation分解特征的基础上,提出了一种多层次并行算法,能够同时挖掘计算过程中的任务级并行和数据级并行,非常适合于以图形处理器(GPU)为代表的大规模并行处理器.同时,采用GPU的并行QR分解算法可以作为基本运算模块被GPU平台上的众多应用程序直接调用.实验结果显示,与CPU平台上使用OpenMP实现的算法相比,基于GPU的多层次并行算法能够获得5倍以上的性能提升,而调用QR分解模块的奇异值分解(SVD)应用可以获得3倍以上的性能提升.     

多核处理器上的并行联机分析处理算法研究

近年来,计算机硬件技术获得了很大发展,尤其是大内存和多核,但算法效率并没有随着硬件技术的发展而提高,根本原因是没有充分利用CPU缓存以及单线程程序设计的局限性。在联机分析处理领域,数据方体计算是一个重要而又耗时的操作,因此如何提高数据方体的计算效率是该领域的一个研究难点。探讨了基于多核CPU特征的并行立方体算法,提出了MT-Multi-Way(multi-threading multi-way)和MT-BUC(multi-threading bottom-up computation)算法。该算法通过有效的数据划分和多线程协作,避免了Cache竞争,并确保了负载均衡,获得了近似线性加速比。以上述算法为基础,提出了处理立方体算法的多核框架,包括数据划分策略及递归算法的多核处理,指导立方体算法的并行化。     

多核CPU和GPU加速分子动力学模拟

在多核中央处理器(CPU)—图形处理器(GPU)异构并行体系结构上,采用OpenMP和计算统一设备架构(CUDA)编程实现了基于AMBER力场的蛋白质分子动力学模拟程序。通过合理地将程序划分为CPU单线程、CPU多线程和GPU多线程执行部分,高效地利用了计算机的处理能力。性能测试结果表明,相对于优化后的CPU串行计算,多核CPU-GPU异构并行计算模型有强大的性能优势,特别是将占整个程序执行时间90%的作用力的计算移植到GPU上执行,获得了最高可达12倍的计算加速比。     

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

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

基于图形处理器的边缘检测算法

边缘检测是一种高度并行的算法,计算量较大,传统的CPU处理难以满足实时要求。针对图像边缘检测问题的计算密集性,在分析常用边缘检测算法的基础上,利用CUDA(Compute Unified Device Architecture,计算统一设备架构)软硬件体系架构,提出了图像边缘检测的GPU(Graphics Processing Unit,图形处理器)实现方案。首先介绍GPU高强度并行运算的体系结构基础,并将Roberts和Sobel这两个具有代表性的图像边缘检测算法移植到GPU,然后利用当前同等价格的CPU和GPU进行对比实验,利用多幅不同分辨率图像作为测试数据,对比CPU和GPU方案的计算效率。实验结果表明,与相同算法的CPU实现相比,其GPU实现获得了相同的处理效果,并将计算效率最高提升到了17倍以上,以此证明GPU在数字图像处理的实际应用中大有潜力。     

多核处理平台上任务图模型的并行调度策略研究

凭借着高性能,低功耗的特性,多核处理器已经占据了目前的主要市场.提出一种多核处理平台上基于任务图模型的调度策略.建立了多核平台上任务图的空间与时间并行调度模型;针对任务图的空间并行与时间并行调度模型提出了并行节点合并、分配的优化算法与流水线并行的优化算法.最后,提出将优化的空间与时间并行调度技术相结合的并行调度策略.通过实验验证,本文提出的算法比其他多核并行调度算法降低了处理器核心间的通信与同步开销,提高了系统的计算效率与吞吐量.     

基于GPU的皮肤变形算法

为提高基于实例的皮肤变形算法的效率和速度,对加权姿态空间变形(WPSD)等算法进行了研究.WPSD中需要的逐顶点计算可以在GPU上以单指令流多数据流(SIMD)方式并行执行.并行顶点计算一般在GPU顶点处理器中执行,但是更进一步的并行操作是可以由片段处理器来获取到的.提出了一种基于GPU片段处理器实现的并行变形算法.每个顶点的关节权值可以由样本姿态自动的计算出,因此减少了手动操作,提高了WPSD等皮肤变形算法的质量.     

基于图形处理器的Cuboid算法

近年来,基于图形处理器的通用计算获得了广泛关注,并在多个领域取得了进展.内存OLAP减少了磁盘I/O,但基于单核或多核CPU的计算能力及cache miss成为新的性能瓶颈,从而无法保证好的效率.而图形处理器由于其众多核和高带宽能够很好地适应OLAP计算特性.通过图形处理器来加速任一cuboid的计算,从而提高整个内存OLAP系统的性能.提出了基于图形处理器的分块并行算法,并对算法进行了优化及讨论了数据稀疏和数据分布倾斜等不同条件下的算法.算法通过扩展可以突破内存限制,组成磁盘、内存、显存三级流水线,适应海量数据计算;同时算法也可以作为计算整个cube的基础.通过实验比较,基于图形处理器的算法明显优于四核CPU算法.     

基于通用多核处理器平台的并行基因表达式编程算法

基因表达式编程(Gene Expression Programming, GEP)是一种计算量大且通用性强的新型进化算法,其传统计算形式不能充分利用目前主流的多核处理器。为提高算法效率,提出了基于通用多核处理器平台的并行基因表达式编程算法(Parallel Gene Expression Programming Based on General Multi-core Processor, PGEP-MP)。主要工作包括:O)分析通用多核处理器平台下并行基因表达式编程算法的机理;(2)利用MPI和()pcnMP混合编程模型设计基于通用多核处理器平台的基因表达式编程算法的粗粒度与细粒度相结合的并行模型;(3)提出改进PEEP-MP算法效率的进化策略;(4)通过对函数挖掘和分类的实验证明,PEEP-Ml〕算法提高了函数挖掘和分类的效率,在并行双核处理器数为4的情况下,PEEP-MP的平均并行加速比分别是传统GEP算法的4. 22倍和 4. 06倍。     

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

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

Parallel cube computation on modern CPUs and GPUs

With the popularity of column-store databases, modern multi-core CPUs, and general-purpose computing on graphics processing units (GPGPUs), there will be radical changes in how processing is done in the online analytical processing (OLAP) and data warehousing fields. Cube computation is a core and time-consuming problem which has been researched extensively. However, most of the algorithms have been proposed without considering the prevalent multi-core architectures and column storage. This paper presents a new parallel cube algorithm that takes advantage of multi-core architectures. We first propose a cache-conscious bottom-up computation (BUC) algorithm called CC-BUC that adopts an integrated bottom-up and breadth-first partitioning order. Each dimension is separately stored and processed. In processing each dimension, breadth-first data scanning and results outputting reduce memory I/O and enhance cache locality. Cache misses are limited in a dimension scope, and translation lookaside buffer (TLB) misses are reduced. Based on CC-BUC, we give a multi-core architecture-based cube algorithm called MC-Cubing. Multiple partitions are processed simultaneously and multiple threads undergo parallel execution inside each partition. MC-Cubing is consistent with multi-core architectures and high parallelism. The layout and associated algorithms take advantage of single instruction, multiple data (SIMD) instructions and thread-level parallelism (TLP). We implement and demonstrate the effectiveness of MC-Cubing on two multi-core architectures: multi-core CPUs and GPUs. Experimental results show that the MC-Cubing algorithm can speed up nearly six times faster than BUC in real datasets.     

Domain decomposition method for unstructured meshes in an OpenMP computing environment

In this paper, an efficient unstructured mesh calculation method in an OpenMP parallel computation using multi-core processor is proposed. This is a new domain decomposition method with two characteristics. The first characteristic is to define the size of the sub-block in the computation domain by the size of the cache memory in each core. The second one is to reduce idle time by distributing a defined sub-block for each core appropriately. Using the proposed method, a computation on compressible flow around a plane was able to achieve speed-up more than about 20% in comparison with a conventional method.     

Cache-Conscious Data Cube Computation on a Modern Processor

As the speed gap between main memory and modern processors continues to widen,the cache behavior becomes more important for main memory database systems(MMDBs).Indexing technique is a key component of MMDBs. Unfortunately,the predominant indexes—B~+-trees and T-trees—have been shown to utilize cache poorly,which triggers the development of many cache-conscious indexes,such as CSB~+-trees and pB~+-trees.Most of these cache-conscious indexes are variants of conventional B~+-trees,and have better cache perf...     

基于BMP架构的多核差异化运行技术研究

随着高速网络及多核处理器技术的快速发展,业务应用的复杂度也在日益增加。为了保证复杂业务的吞吐量及实时性,基于BMP架构提出了多核环境下操作系统任务差异化运行方案,将多核处理器分为数据面与控制面,数据面核的处理能力提供给高性能要求的循环任务使用,控制面核的任务处理不影响数据面核的性能。方案在Linux内核上进行了改造实现,实验结果表明,可有效提升复杂业务实时响应及业务吞吐能力。     

多核并行技术在分子动力学模拟中的应用

为了充分利用多核处理器资源,研究了一种用于分子动力学模拟中的多核并行技术。在多核处理器上利用OpenMP技术实现多线程创建与同步、动态设置子线程的调度运行方式以及负载均衡以减少子线程执行等待时间。通过对不同分子体系结构下的动力学模型测试,得出在不同子线程下并行计算的时间,并且得到了良好的性能加速比。实验结果表明,采用OpenMP并行技术可有效地提高电荷求解过程在分子动力学模拟运算中的时间效率,以及多核计算机资源的利用率。     

面向基带处理的异构多核架构软硬件平台设计

通过研究现代通信系统集中化处理架构中基带处理单元(BB U)的特点,将异构多核处理器应用于BB U中,并提出将物理层算法与控制分离的观点.在ARM+DSP的异构多核中,ARM完成物理层控制,DSP完成物理层算法的功能,提升了BB U基带处理能力,并给出完整的BB U硬件架构以及功能实现.提出了一种应用于基带处理中的异构多核软件架构,从软件层面上实现了对底层硬件的虚拟化,引入了中间件的概念,屏蔽了ARM与DSP操作系统上的差异,并给出基于Linux的非对称系统(AMP)的构建及移植方法,包括异构多核的BootLoader、AMP系统的设计与移植.     

面向同构多核处理器的节能任务调度方法

对于运行在同构多核处理器上的周期性硬实时任务,设计了一个基于动态电压调节的节能调度方法。该方法首先将计算任务按照周期数降序排序并基于计算任务调度长度最短的原则安排任务映射。然后将各个处理核上具有最小通讯时间的计算任务设置为最后执行的计算任务而其它计算任务顺序保持不变。在初始映射中所有计算任务都被分配最高频率的情况下,每个处理核上的计算任务在执行时间扩展过程中确定最佳的计算任务顺序。基于 Intel PXA270的功耗模型,以几个随机任务集作实验。结果表明提出的方法能够有效地降低多核处理器的能量。     

Enabling Highly Efficient k-Means Computations on the SW26010 Many-Core Processor of Sunway TaihuLight

With the advent of the big data era, the amounts of sampling data and the dimensions of data features are rapidly growing. It is highly desired to enable fast and efficient clustering of unlabeled samples based on feature similarities. As a fundamental primitive for data clustering, the k-means operation is receiving increasingly more attentions today. To achieve high performance k-means computations on modern multi-core/many-core systems, we propose a matrix-based fused framework that can achieve high performance by conducting computations on a distance matrix and at the same time can improve the memory reuse through the fusion of the distance-matrix computation and the nearest centroids reduction. We implement and optimize the parallel k-means algorithm on the SW26010 many-core processor, which is the major horsepower of Sunway TaihuLight. In particular, we design a task mapping strategy for load-balanced task distribution, a data sharing scheme to reduce the memory footprint and a register blocking strategy to increase the data locality. Optimization techniques such as instruction reordering and double buffering are further applied to improve the sustained performance. Discussions on block-size tuning and performance modeling are also presented. We show by experiments on both randomly generated and real-world datasets that our parallel implementation of k-means on SW26010 can sustain a double-precision performance of over 348.1 Gflops, which is 46.9% of the peak performance and 84% of the theoretical performance upper bound on a single core group, and can achieve a nearly ideal scalability to the whole SW26010 processor of four core groups. Performance comparisons with the previous state-of-the-art on both CPU and GPU are also provided to show the superiority of our optimized k-means kernel.