Spark平台下类别数据互信息计算的并行化

针对大规模类别数据的互信息计算量非常大的问题,利用Spark内存计算平台,提出了类别数据的并行互信息计算方法,该算法首先采用列变换将数据集转换成多个数据子集;然后采用两个变长数组缓存中间结果,解决了类别数据特征对间互信息计算量大、重复性强的问题;最后在配备了24个计算节点的Spark集群中,使用人工合成和真实数据集验证...     

基于CUDA的细粒度并行计算模型研究

作为应用软件模型和计算机硬件之间的桥梁,编程模型在计算机领域的重要性不言而喻.但随着具备细粒度并行计算能力的图形处理器(GPU)进入主流市场,与之相适应的编程模型发展却相对滞后.Nvidia在GeForce 8系列显卡上推出的统一计算设备架构(CUDA)技术,使得通用计算图形处理单元(GPGPU)从图形硬件流水线和高级绘制语言中解放出来,开发人员无须掌握图形学编程方法即可在单任务多数据模式(SIMD)下完成高性能并行计算.论文从特性、组成和并行架构等几个方面对CUDA并行计算模型进行了研究,充分表明基于GPU进行高性能并行计算,是适应目前大规模计算需求的一个重要发展途径.     

基于数据空间融合的全局计算与数据划分方法

计算与数据划分问题是影响并行程序在分布主存多处理机中执行性能的重要因素,也是并行编译优化的重点.针对该问题,提出了一套关于数据空间融合的理论框架,并基于该框架给出了一种有效的全局计算与数据划分方法,用于分布主存计算环境中的计算与数据划分问题的求解.该方法能够尽量开发计算空间的并行度,利用数据融合技术优化数据分布,并能搜寻优化的全局计算与数据划分.该方法还能很自然地与数据复制以及偏移常量的对准结合在一起,从而使得数据通信量尽可能地小.实验结果表明了所提出方法的有效性.     

基于层次化数据结构的并行有限元计算

高效数据结构及并行算法是大规模并行有限元计算的关键。本文面向非结构网格,提出了一种层次化的数据结构,并在该数据结构基础上设计了并行有限元算法。最后,用数值算例验证了数据结构和并行算法的正确性和并行可扩展性。     

不确定数据流上的并行Skyline查询算法

不确定数据流上的Skyline查询技术逐步引起研究者的关注,传统的集中式流处理算法难以满足海量数据的查询需求,并且云计算所提供的海量计算资源和有效的存储管理模式,为研究并行Skyline查询技术提供了充足的条件。基于上述事实,提出了一种不确定数据流上的并行Skyline查询算法(parallel Skyline over uncertain data streams,PSUDS)。该算法通过交叉划分滑动窗口的方式,将集中式流查询转化为并行处理,以并行执行的方式来解决集中式算法处理性能不足的问题。大量实验结果表明,该算法具有较好的并行可扩展性。     

An Approach to Correctness of Data Parallel Algorithms

The design of data parallel algorithms for fine-grain machines is a fundamental domain in today′s computer science. High standards in the specification and resolution of problems have been achieved in the sequential case. It seems reasonable to apply the same level of quality to data parallel programs. It appears that most data parallel problems can be specified in terms of pre- and postconditions. These conditions characterize the overall state of the fine-grain processors in the initial and final states. In this paper:

• •We present an axiomatic system to prove correctness of data parallel algorithms on single-instruction multiple-data (SIMD) machines.
• •We specify some data parallel problems like tree sum, root finding, radix sorting, and dynamic memory allocation.
• •With this set of axioms we prove the correctness of programs solving the problems above.

It seems that the framework for data parallel problems is quite different from those for problems of parallelism with multiple threads of control, like those solvable in Communicating Sequential Processes (CSP).     

Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach

Explicit multithreading (XMT) is a parallel programming approach for exploiting on-chip parallelism. XMT introduces a computational framework with (1) a simple programming style that relies on fine-grained PRAM-style algorithms; (2) hardware support for low-overhead parallel threads, scalable load balancing, and efficient synchronization. The missing link between the algorithmic-programming level and the architecture level is provided by the first prototype XMT compiler. This paper also takes this new opportunity to evaluate the overall effectiveness of the interaction between the programming model and the hardware, and enhance its performance where needed, incorporating new optimizations into the XMT compiler. We present a wide range of applications, which written in XMT obtain significant speedups relative to the best serial programs. We show that XMT is especially useful for more advanced applications with dynamic, irregular access patterns, where for regular computations we demonstrate performance gains that scale up to much higher levels than have been demonstrated before for on-chip systems.     

基于相对决策熵与加权相似性的粗糙集数据补齐方法

现有的基于粗糙集的数据补齐方法在计算任意两个对象之间的相似性时并没有考虑不同条件属性之间的差异性。针对这一问题,引入一种新的加权相似性的概念,并提出一种基于相对决策熵与加权相似性的粗糙集数据补齐算法RDNAWS。RDNAWS算法采用相对决策熵的概念来度量每个条件属性的重要性,并通过计算每个条件属性的重要性以及决策属性集对其的依赖性来为每个条件属性提供一个权值,从而将不同的条件属性有效地区分开来。在真实数据集上的实验表明,与现有的算法相比,所提算法能够获得更好的分类性能。     

基于线性变换的计算与数据动态分解方法

在并行优化编译器的并行识别过程中,许多串行代码无法找到全局一致的分解结果,数据重分布无可避免,有必要寻找一种有效的方法求解计算和数据的动态分解。该文研究了单个嵌套循环计算与数据分解算法以及分解结果表示方法,提出一种在多个嵌套循环间求解数据线性一致分布的动态分解算法,结合程序的结构分析和程序的控制流信息,用于通用串行代码的并行分解过程,可以同时给出串行代码的计算划分和数据分布结果。     

基于图形处理器的并行方体计算

方体(cube)计算是数据仓库和联机分析处理(Online analytical processing,OLAP)领域的核心问题,如何提高方体计算性能获得了学术界和工业界的广泛关注,但目前大部分方体算法都没有考虑最新的处理器架构.近年来,处理器从单一计算核心进化为多个或许多个计算核心,如多核CPU、图形处理器(Graphic Processing Units, GPU)等.为了充分利用现代处理器的多核资源,该文提出了基于GPU的并行方体算法GPU-Cubing,算法采用自底向上、广度优先的划分策略,每次并行完成一个cuboid的计算并输出;在计算cuboid过程中多个分区同步处理,分区内多线程并行.GPU-Cubing算法适合GPU体系结构,并行度高.与BUC算法相比,基于真实数据集的完全方体计算可以获得一个数量级以上的加速比,冰山方体获得至少2倍以上的加速.     

并行编译中一种线性数据和计算划分算法

对于高性能并行计算机而言,如何找到一种好的计算和数据划分,对数据和计算进行合理划分,增加数据本地化来减少处理器间的通信是提高其并行性能的关键。该文讨论了一种线性的自动进行无数据重组的计算和数据划分算法。     

基于并行计算的认证服务系统

介绍一种基于并行计算的安全认证服务器系统,给出该系统的算法模型。认证服务器的并行环境采用主从模式,私钥分段按照一定顺序存放到各个物理节点中,主节点控制认证流程及私钥发放,从节点保存私钥及密钥计算。在算法模型的基础上实现原型系统,对该方案的安全性能进行了评价。实验结果表明该方案具有抗攻击能力强、认证速度快和结构稳定的特点。     

Cholesky分解细粒度并行算法

本文提出了一种Cholesky分解细粒度流水线并行算法,该算法可以处理任意规模的数据,可以充分开发FP-GA加速器提供的细粒度并行。实验表明,该算法具有很好的可扩展性,在Xilinx XC5 VLX330 FPGA上能够集成36个处理单元(PE),当矩阵的阶为16384、运行频率为200MHz时性能达到14.3GFLOPS。     

Fully Dynamic Partitioning: Handling Data Skew in Parallel Data Cube Computation

Parallel data processing is a promising approach for efficiently computing data cube in relational databases, because most aggregate functions used in OLAP (On-Line Analytical Processing) are distributive functions. This paper studies the issues of handling data skew in parallel data cube computation. We present a fully dynamic partitioning approach that can effectively distribute workload among processing nodes without priori knowledge of data distribution. As supplement, a simple and effective dynamic load balancing mechanism is also incorporated into our algorithm, which further improves the overall performance. Our experimental results indicated that the proposed techniques are effective even when high data skew exists. The results of scale-up and speedup tests are also satisfactory.     

并行编译中数据分布的线性划分模式计算

由于计算机访问本地存储器的速度远远快于通过网络访问异地计算机存储器的速度，因此，在分布式存储环境中，如何对程序中引用的数据进行合理的分布，从而达到在本地进行计算时只需访问存储在本地的数据（即无通信的数据分布）的目的，已成为提高并行计算速度的关键问题，本文主要讨论如何在数组下标表达式为线性的条件下，对一种种锘于线性代数中超平面概念的数组线性划分技术进行扩充，并给出了完整的数据划式计算算法。     

提升小波变换的数据并行计算方法研究

研究了基于SIMD PE阵列对G级像素帧进行9/7提升小波变换的数据并行计算实现方法.首先,在分析9/7提升小波变换运算公式的局部计算特点的基础上,提出了 PE状态标识法和基于PE标识的条件计算方法;其次,提出了SIMD PE阵列的虚拟化实现方法.研究表明,该方法提高了计算的并行度和规则性,并行度仅受限于阵列的规模且具...     

一种建立粗糙数据模型的监督模糊聚类方法

提出了在输入-输出积空间中利用监督模糊聚类技术快速建立粗糙数据模型(rough data model,简称RDM)的一种方法.该方法将RDM模型的分类质量性能指标与具有良好特性的Gustafson-Kessel(G-K)聚类算法结合在一起,并通过引入数据对模糊类的推定隶属度的概念,给出了将模糊聚类模型转化为粗糙数据模型的方法,从而设计出一种通过迭代计算使目标函数最小的两个必要条件方程来获取RDM模型的有效算法,将Kowalczyk方法的多维搜索过程变为以聚类数目为参数的一维搜索,极大地减少了寻优时间.与传统的粗糙集理论和Kowalczyk方法相比,提出的方法具有更好的数据概括能力和噪声数据处理能力.最后,通过不同的数据集实验测试,结果表明了该方法的有效性.     

基于GPU的并行计算性能分析模型

针对GPU并行计算领域缺少精确的性能分析模型和有针对性的性能优化方法,提出一种基于GPU的并行计算性能定量分析模型,其通过对指令流水线、共享存储器访存、全局存储器访存的性能建模,来定量分析并行程序,帮助程序员找到程序运行瓶颈,进行有效的性能优化。实验部分通过3个具有代表性的实际应用(稠密矩阵乘法、三对角线性方程组求解、稀疏矩阵矢量乘法)的性能分析证明了该模型的实用性,并有效地实现了算法的优化。     

多核微机基于OpenMP的并行计算

随着四核微机走向市场和八十核处理器在实验室研制成功，多核正引领软件研发发生基础性变化。开发人员需要在代码中添加线程来利用系统所提供的多个内核，从而提升PC应用软件的功能和性能。文中探讨在多核微机上进行并行计算的实现技术。介绍了共享存储系统并行编程接口OpenMP的模型、指令和库函数，以及Intel C＋＋编译器9．1和Microsoft Visual Studio 2005等对OpenMP的支持；着重探讨了二维离散快速傅里叶变换并行算法的设计、实现与优化技术；展望了高性能并行计算软构件库的开发前景。