基于多层油藏问题负载均衡的并行任务划分

该文基于分布式并行计算机系统,对一类多层二维二相流油藏数值模拟问题给出了3种任务划分策略—“卷帘”方式、区域分解方式和“卷帘”与区域分解结合的方式,对它们进行了比较,提出了减少求解时间、利于负载均衡和提高并行性能的任务划分方法,并实际应用于有多达72万个网格节点的大规模油藏模拟问题.实算结果表明,该策略划分产生的并行求解任务均衡,有利于加速比的提高.该方法也适用于区域或数据并行的任务划分问题.     

非均匀区域油藏模拟负载平衡的分区并行算法*

基于分布式并行计算机系统,对一类非均匀区域的油藏数值模拟问题,采用了区域分解方法并行求解,给出了并行求解的负载平衡模型及区域负载平衡的一种有效分区算法,从而将这类油藏数值模拟问题均衡映射到并行环境中,高效地并行求解.在黑油油藏数值模拟并行软件的研究中,实验结果表明,该算法有利于提高加速比.     

多层油藏模拟并行计算与负载平衡

在油藏数值模拟并行计算中，提高计算速度和资源利用率是一个重要的研究方向，给出分布式并行环境下一种多层油藏模拟并行计算的整体优化方法，其特点是使用高效的区域分解方法并行求解，动态选择两种不同的计算粒度，有效地克服了负载不均衡带来的性能下降问题，实际模型计算表明，此方法策略减少了整体模拟计算时间，并获得较高加速比，采用的算法适用于一类多层油藏模型问题。     

一种基于SMP的并行逐次超松弛迭代法

逐次超松弛迭代方法被广泛应用于油藏数值模拟中压力方程的求解.其并行实现是提高模拟速度的重要途径.传统并行方案大都只是在一次迭代内进行数据划分,而没有进一步将数据划分与迭代空间划分相结合,故针对SOR算法和SMP（symmetric multi-processors）系统的特点,以OpenMP为并行化实现工具,提出了基于SMP的并行逐次超松弛迭代方法（parallelSOR）.方法通过改变不同迭代步内数据点的更新次序,使不同区域内的数据点可以并行执行多次迭代.总结出针对三维油藏区域在数据空间划分和迭代空间合并上相对较优的策略,分析了迭代过程中网格块的生长形状.与传统的并行策略相比,该方法具有可减小同步开销、改进数据局部性、cache命中率高等优点.实验结果表明,该方法具有较高的加速比和效率.     

基于状态方程组并行任务划分的策略

本文在分析了状态方程组并行求解时机间通信对求解性能的影响后，提出了减少求解时间和机间通信数据量的任务划分策略，并运用模拟退火算法实现该策略。结果表明，该策略划分产生的并行求解任务均衡，并行加速比高，适用于种类MIMD系统。     

基于并行约束规划的最大团识别研究

为提高大数据平台下大规模图例的最大团问题求解效率,提出一种基于并行约束规划的最大团识别算法.通过BMT图划分策略将一个复杂图例分割为若干个可独立计算的子图,并将其分配给Spark集群中的计算节点,每个计算节点采用约束规划方法对分割产生的子问题分别进行建模和求解,实现最大团问题的并行化处理.引入时间预测模型,设计基于任务运行时间预测模型的并行图划分方法,从而有效解决计算节点的负载均衡问题.实验结果表明,与基于BMC图划分策略的最大团并行识别算法相比,该算法具有更高的求解效率,可取得近似线性的加速比.     

一种适于黑油模型并行的快速新解法--改进的GMRES算法

本文应用区域分解算法进行油藏模拟的并行计算研究,寻求可高效并行求解三维三相数值模拟问题的最优算法。在对流行的预处理共轭梯度算法及GMRES算法进行对比研究的基础上,提出了改进的GMRES算法,这种算法具有迭代参数不需优化、收敛快、可得到较精确解等优点。应用该解法对三维三相黑油模型软件进行并行化改造。通过模型及实际油藏计算,比软件原算法及GMRES算法的计算速度得到大幅度提高。并行效率较高,并行化后的模拟软件可以有效地解决大型整装构造油藏的数值模拟问题。     

油藏数值模拟有限元并行计算方法研究

针对目前油藏数值模拟普遍采用的有限差分法计算精度低的问题,提出了兼顾计算精度、计算速度问题的有限元油藏数值模拟方法,即在建立了油藏数值模拟数学模型的基础上通过有限元数值分析方法建立有限元数值模型,但有限元在油藏数值模拟时存在单机计算困难、计算时间长的问题,为此提出了利用区域分解技术的油藏数值模拟并行计算方法,最后将该方法通过实例进行检验,取得了良好的加速比和并行效率。     

并行网络蠕虫模拟中任务优化划分的研究

为提高并行网络蠕虫模拟的性能，需要对蠕虫模拟任务进行合理的划分．鉴于基于图划分工具的任务划分方法存在的不足，提出了并行网络蠕虫模拟任务的优化划分方法：以并行网络蠕虫模拟运行时间估计模型作为优化目标函数，采用改进的模拟退火算法实现对蠕虫模拟任务的划分．在PDNS上进行的Slammer蠕虫传播模拟实验表明，该优化划分方法较基于图划分工具的方法提高模拟性能20％以上．     

油藏数值模拟软件的粗粒度层并行计算方法

本文针对目前油藏模拟模型大、求解精度高的特点，在迭代解法进行深入研究的基础上，对预处理方法、节点排序方法等进行了优化，优化出适于并行的最佳解法。以优化后的预处理共轭梯度法为基础，对多层二维二相模拟模型进行按层粗粒度并行。为解决存储及通讯问题，采用了压缩存储及压缩通讯技术，有效地提高了软件的并行效率。模型及实例计算表明并行化的多层二维二相模型具有较高的并行效率。通过对通讯量、层数、共享与分布等实用性影响因素分析，为大规模油藏模拟的并行化提供了有力的工具。     

Observations on using genetic algorithms for dynamic load-balancing

Load-balancing problems arise in many applications, but, most importantly, they play a special role in the operation of parallel and distributed computing systems. Load-balancing deals with partitioning a program into smaller tasks that can be executed concurrently and mapping each of these tasks to a computational resource such as a processor (e.g., in a multiprocessor system) or a computer (e.g., in a computer network). By developing strategies that can map these tasks to processors in a way that balances out the load, the total processing time will be reduced with improved processor utilization. Most of the research on load-balancing focused on static scenarios that, in most of the cases, employ heuristic methods. However, genetic algorithms have gained immense popularity over the last few years as a robust and easily adaptable search technique. The work proposed here investigates how a genetic algorithm can be employed to solve the dynamic load-balancing problem. A dynamic load-balancing algorithm is developed whereby optimal or near-optimal task allocations can “evolve” during the operation of the parallel computing system. The algorithm considers other load-balancing issues such as threshold policies, information exchange criteria, and interprocessor communication. The effects of these and other issues on the success of the genetic-based load-balancing algorithm as compared with the first-fit heuristic are outlined     

The simulation model partitioning problem: An adaptive solution based on self-Clustering

This paper is about partitioning in parallel and distributed simulation. That means decomposing the simulation model into a number of components and to properly allocate them on the execution units. An adaptive solution based on self-clustering, that considers both communication reduction and computational load-balancing, is proposed. The implementation of the proposed mechanism is tested using a simulation model that is challenging both in terms of structure and dynamicity. Various configurations of the simulation model and the execution environment have been considered. The obtained performance results are analyzed using a reference cost model. The results demonstrate that the proposed approach is promising and that it can reduce the simulation execution time in both parallel and distributed architectures.     

面向并行负载平衡的数据剖分技术*

对传统的数据剖分技术和负载平衡对大规模并行计算性能的影响进行了综述,介绍了目前典型的几何剖分方法和图剖分方法的特点,并分析比较各种剖分算法及常用剖分软件包(ParMETIS、Zoltan、JOSTLE等)在实际应用中的优缺点,深入探讨了数据剖分技术是如何对超大规模数值模拟计算任务进行高效划分以解决负载平衡问题的,以期为开展并行计算研究和并行性能优化的研究人员提供参考。     

Development of parallel 3D RKPM meshless bulk forming simulation system

A parallel computational implementation of modern meshless system is presented for explicit for 3D bulk forming simulation problems. The system is implemented by reproducing kernel particle method. Aspects of a coarse grain parallel paradigm—domain decompose method—are detailed for a Lagrangian formulation using model partitioning. Integration cells are uniquely assigned on each process element and particles are overlap in boundary zones. Partitioning scheme multilevel recursive spectrum bisection approach is applied. The parallel contact search algorithm is also presented. Explicit message passing interface statements are used for all communication among partitions on different processors. The parallel 3D system is developed and implemented into 3D bulk metal forming problems, and the simulation results demonstrated the efficiency of the developed parallel reproducing kernel particle method system.     

并行交换中支持包保序的新技术

由于并行交换结构的负载平衡特性和并行原理,到达同一目的输出端口的分组包被分散到了各个交换模块,当它们抵达输出端口时,其先后顺序无法得到保障。文章为解决该难题提出一种新技术,包括虚拟输入排队(VIQ)结构和包保序轮询(SKRR)算法,并且从理论上分析了这种新技术的吞吐率和时延性能。     

基于权重轮询负载均衡算法的优化

随着电商网站用户规模不断增长,高并发问题成为在搭建大规模电商网站系统时面临的一项重大挑战,通过负载均衡算法来实现Web服务集群中各节点均衡负载是解决高并发的手段之一.然而,目前通用的负载均衡算法都存在一些不足之处,针对这一问题,提出了一种动态自适应权重轮询随机负载均衡算法（Dynamic Adaptive Weight Round-Robin Random Load-Balancing,DAWRRRLB）,该算法考虑到影响Web服务集群中服务器节点性能的多重因素,根据节点在运行过程中的实时负载情况动态的改变集群中节点的负载性能,并结合改进的Pick-K算法对权重轮询负载均衡算法进行优化,始终保证性能最优的服务器节点在提供服务.通过多次实验对比,改进的DAWRRRLB算法可以有效的提高负载均衡效率.