基于共享存储和Gzip的并行压缩算法研究

Gzip无损压缩算法.尽管gzip算法能够取得很好的压缩比,但它在分析和压缩编码的过程需要进行大量的计算.为了缩短压缩时间,提出了一种基于共享存储的并行压缩策略,采用OpenMP标准和"生产者/消费者"模型实现了gzip的并行压缩版本.在Beowulf集群中的一个SMP节点(双CPU)和曙光天阔服务器(4路双核)上的测试表明,并行化的gzip程序取得了极大的性能提升,尤其是大文件的压缩.

Performance metrics in a hybrid MPI-OpenMP based molecular dynamics simulation with short-range interactions

We discuss the computational bottlenecks in molecular dynamics (MD) and describe the challenges in parallelizing the computation-intensive tasks. We present a hybrid algorithm using MPI (Message Passing Interface) with OpenMP threads for parallelizing a generalized MD computation scheme for systems with short range interatomic interactions. The algorithm is discussed in the context of nano-indentation of Chromium films with carbon indenters using the Embedded Atom Method potential for Cr-Cr interaction and the Morse potential for Cr-C interactions. We study the performance of our algorithm for a range of MPI-thread combinations and find the performance to depend strongly on the computational task and load sharing in the multi-core processor. The algorithm scaled poorly with MPI and our hybrid schemes were observed to outperform the pure message passing scheme, despite utilizing the same number of processors or cores in the cluster. Speed-up achieved by our algorithm compared favorably with that achieved by standard MD packages. (C) 2013 Elsevier Inc. All rights reserved.

Paralelización mediante OpenMP de segmentación de imágenes para el análisis de materiales bidimensionales

A lo largo de este Proyecto de Fin de Carrera se ha implementado una versión paralela mediante OpenMP de una aproximación al algoritmo de seg- mentación de imágenes level set. El fin de esta segmentación es la extracción de ciertas características de las imágenes necesarias para el cliente con el que se trabaja a lo largo de este proyecto. Además, se ha realizado un estudio previo de los tipos de técnicas de segmentación existentes y se han realizado pruebas experimentales con la paralelización realizada, con el fin de analizar la mejora realizada frente al algoritmo en serie.

有限元单元计算子程序的OpenMP并行化

Intel和AMD双核乃至4核处理器的推出,使得并行计算已经普及到PC机。为了充分利用多核,需要对原有程序进行多线程改造,使其充分利用多核处理带来的性能提升。该文利用共享存储编程的工业标准OpenMP对有限元方法涉及的单元计算子程序进行了并行化实现。在机群的一个双CPU的SMP节点上的测试表明,共享并行化使得该单元子程序的性能提高了一倍。

有限元单元计算予程序的OpenMP并行化

Intel和AMD双核乃至4核处理器的推出，使得并行计算已经普及到PC机。为了充分利用多核，需要对原有程序进行多线程改造，使其充分利用多核处理带来的性能提升。该文利用共享存储编程的工业标准OpenMP对有限元方法涉及的单元计算子程序进行了并行化实现。在机群的一个双CPU的SMP节点上的测试表明，共享并行化使得该单元子程序的性能提高了一倍。

OpenMP循环调度算法及SpMV多核并行化研究

OpenMP是一种支持Fortran，C/C++的共享存储并行编程标准。它基于fork-join的并行执行模型，将程序划分为并行区和串行区。近几年来，OpenMP在SMP(Symmetric Multi-Processing)和多核体系结构的并行编程中得到了广泛的应用。随着多核处理器的发展，实际的应用程序如何充分利用多个处理器核来提高运算效率也成为研究的热点。 在科学计算中，循环结构是最核心的并行对象之一。考虑到负载平衡、调度开销、同步开销等多方面因素，OpenMP标准制定了Static调度、Dynamic调度、Guided调度和Runtime调度等不同策略。针对Guided调度策略不适合递减型循环结构的缺点，本文提出了一种改进的new_guided调度策略，并在OMPi编译器上加以实现。New_guided调度策略的主要思想是对前半部分的循环采用Static调度，后半部分的循环采用Guided调度。此外，本文针对不同的循环结构，在多核处理器上对不同的调度策略进行了评测。测试结果表明，在一般情况下，OpenMP默认的Static策略的调度性能最差；对于规则的循环结构和递增的循环结构，Dynamic调度策略、Guided调度策略和new_guided策略的性能差别不大；对于递减型的循环结构，Dynamic调度策略和new_guided策略的性能相当，要优于Guided调度策略；对于求解Mandelbrot集合这类计算量集中在中间的随机循环结构，Dynamic调度策略优于其它策略，new_guided策略的性能介于Dynamic调度和Guided调度之间。 随着多核处理器的问世和发展，多线程程序设计也已经成为一个不可回避的问题。稀疏矩阵向量乘(SpMV, Sparse Matrix-Vector Multiplication)是一个十分重要且经常被大量调用的科学计算内核。SpMV的存储访问一般都极不规则，导致现有的SpMV算法效率都比较低。目前，多核处理器芯片上的内核数量正在逐步增加。这使得在多核处理器上对SpMV进行并行化加速变得非常重要。本文介绍了稀疏矩阵的两种常用的存储格式CSR和BCSR，并采用OpenMP实现了SpMV的多核并行化。此外，本文还讨论了寄存器分块算法、压缩列索引等优化技术，以及不同调度策略对多线程并行后的SpMV的影响。在曙光天阔服务器S4800A1上的测试表明，大部分矩阵都取得了可扩展、甚至是超线性的加速比，但是对于部分规模较大的矩阵，加速效果并不明显。在我们的测试中，与基于CSR实现的多线程SpMV相比，采用寄存器分块算法优化后的SpMV运算速度平均提高了28.09%。在基于CSR实现的多线程SpMV中，采用列索引优化技术后的程序比优化前的速度平均提高了13.05%。此外，本文实现了一种基于非零元个数的调度策略。在该策略中，每个线程处理几乎相同数量的非零元。我们将它和OpenMP标准提供的三种调度策略进行了测试和分析。测试结果表明：与OpenMP提供的调度策略相比，基于非零元个数的调度策略能取得更好的负载平衡；Dynamic调度和Guided调度在多线程SpMV中的性能基本相当，均优于Static调度策略。

一种改进的OpenMP指导调度策略研究

在科学计算中,循环结构是最重要的并行对象之一.考虑到负载平衡、调度开销等多方面因素,OpenMP标准提供静态调度、动态调度、指导调度和运行时调度等不同策略.针对指导调度策略不适合递减型循环结构的问题,提出一种改进的new_guided指导调度策略,并在OMPi编译器上加以实现.New_guided调度策略的主要思想是对前半部分的循环采用静态调度,后半部分的循环采用指导调度.针对不同循环结构,在多核处理器上对不同调度策略进行评测.结果表明,在一般情况下,OpenMP默认的静态策略的调度性能最差;对于规则的循环结构和递增的循环结构,动态调度、指导调度和new_guided策略的性能差别不大;对于递减型的循环结构,动态调度和new_guided策略的性能相当,要优于指导调度策略;对于某些极不规则的随机循环结构,动态调度明显优于其他策略,new_guided策略的性能介于动态调度和指导调度之间.

Automatic relative debugging of OpenMP programs

In this work we show how automatic relative debugging can be used to find differences in computation between a correct serial program and an OpenMP parallel version of that program that does not yield correct results. Backtracking and re-execution are used to determine the first OpenMP parallel region that produces a difference in computation that may lead to an incorrect value the user has indicated. Our approach also lends itself to finding differences between parallel computations, where executing with M threads produces expected results but an N thread execution does not (M, N > 1, M ≠ N). OpenMP programs created using a parallelization tool are addressed by utilizing static analysis and directive information from the tool. Hand-parallelized programs, where OpenMP directives are inserted by the user, are addressed by performing data dependence and directive analysis.

An environment for OpenMP code parallelization

This chapter discusses the code parallelization environment, where a number of tools that address the main tasks, such as code parallelization, debugging, and optimization are available. The parallelization tools include ParaWise and CAPO, which enable the near automatic parallelization of real world scientific application codes for shared and distributed memory-based parallel systems. The chapter discusses the use of ParaWise and CAPO to transform the original serial code into an equivalent parallel code that contains appropriate OpenMP directives. Additionally, as user involvement can introduce errors, a relative debugging tool (P2d2) is also available and can be used to perform near automatic relative debugging of an OpenMP program that has been parallelized either using the tools or manually. In order for these tools to be effective in parallelizing a range of applications, a high quality fully inter-procedural dependence analysis, as well as user interaction is vital to the generation of efficient parallel code and in the optimization of the backtracking and speculation process used in relative debugging. Results of parallelized NASA codes are discussed and show the benefits of using the environment.

The ParaWise expert assistant - widening accessibility to efficient and scalable tool Generated OpenMP code

Despite the apparent simplicity of the OpenMP directive shared memory programming model and the sophisticated dependence analysis and code generation capabilities of the ParaWise/CAPO tools, experience shows that a level of expertise is required to produce efficient parallel code. In a real world application the investigation of a single loop in a generated parallel code can soon become an in-depth inspection of numerous dependencies in many routines. The additional understanding of dependencies is also needed to effectively interpret the information provided and supply the required feedback. The ParaWise Expert Assistant has been developed to automate this investigation and present questions to the user about, and in the context of, their application code. In this paper, we demonstrate that knowledge of dependence information and OpenMP are no longer essential to produce efficient parallel code with the Expert Assistant. It is hoped that this will enable a far wider audience to use the tools and subsequently, exploit the benefits of large parallel systems.

Generating OpenMP code using an interactive parallelization environment

Code parallelization using OpenMP for shared memory systems is relatively easier than using message passing for distributed memory systems. Despite this, it is still a challenge to use OpenMP to parallelize application codes in a way that yields effective scalable performance when executed on a shared memory parallel system. We describe an environment that will assist the programmer in the various tasks of code parallelization and this is achieved in a greatly reduced time frame and level of skill required. The parallelization environment includes a number of tools that address the main tasks of parallelism detection, OpenMP source code generation, debugging and optimization. These tools include a high quality, fully interprocedural dependence analysis with user interaction capabilities to facilitate the generation of efficient parallel code, an automatic relative debugging tool to identify erroneous user decisions in that interaction and also performance profiling to identify bottlenecks. Finally, experiences of parallelizing some NASA application codes are presented to illustrate some of the benefits of using the evolving environment.