共享存储环境下非平衡动力学方程组并行计算

OpenMP是现代多核机群系统采用的主要并行编程模型之一,在单CPU多核上可以获得良好的加速性能,但在整个机群系统上使用时,需要解决可扩展性差的问题.首先设计了求解非平衡动力学方程的并行算法.基于分布共享的多核机群系统,采用显式数据分布OpenMP并行计算方法,将数据进行分布式划分,分配到每个OpenMP线程,通过数据共享实现数据交换.计算结果表明显式OpenMP并行程序在保持可读性的同时,具有良好的可扩展性,在4核Xeon处理器构成的分布共享机群系统上,非平衡动力学方程组的数值并行计算可以扩展到1024个CPU核,具有明显的并行加速计算效果.     

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

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

并行Shi-Tomasi图像角点特征检测算法

在大规模图像的处理中,串行角点检测算法存在着运算量大、耗时长的问题.基于API、OpenMP及PPL多核CPU技术,提出了三种改进的并行角点检测算法.实验结果显示,三种并行算法对不同尺寸的图片均具有较好的加速效果.此外,实验采取不同的线程数量进行测试.基于API的并行检测算法加速比在四线程情况下平均可达3.02,在八线...     

基于CPU与GPU的异构模板计算优化研究

模板计算是一类使用固定模板的算法，被广泛应用于图像处理、计算流体动力学模拟等领域，现有的模板计算存在计算并行度弱、缓存命中率低、无法充分利用计算资源等问题。在消息传递接口（MPI）计算模型和跨平台多线程（OpenMP)计算模型的基础上提出MPI+OpenMP、统一计算设备架构（CUDA）+OpenMP两种混合计算模型。相较于常规的MPI计算模型，MPI+OpenMP计算模型通过使用MPI进行多节点之间的粗粒度通信，使用OpenMP实现进程内部的细粒度并行计算，并结合单指令多数据、非一致内存访问、数据预取、数据分块等技术，提高模板计算过程中的缓存命中率与计算并行能力，加快计算速度。在只采用CUDA进行模板计算时，CPU的计算资源没有得到充分利用，浪费了大量计算资源，CUDA+OpenMP计算模型通过对计算任务的负载划分让CPU也参与到计算中，以减少通信开销及充分利用CPU的多核并行计算能力。实验结果表明，OpenMP+MPI计算模型相较于MPI计算模型的平均加速比为3.67,CUDA+OpenMP计算模型相较于CUDA计算模型的平均加速比为1.26,OpenMP+MPI和CUDA+Ope...     

基于OpenMP的AVS并行编码算法研究与实现

为了提高新一代音视频编解码技术标准AVS的编码速度,利用OpenMP在多核处理器平台上研究并实现了AVS的GOP级、条带级,帧级和基于任务队列模型的帧级并行编码算法.对CIF格式的视频序列进行了测试,在四核处理器平台上加速比最高能达到3.82x.另外,基于任务队列模型的帧级并行算法在保持图像质量不变的基础上解决了帧级并行算法加速比偏低的缺点.实验结果表明,OpenMP是一种简单而有效的并行化编程工具,基于OpenMP的各个AVS并行编码算法与原串行算法相比,编码速度都有显著提高.     

基于多核CPU的并行程序在指控系统中的应用

简单介绍了多核处理器产生背景和原理,分析了多核处理器和基于多线程的并行程序设计在指控系统中的应用前景,介绍了并行应用的编程过程。最后在Microsoft Visual Studio.Net 2005环境下采用OpenMP编程实现了指控系统中一个算法的并行化,并根据多次运行给出该程序在不同线程数目下的平均耗时,验证和分析了基于多核CPU的并行程序的性能。     

Research on Parallel Algorithm of Fdge Extraction Based on Multi-processor

随着处理器由高主频的单核处理器逐步转向片上多核处理器(CMP),计算机并行处理能力不断提升.通过分析GIS串行算法面临的性能瓶颈,利用CMP的优势,采用线程级并行处理栅格数据.针对边缘提取算法,深入分析和比较了MPI、OpenMP等当前主流的并行编程模式,提出了并行性能估计模型.基于OpenMP编程模型分析线程数、调度方式和分块大小对算法并行性能的影响,实现边缘提取最优并行.实验证明,性能评估模型能够准确预测CMP环境下的并行性能,基于OpenMP实现的边缘提取并行算法能够提高图像边缘提取效率.     

多层次并行体绘制算法的研究与应用

三维数据场的体绘制技术是科学可视化中一个重要的研究方向,本文在研究和总结体绘制的发展历程与关键技术的基础之上,着重研究了体绘制中的光线投射算法,结合多核处理器机群系统,提出并实现了一种基于多层次并行编程模型的并行光线投射体绘制算法,并成功地将该算法应用于三维城市浅层地质模型,取得了良好的可视化效果。分别对MPI环境和多层次并行编程MPI+OpenMP环境下的光线投射算法进行了不同计算规模的性能比较实验。实验和分析表明,多层次并行光线投射体绘制算法加快了体绘制的速度,MPI+OpenMP多层次并行模型性能高于纯MPI编程模型的性能。     

基于MPI和OpenMP混合编程的非负矩阵分解并行算法

非负矩阵分解(NMF)作为一种数据降维和特征提取的有效工具,已经在文本聚类、推荐系统等多个领域得到应用,但是其计算过程比较复杂。对此,提出一种基于MPI+OpenMP的混合层次化并行NMF方法,其充分利用基于MPI的消息传递模型和基于OpenMP的共享存储模型各自的优势,并基于多核节点集群进行测试。实验结果表明,所设计的并行NMF算法达到了较高的加速比,能有效处理高阶矩阵的非负分解,极大地提高了计算的效率。     

基于分层存储理论模型的近似字符串匹配 并行算法研究

CUDA (Compute Unified Device Architecture)是一种重要的并行处理架构,但其具有相对复杂的线程管理机制和多重存储模块,从而使得基于CUDA的算法时间复杂度很难量化.针对这一问题,提出了一种分层存储理论模型—HMM (Hierarchical Memory Machine)模型,该模型所具有的分层存储结构可以有效地描述图形处理单元设备不同存储模块的物理特性,因此非常适用于对CUDA算法时间复杂度的量化评估.作为HMM模型的应用实例,文章提出了一种基于HMM模型的并行近似字符串匹配算法,并给出了相应算法时间复杂度的计算过程.与串行算法相比,该算法可以获得60倍以上的加速比.     

过程模型切片技术的研究

将程序切片技术引入到过程模型中,定义过程模型中的关联关系和数据连接关系,在此基础上给出了过程模型的切片定义,并定义了过程模型的三种切片：前向切片,后向切片和双向切片,提出了前向切片、后向切片和双向切片的算法,最后通过实例分析证明了该算法的可行性和实用性。     

对象级粗粒度切片方法

基于面向对象程序的对象间语义级关系,提出了一种对象级粗粒度切片方法,用于解决以往传统程序切片构造过程复杂,切片结构庞大,可理解性不强等问题.该方法并非基于传统的程序依赖图或系统依赖图,而是建立在对象间的关联、组合等语义级关系的基础之上.依据对象间语义级关系构造程序的对象图,在对象图的基础上获取程序的前向对象级粗粒度切片和后向对象级粗粒度切片,并结合了对象间的组合关系使得所得后向对象级粗粒度切片更加精简.     

前向切片与后向切片之间关系的研究

前向切片和后向切片是两种不同的切片技术,为了研究它们之间的异同,通过实验,得到两个结论：后向切片分析的平均缩减率等于前向切片分析的平均缩减率;后向切片分析的缩减率较均衡,前向切片分析的缩减率变化较大,极端情况较多。     

一种基于Java程序分层模型的方法内切片生成算法

程序切片作为软件理解领域的一种重要的分析技术,可以将程序分解为独立的程序线程。系统依赖图的概念及两阶段图形可达性算法的出现,则有效解决了程序切片的过程调用问题。文章介绍了程序切片的基本概念,并给出了在面向对象程序中进行静态分层切片的思想。作为分层切片思想的应用,文章给出了在一种Java程序切片工具模型JSTM(JavaSlicingToolsModel)中运用系统依赖图进行方法内切片的具体算法。     

Theoretical foundations of dynamic program slicing

This paper presents a theory of dynamic slicing, which reveals that the relationship between static and dynamic slicing is more subtle than previously thought. The definitions of dynamic slicing are formulated in terms of the projection theory of slicing. This shows that existing forms of dynamic slicing contain three orthogonal dimensions in their slicing criteria and allows for a lattice-theoretic study of the subsumption relationship between these dimensions and their relationship to static slicing formulations.     

程序切片技术的研究与应用

软件逆向工程和维护通常是一种繁复的任务,它需要对程序的大量阅读,透切理解,耗费大量的人力物力。正是基于这种情况,产生了大量有关程序理解的技术,而程序切片技术是其中比较突出的一种。程序切片技术(Program slicing)最早由MarkWeiser提出,他论述了通过遍历程序依赖图(ProgramDependence Graph,PDG)得到过程内切片(intrapro cedural slice)的技术。此后,Horwitz通过将PDG扩展为系统依赖图(System Dependence Graph,SDG)从而     

一种面向对象程序的过程间切片算法

程序切片是一种程序分析技术，它通过把程序减少到只包含与某个特定计算相关的那些语句来分析程序，过程间切片作为图形可达性问题时，需要扩展过程内切片所用的程序依赖图（PDG）成系统依赖图（SDG），然后利用两阶段图形可达性算法计算比较精确的切片，目前程序切片技术的研究以面向对象程序切片为主，文中讨论了一种合适面向对象程序的分层切片方法，并综合分层切片方法和两阶段图形可达性算法提出了一种简化的计算面向对象程序过程间切片的算法。     

A study of effectiveness of dynamic slicing in locating real faults

Dynamic slicing algorithms have been considered to aid in debugging for many years. However, as far as we know, no detailed studies on evaluating the benefits of using dynamic slicing for locating real faults present in programs have been carried out. In this paper we study the effectiveness of fault location using dynamic slicing for a set of real bugs reported in some widely used software programs. Our results show that of the 19 faults studied, 12 faults were captured by data slices, 7 required the use of full slices, and none of them required the use of relevant slices. Moreover, it was observed that dynamic slicing considerably reduced the subset of program statements that needed to be examined to locate faulty statements. Interestingly, we observed that all of the memory bugs in the faulty versions were captured by data slices. The dynamic slices that captured faulty code included 0.45 to 63.18% of statements that were executed at least once.

在程序理解中使用切片技术

对于遗产软件的理解和维护在软件研究领域中已经变得越来越重要，综述了程序理解的策略及工具，引入了程序切片的思想，并在此基础上对传统的切片方法进行改进以更好地完成程序理解的任务。     

HSFal: Effective fault localization using hybrid spectrum of full slices and execution slices

Most of the existing fault localization approaches use execution coverage of test cases to isolate the suspicious codes that likely contain faults. Program slicing can extract the dependencies of program entities with respect to a specific criterion. Therefore this technique is expected to have a beneficial effect on fault localization. In this paper, we propose a novel approach using a hybrid spectrum of full slices and execution slices to improve the effectiveness of fault localization. In particular, our approach firstly computes full slices of failed test cases and execution slices of passed test cases respectively. Secondly it constructs the hybrid spectrum by intersecting full slices and execution slices. Finally it computes the suspiciousness of each statement in the hybrid slice spectrum and generates a fault location report with descending suspiciousness of each statement. We also implement our proposed approach in our prototype tool HSFal by Java programming language. To verify the effectiveness of our approach, we performed an empirical study by the prototype on several widely used open source programs. Our approach is compared with eight representative coverage-based and slice-based fault localization approaches. Final experimental results show that our proposed approach is more effective in fault localization than other compared approaches, and can reduce almost 2.98–31.79% of the average cost of examined code significantly.