面向MPP Fortran 的自动数据分布

自动数据分布是面向大规模并行处理MPP(massively parallel processing)系统程序自动并行化的一项关键技术.数据分布方式直接影响着应用程序在MPP系统上的并行执行性能.本文以MPP Fortran为例,详细探讨了自动数据分布的有关技术,如对准分析、分布方式的产生、静态性能评估和数据重新分布等,并提出了相应的算法.这些算法将在作者研制的面向MPP Fortran 的程序自动并行化工具中实现.     

基于粒计算的双权网络分层算法

复杂网络环境下数据分布优化问题是个NP问题,但由于大多复杂网络有层次性特征,在此情形下可降低优化问题计算复杂性。应用粒计算理论提出了一种双权分层网络数据分布优化模型和算法,将双权复杂网络映射成一个分层网络,在分层网络上计算数据优化解。算法的时间复杂度为O（C×n2）。仿真实验表明,算法能够得到数据分布优化的满意解,且可通过调整子网络的粒度达到实际应用的需求。     

供应链金融大数据分布特征的分析与洞见

半结构、非结构化、海量的供应链金融数据使得大数据环境下金融数据分析的模式和方法相对复杂。面向大数据样本研究,如何将大样本相比于小样本的独有特征体现在分类模型中值得深入探索。文中从供应链金融数据分布特征入手,分析影响信用风险分类模型的主要因素；对多年来的相关研究成果进行归类分析,概括信用数据分布特征,包括信用数据非均衡与不对称性、信用数据噪声和离群点的存在以及信用数据的非线性多维特征,并探讨了进一步的解决策略。供应链金融大数据分布特征的分析旨在助力挖掘隐含在海量金融数据背后的知识信息,为信用风险模型的构建奠定了坚实的基础。     

分布存储并行计算机优化数据安放一种方法

本文分析了面向分布存储ＳＩＭＤ／ＭＩＭＤ并行机的并行程序的优化数据安放问题，在ＦＯＲＡＬＬ程序模型和ＭＥＳＨ通信模型上，研究了数据分解过程中减少通信代价的优化要求，我们使用编好图描述并行数组之间的对准需求，通过消除维偏好图中的冲突，可得到维对准对准图，一个维对准图就对应一个数据安放方案，维对准图的总代价越大，对应的通信代价就越小，文中给出了最大代价维对准图的一个近似算法。     

基于力导向模型的网络图自动布局算法综述

实现网络图形中节点和边自动布局一直是可视化研究中一个重要内容,基于力导向模型的自动布局算法则是该类研究中应用最广、文献最多的一类方法。根据研究方向出现的时间顺序,从基本模型、基于多维尺度分析的布局算法、多层迭代布局算法、非欧空间节点布局算法、受约束图形自动布局算法等五个方面对基于力引导模型的网络图自动布局算法的典型方法、研究进展、分支情况等进行了描述,并对发展前沿进行了讨论。     

分布存储并行计算机优化数据安放的一种方法

本文分析了面向分布存储ＳＩＭＤ／ＭＩＭＤ并行机的并行程序的优化数据安放问题，在ＦＯＲＡＬＬ程序模型和ＭＥＳＨ通信模型之上，研究了数据分解过程中减少通信代价的优化要求．我们使用维偏好图描述并行数组之间的对准需求，通过消除维偏好图中的冲突，可得到维对准图．一个维对准图就对应一个数据安放方案．维对准图的总代价越大，对应的通信代价就越小．文中给出了求最大代价维对准目的一个近似算法．     

并行数据库上的并行CMD－Join算法

并行数据库在多处理机之间的分布方法(简称数据分布方法)对并行数据操作算法的性能影响很大.如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法.本文研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基于CMD多维数据分布方法的并行CMD－Join算法.理论分析和实验结果表明,并行CMD－Join算法的效率高于其它并行Join算法.     

并行数据库上的并行CMD_Join算法

并行数据库在多处理机之间的分布方法(简称数据分布方法)对并行数据操作算法的性能影响很大.如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法.本文研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基于CMD多维数据分布方法的并行CMD_Join算法.理论分析和实验结果表明,并行CMD_Join算法的效率高于其它并行Join算法.     

OpenMP数据分布子句自动生成算法

将OpenMP程序扩展到异构多核结构时,非本地存储访问会导致访存开销增加,影响程序性能。针对该问题,引入带数组划分信息的数据分布子句,对数据在异构多核存储系统的布局进行管理,提出一种基于并行循环识别和数组引用模式分析的算法,实现该类子句的自动生成。实验结果表明,自动生成的OpenMP程序包含数据分布子句,具有较好的数据局部性,可降低访存开销,在异构多核系统上获得明显的性能提升。     

面向不同数据分布的多维直方图算法COCA-Hist

基于代价的RDBMS优化器需要对含有范围查询的合取谓词的结果集基数进行准确的估计,多维直方图对多维数据分布进行模拟,避免在估计结果集基数时采用数据独立性假设,造成估计误差过大,进而导致选择非优化的查询执行计划.在不同的数据分布情况下,传统的多维直方图(如MHist-2)效果有很大不同.数据相关系数和值域密度、值域参数是准确刻画多维数据分布的有效指标,文中提出了根据不同的指标采用不同的动态优化的多维直方图算法COCA-Hist,可以大大改善传统多维直方图在平均情况下的准确性.通过分析传统的多维直方图的最坏情况,COCA-Hist的改进算法可以改进传统的多维直方图在最坏情况下的准确性.实验比较了COCA-Hist和传统的多维直方图MHist-2以及GENHist和STHoles的准确性和时间效率.实验显示无论在平均情况下还是在最坏情况下COCA-Hist的改进算法均优于传统的MHist-2直方图,并且COCA-Hist的准确性和创建时间均比GENHist有极大的改善,在准确性方面COCA-Hist较优于STHoles,而在空间预算有限时STHoles的创建时间比COCA-Hist高两个数量级.     

基于OpenMP的包络对齐并行方法研究与实现

采用加矩形窗的积累互相关法和基于Fourier变换频域移位性质的最小熵法进行一维距离像包络对齐。针对包络对齐算法数据量大、复杂度高、运行时间长等缺点,提出一种应用于多核处理器的包络对齐并行算法。该方法利用OpenMP编译指导指令#pragma omp section和#pragma omp for对积累互相关算法和最小熵算法进行多线程并行优化。理论分析和仿真实验表明,该方法大大提升了算法的执行效率。     

#br# 分级存储数据多维分析技术的研究与应用

多维数据分析是数据仓库系统需要具备的一个主要功能,它接受用户的多维数据查询请求,生成多维数据集,为建立数据挖掘模型提供基础数据。本文提出一种分级存储数据的多维分析方法,实现分布式多维数据的报表展现原型系统,解决分布式环境下数据的即时展现应用问题,为分布式数据的统计展现提供了多角度、多层次和直观性的分析手段。     

一种并行处理多维连接和聚集操作的有效方法

随着并行计算算法的完善和廉价、功能强大的多处理机系统的成熟，使得采用多处理机系统来并行处理多维数据仓库的连接和聚集操作成为当前有效提高OLAP查询处理性能的首选技术．为此，提出一种降低连接和聚集操作开销的并行算法PJAMDDC(parallel join and aggregation for multi-dimensional data cube)．算法充分考虑了多维数据立方体的存储机制和多处理机分布系统的结构特点，在原有聚集计算多维数据立方体的搜索点阵逻辑结构的基础上，采用多维数据仓库的层次联合代理(hierarchy combined surrogate)和对立方体的搜索点阵进行加权的方法，使得立方体数据在多个处理机间的分配达到最佳的状态，从而在分割多维数据的同时，提高了并行处理多维连接和聚集操作的效率．算法实验评估表明，PJAMDDC算法并行处理多维数据仓库的连接和聚集操作是有效的．     

多维浮点数据的曲线拟合压缩存储方法

以三维位置信息为代表的多维浮点数据是当前高性能计算机系统处理的主要数据对象,对其进行压缩存储是解决海量多维数据量快速增长的需求与存储空间、存储带宽不足的矛盾的手段之一。现有数据压缩算法对浮点多维数据难以取得理想的压缩效果。将多维浮点数据投影到二维坐标上,使用多项式曲线对其进行拟合,将坐标值的存储转换为多项式系数的存储,实现了多维数据的曲线拟合压缩。算法设计中引入了排序作为数据预处理手段,从而得到了较小的压缩误差。理论分析和实验结果表明,在与现有有损压缩误差相当的条件下,得到了优于现有算法的压缩率。     

有限混合密度模型及遥感影像EM聚类算法

遥感信息是地球表层信息的综合反映，由于地球表层系统的复杂性和开放性，地表信息是多维的、无限的、遥感信息传递过程中的局限性以及遥感信息之间的复杂相关性，决定了遥感信息其结果的不确定性和多解性，遥感信息具有一定的统计特性，同时又具有高度的随机性和复杂性，在特征空间中往往表现为混合密度分布，针对遥感信息这种统计分布的复杂性，提出了有限混合密度的期望最大（EM）分解模型，该模型假设总体分布可分解为有限个参数化的密度分布，通过EM迭代计算可估计出各密度分布的最大似然参数集；将有限混合EM聚类算法应用于遥感影像的聚类分析中，并与传统统计聚类方法进行了比较，比较结果表明，其对复杂地物的区分具有优势，另外在融合专家知识、初始化等方面具有扩展能力。     

云计算中基于遗传算法的数据布局策略

数据布局的合理性直接影响数据中心间的数据调度效率,进而提高对用户的数据采集效率。论文以数据中心之间数据调度为基础建立数学模型,利用分布式云计算技术处理用户的海量数据,并提供高性能计算资源和海量存储资源模式。在分布式云计算系统中,数据密集型计算可以有效处理数据中心之间的数据调度,通过遗传算法的全局优化能力产生最佳的近似解,并最终获得数据布局的最佳近似结果。实验结果表明,遗传算法可以有效地计算出最优数据布局的近似结果,并使数据中心之间的数据调度最小化。     

Automatic data allocation to minimize communication on SIMD machines

Straightforward compilation of array operations onto massively parallel SIMD machines results in a significant amount of interprocessor data motion. Careful allocation of data across the processors eliminates much of this interprocessor data motion. Researchers are working on extending programming languages to include user directives for specifying good data allocation. Our focus is to automate the data allocation through compiler techniques to achieve portability without sacrificing efficiency. These techniques can be used to fully automate the data allocation process or can be integrated with alignment directives.We present here a complete compiler algorithm for the automatic layout of data to minimize interprocessor data motion. Arrays are aligned by mapping them onto the processors based on their usage. Arrays may be mapped differently in different sections of the program, eliminating much of the interprocessor data motion resulting from a static mapping of arrays. We describe an integrated technique for determining the alignment of arrays locally within regions of the program and minimizing communication globally among these regions. This technique starts with the alignments specified by the directives, if any, and determines the alignment for the remaining arrays.The algorithms proposed in this paper were used in the SIMD compilers at Compass, Inc. Preliminary results from the initial implementation of the data optimization techniques described here suggest a significant decrease of the interprocessor data motion. More analysis is required to better understand the range of expected gains and the conditions under which those gains are achieved.The research described in this paper was supported in part by the Defense Advanced Research Projects Agency under contracts N00014-87K-0825, F19628-92-C-0045, and N00014-91-J-1698 and in part by a National Science Foundation Presidential Young Investigator Award, grant MIP-8657531, with matching funds from General Electric Corporation, IBM Corporation, and AT&T.     

Concentric layout,a new scientific data layout for matrix data-set in Hadoop file system

Due to the explosive growth in the size of scientific data-sets, data-intensive computing and analysing are an emerging trend in computational science. In these applications, data pre-processing is widely adopted because it can optimise the data layout or format beforehand to facilitate the future data access. On the other hand, current research shows an increasing popularity of MapReduce framework for large-scale data processing. However, the data access patterns which are generally applied to scientific data-set are not supported by current MapReduce framework directly. This gap motivates us to provide support for these scientific data access patterns in MapReduce framework. In our work, we study the data access patterns in matrix files and propose a new concentric data layout solution to facilitate matrix data access and analysis in MapReduce framework. Concentric data layout is a data layout which maintains the dimensional property in chunk level. Contrary to the continuous data layout adopted in the current Hadoop framework, concentric data layout stores the data from the same sub-matrix into one chunk. This layout can guarantee that the average performance of data access is optimal regardless of the various access patterns. The concentric data layout requires reorganising the data before it is being analysed or processed. Our experiments are launched on a real-world halo-finding application; the results indicate that the concentric data layout improves the overall performance by up to 38%.     

基于GA和FEM的夹具布局和变夹紧力优化设计

通过夹具布局和夹紧力大小的优化可以提高薄壁件加工精度．建立了夹具布局和变夹紧力分层优化模型．首先,以工件加工变形最小化和变形最均匀化为目标函数,对夹具布局进行优化设计;其次,基于优化的夹具布局对变夹紧力进行设计．采用有限元法计算工件的加工变形,加工变形求解时综合考虑了接触力、摩擦力、切削力、夹紧力和切屑的影响．采用遗传算法求解优化模型,获得优化的夹具布局和变夹紧力．通过实例分析,验证了分层优化设计方法可以进一步减小工件加工变形,提高加工变形均匀度．