首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 171 毫秒
1.
乐观策略下并行离散事件仿真动态负载划分优化算法   总被引:4,自引:0,他引:4  
动态负载划分是提高并行离散事件仿真运行性能的有效途径之一.现有研究往往孤立地考虑计算负载平衡和通信负载优化,使得复杂应用背景下整体性能低下.论文综合考虑仿真模型计算负载和交互模式,提出了一个基于带权重无向图有限容量k划分问题的并行离散事件仿真负载划分模型,并配合一套通用的仿真运行性能度量方法,提出了一个基于顶点交换的启发式局部搜索近似划分算法,实现了在计算负载平衡的前提下系统通信负载最优化,其近似解与全局最优解比值不小于(1-1/|N|)(1-ε).实验证明了该动态负载划分算法的有效性和实用性.  相似文献   

2.
基于数据空间融合的全局计算与数据划分方法   总被引:2,自引:1,他引:2  
夏军  杨学军 《软件学报》2004,15(9):1311-1327
计算与数据划分问题是影响并行程序在分布主存多处理机中执行性能的重要因素,也是并行编译优化的重点.针对该问题,提出了一套关于数据空间融合的理论框架,并基于该框架给出了一种有效的全局计算与数据划分方法,用于分布主存计算环境中的计算与数据划分问题的求解.该方法能够尽量开发计算空间的并行度,利用数据融合技术优化数据分布,并能搜寻优化的全局计算与数据划分.该方法还能很自然地与数据复制以及偏移常量的对准结合在一起,从而使得数据通信量尽可能地小.实验结果表明了所提出方法的有效性.  相似文献   

3.
分布存储系统中优化通信的冗余计算分割   总被引:1,自引:0,他引:1  
针对并行循环套序列,提出一种冗余计算分割的通信优化方法,根据数据流分析,文中给出用以确定每个循环套的冗余计算量的一般方法,并在此基础上提出冗余计算分割的实现和判定,针对规则依赖的程序,该文还提出了一个高效的冗余计算分割的实现方法,该技术已经在一个并行编译器中实现,试验结果表明,它比传统的通信优化技术有明显的优越性。  相似文献   

4.
计算划分问题是并行编译中最为重要的问题之一.针对并行循环,在数据分布确定的情况下,提出了基于规范集的计算划分算法,具体讨论了规范集的获取方法及综合通信与负载均衡的最优方案选取算法.实验表明,在并行循环处理方面,这一算法与以前几种算法相比更加简单、有效;采用这一算法的p_HPF编译器对数据并行应用问题可以获得良好的加速比和效率.该编译器已在石油领域得到应用.  相似文献   

5.
刘晓娴  赵荣彩  赵捷  徐金龙 《软件学报》2014,25(6):1154-1168
发掘DOACROSS 循环中蕴含的并行性,选择合适的策略将其并行执行,对提升程序的并行性能非常重要.流水并行方式是规则DOACROSS 循环并行的重要方式.自动生成性能良好的流水并行代码是一项困难的工作,并行编译器对程序自动并行时常常对DOACROSS 循环作保守处理,损失了DOACROSS 循环包含的并行性,限制了程序的并行性能.针对上述问题,设计了一种选择计算划分循环层和循环分块层的启发式算法,给出了一个基于流水并行代价模型的循环分块大小计算公式,并使用计数信号量进行并行线程之间的同步,实现了基于OpenMP 的规则DOACROSS 循环流水并行代码的自动生成.通过对有限差分松弛法(finite difference relaxation,简称FDR)的波前(wavefront)循环和时域有限差分法(finite difference time domain,简称FDTD)中典型循环以及程序Poisson,LU 和Jacobi 的测试,算法自动生成的流水并行代码能够在多核处理器上获得明显的性能提升,使用的流水分块大小计算公式能够较为精确地计算出循环流水并行时的最佳分块大小.自动生成的流水并行代码与基于手工选择的最优分块大小的流水并行代码相比,加速比达到手工选择加速比的89%.  相似文献   

6.
当计算划分层迭代数目较大,或是循环体单次迭代工作量较大,但可用的并行线程数目较小时,传统的基于循环分块的流水粒度优化方法无法进行处理。为此,提出一种基于循环分块减小流水粒度的方法,并根据流水并行循环的代价模型实现最优流水粒度的求解,设计实现了一个流水计算粒度的优化算法。对有限差分松弛法(FDR)的波前循环和时域有限差分法(FDTD)中典型循环的测试表明,与传统的流水粒度选择方法相比,所提算法能够得到更优的循环分块大小。  相似文献   

7.
大规模系统两层递阶控制的直接分解算法   总被引:2,自引:0,他引:2  
提出一个新的递阶控制的分解协调方法,它是由最优化问题的直接梯度解及性能函数的一个柔性分解组成。通过性能函数分解的自由度得到所需要的混合结构控制律,其下层控制器是闭环控制部分,上层是保证全局系统最优化的开环控制部分,局部性能函数的柔性选取,使两层优化任务的重新划分既能离线计算,也能在线修正。  相似文献   

8.
龚雪容  生拥宏  沈亚楠 《计算机应用》2006,26(10):2473-2475
着重论述了串行程序并行化过程中的数据收集部分代码的自动生成。提出利用等价类的方法获取数据的最后写关系,并建立包括计算划分、循环迭代和数据最后写关系的不等式限制系统,最后利用FME消元法对不等式限制系统进行消元处理,最终实现数据收集代码的自动生成。  相似文献   

9.
为了解决雷达数据处理系统数据量日益增大,计算能力逐渐不足的问题,提出两种并行处理方法。第一种方法是对数据处理各步骤中的循环采用多个线程并行处理,属于细粒度并行;第二种方法是根据雷达数据的局部性特征,把雷达探测空域按照径向距离划分成多个部分,由多个子任务并行处理,属于粗粒度并行。实验结果显示,4线程细粒度并行雷达数据处理架构性能是原来的3倍,4任务粗粒度并行架构性能是原来的5倍,证明并行处理技术在雷达数据处理中的有效性,并且任务级的粗粒度并行架构更适合雷达数据处理。  相似文献   

10.
针对公用总线的局域网环境,提出并分析了并行分类的两种方法:局部分类全局合并(LSGM)及全局分配局部分类(GDLS)。根据不同的输入/输出要求,分析了计算复杂性和通信复杂性,GDLS的计算复杂性最为理想,在输入.输出文件均为分布式的情况下,GDLS的通信复杂性远比LSGM好得多。同时也讨论了输入、划分、分类及输出处理的重叠操作。  相似文献   

11.
A finite element method often leads to large sparse symmetric and positive definite systems of linear equations. We consider parallel solvers based on the Schur complement method on homogeneous parallel machines with distributed memory. A finite element mesh is partitioned by graph partitioning. Such partitioning results in submeshes with similar numbers of elements and, consequently, submatrices of similar sizes. The submatrices are partially factorised. The time spent on the partial factorisation can be different, i.e., disbalanced, because methods exploiting the sparsity of submatrices are used. This paper proposes a Quality Balancing heuristic that modifies classic mesh partitioning so that the partial factorisation times are balanced, which saves overall computation time, especially for time dependent mechanical and nonstationary transport problems.  相似文献   

12.
The generalized partitioning estimation method, which is well known in tho literature (for example, Lainiotis 1976), is applied to solve the bias correction filtering, predicting and amoothing problems for a linear continuous.time system with undisturbable bias subsystem. With tho aid of an initial dependent-type partitioning approach, it is shown that the Friedland (1969) elemental results con be readily extended to the more general case where the bias and the original states are mutually dependent at the initial time, and that two-stage bias correction predictors and smoothers can also be developed. Finally, the dual set of Chandrasekhar algorithms, which alleviates the computation burden for a bias correction fixed-interval smoother evolving forwards in time, is presented.  相似文献   

13.
在简化方法的基础上,提出了在MIMD模型上采用异步通信模式求解模糊线性方程组的分布式并行分割算法,算法有效地平衡了负载,并分析了算法的时间复杂性和通信复杂性。  相似文献   

14.
In this paper we present a novel approach to NMPC based on state-space partitioning in conjunction with one-step ahead prediction and judicious use of graph theory to deliver an optimized control law which is robust, and is suitable for fast sampling applications. The only on-line computation required is a one-step ahead QP minimization which is linear in the number of inputs. The paper describes the general idea of the method and presents results, whose efficiency is demonstrated by means of a design study.  相似文献   

15.
A weak formulation of linear two-point boundary-value problems is introduced. Then the factorization method, which is suitable for hybrid computation, is applied. So we can treat the problems with right-hand side containing Dirac distributions or some more general ones. In the general case, the coefficient of the differential operator are measurable bounded and the right-hand side belong to the relevant Sobolev space of distribution. Practical examples are given.  相似文献   

16.
This paper presents a non-linear generalised minimum variance (NGMV) controller for a second-order Volterra series model with a general linear additive disturbance. The Volterra series models provide a natural extension of a linear convolution model with the nonlinearity considered in an additive term. The design procedure is entirely carried out in the state space framework, which facilitates the application of other analysis and design methods in this framework. First, the non-linear minimum variance (NMV) controller is introduced and then by changing the cost function, NGMV controller is defined as an extended version of the linear cases. The cost function is used in the simplest form and can be easily extended to the general case. Simulation results show the effectiveness of the proposed non-linear method.  相似文献   

17.
The basic concept of pipelined data-parallel algorithms is introduced by contrasting the algorithms with other styles of computation and by a simple example (a pipeline image distance transformation algorithm). Pipelined data-parallel algorithms are a class of algorithms which use pipelined operations and data level partitioning to achieve parallelism. Applications which involve data parallelism and recurrence relations are good candidates for this kind of algorithm. The computations are ideal for distributed-memory multicomputers. By controlling the granularity through data partitioning and overlapping the operations through pipelining, it is possible to achieve a balanced computation on multicomputers. An analytic model is presented for modeling pipelined data-parallel computation on multicomputers. The model uses timed Petri nets to describe data pipelining operations. As a case study, the model is applied to a pipelined matrix multiplication algorithm. Predicted results match closely with the measured performance on a 64-node NCUBE hypercube multicomputer  相似文献   

18.
目的 近年来双目视觉领域的研究重点逐步转而关注其“实时化”策略的研究,而立体代价聚合是双目视觉中最为复杂且最为耗时的步骤,为此,提出一种基于GPU通用计算(GPGPU)技术的近实时双目立体代价聚合算法。方法 选用一种匹配精度接近于全局匹配算法的局部算法——线性立体匹配算法(linear stereo matching)作为代价聚合策略;结合线性代价聚合的原理,对其主要步骤(代价计算、均值滤波及系数求解等)的计算流程进行有针对性地并行优化。结果 对于相同的实验样本,用本文方法在NVIDA GTX780 实验平台上能在更短的时间计算出代价矩阵,与原有的CPU实现方法相比,代价聚合的效率平均有了数十倍的提升。结论 实时双目立体代价聚合方法,为在个人通用PC平台上实时获取高质量双目视觉深度信息提供了一个高效可靠的途径。  相似文献   

19.
针对目前大多数的定位算法均或多或少地需要专门的设备问题,本文使用普及性较广的数码相机来对目标进行定位。根据双目定位理论,建立相机成像的线性模型,设计一种检验方法来检验该模型,最后对其成像精度和稳定性作详细分析。该模型简单、计算量小、可扩充性强,对多个相机成像的位置标定具有较高的参考价值和广阔的应用前景。  相似文献   

20.
由于移动设备要求计算量小,一些经典的算法保形效果好,但计算量大,不太适合移动环境;而通用取中点的收缩方法虽然非常简化,但保形性不好。设计了一个在保持模型外观的基础上对网格模型进行简化和简化后的模型恢复的完整算法。首先设计了综合平均曲率大小和曲率变化量大小的特征保留折叠代价策略。平均曲率大小是利用边的两个顶点所邻接三角形片的两两法向夹角的平均值来计算特征保留折叠代价队列;同时考虑到存在的一些特殊情况提出加入曲率变化量来判断特征片面的特征保留策略。为了避免综合判断带来的计算量的增加,所设计的平均曲率代价和曲率变化量代价均是同一个Cost函数的线性组合。此外,还设计了基于权重代价的在折叠边上快速计算该边的收缩点位置的有效方法,基于Cost函数的线性计算,由于Cost函数在整个算法中可重复利用,因此在没有增加计算量的情况下又提高了保形性,在计算效率和简化质量两者之间取得了一个均衡。实验证明,该算法可以在保持模型外观的同时有效地降低模型规模并计算量较小,适用于计算能力低的移动设备运算环境。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号