机群系统中矩阵的并行QR分解算法

随着高速网络技术的快速发展,机群系统已经成为并行计算的主要平台,由于它的高通信延迟,某些在并行机上实现的细粒度并行算法已不适合在该环境下运行,为此有必要研究它们在机群系统中的并行实现。基于这一点,对矩阵的QR分解提出了一种新的任务划分策略,并由此得到了它的一种粗粒度并行算法。实验结果表明,设计的并行算法在机群系统中具有较高的加速比。     

Realistic efficiency evaluations for parallel computations under workstation cluster

In recent years high performance scientific computing under workstation cluster connected by local area network is becoming a hot point. Owing to both the longer latency and the higher overhead for protocol processing compared with the powerful single workstation capacity, it is becoming severe important to keep balance not only for numerical load but also for communication load, and to overlap communications with computations while parallel computing. Hence, our efficiency evaluation rules must discover these capacities of a given parallel algorithm in order to optimize, the existed algorithm to attain its highest parallel efficiency. The traditional efficiency evaluation rules can not succeed in this work any more. Fortunately, thanks to Culler's detail discuss in LogP model about interconnection networks for MPP systems, we present a system of efficiency evaluation rules for parallel computations under workstation cluster with PVm3.0 parallel software framework in this paper. These rules can satisfy above acquirements successfully. At last, two typical synchronous and asynchronous applications are designed to verify the validity of these rules under 4 SGIs workstations cluster connected by Ethernet.     

机群系统中矩阵的并行QR分解算法

随着高速网络技术的快速发展，机群系统已经成为并行计算的主要平台，由于它的高通信延迟，某些在并行机上实现的细粒度并行算法己不适合在该环境下运行，为此有必要研究它们在机群系统中的并行实现。基于这一点，本文对矩阵的QR分解提出了一种新的任务划分策略，并由此得到了它的一种粗粒度并行算法。实验结果表明，设计的并行算法在机群系统中具有较高的加速比。     

Optimal algorithms for scheduling large scale application on heterogeneous systems

This paper studies optimal algorithms for scheduling largescale application on heterogeneous systems using Divisible Load Theory. A more realistic and general model, i.e., both processors and communication links may have different speeds and arbitrary startup costs, and communication is in nonblocking mode, is introduced. Under such environment, the following results are obtained: ①Mathematic model and closedform expressions both for the processing time and the fraction of load for each processor are derived;②the influence of startup costs on the optimal processing time is analyzed; ③for a given heterogeneous systems and a largescale computing problem, optimal algorithms are proposed.     

一种新型发夹线耦合窄带带通滤波器的设计与实现

设计了一种与传统发夹型滤波器不同的窄带带通滤波器.通过在振荡器上加载一段开路短截线,并在短截线的中心减去一个小方形作为微扰元件,得到需要的窄带频率响应.使用全波电磁仿真软件Ansoft HFSS进行仿真优化,设计出了中心频率为2.64GHz、带宽为20MHz的窄带滤波器.实测结果与仿真结果基本一致.     

On increasing the parallelism in numerical algorithms

Parallel algorithms have been designed for the past 20 years initially by parallelising existing sequential algorithms for many different parallel architectures. More recently parallel strategies have been identified and utilised resulting in many new parallel algorithms. However the analysis of such algorithms reveals that further strategies can be applied to increase the parallelism. One of these, i.e., increasing the computational capacity in each processing node can reduce the congestion/communication for shared memory/distributed memory multiprocessor systems and dramatically improve the performance of the algorithm. Two algorithms are identified and studied, i.e., the cyclic reduction method for solving large tridiagonal linear systems in which the odd/even sequence is increased to a ‘stride of 3’ or more resulting in an improved algorithm. Similarly the Gaussian Elimination method for solving linear systems in which one element is eliminated at a time can be adapted to parallel form in which two elements are simultaneously eliminated resulting in the Parallel Implicit Elimination (P.I.E.) method. Numerical results are presented to support the analyses.     

电力系统潮流并行算法的研究进展

随着高性价比可扩展集群并行系统的逐步成熟和应用 ,大规模电力系统潮流并行计算和分布式仿真成为可能。该文首先简要介绍了电力系统的潮流计算模型及基本算法 ,分析了算法中存在的困难。然后分析了 4类较重要的电力系统潮流并行算法 :分块法、多重因子化法、稀疏矢量法和逆矩阵法 ,同时讨论了这 4种潮流并行算法的基本原理和实用效果 ,比较了各种并行算法的优点和局限性 ,并指出基于集群系统的粗粒度区域分解潮流并行算法最具发展潜力。     

Performance Metrics and Delay Thresholds for Multi-Link Cluster Monitoring in Seismic Profession

Seismic cluster nodes can be monitored by monitoring system,but thresholds for link failure alarm in monitoring systems are not determined presently,especially in different types of cluster links.Communication link types are discussed in seismic profession.By analyzing the characteristics of various links,the main performance metric,network latency,was proposed,which influenced states of communication links and gave the monitoring results deviation formula for judging the cluster monitoring system at different delay thresholds settings based on multiple-link delay error ratio analysis algorithm we offered.From the final experimental data of the monitoring system,fault alarm thresholds settings were posed under five different communication links,which had the instruction significance to the cluster monitoring in seismic profession.     

Optimizing a Parallel Video Encoder with Message Passing and a Shared Memory Architecture

Implementing video applications on emerging multi-core processors is a promising technique for personal, real-time multi-media applications. However, when porting the legacy parallel video encoders developed for clusters to shared-memory multi-cores, the existing parallel algorithms result in workload imbalances on different cores and communication inefficiencies. This paper describes a strip-wise parallel scheme to balance workloads and a hybrid communication mechanism to reduce communication overhead. The implementation of the H.264 parallel encoder on an eight CPU Intel Xeon system achieves 5x to 6x speed-up over a single thread encoder and achieves a 29% performance improvement over the commonly used master-slave schemes on clusters. The paper also gives further analysis on scalability, parallel efficiency, workload balance, and communication overhead as the number of cores varies.     

High-Performance Broadcasting Algorithms on Cluster

In many clusters connected by high-speed communication networks, the exact structure of the underlying communication network and the latency difference between different sending and receiving pairs may be ignored when they broadcast, such as in the approach adopted by the broadcasting method in MPICH，a widely used MPI implementation. However, the underlying network cluster topologies are becoming more and more complicated and the performance of traditional broadcasting algorithms, such as MPICH‘s MPI_Bcast, is far from good. This paper analyzed the impact of communication latencies and the underlying topologies on the performance of broadcasting algorithms for multilevel clusters. A multilevel model was developed for broadcasting in clusters with complicated topologies, which divides the cluster topology into many levels based on the underlying topology. The multilevel model was used to develop a new broadcast algorithm，MLM broadcast-2 (MLMB-2), that adapts to a wide range of clusters. Comparison of the performance of the counterpart MPI operation MPI_Bcast and MLMB-2 shows that MLMB-2 outperforms MPI_Bcast by decreasing the broadcast running time by 60%-90%.     

一种面向应用的开放式并行操作系统的设计原理

设计了一个能降低系统自举时间，避免系统调用瓶颈，容错，动态可变以及面向应用的开放式并行操作系统。系统范围的消息传递是低延迟高效率，把并行操作系统设计成一族程序模块，并行应用是这个族不可缺少的组成部分，利用面向对象来高效地实现这样的并行操作系统。     

多级负载平衡系统的设计和实现

目前机群系统中采用的负载平衡多是在作业、进程和线程中的任一级实现，很少有采用多级负载平衡的系统，其原因是为了减少在实现负载平衡的过程中引入的通信开销。该文提出了一种结合作业级和进程级的多级负载平衡算法，通过采用动态多阈值的自适应负载收集技术以减少通信开销。实验结果表明，这种负载平衡方法能够有效地提高并行作业的运行性能。     

量子计算及其应用

讨论量子计算机模型及其物理实现方案，量子计算过程，量子计算模型和量子并行算法，分析量子计算的指数级存储容量和指数加速特征，并简述量子计算和量子信息技术在保留通信、密码系统、数据库搜索等重要领域的应用。     

基于三维Mesh片上网络的双链路互连架构

片上网络(network on chip,NoC)作为一种全新的片上互连通信架构,面积受限,却具有丰富的线资源。而且,三维片上网络的层间互连线很短,同时提供了在第三维度上的互连扩展性。根据这些特性,该文提出了一种基于三维Mesh片上网络的双链路互连架构。在垂直方向上,该架构采用双链路互连,使其通信带宽加倍;而且,跨层连接的垂直链路降低了消息传输的路由跳数。这些都带来网络平均延时的降低和最大吞吐量的提高,却仅仅增加一些控制逻辑电路。仿真结果验证了理论分析。与传统的单链路架构相比,该架构以较小的面积开销换取了较大的性能提高。     

分布式随机迭代系统稳定性分析的并行算法

针对分布式随机迭代系统的特点,运用离散随机大系统的稳定性分析方法,提出一种易于作自动推理的分布式随机迭代系统稳定性并行分析法;解决了具有分布结构的随机迭代系统中出现的Ｌｙａｐｕｎｏｖ方程的高效并行算法问题．     

TTCAN周期性任务的优化调度算法

TTCAN周期性任务调度是最优装载问题的推广,它在通信时间关键的实时分布式系统中有着很强的应用背景.本文提出了4种确定基本周期的策略,给出了首次适应和最佳适应两种不同的可以在多项式时间内构造出TTCAN周期性任务调度表的算法,最后对不同规模下的两种算法的实验结果进行了比较,指出了两种算法在不同的周期策略下的渐近性能比.     

广域DGNSS信息大规模实时播发系统研究

实践证明广域DGNSS(Differential Global Navigation Satellite System，DGNSS)可有效提高定位精度和完好性,但在高层建筑物较多的城市或室内,由于建筑物对卫星信号遮挡严重,根本无法实现高精度定位导航,通过互联网播发增强信息,有其独特的优越性。通过研究基于互联网的广域DGNSS(IBWD)的系统组成,并设计了其网络结构。将i3组播和基于IP路由信息表的应用层组播相结合,构建了基于节点异构性的分层混合组播网络。分析IBWD的结构特点,建立其网络模型,结果显示,IBWD具有较好的实时性和可扩展性,可以很好地满足导航增强信息在互联网上播发的应用需求。     

现代浮空器军事应用

 现代浮空器在军事应用中最成熟、最普遍的是系留气球。本文介绍了系留气球相对于其他飞行器的优势,梳理了系留气球在军事应用中的主要作用,列举国外典型的系留气球系统;对系留气球的生存能力进行评估,分析了国外平流层飞艇在军事应用中的现状,最后对浮空器进行展望。     

Rank of loop, constraint degree of path, coupling degree of graph and their application

Some new concepts (rank of a loop, degree of freedom of a graph, path unit and ordered path arrangement, constraint degree of path, coupling degree of a graph, basic graph, etc. ), formulas, and algorithms, are proposed in this paper. Based on these concepts, a new systematic theory and practical method for the design of topological structure, kinematics and dynamics of mechanical systems is established. Some conjectures and problems needed to be researched are also put forward. The concepts, formulae and algorithms presented in this paper will find wide potential applications.     

电力系统低频振荡在线辨识的改进Prony算法

研究在线的振荡特征辨识算法是实现电力系统低频振荡在线监视以及广域阻尼控制的重要理论基础。广域测量系统的发展和应用使得低频振荡的在线辨识成为可能。该文提出了一种用于在线分析电力系统低频振荡的改进Prony算法,该算法针对输入信号的实际阶数和线性预测参数的估计进行了综合改进。经过算法时间复杂度的分析,证明改进算法提高了计算速度。计算机仿真和动模实验结果表明,改进算法能够得到更符合系统实际阶数的降阶模型,分析计算占空比小于4%,满足在线低频振荡辨识和系统振荡特性分析的需要。