Dynamic Distribution Model with Prime Granularity for Parallel Computing

Dynamic distribution model is one of the best schemes for parallel volume rendering. How- ever, in homogeneous cluster system.since the granularity is traditionally identical, all processors communicate almost simultaneously and computation load may lose balance. Due to problems above, a dynamic distribution model with prime granularity for parallel computing is presented. Granularities of each processor are relatively prime, and related theories are introduced. A high parallel performance can be achieved by minimizing network competition and using a load balancing strategy that ensures all processors finish almost simultaneously. Based on Master-Slave-Gleaner ( MSG) scheme, the parallel Splatting Algorithm for volume rendering is used to test the model on IBM Cluster 1350 system. The experimental results show that the model can bring a considerable improvement in performance, including computation efficiency, total execution time, speed, and load balancing.

A self-routing load balancing algorithm in parallel computing: comparison to the central algorithm

Load balancing is an important stage of a system using parallel computing where the aim is the balance of workload among all processors of the system. In this paper, we introduce a new load balancing algorithm with new capabilities for parallel systems, among which is the independence of a separate route-finder algorithm between the load receiver and sender nodes. In addition to simulation of the new algorithm, due to similarity in behavior to the proposed algorithm, the central algorithm is simulated. Simulation results show that, the system performance increases with the increase of the degree of neighborhood between the processors. These results also indicate the algorithm’s high compatibility with environment changes.

CLUSTER OF WORKSTATIONS BASED ON DYNAMIC LOAD BALANCING FOR PARALLEL TREE COMPUTATION DEPTH-FIRST-SEARCH

The real problem in cluster of workstations is the changes in workstation power or number of workstations or dynmaic changes in the run time behavior of the application hamper the efficient use of resources. Dynamic load balancing is a technique for the parallel implementation of problems, which generate unpredictable workloads by migration work units from heavily loaded processor to lightly loaded processors at run time. This paper proposed an efficient load balancing method in which parallel tree computations depth first search (DFS) generates unpredictable, highly imbalance workloads and moves through different phases detectable at run time, where dynamic load balancing strategy is applicable in each phase running under the MPI(message passing interface) and Unix operating system on cluster of workstations parallel platform computing.

Implementation Study of Dynamic Load Balancing Algorithm of Parallel Tree Computation on Clusters of Heterogeneous Workstation

The rapid growth of interconnected high performance workstations has produced a new computing paradigm called clustered of workstations computing. In these systems load balance problem is a serious impediment to achieve good performance. The main concern of this paper is the implementation of dynamic load balancing algorithm, asynchronous Round Robin (ARR), for balancing workload of parallel tree computation depth-first-search algorithm on Cluster of Heterogeneous Workstations (COW) Many algorithms in artificial intelligence and other areas of computer science are based on depth first search in implicitty defined trees. For these algorithms a load-balancing scheme is required, which is able to evenly distribute parts of an irregularly shaped tree over the workstations with minimal interprocessor communication and without prior knowledge of the tree’s shape. For the (ARR) algorithm only minimal interprocessor communication is needed when necessary and it runs under the MPI (Message passing interface) that allows parallel execution on heterogeneous SUN cluster of workstation platform. The program code is written in C language and executed under UNIX operating system (Solaris version).

MDSLB:A new static load balancing method for parallel molecular dynamics simulations

Large-scale parallelization of molecular dynamics simulations is facing challenges which seriously affect the simula- tion efficiency, among which the load imbalance problem is the most critical. In this paper, we propose, a new molecular dynamics static load balancing method （MDSLB）. By analyzing the characteristics of the short-range force of molecular dynamics programs running in parallel, we divide the short-range force into three kinds of force models, and then pack- age the computations of each force model into many tiny computational units called ＂cell loads＂, which provide the basic data structures for our load balancing method. In MDSLB, the spatial region is separated into sub-regions called ＂local domains＂, and the cell loads of each local domain are allocated to every processor in turn. Compared with the dynamic load balancing method, MDSLB can guarantee load balance by executing the algorithm only once at program startup without migrating the loads dynamically. We implement MDSLB in OpenFOAM software and test it on TianHe-lA supercomputer with 16 to 512 processors. Experimental results show that MDSLB can save 34%-64% time for the load imbalanced cases.

LOW-COST HIGH PERFORMANCE CLUSTER OF WORK-STATIONS BASED ON DYNAMIC LOAD BALANCING FOR PARALLEL DEPTH-FIRST SEARCH(DFS)

This paper presented an idea to replace the traditionally expensive parallel machines by heterogeneous cluster of workstations. To emphasise the usability of cluster of workstations platform for parallel and distributed computing, also the paper presented the status report on the effort and experiences for the implementation of a dynamic load balancing for parallel tree computation depth first search(DFS) on the cluster of a workstations project. It compared the speedup performance obtained from our platform with that obtained from the traditional one. The speedup results show that cluster of workstations can be a serious alternative to the expensive parallel machines.

Thread-Oriented Online Load Balancing

Dynamic task assignment and migration are the key technique to load balancing which plays an important role in the achievement of high performance in distributed computing system. In this paper, we describe the design and implementation of an online thread scheduling and migration system (S&M) based on a previous work of LWP -MPI. Experimental results show that performance is enhanced.

Energy-efficient task allocation for reliable parallel computation of cluster-based wireless sensor network in edge computing

To efficiently complete a complex computation task,the complex task should be decomposed into subcomputation tasks that run parallel in edge computing.Wireless Sensor Network(WSN)is a typical application of parallel computation.To achieve highly reliable parallel computation for wireless sensor network,the network's lifetime needs to be extended.Therefore,a proper task allocation strategy is needed to reduce the energy consumption and balance the load of the network.This paper proposes a task model and a cluster-based WSN model in edge computing.In our model,different tasks require different types of resources and different sensors provide different types of resources,so our model is heterogeneous,which makes the model more practical.Then we propose a task allocation algorithm that combines the Genetic Algorithm(GA)and the Ant Colony Optimization(ACO)algorithm.The algorithm concentrates on energy conservation and load balancing so that the lifetime of the network can be extended.The experimental result shows the algorithm's effectiveness and advantages in energy conservation and load balancing.

Parallel scheduling strategy of web-based spatial computing tasks in multi-core environment

In order to improve the concurrent access performance of the web-based spatial computing system in cluster,a parallel scheduling strategy based on the multi-core environment is proposed,which includes two levels of parallel processing mechanisms.One is that it can evenly allocate tasks to each server node in the cluster and the other is that it can implement the load balancing inside a server node.Based on the strategy,a new web-based spatial computing model is designed in this paper,in which,a task response ratio calculation method,a request queue buffer mechanism and a thread scheduling strategy are focused on.Experimental results show that the new model can fully use the multi-core computing advantage of each server node in the concurrent access environment and improve the average hits per second,average I/O Hits,CPU utilization and throughput.Using speed-up ratio to analyze the traditional model and the new one,the result shows that the new model has the best performance.The performance of the multi-core server nodes in the cluster is optimized;the resource utilization and the parallel processing capabilities are enhanced.The more CPU cores you have,the higher parallel processing capabilities will be obtained.

Efficient Data-parallel Computations on Distributed Systems

Task scheduling determines the performance of NOW computing to a large extent. However, the computer system architecture, computing capability and system load are rarely proposed together. In this paper, a biggest heterogeneous scheduling algorithm is presented. It fully considers the system characteristics (from application view), structure and state. So it always can utilize all processing resource under a reasonable premise. The results of experiment show the algorithm can significantly shorten the response time of jobs.

A Parallel Interval Computation Model for Global Optimization with Automatic Load Balancing

In this paper, we propose a decentralized parallel computation model for global optimization using interval analysis. The model is adaptive to any number of processors and the workload is automatically and evenly distributed among all processors by alternative message passing. The problems received by each processor are processed based on their local dominance properties, which avoids unnecessary interval evaluations. Further, the problem is treated as a whole at the beginning of computation so that no initial decomposition scheme is required. Numerical experiments indicate that the model works well and is stable with different number of parallel processors, distributes the load evenly among the processors, and provides an impressive speedup, especially when the problem is time-consuming to solve.

基于Delaunay三角网的克里金并行算法优化

当采样点数据量较大时,可以采用Delaunay三角剖分建立三角网来使用局部邻域采样点进行克里金插值.但是该算法需要对每个插值点拟合半变异函数,插值点规模大时造成巨大开销.为此,本文提出了一种以三角形为单位拟合半变异函数的克里金插值方法,采用CPU-GPU负载均衡将部分计算优化,充分考虑不均匀样本对克里金插值效果的影响.结果表明,本文算法能够保证不均匀样本集的插值效果,提升了计算性能且能够保证较高的精度.

高分三号数据分布式自适应负载均衡并行转换算法研究

针对PolSARpro软件自带高分三号数据转换模块无法自适应分布式差异化硬件环境问题,提出了一种按照该软件的数据格式要求进行分布式自适应负载均衡并行转换算法,将高分三号多极化数据快速、精确地进行定标与格式转换,对不同硬件配置环境自适应,能够抗数据偏斜,并且通过KingMap V10.5平台实现了算法并在实际数据中进行测试,试验结果表明性能提升了约12.7倍,验证了算法的可行性、高效性和正确性。

Parallelization Load Balance Strategy for a Global Grid-Point Model

The Global/Regional Assimilation and PrEdiction System（GRAPES）is a new-generation operational numerical weather prediction（NWP）model developed by the China Meteorological Administration（CMA）.It is a grid-point model with a code structure different from that of spectral models used in other operational NWP centers such as the European Centre for Medium-Range Weather Forecasts（ECMWF）,National Centers for Environmental Prediction（NCEP）,and Japan Meteorological Agency（JMA）,especially in the context of parallel computing.In the GRAPES global model,a semi-implicit semi-Lagrangian scheme is used for the discretization over a sphere,which requires careful planning for the busy communications between the arrays of processors,because the Lagrangian differential scheme results in shortened trajectories interpolated between the grid points at the poles and in the associated adjacent areas.This means that the latitude-longitude partitioning is more complex for the polar processors.Therefore,a parallel strategy with efficient computation,balanced load,and synchronous communication shall be developed.In this paper,a message passing approach based on MPI（Message Passing Interface）group communication is proposed.Its key-point is to group the polar processors in row with matrix-topology during the processor partitioning.A load balance task distribution algorithm is also discussed.Test runs on the IBM-cluster 1600 at CMA show that the new algorithm is of desired scalability,and the readjusted load balance scheme can reduce the absolute wall clock time by 10% or more.The quasi-operational runs of the model demonstrate that the wall clock time secured by the strategy meets the real-time needs of NWP operations.

格子Boltzmann方法多层网格负载均衡算法优化研究

基于格子Boltzmann方法的多层网格局部加密技术,通过多尺度网格计算不同层次的流动特征,避免了单层均匀笛卡尔网格中的低效率与计算资源的浪费,但仍存在并行性能上的不良影响.本文考虑并行计算中的负载均衡效应,从单层网格出发,通过考虑多层网格的运算特点来研究基于负载均衡的网格划分方法.同时,将网格划分与程序实现进行分离,在单层和多层网格中均完成了任意网格划分下的并行计算.在单层网格中,以二维血管流动的不同并行策略为例,研究了负载量划分与不同进程的各自时间开销的关系.在多层网格中,首先论述了多尺度网格在运算顺序上的特征,其次以三种不同的多层网格验证二维翼型绕流的计算结果,最后在每种网格中均使用三种不同的网格划分方法进一步探讨负载均衡与时间开销的关系.在128核的高性能计算平台上进行并行性能测试,强可扩展性可达到60%左右,弱可扩展性可达到82.78%.这种高可扩展性结果表明本文通过改进负载均衡性能,明显提升了多层网格计算中的并行性能.

异构并行计算下高维混合型数据聚类算法研究

高维数据维度增加,数据空间的体积呈指数增长,容易陷入“维数灾难”,导致聚类算法执行效率低,为此,提出异构并行计算下高维混合型数据聚类算法。构建高维混合型数据相异度矩阵,提取高维混合型数据的统计序列特征值,利用时间窗口进行特征优化。采用K⁃Prototypes聚类算法提取高维混合型数据的统计序列特征,评估数据与类中心的相异性,计算数据与类中心的欧氏距离,实现高维混合型数据聚类。采用异构并行计算技术进行高维混合型数据K⁃Prototypes聚类的并行化处理,合理分配CPU与GPU工作,达到CPU与GPU的工作负载平衡,提高K⁃Prototypes的聚类效率。实验结果表明,此算法对于高维混合型数据的聚类效果好、运行时间短、性能稳定。

基于CPBOA的并行DCNN优化算法

针对大数据环境下并行DCNN算法存在的冗余特征图过多、卷积运算效率低下以及节点负载不均衡等问题,提出一种基于Spark和CPBOA的并行DCNN优化算法PDCNN-SCPBOA。提出一种基于奇异值分解与JS散度的特征压缩策略对特征图进行分组压缩,消除过多的冗余特征图;结合Spark提出一种基于蝴蝶优化算法的并行CP分解策略,利用分解后的卷积核并行训练,提高卷积运算效率;提出一种基于簇分割的负载均衡策略,对中间数据簇进行均匀分配后再进行处理,平衡节点负载。实验结果表明,所提算法具有良好的训练效果,适用于大规模图像数据的分类。

一个有效的动态负载平衡方法

动态负载平衡问题是影响工作站网络并行计算性能的重要因素 .首先分析出在负载平衡中产生额外开销的根本原因是负载的移动 ,进而定性地给出了每次移动负载的粒度公式 .引入益处估计的方法 ,仅在有益的情况下进行负载平衡 .另外还提出了一个动态负载平衡算法 .最后 ,通过实验 ,将该算法的运行结果与其他人的负载平衡结果以及不作负载平衡的情况进行了对比 .此负载平衡方法在工作站为空载以及不同的负载和应用问题的数据规模的情况下 ,都优于 Siegell等人提出的方法 .

负载均衡策略研究综述

负载均衡是最大化处理器利用率和提高并行计算效率的一个关键问题,而其发展相对滞后的软件成为影响并行计算应用发展的重要因素.本文给出负载均衡问题的一般性阐述,从算法理论和并行计算应用问题角度出发综述了现有负载均衡策略及其软件的研究成果.结合当前新兴并行体系结构和应用的发展趋势,分析并指出了下一步研究的问题和方向.

一种实现拓扑关系高效并行计算的矢量数据划分方法

分析了拓扑关系并行算法的特点,为实现拓扑关系并行计算进程间的任务均衡与负载均衡,提出了一种矢量目标集的数据均衡划分方法,基于该划分方法设计了拓扑关系并行算法并测试了算法性能。测试表明:利用该方法可实现进程间计算负载的高度均衡与数据负载的基本均衡,加速比随进程数基本呈线性增长,算法并行效率基本不随进程数增加而衰减,基本稳定在80%。该方法为面向单机多核、众核和高性能集群环境下的海量数据拓扑关系分析软件的开发与服务提供一种高效的矢量数据划分方法。