【作者】 周毅；

【导师】 何发智；

【作者基本信息】 武汉大学 ， 计算机应用， 2016， 博士

【摘要】 由于受到半导体工艺、功耗、指令级并行等各种因素的限制,中央处理器体系结构朝着并行方向发展,比如多核架构。与此同时,图形处理器也从专用的图像渲染设备进化成通用并行计算设备,并被重新定义为众核架构。并行硬件架构的高速发展,使处理器的理论峰值性能极大提升,这为大规模科学和工程计算提供了非常好的机遇。然而由于处理器体系结构的多样性,和并行编程的复杂性,传统的算法如何并行化以高效发挥硬件能力,成为一个严峻的挑战。随着高级并行编程模型(如OpenCL, CUDA和Direct Compute)的相继推出,并行程序设计的难度在一定程度上有所降低,简单的移植串行算法到并行平台执行已经不再是难题。但由于并行处理器结构的不同、算法计算特点和编译器优化差异的影响,如何针对特定并行架构设计优化的并行算法仍然是学术界研究的热点。为了解决并行算法针对特定并行架构优化的问题,本文立足于基于多核CPU和众核GPU体系结构,着重针对并行优化算法做了深入的研究。本文采用理论与实验研究相结合的方法,一方面分析了多核CPU和众核GPU的不同体系结构,探讨实现多核CPU和众核GPU的并行计算方法；另一方面结合经典并行算法,研究其在多核CPU和众核GPU体系结构上的优化,并利用标准算例验证所提出方法的有效性。具体工作及创新点归纳为以下四方面：(1)基于动态策略的GPU蚁群算法针对目前GPU蚁群优化算法求解问题规模受限于GPU片上芯片存储器大小,及其加速比不显著的情况,提出了一种基于动态策略的GPU蚁群算法。该算法相比之前的GPU蚁群算法,增加了求解的规模,解决了求解更大规模的问题；通过优化的算法设计,改进了算法的执行效率。(2)基于多核SIMD CPU的蚁群算法针对多核CPU上的并行蚁群模型和算法优化进行了深入的研究。在传统的任务并行模型基础上,研究了算法的向量化及其性能,并与高性能的GPU实现进行了实验对比。该蚁群算法在多核SIMD CPU上的性能比在GPU上更优,尽管在理论性能上面CPU远弱于GPU,但此表现反映出了多核CPU在处理不规则和随机性算法方面的优势。(3)GPU并行迭代局部搜索算法性能优化针对目前GPU并行化的元启发式算法研究缺少量化性能评价方法的情况,以典型的迭代局部搜索算法为研究对象,及其GPU并行化相关工作开展研究,提出了一种优化的GPU迭代局部搜索算法。该算法的优化方法是通过量化性能分析模型确定其在GPU上的瓶颈,并进行了针对性的优化处理。最终获得了在元启发式算法上具有有效性的并行算法量化性能分析应用,这对于这类并行算法的优化具有指导性的意义。(4)基于CPU-GPU协同并行图像卷积算法以图像处理领域的图像卷积做为研究对象,研究了多核CPU与众核GPU的协同并行模型,提出了一种新的CPU/GPU协同并行图像卷积算法,设计了静态和动态两种CPU/GPU协同并行计算图像卷积方法。由于卷积处理时容易忽视CPU高计算性能,导致并行算法仅仅利用了GPU的并行计算特性,而大部分CPU线程都处于闲置状态。此外,传统的CPU和独立GPU之间通过PCI-E总线进行数据传输,也存在一定的通讯开销。因此本文充分利用单芯片CPU/GPU的并行计算性能,提出基于CPU/GPU协同并行图像卷积算法,获得高效的CPU/GPU协同并行计算解决方案。更多还原

【Abstract】 Due to the constraint of semiconductor technology, power and Instruction-level parallelism, the performance of center processing units (CPUs) is enhanced by parallel processing architecture, e.g., multi-core. Meanwhile, graphic processing units (GPUs) have evolved from fixed function rendering devices to programmable and parallel processors. And the architecture of GPUs is redefined as many-core. The theoretical peak performance of parallel processors is dramatically increased, which brings opportunities for the development of large scale scientific and engineer computation. However, since the architecture of parallel processors is various and parallel programming is complex, algorithm parallelization that is suitable for specific parallel hardware is a big challenge.Since the emerging of high-level parallel programming model, e.g., OpenCL, CUDA and Direct Compute, parallel programming is less complex than before. And simply porting existing algorithms to new hardware is not enough as a scientific goal. But due to different characteristics of parallel architectures, computational features of parallel algorithms and discrepancies of the compiler optimizations, How to parallelize algrithms on a specific parallel arichitecture with optimized performance is a topic of interest.In order to solve the problems in parallel algorithm optimization on a specific parallel arichitecture, this thesis is based on the multi-core CPU and many-core GPU architectures to research parallel optimization algorithms. The research methods are both theory and experiment. On one hand, the multi-core CPU and many-core GPU architectures are investigated and analyzed. And the parallel implementation issues on these architectures are also researched. On the other hand, the optimization approaches of parallel algorithms on these architectures are studied. And the effectiveness of the approaches is validated with public test datasets. The work and major contributions are as follows:(1) Dynamic strategy based Parallel Ant Colony Optimization on GPUsExisting GPU-based ant colony optimization algorithms (ACOs) face on-chip memory limitations and not significant speedups toward CPU. We propse a dynamic strategy based ACO on GPUs, which could solve larger problems than existing algorithms and is optimized with improved efficiency.(2) Parallel ACO on multicore-SIMD CPUsWe futher study parallel ACO models on multicore-SIMD CPUs. Based on the traditional task parallel ACO model, we propose vectorized ACO models and their performance issues. We compare our CPU-based ACO algorithm with existing high performance GPU ACOs, and the results demonstrate that the CPU-based algirthm is better than GPU-based one. Considering the theoratic peak performance of the GPU is far beyond the CPU, we could deduce that multicore-SIMD CPU is more suitable for irregular and random-based algorithms than the GPU.(3) Optimization of parallel iterated local search (ILS) algorithms on GPUsWe propose an optimizaiton approach with quantitative performance analysis for parallel ILS algorithms. ILS algorithm is a typical single-solution based metaheuristic algorithm. We research the parallization of ILS on GPUs and ultilize a quantitative performance analysis model to identify the bound factor of a GPU-based ILS algorithm. After we optimize the algorithm according to the bound factor. The experimental results show the effectiveness of our approach. To be general, our method could guide the optimization for other parallel algorithms.(4) CPU-GPU collaborative computing image convolution filtering algorithmWe research a one of the most important algorithm in image processing. We propose a CPU-GPU collaborative computing model for parallel image convolution algorithm. Two collaborative approaches, static task assignment and dynamic task assignment, are presented and evaluated. The existing GPU-parallel image convolution algorithms ignore the high performance computing feature of the modern CPU, which causes many CPU cores in idle status. Besides, a discrete GPU communicates with a CPU through PCI-E bus, which introduces considerable overhead. Therefore, we exploit both CPU and GPU in parallel image convolution computation. The experimental results demonstrate this approach could ultilize both the CPU and GPU computing power, and it has a strong potential.更多还原