并行算法的发展与展望

本文综述三个方面的问题。首先介绍并行算法概念及其作用,并给出并行算法加速比的三种不同定义公式;第二介绍了并行算法的发展概况,重点阐述了并行算法所经历的三个阶段以及每一阶段,并行算法研究特点;第三浅谈了九十年代并行算法研究展望,提出并行算法基础研究和应用方面所关心内容。     

容错并行算法的性能分析

容错并行算法是一种应用级容错方法,它通过并行复算的方法实现快速的故障恢复.容错并行算法是在并行算法设计的基础上增加了容错设计部分,因此其性能评估必须考虑故障对程序性能的影响.研究了评估故障情况下容错并行算法性能的各种度量,建立了性能模型预测容错并行算法的期望执行时间,以此为基础评估了程序段的运行时间、数据保存开销、故障率以及并行复算加速比等系统参数对容错并行算法性能的影响.     

挖掘关联规则的并行算法

从大型数据库中挖掘关联规则是数据挖掘中一个重要的课题 .从挖掘要求的时间和空间上看 ,传统的顺序算法已很难适应于现实中不断增大的数据库规模 .而研究和发展高性能、可扩展的并行算法对解决这一问题就显得十分必要 .本文介绍了挖掘关联规则一些主要的并行算法 ,并对它们进行了一定分析 ,指出了发展并行算法要考虑的一些问题 .     

并行算法可伸缩性的E微商分析法

1.引言 并行算法在并行体系结构上的可伸缩性分析(Scalability analysis)是目前巨量并行理MPP研究的中心问题之一。可伸缩性作为巨量并行机上并行算法的主要性能指标,揭示了在性能计算机     

基于PRAM模型的二叉树A序列并行算法的研究

运用并行计算的PRAM模型研究二叉树A序列问题,提出了二又树的A序列的一种并行算法,并以应用实例对并行算法的过程进行详细描述和验证性分析.二叉树A序列的并行算法,为应用到二叉树序列遍历的系统与应用程序的并行化问题的解决提供借鉴和参考.     

物理场图形生成的多处理机并行算法的研究和实现

计算机图形生成的并行处理是结合图形学、并行处理及并行算法交叉而产生的一个新课题.本文首先介绍了近几年来这一领域的发展,然后针对计算机图形学领域发展最为迅速的分支之一——物理场的图形显示,利用最新提出的并行算法进行了研究和实现,并就其在两种并行处理机环境下的具体实现进行了结果分析.     

分布并行算法分析与设计

计算机计算方法从单机技术发展到多机并行技术,这是计算机计算模式适应未来科技发展的趋势,国家的科技发展需要并行处理技术的推动,并行处理技术能快速地发展,源动力来自于人们对工程计算机能力的需求.在这几年,并行处理技术得到很大的推动与发展,并行算法处理技术的应用提高了计算机大数据处理的能力.介绍并行算法应用情况的背景和研究现状,阐述了并行算法技术的分类及设计方法.     

一种计算一维离散Fourier变换的MIMD并行算法

1.引言 一维离散Fourier变换(即一维DFT)的快速计算是许多应用领域的迫切要求,若干年来,人们从软、硬方面对此进行了深入研究,提出了不少高效的串、并算法和专用硬件,随着多处理机的广泛应用,研究计算一维DFT的多处理机并行算法(即MIMD并行算法)具有重要意义。     

构造宏流水线并行算法的一种有效方法

本文基于任务相关、作业排队等理论,提出构造宏流水线并行算法的一种有效方法,并且利用这种方法构成了一组用于数字信号处理的线性和非线性宏流水线并行算法.其中部分算法已应用于分布式自动控制与测试系统FZC-1中,具有并行计算效率高和性能价格比好等优点.     

基于SIMD-SM模型的树的后根遍历并行算法

文章基于SIMD-SM模型研究树的遍历问题,运用遍历树的边的思维方法,实现了树的后根遍历的一种并行算法,并且对该并行算法的复杂性进行了分析。     

并行智能优化算法研究进展

基于种群迭代搜索的智能优化算法在农业、交通、工业等很多领域都取得了广泛的应用.但是该类算法迭代寻优的特点使其求解效率通常较低,很难应用到大规模、高维或实时性要求较高的复杂优化问题中.随并行分布式技术的发展,国内外很多学者开始着手研究智能优化算法的并行化.本文首要介绍了并行智能优化算法的基本概念;其次从协同机制、并行模型以及硬件结构3个维度综述了几类常见的并行智能优化算法,详细分析阐述了它们优点及不足;最后对并行智能优化算法的未来研究进行了展望.     

The two list algorithm for the knapsack problem on a FPS T20

The advent of parallel machines brought about a controverse in the domain of parallel algorithms: is it worth to conceive parallel algorithms for NP-complete problems? In this work we present a parallel implementation of a sequential algorithm from Horowitz and Sahni for the knapsack problem on a FPS T20. Our aim is to establish some experimental results in order to allow comparisons for forthcoming works. The results show that the development of theory and technology yields the computation tractability of very large knapsack problems.     

Parallel metaheuristics: recent advances and new trends

The field of parallel metaheuristics is continuously evolving as a result of new technologies and needs that researchers have been encountering. In the last decade, new models of algorithms, new hardware for parallel execution/communication, and new challenges in solving complex problems have been making advances in a fast manner. We aim to discuss here on the state of the art, in a summarized manner, to provide a solution to deal with some of the growing topics. These topics include the utilization of classic parallel models in recent platforms (such as grid/cloud architectures and GPU/APU). However, porting existing algorithms to new hardware is not enough as a scientific goal, therefore researchers are looking for new parallel optimization and learning models that are targeted to these new architectures. Also, parallel metaheuristics, such as dynamic optimization and multiobjective problem resolution, have been applied to solve new problem domains in past years. In this article, we review these recent research areas in connection to parallel metaheuristics, as well as we identify future trends and possible open research lines for groups and PhD students.     

Applying asynchronous parallel characteristic methods for solving systems of hyperbolic PDEs

We propose asynchronous parallel algorithms for numerically solving systems of hyperbolic partial differential equations. The algorithms are based on the solutions along the characteristic directions. We show that the characteristic directions can be computed in parallel without the need for sharing information or synchronizing on a common time step. This permits the development of efficient asynchronous parallel algorithms. Our solutions cover the cases when the characteristic lines are intersected to form shock waves. We discuss the time performance of our algorithms as well as their implementation on a parallel computer.Supported by the R&D administration of the Ministry of Defense and the Ministry of Immigration Absorption, Israel.     

Experiences with a parallel algorithm for data flow analysis

We have designed a family of parallel data flow analysis algorithms for execution on distributed-memory MIMD machines, based on general-purpose, hybrid algorithms for data flow analysis [Marlowe and Ryder 1990]. We exploit a natural partitioning of the hybrid algorithms and explore a static mapping, dynamic scheduling strategy. Alternative mapping-scheduling choices and refinements of the flow graph condensation used are discussed. Our parallel hybrid algorithm family is illustrated on Reaching Definitions, although parallel algorithms also exist for many interprocedural (e.g., Aliasing) and intraprocedural (e.g., Available Expressions) problems [Marlowe 1989]. We have implemented the parallel hybrid algorithm for Reaching Definitions on an Intel iPSC/2. Our empirical results suggest the practicality of parallel hybrid algorithms.An earlier version of this paper was presented at Supercomputing '90.The research reported here was supported, in part, by the New Jersey Commission on Science and Technology and the CAIP Center's Industrial Members, by Siemens Research Corporation and by National Science Foundation grant CCR-8920078.     

基于PRAM并行模型最大值查找的方法与改进

随着多处理器的出现,并行技术受到了广泛的关注,成为了加速处理问题速度的重要技术.但是使用并行技术在加速计算的同时也带来了对处理器数量需求的急剧提升,并行成本的显著增加.针对这一问题,通过研究基于PRAM （Parallel Random Access Machine）下的3种最大值查找并行算法中的不足,提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本（cost）更优的基于数据划分方法的最大值查找并行算法.基于数据划分方法的最大值查找算法有效的解决了现有并行方法中处理器工作量分配不均,对处理器需求过大,实现条件苛刻等问题.为此后类似并行算法降低并行成本提供一个方向.     

Solving Systems of Linear Equations with Relaxed Monte Carlo Method

The problem of solving systems of linear algebraic equations by parallel Monte Carlo numerical methods is considered. A parallel Monte Carlo method with relaxation is presented. This is a report of a research in progress, showing the effectiveness of this algorithm. Theoretical justification of this algorithm and numerical experiments are presented. The algorithms were implemented on a cluster of workstations using MPI.     

遗传算法的初步研究及改进后的遗传算法程序IGA1.0

遗传算法是近年来被广泛应用的一种非线性和并行算法。本文研究了几种改进遗传算法效率，提高搜索速度的方法，引入了两种变异的方法，并根据最大最小适应值的差值对适应值函数进行了修正，同时，对三种算子进行了重新安排以拓展搜索工在搜索过程中加入排序以提高杂交效率，同传统的遗传算法相 文的遗传算法没有使用固定的变异率和杂交率，而是让它们随着搜索过程中群体中的个体的重复情况改变，用经典的验证函数检验，这些改进提高     

Scalable Parallel Genetic Algorithms

Genetic algorithms, search algorithms based on the genetic processes observed in natural evolution, have been used to solve difficult problems in many different disciplines. When applied to very large-scale problems, genetic algorithms exhibit high computational cost and degradation of the quality of the solutions because of the increased complexity. One of the most relevant research trends in genetic algorithms is the implementation of parallel genetic algorithms with the goal of obtaining quality of solutions efficiently. This paper first reviews the state-of-the-art in parallel genetic algorithms. Parallelization strategies and emerging implementations are reviewed and relevant results are discussed. Second, this paper discusses important issues regarding scalability of parallel genetic algorithms.     

Towards a single model of efficient computation in real parallel machines

We propose a model of parallel computation, the YPRAM, that allows general parallel algorithms to be designed for a wide class of parallel models. The basic model captures locality among processors, which is measured as a function of two parameters; latency and bandwidth.

We design YPRAM algorithms for solving several fundamental problems: parallel prefix, sorting, sorting numbers from a bounded range, and list ranking. We show that our model predicts, reasonably accurately, the actual known performances of several basic parallel models — PRAM, hypercube, mesh and tree — when solving these problems.