并行多层快速多极子算法中近场计算的负载均衡

指出多层快速多极子算法(MLFMA)近场计算部分负载均衡的核心在于近邻阻抗矩阵的划分。阐述按组对划分近邻阻抗矩阵的方案,辅以正方形扩展算法增加组对分布的聚集性,克服了传统的基于并行分布树最细层几何信息所产生的近邻阻抗矩阵划分的负载不均衡性。实验结果表明改进后算法的效率有明显提高。     

多层快速多极子算法并行实现的数据划分策略

虽然多层快速多极子算法在解决大尺度电磁散射问题中表现出了很好的效率,但是,当未知量达到千万时,由于复杂的结构和计算该算法很难再保持高效的计算能力。为了解决负载均衡引起的性能瓶颈问题,提出多层快速多极子算法基于八叉树的多层结构并行数据划分策略。该方法包括根据树结构中分布层和共享层不同特征的单独处理,也包括解决数据冲突的转移层的处理方法和为了减少分布存储系统中的通信时间而在分布层引入的冗余技术。实验结果表明多层快速多极子算法并行计算的开销明显减少,并且能够获得比较高的并行效率。     

基于并行MLFMA最细层数据建立算法的Petri网建模方法

为解决并行多层快速多极子算法(MLFMA)的功能和性能评测的问题,分析了MLFMA算法的关键问题分布树最细层数据的建立,提出了一种可以同时进行性能分析和正确性验证的形式化方法Petri网.将Petri网理论应用到具体的项目中,针对基于消息传递机制的最细层数据建立的并行算法进行形式化建模.在体现Petri网对基于消息传递机制的并行程序进行建模的优越性的同时,为后续进一步的程序正确性验证和性能分析打下基础.     

基于信息熵多种群遗传算法的组播路由

针对网络信息不确定性和链路负载不均匀所造成的网络拥塞,提出基于信息熵的组播路由算法。该遗传算法从最小代价树开始,在多种群中不断选择信息熵较大的种群,以求得满足延时要求且路径负载较小的组播树。结果表明,该算法性能快速、有效地构造最小时延组播树,且保证网络负载均衡分布。     

考虑负载均衡的无线传感器网络数据汇集算法

基于最小生成树策略的数据汇集算法使得数据传输效率高,但是树的构造使得转发节点负载过高,能量消耗过大,还会造成无线传感器网络的负载不均衡。针对这种情况,提出一种考虑负载均衡的数据汇集算法,该算法基于最小代价树的建立策略,在构造树的过程中避开剩余能量小的节点,最大化无线传感器网络的生存时间。     

基于负载均衡的模糊概念并行构造算法

提高模糊概念格直接构造效率是形式概念分析领域的主要问题之一,而当前基于模糊伽罗瓦联系的闭包运算仍是构造模糊概念的主要计算负荷,为此,提出一种基于负载均衡的并行构造模糊概念算法.该算法使用树状结构组织,遍历由自然数区间简化的搜索空间,逐级并行产生模糊概念、缩减搜索区间,并通过重新划分子搜索空间,实现各个计算节点负载均衡.实验结果表明,所提出的算法在稀疏数据集上表现优秀,能够有效地提高模糊概念构造效率.     

Wireless HART负载均衡方法研究

无线HART网络是同类无线网络中网络稳定性和健壮性最好的网络之一,负载均衡的网络可以有效的提高传感器网络的生存周期,本文针对Wireless HART的mesh网络结构提出一种以节点负载为中心的负载均衡因子,并在此基础上提出一种通过在无线网络拓扑图中构造负载均衡树的方法来改进网络负载均衡的算法。最后通过实验仿真比较发现新算法是一种更有效的均衡策略。     

改进鲸鱼算法在云计算资源负载预测中的应用

为了解决传统云计算资源负载预测方法对负载序列高频分量预测精度不高和泛化能力弱的缺点,提出一种混合小波包变换和正余混沌双弦鲸鱼优化（CSCWOA）算法优化多层感知器神经网络（MLP）的短期云计算资源负载预测方法。通过小波包变换对负载序列进行多频段预处理分解,然后采用CSCWOA算法优化的MLP神经网络,对单支重构所得的负载子序列进行预测;最后叠加各子序列的预测值来获取实际预测结果。实验结果表明,该方法能掌握负载序列各频段冲击毛刺的变化规律,具有较好的预测精度和泛化能力。     

面向建筑作业3D打印的双机协作任务分配算法

建筑3D打印通常将对象模型做人工划分后交由多机并行工作,模型划分优劣直接影响打印效率和外观效果.为了提高分块质量,提出一种双机协作任务分配算法.首先依据待打印体支撑关系粗略分块,并由分块特征识别模型中支撑柱、短墙、装饰等不宜分割部位;然后以提高并行效率为目的建立分块几何聚集指标和任务均衡指标,并由此构建任务分配多目标优化模型;最后由求解所得的任务子集将原模型切割输出.所提算法针对双机协作模式,但可通过参数调整推广至多机协作.与常见几何均分、按墙体连接划分的分割实验结果对比表明,该算法可避免切割对特征的破坏,且分配任务不均衡度低,能够有效地提高建筑3D打印效率.     

一种异构NOWs上负载均衡的适应式并行调度算法

分析了并行作业调度算法，针对异构工作站群机系统(Network of Workstations，NOWs)提出了一种负载均衡的适应式划分(Adaptive Partition，AP)策略的并行调度算法，它利用了短作业需求优先(Shortest Demand First，SDF)的策略，主要思想是让系统中所有作业尽可能均分同时结束，以达到均衡负载。实验结果证明该算法公平和高效。     

SELF-STABILIZING DISTRIBUTED SORTING IN TREE NETWORKS

This paper presents a self-stabilizing distributed sorting algorithm for tree networks. The distributed sorting problem can be informally described as follows: Nodes cooperate to reach a global configuration where every node, depending on its identifier, is assigned a specific final value taken from a set of input values distributed across all nodes. The input values may change in time. In our solution, the system reaches its final configuration in a finite time after the input values are stable and the faults cease. The fault-tolerance and the adaptivity to changing input is achieved using Dijkstra's paradigm of self-stabilization. A self-stabilizing algorithm, regardless of the initial system state, will converge in finite time to a set of legitimate states without the need for explicit exception handlers or backward recovery. Our solution is based on a continuous broadcast with acknowledgment along the tree edges to achieve the synchronization among processes in the system. It has 0(n ×h) time complexity and only 0(log(n) × ) memory requirement where h is the degree of the tree and h is the height of the tree.     

On the Performance of Randomized Embedding of Reproduction Trees in Static Networks

High performance computing requires high quality load distribution of processes of a parallel application over processors in a parallel computer at runtime such that both the maximum load and dilation are minimized. The performance of a simple randomized tree embedding algorithm that dynamically supports tree-structured parallel computations on arbitrary static networks is analyzed in this paper. The algorithm spreads newly created tree nodes to neighboring processors, which actually provides randomized dilation-1 tree embedding in static networks. We develop a linear system of equations that characterizes expected loads on all processors under the reproduction tree model, which can generate trees of arbitrary size and shape. It is shown that as the tree size becomes large, the asymptotic performance ratio of the randomized tree embedding algorithm is the ratio of the maximum processor degree to the average processor degree. This implies that the simple randomized tree embedding algorithm is able to generate high quality load distributions on virtually all static networks commonly employed in parallel and distributed computing.     

基于负载可迁移的分布式计费系统研究

宽带视频点播计费系统以分布式并行操作系统和分布式并行数据库系统为基础,通过量化的计费进程激活指数,结合计费进程互斥进入临界区算法,实现了多进程分布式协同计费。系统具有负载均衡能力,能够自动选择负载最轻的服务器作为计费节点。引入迁移惰性指数,使进程迁移的可控性得到进一步提高;系统具有很强的稳健性、实时性和不间断性的优点。该计费系统的设计方法不仅适用于宽带视频点播计费系统,也可供其它相近或相关计费系统借鉴。     

Distributed hierarchical search for balanced energy consumption routing spanning trees in wireless sensor networks

We provide a new heuristic method approach to search for degree-balanced and small weight routing spanning trees in a network. The method is a modification of Kruskal’s minimum spanning tree search algorithm and is based on a distributed search by hierarchical clusters. It provides spanning trees with a lower maximum weighted degree, a bigger diameter, and can be used for balanced energy consumption routing in wireless sensor networks (WSN’s). The method can be naturally implemented in parallel or as a simple locally distributed algorithm. Simulations for a realistic case scenario WSN are done based on the transmission energy matrix. The simulation results show that the proposed approach can extend the functional lifetime of a WSN in terms of sensor transmission energy by 3–4 times. We also show that the results can be further improved by using a preliminary clustering of the input network.     

Distributed Graph Traversals by Relabelling Systems with Applications

Graph traversals are in the basis of many distributed algorithms. In this paper, we use graph relabelling systems to encode two basic graph traversals which are the broadcast and the convergecast. This encoding allows us to derive formal, modular and simple encoding for many distributed graph algorithms. We illustrate this method by investigating the distributed computation of a breadth-first spanning tree and the distributed computation of a minimum spanning tree. Our formalism allows to focus on the correctness of a distributed algorithm rather than on the implementation and the communication details.     

Efficient breadth first search on multi-GPU systems

Simple algorithms for the execution of a Breadth First Search on large graphs lead, running on clusters of GPUs, to a situation of load unbalance among threads and un-coalesced memory accesses, resulting in pretty low performances. To obtain a significant improvement on a single GPU and to scale by using multiple GPUs, we resort to a suitable combination of operations to rearrange data before processing them. We propose a novel technique for mapping threads to data that achieves a perfect load balance by leveraging prefix-sum and binary search operations. To reduce the communication overhead, we perform a pruning operation on the set of edges that needs to be exchanged at each BFS level. The result is an algorithm that exploits at its best the parallelism available on a single GPU and minimizes communication among GPUs. We show that a cluster of GPUs can efficiently perform a distributed BFS on graphs with billions of nodes.     

Extremal Optimization applied to load balancing in execution of distributed programs

The paper describes methods for using Extremal Optimization (EO) for processor load balancing during execution of distributed applications. A load balancing algorithm for clusters of multicore processors is presented and discussed. In this algorithm the EO approach is used to periodically detect the best tasks as candidates for migration and for a guided selection of the best computing nodes to receive the migrating tasks. To decrease the complexity of selection for migration, the embedded EO algorithm assumes a two-step stochastic selection during the solution improvement based on two separate fitness functions. The functions are based on specific models which estimate relations between the programs and the executive hardware. The proposed load balancing algorithm is assessed by experiments with simulated load balancing of distributed program graphs. The algorithm is compared against a greedy fully deterministic approach, a genetic algorithm and an EO-based algorithm with random placement of migrated tasks.     

基于退火策略的分布式资源负载均衡算法

针对分布式资源导致的访问热点等一系列问题,建立了一个用于分布式资源退火的处理模型.根据该模型,提出了基于退火策略的分布式资源负载均衡算法;该算法通过访问分类、定向扩散等方法提高了系统性能.性能及试验分析表明,该算法能够减少系统内部通信量,抑制资源扩散的抖动现象等.     

Hierarchical deablock detection for nested transactions

In this paper, we propose an algorithm for detecting deadlocks in a distributed Nested Transaction. This algorthms does not require that the global wait-for graph be built and maintained nor that the edges of a global wait-for graph be followed in order for deadlocks to be detected. Our algorithm uses the fact that transactions are organized in a tree structure. Each transaction maintains a representative wait-for graph that summarizes the waiting conditions in the subtree below the transaction. Deadlocks can be detected by individually checking these condensed wait-for graph. Marta Rukoz received an under-graduate degree in Computer Science from the Central University of Venezuela in 1981, a Masters degree from Simon Bolivar University in 1985, and a Ph.D. from the Pierre et Marie Curie, Paris VI University in France. She was a member of the faculty at the Central University of Venezuela from 1982–1985 and returned in 1989 where she is currently a Professor Agregado. From 1987–1989 she worked at the University of Paris Nord. Professor Rukoz's research interests include: distributed algorithms, distributed databases, and Petri net models.A preliminary draft of this paper appears in Bermond J, Raynal M (eds) Proceedings of distributed algorithms. Lect Notes Comput Sci. vol. 392. Springer, Berlin Heidelberg New York, 1989     

一种支持分布式进程迁移的动态负载平衡征募算法的研究

负载平衡是分布式系统必须考虑的问题,本文介绍的征募算法独立于网络拓扑结构,其思想可以应用到分布式系统中,征募算法的设计思想向传统负载平衡算法提出了挑战,它不但克服了投标算法的缺点,而且在减小通讯开销和提高处理机利用率两方面作了很多努力,使其成为一种高效的分布式进程迁移和动态负载平衡策略。我们在分布式ＵＮＩＸ系统上实现并验证了征募算法的高效性。