一种改进的全区域覆盖算法

针对Fukushima提出的求解无约束最优化问题的同步并行转换算法(PVT),提出一个整体异步并行算法,该算法去除了并行计算中同步与通信的开支.在一定的条件下,证明,该算法具有全局收敛性以及线性收敛速度.数值试验结果表明,异步PVT算法优于同步PVT算法.     

一个无约束优化问题并行算法的异步执行

在这篇文章里,我们对Fukushima提出的关于无约束优化问题的PVT算法作了改进,提出利用PVD算法中的PVD-方向来构造的PVT-变换矩阵,得到一个更适合于异步执行的PVT算法,从而减少各处理机之间的等待时间,提高并行机的并行效率．文中证明算法具有线性收敛速度,且其线性收敛比与处理机个数无关,该结果改进了中的结果,更适合于并行计算．     

多类关联规则生成算法

针对传统关联规则算法产生的规则关联性弱、种类少的缺点,结合Spearman秩相关系数,提出了一种多类关联算法。该算法在传统算法产生的强规则基础上,利用Spearman秩相关方法计算出规则中产品间的同步异步等相关性。将其作为兴趣度阈值,算法可同时产生同步正规则、异步正规则、同步负规则和异步负规则四类关联规则,且规则间联系紧密。实验结果表明了算法的有效性和优越性。     

异步网络中萤火虫同步改进算法研究

根据对频率同步网络中的时间同步技术的研究,现提出一种频率异步网络中的加窗耦合算法。该算法主要基于M S模型,网络拓扑中节点的相位增量摒弃传统萤火虫同步中的‘遇激则增’原则,通过加窗来筛选脉冲,进而实现节点相位突变;对于已同步的节点集合,采用周期最值原则,最终实现全网节点的频率和相位全同步。应用数学几何原理对该算法的同步性能进行了理论分析,最后通过仿真实验验证本方案,实验结果表明在频率异步网络中,该算法实现了全同步,符合预期分析。     

基于OFDM的跨小区下行链路异步多用户检测

针对3GPP长期演进计划(LTE)下行链路的OFDMA传输以及基站之间异步部署的特点,引入了异步OFDM干扰消除问题来改善小区边缘用户的服务质量以及提高整个蜂窝系统的下行容量.在同步OFDM-IDMA原理的基础上,提出了低复杂度的基于滑动窗口的异步多用户检测算法.仿真结果表明,在窗口长度很小的情况下,该异步检测算法仍然可以在高信噪比区域接近同步的性能.     

偶发实时系统可调度性分析问题的整数规划方法

偶发实时任务最早截止期优先（earliest deadline first,简称EDF）可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法（pseudo-polynomail time decision algorithm,简称PTDA）均局限于利用率U严格小于1的同步任务系统.对于U≤1的同步系统或更加困难的异步系统,现有PTDA则不再适用.针对以上问题,为同步和异步两类实时系统建立了统一的整数规划模型,其规模并不依赖于利用率U的取值.基于多面体理论证明了模型维数和极大诱导不等式,进而提出了同/异步系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法.实验结果表明,该方法能够获得较紧的问题解下界,在异步和同步系统中,线性松弛解与最优解之间的平均百分界差gap分别为0.78%和1.27%.另外,随机生成了大量同步和异步系统的算例,用于该算法和传统算法进行性能比较.对于同步算例,实验结果表明,在U>0.99时,该算法能够对70%的算例给出判定结果,算法性能与QPA算法相比有指数级提升.对于异步算例,实验结果表明,该算法能够对近96%的算例给出可调度性判定.与传统算法相比,该方法将不能判定可调度性的算例比例平均降低了29.27%.对于剩余的4%的算例,该算法将可调度上界的值平均降低了近10⁴倍.     

工作流中同步区与异步区的动态修改

在信牌驱动模型中使用同步区/异步区规则旨在解决在不同语义环境下的同步问题。在动态修改中需要解决的一个重要问题便是正确地将同步区修改为异步区或将异步区修改为同步区,即在合适的信牌箱中添加或删除假信牌。深入分析了将同步区修改为异步区及将异步区修改为同步区的策略与算法,并讨论了算法的合理性。最后给出了一些典型的对同步区/异步区进行动态修改的实例。     

一种无权重的高性能CICQ结构调度算法

在Crossbar交换单元的交叉节点加少量缓存的组合输入交叉节点排队(CICQ)结构,具有调度算法简单、性能优良、适于高速大容量路由器实现的特点。在总结现有研究成果的基础上,提出了一种避免仲裁指针同步的异步指针轮询算法。该算法将所有的输入、输出仲裁器的指针全部设置为异步,每个时隙静态地更新所有的仲裁器的指针,以达到网络指针去同步的目的。仿真结果表明,该算法在保持无权重算法简单性同时对不同业务流下的时延和吞吐率性能均有明显改善。     

基于同步和异步时间管理的混合时间管理算法

基于HLA的并行分布式仿真是目前仿真的一种趋势.HLA的接口规范中定义了六类服务,其中时间管理服务是保证联邦成员之间正确交互的基础.时间管理服务保证了在仿真过程中所发生的事件在逻辑上的正确性,以及所发送的消息在逻辑上的有序性.实现该管理机制有两种方法:保守时间推进算法和乐观时间推进算法.而保守时间推进又可以通过异步时间管理算法或同步时间管理算法来实现,异步和同步算法各有优缺点,这使得它们的运用具有一定的局限性.文中全面分析了异步和同步时间管理算法的优缺点,在此基础上提出了一种将两者结合,进行优缺点互补的混合时间管理算法,以此来提高保守时间推进算法的效率,使其能更好地运用于RTI中.并通过实验验证了该混合算法的有效性.     

并行环境下的同步异步PSO算法

并行计算能够有效地缩减求解大规模问题的时间.文中在介绍了粒子群算法(Particle Swarm Optimization algo rithm)的基础上,对PSO算法的同步异步模型进行分析,给出了并行环境下的同步异步PSO算法.该并行算法在联想深腾1800大型汁算机上测试.实验证明PSO算法具有较高的并行性,并行算法明显提高了求解的速度.     

Parallel synchronous and asynchronous coupled simulated annealing

The Journal of Supercomputing - We propose a parallel synchronous and asynchronous implementation of the coupled simulated annealing (CSA) algorithm in a shared-memory architecture. The original...     

Benchmarking Explicit State Parallel Model Checkers

This paper presents a set of benchmarks and metrics for performance reporting in explicit state parallel model checking algorithms. The benchmarks are selected for controllability, and the metrics are chosen to measure speedup and communication overhead. The benchmarks and metrics are used to compare two parallel model checking algorithms: partition and random walk. Implementations of the partition algorithm using synchronous and asynchronous communication are used. Metrics are reported for each benchmark and algorithm for up to 128 workstations using a network of dynamically loaded workstations. Empirical results show that load balancing becomes an issue for more than 32 workstations in the partition algorithm and that random walk is a reasonable, low overhead, approach for finding errors in large models. The synchronous implementation is consistently faster than the asynchronous. The benchmarks, metrics and results given here are intended to be a starting point for a larger discussion of performance reporting in parallel explicit state model checking.     

基于EDA的并行基因表达式程序设计方法

将分布评估算法(EDA)引入基因表达式程序设计方法中,以提高其收敛速度。为减少计算时间,提高解质量,在加入EDA的基因表达式程序设计方法的基础上设计了同步和异步分布式并行算法,同时比较了同步和异步并行算法。实验结果表明,并行算法提高了运行速度和解质量。最后通过实验分析了迁移代频对并行算法的影响。     

MPI implementation of parallel subdomain methods for linear and nonlinear convection–diffusion problems

The solution of linear and nonlinear convection–diffusion problems via parallel subdomain methods is considered. MPI implementation of parallel Schwarz alternating methods on distributed memory multiprocessors is discussed. Parallel synchronous and asynchronous iterative schemes of computation are studied. Experimental results obtained from IBM-SP series machines are displayed and analyzed. The benefits of using parallel asynchronous Schwarz alternating methods are clearly shown.     

APHID: Asynchronous Parallel Game-Tree Search

Most parallel game-tree search approaches use synchronous methods, where the work is concentrated within a specific part of the tree or at a given search depth. This article shows that asynchronous game-tree search algorithms can be as efficient as or better than synchronous methods in determining the minimax value.  APHID, a new asynchronous parallel game-tree search algorithm, is presented. APHID is implemented as a freely available portable library, making the algorithm easy to integrate into a sequential game-tree searching program. APHID has been added to four programs written by different authors. APHID yields better speedups than synchronous search methods for an Othello and a checkers program and comparable speedups on two chess programs.     

Asynchronous Schwarz methods applied to constrained mechanical structures in grid environment

This paper deals with the parallel solution of the stationary obstacle problem with convection–diffusion operator. The obstacle problem can be formulated by various ways and in the present study it is formulated like a multivalued problem. Another formulation by complementary problem is also considered. Appropriate discretization schemes are considered for the numerical solution on decentralised memory machines by using parallel synchronous and asynchronous Schwarz alternating algorithms. The considered discretization schemes ensure the convergence of the parallel synchronous or asynchronous Schwarz alternating methods on one hand for the solution of the multivalued problem and on the other hand for the solution of the complementary problem. Finally the implementation of the algorithms is described and the results of parallel simulations are presented.     

Parallel simulations of multiprocessors

This paper describes the implementation and the performance of a synchronous, parallel discrete event simulation (SPaDES) method on two shared memory multiprocessors. The presented method aims at the efficient simulation of architectural designs for which the asynchronous PDES methods are less effective. A multiprocessor machine is simulated, and the performance achieved is compared to the performance of a parallel version of the centralized-time synchronous simulation method. The results show that the SPaDES method alleviates bottlenecks usually attributed to synchronous methods, and thus we are able to efficiently exploit most of the parallelism available in the simulation of synchronous architectural designs.     

JACK: an asynchronous communication kernel library for iterative algorithms

This article presents a new communication library developed to ease the implementation of both asynchronous and synchronous iterative methods. A mathematical and algorithmic framework about fixed-point methods is described to introduce this class of parallel iterative algorithms, although this library can be used for a larger class of parallel algorithms. After an overview of the main features, we describe detailed implementation aspects arising from the asynchronous context. While the library is mainly based on top of Message Passing Interface library, it has been designed to be easily extended to other types of communication middleware. Finally, some numerical experiments validate this new library, used for implementing both a classical parallel scheme and a sub-structuring approach of the Jacobi iterative method.     

Asynchronous grid computation for American options derivatives

In relation with the mathematics of financial applications, the present study deals with the solution of the time dependent obstacle problem defined in a three-dimensional domain; this problem arises in the pricing of American options derivatives. In order to solve very quickly large scale algebraic systems derived from the discretization of the obstacle problem, the parallelization of the numerical algorithm is necessary. So, we present parallel synchronous, and more generally asynchronous, iterative algorithms to solve this problem. For the considered problem, arguments implying the convergence of parallel synchronous and asynchronous algorithms are given in a general framework. Finally, computational experiments on GRID’5000, the French national grid, are presented and analyzed. They allow us to compare both synchronous and asynchronous versions with local and distributed clusters and to show the interest of such methods in the context of grid computing.