求解三对角线性方程组的双向并行分裂法

首先回顾了Ｈ．Ｈ．Ｗａｎｇ的分裂法＾［８］Ｍｉｃｈｉｅｌｓｅ＆Ｖｏｒｓｔ给出的改进算法＾［９］，分析了影响分裂法及改进算法的并行效率的主要因素，然后提出了一种求解三对角方程组的双向并行分裂法（简记为ＤＰＰ算法），ＤＰＰ算法的通讯建立的次数为Ｍ＆Ｖ算法的５０％，数据传输量为其３０％，最后在工作站网络环境下实现了ＤＰＰ算法，并就并行效率与Ｍ＆Ｖ算法进行了比较，结果表明在由６台工作站组成的网络中ＤＰＰ算     

工作站网络环境中三对角方程组并行求解

此文考虑工作站网络环境中三对角方程组的有效并行求解，其中每台处理机只拥有原方程组的部分等式信息，并提出适合于分布主存并行计算的并行ＬＵ分解算法，同时给出算法的计算与通讯的复杂性分析；并从理论及实验两方面阐述了缩减系统求解策略是影响算法在多机系统中求解效率的重要因素；所有算法由ＰＶＭ软件系统，支持实现并在工作站网络环境中测试。     

三对角线性方程组的分布式并行算法

文中回顾了Ｍｉｃｈｉｅｌｓｅ＆Ｖｏｒｓｔ算法，分析了影响Ｍ＆Ｖ．算法并行效率的主要因素，根据分布治之思想提出了一种求解三对角方程组的并行算法，新算法通信建立次数的Ｍ＆Ｖ算法的５０％，数据传输量为其３３％，最后的工作站网络环境下实现了新算法，就并行效率与Ｍ＆Ｖ算法进行了比较，结果表明在由６台工作站的组成的网络中新算法必能提高可达到４０％。     

工作站网络环境下的并行计算

当前工作站网络环境（ＮＯＷｓ）下高性能科学与工程计算是并行计算的一个热门话题，本文借助于ＬｏｇＰ并行计算模型，提出了一套新的效率评价准则，用于优化并行算法效率以达到最佳实现效果，揭示了影响算法并行效率发挥的关键因素，并从算法和程序设计角度提出了相应措施，探讨了急需解决的几个关键性问题，三个典型应用问题的数值实验结果文中给出。     

基于龙格库塔法的弹塑性有限元并行计算

基于MPI集群环境对弹塑性区域分解有限元并行计算进行研究。提出了基于三阶和四阶的龙格库塔（Runge-Kutta）方法对应力-应变关系进行积分的算法。积分过程中自动调整子步大小来控制积分过程中的误差。研制了采用最小残余平滑法的子结构预处理共轭梯度并行求解算法。算法在基于工作站机群的并行环境下实现。计算结果表明：该算法具有良好的并行加速比和效率,是一种有效的并行求解算法。     

基于IFWA-ELM的六维力传感器解耦算法

针对六维力传感器的维间耦合严重影响测量精度的问题，本文提出了一种基于改进烟花算法优化极限学习机（IFWA-ELM）的解耦算法。首先，对烟花算法的爆炸半径、变异算子和选择策略进行改进，形成改进烟花算法（IFWA）。其次，采用改进烟花算法寻找极限学习机的最佳网络参数，解决极限学习机随机生成初始权值和阈值导致网络不稳定、隐含层神经元数量对网络性能影响较大的问题。为了验证算法的解耦性能，本文以应用于4500m深海机械臂的六维力传感器作为研究对象，采用最小二乘法（LS）、BP神经网络（BPNN）、极限学习机（ELM）和IFWA-ELM算法进行解耦实验。实验结果表明：IFWA-ELM算法具有较好的非线性解耦能力，解耦后Ⅰ类误差控制在0.27%以内，Ⅱ类误差控制在0.13%以内，有效提高了六维力传感器的测量精度。     

大规模生物网络马尔可夫聚类的并行化算法

马尔可夫聚类算法（MCL）是在大规模生物网络中寻找模块的一个有效方法，能够挖掘网络结构和功能影响力较大的模块。算法涉及到大规模矩阵计算，因此复杂度可达立方阶次。针对复杂度高的问题，提出了基于消息传递接口（MPI）的并行化马尔可夫聚类算法以提高算法的计算性能。首先，生物网络转化成邻接矩阵；然后，根据算法的特性，按照矩阵的规模判断并重新生成新矩阵以处理非平方倍数矩阵的计算；其次，并行计算通过按块分配的方式能够有效地实现任意规模矩阵的运算；最后，循环并行计算直至收敛，得到网络聚类结果。通过模拟网络和真实生物网络数据集的实验结果表明，与全块集体式通信（FCC）并行方法相比，平均并行效率提升了10个百分点以上，因此可以将该优化算法应用在不同类型的大规模生物网络中。     

在PVM应用程序中调用ScaLAPACK库函数方法

１．引言ＳｃａＬＡＰＡＣＫ是村卫ｆａｂｌｅＬｉｎｅａｒＡｌｇｅｂｒａＭａｇｅ的缩写，是为在基于消息传递的ＭＩＭＤ并行计算机系统上解数值线性代数问题，并由美国橡树岭国家实验室和田纳西大学等联合开发．它支持对（）线性代数方程组问题（）最小二乘问题（３特征值问题（４）奇异值分解等问题的求解（参见文献［１—３１）．这些问题由于在科学与工程计算中经常出现，它们的高效求解成了应用程序获得高性能的关键．随着计算机的发展，相继开发了ＬｉｎＰａｃｋ；ＥｉｓＰａｃｋ；ＬＡＰＡＣＫ和ＳｃａＬＡＰＡＣＫ等数值软件包，利…     

求解一般带状线性方程组的解耦分解并行算法

本文给出了适用于ＭＩＭＤ多处理机系统的求解一般带状线性方程组的解耦分解并行算法，并在Ｓ１０－２并行机上进行了数值实验，理论分析和数值实验的结果表明，该并行算法是有效的。     

神经网络的具有自适应动量和步长的伪牛顿算法

以单隐层的３层前向神经网络为基础，由自适应ＢＰ算法和牛顿优化算法导出了自适应步长和动量解耦的伪牛顿算法（ＱＮＡＤＳＭ）．该算法计算量小，收敛速度快．文中还给出了该算法的收敛性证明、算法的仿真结果及其它算法的比较结果，并对网络的训练及该算法的特点作了进一步的讨论．仿真结果表明ＱＮＡＤＳＭ算法是一种有效的工程实用算法．     

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

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

PORTING REGULAR APPLICATIONS ON HETEROGENEOUS WORKSTATION NETWORKS: PERFORMANCE ANALYSIS AND MODELING

Abstract

Heterogeneous networks of workstations and/or personal computers (NOW) are increasingly used as a powerful platform for the execution of parallel applications. When applications previously developed for traditional parallel machines (homogeneous and dedicated) are ported to NOWs, performance worsens owing in part to less efficient communications but more often to unbalancing.

In this paper, we address the problem of the efficient porting to heterogeneous NOWs of data-parallel applications originally developed using the SPMD paradigm for homogeneous parallel systems with regular topology like ring.

To achieve good performance, the computation time on the various machines composing the NOW must be as balanced as possible. This can be obtained in two ways: by using an heterogeneous data partition strategy with a single process per node, or by splitting homogeneously data among processes and assigning to each node a number of processes proportional to its computing power. The first method is however more difficult, since some modifications in the code are always needed, whereas the second approach requires very few changes.

We carry out a simplified but reliable analysis, and propose a simple model able to simulate performance in the various situations. Two test cases, matrix multiplication and computation of long-range interactions, are considered, obtaining a good agreement between simulated and experimental results.

Our analysis shows that an efficient porting of regular homogeneous data-parallel applications on heterogeneous NOWs is possible. Particularly, the approach based on multiple processes per node turns out to be a straightforward and effective way for achieving very satisfying performance in almost all situations, even dealing with highly heterogeneous systems.     

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

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

Parallel implementation of back-propagation algorithm in networks of workstations

This work presents an efficient mapping scheme for the multilayer perceptron (MLP) network trained using back-propagation (BP) algorithm on network of workstations (NOWs). Hybrid partitioning (HP) scheme is used to partition the network and each partition is mapped on to processors in NOWs. We derive the processing time and memory space required to implement the parallel BP algorithm in NOWs. The performance parameters like speed-up and space reduction factor are evaluated for the HP scheme and it is compared with earlier work involving vertical partitioning (VP) scheme for mapping the MLP on NOWs. The performance of the HP scheme is evaluated by solving optical character recognition (OCR) problem in a network of ALPHA machines. The analytical and experimental performance shows that the proposed parallel algorithm has better speed-up, less communication time, and better space reduction factor than the earlier algorithm. This work also presents a simple and efficient static mapping scheme on heterogeneous system. Using divisible load scheduling theory, a closed-form expression for number of neurons assigned to each processor in the NOW is obtained. Analytical and experimental results for static mapping problem on NOWs are also presented.     

一种基于检查点的卷回恢复与进程迁移系统*

ChaRM是一种并行程序后向故障恢复与进程迁移系统.它不仅实现了对工作站机群系统瞬时故障的恢复,而且通过检查点设置时的Mirror存储技术和进程迁移技术,实现了对机群系统结点永久故障的恢复,并支持系统软硬件的在线维护、处理机资源的排他/限时使用和动态负载平衡等功能.文章主要介绍ChaRM系统的检查点设置与回卷恢复、进程迁移等实现技术,并给出了部分性能评测结果.     

Evaluating scheduling policies for fine-grain communication protocols on a cluster of SMPs

Distributed-memory parallel computers and networks of workstations (NOWs) both rely on efficient communication over increasingly high-speed networks. Software communication protocols are often the performance bottleneck. Several current and proposed parallel systems address this problem by dedicating one general-purpose processor in a symmetric multiprocessor (SMP) node specifically for protocol processing. This protocol processing convention reduces communication latency and increases effective bandwidth, but also reduces the peak performance since the dedicated processor no longer performs computation. In this paper, we study a parallel machine with SMP nodes and compare two protocol processing policies: the Fixed policy, which uses a dedicated protocol processor; and the Floating policy, where all processors perform both computation and protocol processing. The results from synthetic microbenchmarks and five macrobenchmarks show that: (i) a dedicated protocol processor benefits light-weight protocols much more than heavy-weight protocols, (ii) a dedicated protocol processor is generally advantageous when there are four or more processors per node, (iii) multiprocessor node performance is not as sensitive to interrupt overhead as uniprocessor node because a message arrival is likely to find an idle processor on a multiprocessor node, thereby eliminating interrupts, (iv) the system with the lowest cost-performance will include a dedicated protocol processor when interrupt overheads are much higher than protocol weight—as in light-weight protocols.     

工作站网络系统进程迁移机制

进程迁移是工作站网络系统实现负载平衡、提高系统可用性功能的重要手段.该文提出了一种基于接收/发送方消息记录的进程迁移技术.它在消息传递库PVM(parallel virtual machine)之上实现,具有对用户程序透明、可移植性好、开销小和实现简单等特点.此技术已实际应用于作者自行研制的“并行程序运行回卷恢复与进程迁移系统—ChaRM(checkpointing-based rollback recovery and migration system)”中.     

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

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

群机系统上单并发任务簇的近优分配算法

缩短程序的序的时间是并行处理的首要目标,有效的任务分配算法是实现这一目标的关键,对群机４系统来说更是如此。文中针对并行语言中常用的并行范式－单并发任务簇提出了近优分配算法ＯＰＴＡ,并在群机系统上做了与ＭＨ算法的比照实验,结果表明较ＭＨ算法缩短程序执行时间１０％左右．