航空发动机包容性数值仿真并行计算效率研究

研究如何提高航空发动机包容性数值仿真并行计算效率的问题。由于仿真需要庞大的网格数量、高度的非线性和复杂的接触算法,并行计算效率一直比较低,已经成为制约工程应用的重要因素。为了提高航空发动机包容性数值仿真并行计算效率,提出了在共享内存并行模式(Share-Memory Parallel,SMP)下,采用自接触算法进行显式动力学分析,提高并行计算效率的方法。实际算例的比较表明,相比传统的面-面接触算法,采用自接触算法可以有效提高航空发动机包容性数值仿真并行计算效率。     

基于云计算的受限玻尔兹曼机推荐算法研究

数据的指数级增长及算法本身的复杂性使受限玻尔兹曼机面临着计算效率的问题。在详细分析受限玻尔兹曼机的基础上,将受限玻尔兹曼机与Hadoop平台的并行计算架构相结合,提出基于云平台的受限玻尔兹曼机推荐算法。该算法通过复制机制解决数据相关性问题,并将传统的受限玻尔兹曼机过程分解为若干个Hadoop任务的循环,实现并行计算。实验结果表明,与在传统平台上的实现相比,基于Hadoop并行架构的受限玻尔兹曼机推荐算法在大体量数据集的条件下可大幅提高推荐计算效率。     

冒险模拟退火算法及其在任务映射上的应用

本文提出了一种冒险模拟退火算法。该算法将冒险计算引进模拟退火算法来处理任务映射问题。它引入任务图与费用函数的概念，不仅考虑到任务的计算时间，还考虑到任务间的通信时间。既确保了模拟退火的串行顺序，使解趋于最优，又缩短了达到最优所需时间，提高了并行计算效率。     

一种并行二值图像连通域标记算法

连通域标记算法在CPU运行效率比较有限,这也是连通域标记算法处理图像的症结所在,针对这一问题,提出了一种并行二值图像连通域标记算法.从二值图像处理问题的可并行化出发,根据GPU并行计算的特点设计出了一种图像预处理、溯源(伪溯源)、伪溯源处理三个步骤的并行标记算法,采用硬件支持的多个线程并行执行处理的方式来提升算法的效率并实现了该算法,实验结果表明该算法相对CPU单线程处理算法效率具有明显提升,也更具有鲁棒性,尤其是图像像素不断增多后,效率更加明显.     

基于Fork/Join框架的等值面快速生成并行算法

针对传统串行等值面提取算法在处理离散点数量多、网格点密度大的数据时生成效率差的问题,提出一种新的基于Fork/Join框架下的等值面快速生成并行算法。通过对传统串行算法中的关键步骤进行并行计算可行性分析,提出可以实施并行计算的四个单独步骤:离散点数据网格化处理、等值点计算、等值线追踪与光滑、等值面标记识别。通过将并行计算作用于等值面生成的这四个步骤中,减少了等值面计算的执行时间,加快了等值面的生成速度。实验结果表明,在数据计算量较大时,与传统串行算法相比,并行算法能在2秒内快速生成等值面,最大加速比高于5.0,提高了等值面的生成效率并取得了良好的绘制效果,满足了高实时性的业务需求。     

数据不规则问题并行计算的负载平衡策略的研究

讨论以边缘通信为特征的数据不规则问题并行计算的静态负载平衡策略。从图论的角度讨论了静态负载平衡问题，给出三个优化目标，即点集等分，最短通路和通信量最小。对于以边缘通信为特征的一般数值计算问题，论述了二维问题正方形划分总通信量最小、并行效率最高，三维问题立方体划分总通信量最小、并行效率最高的结论。基于以上结论和实际课题特点，提出一种一维优先的规则分块算法和基于自动重分块的不规则分块算法相结合的方法。实验证明，该方法实现简单，能够处理不同规模的数据不规则问题，达到较优的负载平衡和较高的通信效率，提高并行程序的整体效率．     

面向大数据的并行聚类算法

在大数据时代,针对CLUBS算法较高的计算复杂度导致训练效率低下的问题,提出一种面向大规模数据的并行聚类算法CLUBS‖,通过将CLUBS算法的思想融入MapReduce并行计算框架,实现数据的并行处理,提高算法的计算效率,从理论上对几个关键计算的并行化进行较为深入的分析,基于Ad-hoc消息传递对该算法进行实现.实验结果验证了所提方法的有效性.     

云计算环境下并行计算优化调度研究与仿真北大核心CSCD

由于云计算环境下并行数据具有不同的特征,采用不同的表达式描述客户对并行计算任务的满意度时,无法使客户所需并行计算任务和客户满意度完全符合调度条件。传统的调度方法,主要以客户满意度作为并行计算调度的前提,没有充分考虑并行计算任务和客户满意度之间的关系对任务调度准确性的影响,导致调度效率差的问题。提出一种基于优化遗传算法的云计算环境下的并行计算调度方法。建立并行计算调度任务模型,将模糊逻辑和虚拟机利用率的方差作为控制变量,利用遗传算法进行并行计算调度策略的寻优,在交叉操作中引入了参数可调的概率函数,在变异操作中引入了自适应变异的概率函数,从而提高了并行计算中的调度效率。仿真结果表明,改进算法能够提高调度效率,效果令人满意。     

并行谱聚类算法

谱聚类算法是建立在谱图理论上的一种点对聚类算法,具有实现简单、理论基础扎实和适应任意数据空间的优点,因而成为机器学习领域的研究热点.谱聚类算法最大的问题在于计算复杂度过高,而并行计算可以提高解题效率,因此本文采用最为流行的并行计算框架MAP/REDUCE在Hadoop环境中实现了并行谱聚类算法,大大改善了谱聚类算法在大规模数据环境中的聚类效率问题.     

几何定理并行验证算法研究

几何定理证明的数值验证法以数值计算代替符号计算来提高效率，但是在实际应用中对复杂命题的解题效率还存在问题。该文尝试用并行计算方法来提高算法效率，分析了MPI编程模型下的任务划分、通信组织、任务调度等问题，并在MPICH2下实现了数值并行验证算法，对算法的并行性能指标进行了测试，得到了较好的结果。     

基于处理能力预约的工作站机群协同调度

本文提出了一种基于处理能力预约的工作站机群协同调度方法,它以一定的处理能力为基础,对参与并行计算的所有工作站进行处理能力的预约,使得并行程序以协调一致的步调得到执行。模拟结果表明,这不仅提高了应用程序所能获得的有效并行计算性能,而且还提高了处理器的利用率,同时它在不同应用环境一的适应性好。     

Parallel techniques for information extraction from hyperspectral imagery using heterogeneous networks of workstations

Recent advances in space and computer technologies are revolutionizing the way remotely sensed data is collected, managed and interpreted. In particular, NASA is continuously gathering very high-dimensional imagery data from the surface of the Earth with hyperspectral sensors such as the Jet Propulsion Laboratory's airborne visible-infrared imaging spectrometer (AVIRIS) or the Hyperion imager aboard Earth Observing-1 (EO-1) satellite platform. The development of efficient techniques for extracting scientific understanding from the massive amount of collected data is critical for space-based Earth science and planetary exploration. In particular, many hyperspectral imaging applications demand real time or near real-time performance. Examples include homeland security/defense, environmental modeling and assessment, wild-land fire tracking, biological threat detection, and monitoring of oil spills and other types of chemical contamination. Only a few parallel processing strategies for hyperspectral imagery are currently available, and most of them assume homogeneity in the underlying computing platform. In turn, heterogeneous networks of workstations (NOWs) have rapidly become a very promising computing solution which is expected to play a major role in the design of high-performance systems for many on-going and planned remote sensing missions. In order to address the need for cost-effective parallel solutions in this fast growing and emerging research area, this paper develops several highly innovative parallel algorithms for unsupervised information extraction and mining from hyperspectral image data sets, which have been specifically designed to be run in heterogeneous NOWs. The considered approaches fall into three highly representative categories: clustering, classification and spectral mixture analysis. Analytical and experimental results are presented in the context of realistic applications (based on hyperspectral data sets from the AVIRIS data repository) using several homogeneous and heterogeneous parallel computing facilities available at NASA's Goddard Space Flight Center and the University of Maryland.     

An effective methodology to improve the performance of the up*/down* routing algorithm

Networks of workstations (NOWs) are being considered as a cost-effective alternative to parallel computers. Most NOWs are arranged as a switch-based network and provide mechanisms for discovering the network topology. Hence, they provide support for both regular and irregular topologies, which makes routing and deadlock avoidance quite complicated. Current proposals use the up*/down* routing algorithm to remove cyclic dependencies between channels and avoid deadlock. However, routing is considerably restricted and most messages must follow nonminimal paths, increasing latency and wasting resources. We propose and evaluate a simple and effective methodology to compute up*/down* routing tables. The new methodology is based on computing a depth-first search (DPS) spanning tree on the network graph that decreases the number of routing restrictions with respect to the breadth-first search (BFS) spanning tree used by the traditional methodology. Additionally, we propose different heuristic rules for computing the spanning trees to improve the efficiency of up*/down* routing. Evaluation results for several different topologies show that computing the up*/down* routing tables by using the new methodology increases throughput by a factor of up to 2.48 in large networks with respect to the traditional methodology, and also reduces latency significantly.     

工作站网络下三对角方程组并行求解

考虑工作站网络（ＮＯＷｓ）中三对角线性方程组的并行求解，基于最小秩解耦算法与分布治之并行计算模式，并行最小秩解耦算法（ＰＭＲＤ）。它在计算过程中保持原矩阵的结构特征，数值稳定性高，本文给出算法的数值特征分析以及计算与通讯复杂性分析并与Ｍｅｈｒｍａｎｎ分治算比较，所有算法由ＰＶＭ软件系统实现并在工作站网络中测试。     

Dynamic mapping of cooperating tasks to nodes in a distributed system

Networks of workstations (NOWs) are a low-cost and widespread platform for parallel computing. This paper focuses on the dynamic task-scheduling problem in NOW environments. The aim is to minimize the completion time of parallel programs by distributing cooperating concurrent tasks to homogeneous networked nodes. Cooperation dependencies as well as creation and termination dependencies between tasks are taken into account. An event lattice model is introduced to describe past, actual and future behavior of a parallel program in execution. Based on this model an algorithm is presented to dynamically assign tasks to the nodes of a dedicated distributed system. Crucial for the efficiency of this approach is a top-down construction of all operating system entities involved in distributed resource management, particularly the close cooperation of the compiler and runtime system, which allows the creation of event lattice clippings at runtime.     

Fault-Tolerant Matrix Operations for Networks of Workstations Using Diskless Checkpointing

Networks of workstations (NOWs) offer a cost-effective platform for high-performance, long-running parallel computations. However, these computations must be able to tolerate the changing and often faulty nature of NOW environments. We present high-performance implementations of several fault-tolerant algorithms for distributed scientific computing. The fault-tolerance is based on diskless checkpointing, a paradigm that uses processor redundancy rather than stable storage as the fault-tolerant medium. These algorithms are able to run on clusters of workstations that change over time due to failure, load, or availability. As long as there are at leastnprocessors in the cluster, and failures occur singly, the computation will complete in an efficient manner. We discuss the details of how the algorithms are tuned for fault-tolerance and present the performance results on a PVM network of Sun workstations connected by a fast, switched ethernet.     

基于阶段并行模型的算法设计研究

NOWs正成为并行计算领域的一个新的发展热点,以太网构成的微机集群系统是NOWs的一种重要实现形式。阶段并行模型是BSP模型的改进,它更接近于表述实际的机器行为,同时具有编程简单、独立于体系结构和执行性能可预测等特点。文章研究了群集系统中阶段并行模型上的并行算法设计,以FFT算法为例,进行了设计和分析,并给出了测试结果。     

一个用于工作站网络的动态负载平衡算法

数学和科学计算中的大部分问题都可以用数据并行程序来开发其并行性,但是在工作站网络环境中,负载波动很大,负载平衡是影响其效率的一个重要因素。本文提出了一种动态负载平衡的算法,它可以使数据并行程序在运行时动态地调整负载。并且文中给出了这种算法的实验结果。     

Impact of platform heterogeneity on the design of parallel algorithms for morphological processing of high-dimensional image data

The main objective of this paper is to describe a realistic framework to understand parallel performance of high-dimensional image processing algorithms in the context of heterogeneous networks of workstations (NOWs). As a case study, this paper explores techniques for mapping hyperspectral image analysis techniques onto fully heterogeneous NOWs. Hyperspectral imaging is a new technique in remote sensing that has gained tremendous popularity in many research areas, including satellite imaging and aerial reconnaissance. The automation of techniques able to transform massive amounts of hyperspectral data into scientific understanding in valid response times is critical for space-based Earth science and planetary exploration. Using an evaluation strategy which is based on comparing the efficiency achieved by an heterogeneous algorithm on a fully heterogeneous NOW with that evidenced by its homogeneous version on a homogeneous NOW with the same aggregate performance as the heterogeneous one, we develop a detailed analysis of parallel algorithms that integrate the spatial and spectral information in the image data through mathematical morphology concepts. For comparative purposes, performance data for the tested algorithms on Thunderhead (a large-scale Beowulf cluster at NASA’s Goddard Space Flight Center) are also provided. Our detailed investigation of the parallel properties of the proposed morphological algorithms provides several intriguing findings that may help image analysts in selection of parallel techniques and strategies for specific applications.