多核CPU下的K-means遥感影像分类并行方法

针对海量遥感影像快速分类的应用需求,提出一种基于K-means算法的遥感影像并行分类方法.该方法结合CPU下进程级与线程级模式的并行特征,设计融合进程级与线程级并行的两阶段数据粒度划分方法和任务调度方法,在保证精度的基础上实现并行加速.利用大数据量的多尺度遥感影像进行实验,结果表明:所提并行方法可大大减少遥感影像的分类时间,取得了良好的加速比(13.83),并可达到负载均衡,从而解决了大区域遥感影像快速分类的问题.     

完全拓扑关系结构D-TIN多核并行构建

为了充分利用普通PC机多核CPU计算资源实现大数据量离散点集矢量地形快速构建,提出具有完全拓扑关系结构D-TIN的多核并行生成算法.首先基于四方边缘结构设计具有完全拓扑关系的D-TIN数据结构及系列函数接口,用于操作该数据结构;然后顾及线程间数据负载平衡和空间均质性,采用坐标排序法对离散点集进行均等虚拟划分;再基于离散点集凸包"生成—消融—生成"周期性特征和分治算法思想设计D-TIN串行构建算法;最后以其作为D-TIN并行构建算法的内核,Open MP作为多核并行编程模型,实现了单机多核环境下的D-TIN并行构建.实验结果表明,当数据量较大时,该算法效率明显高于串行算法,且两者的计算结果具有完全一致性;同时,参与计算线程数与总耗时呈负相关.     

基于OpenCL的并行kNN算法设计与实现

kNN算法是机器学习和数据挖掘程序中经常使用的经典算法。随着数据量的增大,kNN算法的执行时间急剧上升。为了有效利用现代计算机的GPU等计算单元减少kNN算法的计算时间,提出了一种基于OpenCL的并行kNN算法,该算法对距离计算和排序两个瓶颈点进行并行化,在距离计算阶段使用细粒度并行化策略和优化的线程模型,排序阶段使用优化内存模型的双调排序。以UCI数据集letter为测试集,分别使用E8400和GTS450运行kNN算法进行测试,采用GPU加速的并行kNN算法的计算速度比CPU版提高了40.79倍。     

一种增量式并行Web信息采集方法

提出了一个基于多线程并行的增量式Web信息采集结构模型,并加以实现,该模型以线程并行的方式对Web页面同时采集,实现了全面、高效并且灵活的信息搜集,在系统实现过程中,采取Java语言中最新的特性、独特的URL调度策略保证了各个线程时间的下载并行与互不相交,页面分析过程为各个线程源源不断地提供下载源,而指纹判别算法保证了并行采集过程中的同步,有效地去除了冗余。对该系统作了测试,实验证明,该系统能有效地提高信息采集性能。     

MPI和OpenMP混合并行模型下的遥感编目信息检索

目的 空间位置检索是遥感影像检索中的关键步骤,为进一步提高海量遥感影像编目数据定位检索效率,降低误检率,提出一种基于MPI和OpenMP混合编程模型对射线法进行多层次并行化实现。方法 首先完善传统射线法处理点在多边形边上以及射线与边的端点相交的情况;其次采用MPI实现基于程序层面多机并行,OpenMP实现算法层面单机多线程并行,通过开启多个线程同时处理多边形的各个点,判断它们是否在另一个多边形的内部。结果 当系统中所有节点开启线程数之和等于主节点的最佳线程数时,全局计算速度达到最佳。混合并行算法相比串行算法检索时间减少50%以上,效率更高。结论 MPI+OpenMP混合并行比普通的串行执行、单纯MPI并行或单纯OpenMP并行执行空间定位检索算法效率显著提高,这种并行方案普遍适用于集群环境下的并行程序,并且可以进一步拓展到其他图像处理算法领域。     

基于TBB的谐波分析多核并行化研究

电能质量谐波分析中通常使用快速傅立叶变换算法(FFT),但在大数据量时其循环体执行效率低,实时性不高。针对上述问题,提出在多核处理器上采用TBB(Intel线程构建模块)并行实现复序列FFT的思路,提高谐波分析的速度,增强实时性。此外,与其他并行库改造程序的实验对比结果表明,TBB可以以更简单的手段,实现更高效的程序并行。     

基于图的分布式并行基因编程模型

基因编程(GP)算法具有天然的并行性,因此出现了并行分布式GP模型,如主从模型、岛屿模型和网格模型等。但是实现这些分布式模型的算法过程复杂,不具有可重用性,很难依据不同拓扑结构来快速实现大规模的GP计算。针对这些缺点,提出了基于图的并行分布式GP模型,形式化地描述了图中的各种GP操作,使其能够支持不同拓扑结构的GP分布式并行计算。经过实验测试,该模型能够实现上述三种GP模型,并具有稳定、高效、易实现的特点。     

并行演化算法研究进展

并行计算与演化计算同为复杂问题寻优的现代技术.两者的结合不仅减少运行时间、提高解的质量,还增加计算能力,即增加应用领域.并行演化算法除了主从式、粗粒度、细粒度和分层四类并行化模型外,还有改进的并行演化算法.本文分析介绍加速比定义分类、迁移策略与并行演化算法的应用情况,总结前人对并行演化算法开展的理论分析与实践应用研究进展,并就该领域的进一步研究方向提出了一些看法,指出细胞状模型和并行遗传程序设计将成为两大研究热点.     

多核集群系统下的混合并行遗传算法研究

为应对传统遗传算法在处理大规模组合优化问题面临的进化速度缓慢,难以达到实时要求的严峻挑战,提出了一种在多核PC集群系统上实现“粗粒度一主从式”混合并行遗传算法的模型:通过把“粗粒度一主从式”并行遗传算法映射到多核PC集群上,结合消息传递和共享存储两种并行编程模型,在节点间使用消息传递模型(MPI),对应的遗传算法为粗粒度并行遗传算法,在节点内使用共享存储模型(OpcnMP),对应的遗传算法为主从式并行遗传算法,用MPI和OpenMP混合编程的方式以进程和线程两级并行在多核集群上实现具体的混合并行遗传算法。理论分析和实验结果表明,提出的实现模型有较好的性能,可大大改进传统遗传算法的缺陷。为利用并行遗传算法在普通多核PC集群上处理大规模组合优化问题提出了一种有效、可行的解决方案。     

Win32平台基于通信的多核并行编程方法

随着计算机硬件的发展,多核并行计算在计算机软件及应用领域的出现率也越来越频繁。目前的多核编程模型采用线程级并行模型,现有的多线程并行编程模型主要有线程库、指令模型和任务式模型三种。提出一种与MPI并行编程模型相似的基于通信的方法在Win32平台上来实现并行编程,在此基础上实现MTI并行编程模型。通过若干典型的测试给出使用MTI进行并行编程的执行结果,结果表明MTI是有效、易用的。     

Accelerating data gravitation-based classification using GPU

Data gravitation-based classification model, a new physic law inspired classification model, has been demonstrated to be an effective classification model for both standard and imbalanced tasks. However, due to its large scale of gravitational computation during the feature weighting process, DGC suffers from high computational complexity, especially for large data sets. In this paper, we address the problem of speeding up gravitational computation using graphics processing unit (GPU). We design a GPU parallel algorithm namely GPU–DGC to accelerate the feature weighting process of the DGC model. Our GPU–DGC model distributes the gravitational computing process to parallel GPU threads, in order to compute gravitation simultaneously. We use 25 open classification data sets to evaluate the parallel performance of our algorithm. The relationship between the speedup ratio and the number of GPU threads is discovered and discussed based on the empirical studies. The experimental results show the effectiveness of GPU–DGC, with the maximum speedup ratio of 87 to the serial DGC. Its sensitivity to the number of GPU threads is also discovered in the empirical studies.

     

某结冰风洞喷雾水压控制系统设计

喷雾系统作为某结冰风洞关键子系统之一,用以模拟高空云雾环境,其喷嘴前端水压控制精度和快速稳定性对提高云雾均匀性和风洞试验效率具有重要意义。针对该风洞喷雾水压系统设备数量多、布局分散的特点,设计了主从控制网络拓扑结构;针对系统指标要求高、环境条件严苛的特性对调节阀执行机构的定位精度、控制系统的可靠性等进行了设计,最后分析了系统多支路并联调压的特性,提出了控制策略,并基于分段PID算法实现了喷雾水压的精确和快速控制。该设计方法对复杂工况下风洞系统设计以及多支路并联调压系统的设计具有借鉴作用。     

一种任意三维实体网格模型的体积特征提取算法

体积在不同轴向上的分布是三维网格模型的重要几何特征。在分析三维模型数据结构的基础上,提出一种提取任意三维实体网格模型体积分布特征的算法。算法首先应用主元分析法确定模型的主轴方向,并将模型按主轴方向旋转至特定姿态,再以一组等距的平行平面从三个坐标轴方向对模型进行剖分处理,并利用平面简单多边形的带符号面积公式求取相应的截面面积,进而求得模型的沿不同轴向的体积分布特征。模型在三个坐标轴向上的体积分布描述了模型的几何特征。实验表明,算法程序运行稳定、快速,可用于提取具有任意几何和拓扑复杂性的各类实体模型的体积分布特征。     

特殊工艺约束并行多机双目标调度问题的研究

针对在特殊工艺约束下,非等同并行多机总完工时间最小和总拖后惩罚最小双目标调度问题（BOSP）,设计了一个双目标调度模型,进而构造了一个基于向量组编码的遗传算法。此算法的编码方法简单,能有效地反映实际调度方案,收敛速度快。同时为了更好地适应调度实时性和解大型此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性,并能适用于解大型此类调度问题。     

基于不完全算法的并行FPGA SAT求解器

可满足性问题是计算机理论与应用的核心问题。在FPGA上提出了一个基于不完全算法的并行求解器pprobSAT+。使用多线程的策略来减少相关组件的等待时间,提高了求解器效率。此外,不同线程采用共用地址和子句信息的数据存储结构,以减少片上存储器的资源开销。当所有数据均存储在FPGA的片上存储器时,pprobSAT+求解器可以达到最佳性能。实验结果表明,相比于单线程的求解器,所提出的pprobSAT+求解器可获得超过2倍的加速比。     

A concurrent van Emde Boas array as a fast and simple concurrent dynamic set alternative

Increasing demand for computationally efficient algorithms and processors has turned the attention of researchers toward parallel and concurrent solutions. Because the frequency of contemporary processors cannot be tweaked infinitely, the only hopes for squeezing more performance from computers are parallel processing and parallel computation. The important part of every parallel solution is concurrent data structures, which allow multithread programming environments to be taken advantage of. In this article, a new concurrent dynamic set structure is proposed. It is based on the van Emde Boas trees concept, where on every node of a tree, an array of the node's children is stored. The structure is equipped with a simple but effective locking algorithm, which allows it to be used concurrently by any number of threads. The presented algorithm idea is accompanied by an experimental implementation written in JAVA 6. Preliminary tests prove that, especially for moderately larger data sets with a predominance of read operations, the concurrent van Emde Boas array proposed in this article may be a viable alternative for other structures providing a similar functionality. Copyright © 2013 John Wiley & Sons, Ltd.     

A parallel finite element procedure for contact-impact problems

An efficient parallel finite element procedure for contact-impact problems is presented within the framework of explicit finite element analysis with thepenalty method. The procedure concerned includes a parallel Belytschko-Lin-Tsay shell element generation algorithm and a parallel contact-impact algorithm based on the master-slave slideline algorithm. An element-wise domain decomposition strategy and a communication minimization strategy are featured to achieve almost perfect load balancing among processors and to show scalability of the parallel performance. Throughout this work, a prototype code, named GT-PARADYN, is developed on the IBM SP2 to implement the procedure presented, under message-passing paradigm. Some examples are provided to demonstrate the timing results of the algorithms, discussing the accuracy and efficiency of the code.     

Parallel strategy for multiple scan operations with data replication

To support the large-scale analytic for Web applications, the backend distributed data management system must provide the service for accessing massive data. Thus, the scan operation becomes a critical step. To improve the performance of scan operation, modern data management systems usually rely on the simple partitioned parallelism. Under the partitioned parallelism, tables are consist of several partitions, and each scan operation can access multiple partitions separately. It is a simple and effective solution for a single scan operation. In this paper, we consider managing multiple scan operations together, where the situation is no longer straightforward. To address the problem, we propose the parallel strategy to schedule batched scan operations together beyond the simple partitioned parallelism. For the sake of performance, first, we utilize replications to increase the parallelism and propose an effective load balancing strategy over replication nodes based on linear programming. Second, we propose an effective chunk-based scheduling algorithm for multi-threading parallelism on each node to guarantee all threads have even workloads under a qualified cost model. Finally, we integrate our parallel scan strategy into an open-sourced distributed data management system. Experimental evaluation shows our parallel scan strategy significantly improves the performance of scan operation.

     

Improving dissolve spatial operations in a simple feature model

This paper presents an algorithm to improve the performance of a spatial operation called ‘dissolve’ widely used in Geographic Information System (GIS) through spatial database systems. In simple feature models (lacking of persistent topology) executing some common spatial operations requires a high amount of system resources. Such common operations occur for example in the ‘OpenGIS Simple Features for SQL’ protocol (SFS), a client-server interoperability standard defined by ‘The Open Geospatial Consortium, Inc.’ (OGC). The specific spatial operation studied in this paper is called ‘dissolve’. It is carried out using the union spatial operator defined by OGC) and consists of removing the boundaries between adjacent polygons. The proposed algorithm improves substantially the performance of this spatial operation and it needs between 100 and 1000 times less amount of resources. This way it enables the database server to carry out this spatial operation on huge datasets containing up to millions of geometries. To check and to validate this algorithm a new open source software package (PGAT) has been developed.