集群计算环境下基于复杂网络的社会学仿真负载划分优化算法

负载划分是决定集群计算环境下基于复杂网络的并行社会学仿真性能的核心因素之一.由于背景负载等因素的影响,集群系统中往往需要根据实际可用计算资源非均匀分配仿真任务,而现有针对无标度特性拓扑结构的并行仿真负载划分算法无法适应集群环境下计算负载非均匀划分的需求.针对这一问题,提出了一个基于集散节点聚合的负载划分算法,将集群计算...     

基于前验负载差异的负载平衡性能模型

基于有限差分离散的并行应用非常普遍,针对此类问题的负载平衡性能评估,引入了一个刻画应用问题负载平衡能力的关键参数:最大负载变化率,推导了一个以并行效率为目标函数的负载平衡性能模型,涉及问题规模、并行通信计算比、离散格式复杂度和并行规模等.以POP全球海洋模式并行程序为测试实例,验证了该模型的性能.结果显示最大负载变化率作为衡量负载平衡程度的指标是有效的,基于模型的预测性能与实测性能在总体趋势上基本吻合.该性能模型对基于有限元、有限体积等其他局部离散格式的大型并行计算应用的负载平衡能力评估也具有参考价值.     

基于最大负载偏移率的并行负载平衡性能分析

大规模并行应用的负载平衡能力对性能的影响很大,但难以度量.针对基于局部离散格式的(有限差分、有限元等)并行应用,通过分析并行计算通信比、并行规模、问题规模、格式复杂度与并行效率之间的数量关系,提出一个"最大负载偏移率"概念,即并行任务的最大负载相对平均负载的偏移量与平均负载之比,作为衡量负载平衡能力的性能指标,并导出了一个负载平衡性能量化模型.将POP全球海洋模式Benchmark程序作为计算实例,验证了负载平衡性能模型的有效性.该模型揭示出整体并行计算性能对负载平衡的依赖程度,特别是对大规模并行计算的情形,负载平衡程度对整体性能的影响随着并行规模的增大而愈加敏感.     

基于时间偏差协议的动态负载平衡技术*

对并行VHDL模拟的特殊性进行分析后,建立了一个并行VHDL模拟的动态负载平衡模型。在此模型中,提出动态调节最佳并行规模的动态负载平衡方法来解决系统资源紧张的问题,采用一种新的模拟中负载的度量方法——模拟推进度。此模型还包括基于标准偏差和最小通信变化量的动态负载平衡算法和一个运行中的负载迁移机制。最后对该模型进行可行性分析。     

基于并行构件的动态负载池平衡技术的研究

在基于并行构件的系统中，负载平衡技术是充分利用系统资源，提高系统性能的关键技术。该文提出了一种基于并行构件的动态负载池平衡技术，与已有的负载平衡策略不同，该技术综合考虑了通信延迟、容错技术以及数据一致性对负载平衡策略的影响，旨在提高策略的准确性、高效性和健壮性，增强运行时系统的性能。     

基于时间偏差的并行逻辑模拟的动态负载平衡

随着大规模集成电路的复杂性日益增加,逻辑模拟开始采用并行离散事件模拟技术。在现有的基于时间偏差协议的并行逻辑模拟系统的基础上,提出了一个动态负载平衡模型,模型能够针对模拟时的负载变化,进行以一组模拟对象为单位的迁移以实现负载平衡。提出模拟推进度的概念,作为对并行逻辑模拟过程中的负载进行准确的衡量标准。     

并行自适应有限元计算中的负载平衡研究

偏微分方程的并行求解,关键问题之一是网格划分,它不仅要求每个进程拥有相等的计算负载,同时要求有良好的划分质量,以减少进程间通信.在自适应有限元计算过程中,网格/基函数不断调整,会导致负载不平衡,必须动态地调整网格分布,从而实现动态负载平衡.本文研究了不同的负载平衡方法,并在并行自适应有限元平台PHG中实现.数值实验表明我们的动态负载平衡算法具有很高的划分质量,运行速度快,可有效划分网格并减少运行时间.     

"NOW"环境下电路并行仿真算法的研究和实现

针对电路并行仿真,基于求解对角分块结构非线性系统的并行方法,提出并实现了"NOW"(Network Of Workstations) 环境下的一个并行计算模型.主要分析了该算法的并行特性、同步条件及"NOW"环境并行性能关键影响因素.文中提出了一种启发式的静态、动态负载平衡算法,并在Linux平台下采用MPI消息库实现该并行模型.仿真结果表明该算法在"NOW"环境下能获得比串行算法较为可观的加速比.同时文中提出的负载平衡算法也比一些经典算法能更有效得平衡系统负载.     

利用层次任务图和多种群遗传算法的可重构计算任务划分

为实现可重构计算中软硬件任务的自动划分,提出一种基于层次任务图模型和采用遗传算法作为搜索算法的任务划分算法.首先设计了一个层次任务图模型,其不同于基于有向非循环图(DAG)的模型,可以在任务划分时动态改变任务颗粒度,进而得到不同任务粒度下的最优解;其次设计了一个考虑了时间、功耗、资源和通信代价的适应度函数,并根据任务数量不固定的特点对遗传算法进行了改进.对文中算法在FPGA上进行实验验证和分析的结果表明,该算法的结果优于基于DAG任务图模型的任务划分.     

游戏网格服务划分算法研究*

为了充分利用游戏网格的计算资源,使用其强大的并行计算能力,部署在游戏网格的网络游戏必须要划分成可以并行的多个服务。提出了一种基于动态二叉树的游戏网格服务划分算法;讨论了如何采用二叉树的数据结构来组织服务节点并根据服务节点的负载动态调整其服务划分;最后实现一个模拟游戏网格环境,通过实验结果证明该算法可以取得良好的性能。     

Web协同应用中基于文档划分的一致性维护模型

针对已有的Web协同应用中的一致性维护方法会带来严重的服务器耗费问题,提出了一种基于文档划分的一致性维护模型。该模型在操作转换算法SLOT(symmetric linear operational transformation)的基础上引入文档划分的思想。从降低服务器通信和内存耗费的角度出发,结合用户数量和操作频率的变化,给出一种动态的文档划分策略及其实现算法。仿真实验结果表明,该模型可以有效地降低大规模协同应用中服务器的通信和内存耗费。     

动态图划分算法研究综述

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.     

一种基于GN算法的动态图划分方法

随着图规模的急剧增长，对动态图进行实时处理的需求日益增加。大多现有的算法针对静态图划分是有效的，直接用其处理动态图会带来较大的通信开销。针对该问题，提出一种基于GN算法的动态图划分方法。首先收集一段时间内加入动态图中的顶点；然后，利用GN算法对这些新加入的顶点进行预划分，产生若干个内部联系紧密的社区；最后，将预划分产生的社区结果插入到已经划分好的当前图中。实验从交叉边数和负载均衡度两方面将该方法与传统流式划分方法进行比较，结果表明， 在公开数据集上，该方法的交叉边数降低了13%，负载均衡度减少了42.3%。由此可见，该方法的划分质量明显优于传统的流式划分方法。     

基于广度优先遍历加权图生成的启发式图分区

图分区质量极大程度上影响着计算机之间的通信开销和负载平衡, 这对于大规模并行图计算的性能是至关重要的. 然而, 随着图数据规模的越来越大, 图分区算法的执行时间成了一个不可避免的问题. 因此, 研究如何优化图分区算法的执行效率是有必要的. 本文提出了一个基于广度优先遍历加权图生成的启发式图分割方法, 该方法在实现较低的通信代价和较好负载平衡的同时, 只引入了少量的预处理时间开销. 实验结果表明, 本文的划分方法减少了复制因子, 降低通信开销, 并且引入的时间开销较小.     

动态可重构系统的时域划分及其行为级算法的定量分析

对近20年来可重构系统的时域划分算法进行了分析,把它们分为网表级和行为级算法两大类.网表级时域划分算法主要采用网络流方法,使电路的面积、割网的个数等最小化,并使电路获得较小的时延和通信代价.我们对层划分、簇划分、增强静态列表调度、多目标时域划分等四种行为级时域划分算法进行了定量分析和比较,评价指标体系包括划分后的模块数、跨模块的输入/输出边数、划分后所有模块的执行总延迟.实验结果表明,层划分是四个算法划分后所有模块执行总延迟最小的;簇划分算法获得较少的跨模块的输入/输出边数;增强的静态列表调度和多目标时域划分两个算法在三个指标之间获得了一个好的折中.然而,这四个算法均没有考虑划分后的模块形状及模块的跨层映射成本.     

Task spreading and shrinking on multiprocessor systems and networksof workstations

In this paper, we describe how our computational model can be used for the problems of processor allocation and task mapping. The intended applications for this model include the dynamic mapping problems of shrinking or spreading an existing mapping when the available pool of processors changes during execution of the problem. The concept of problem edge class and other features of our model are developed to realistically and efficiently support task partitioning and merging for static and dynamic mapping. The model dictates realistic changes in the computation and communication characteristics of a problem when the problem partitioning is modified dynamically. This model forms the basis of our algorithms for shrinking and spreading, and yields realistic results for a variety of problems mapped onto real systems. An emulation program running on a network of workstations under PVM is used to measure execution times for the mapping solutions found by the algorithms. The results indicate that the problem edge class is a crucial consideration for processor allocation and task mapping     

On parallelizing the EM algorithm for PET image reconstruction

The expectation maximization (EM) algorithm is one of the most suitable iterative methods for positron emission tomography (PET) image reconstruction; however, it requires a long computation time and an enormous amount of memory space. To overcome these problems, we present two classes of highly efficient parallelization schemes: homogeneous and inhomogeneous partitionings. The essential difference between these two classes is that the inhomogeneous partitioning schemes may partially overlap the communication with computation by deliberate exploitation of the inherent data access pattern with a multiple-ring communication pattern. In theory, the inhomogeneous partitioning schemes may outperform the homogeneous partitioning schemes. However, the latter require a simpler communication pattern. In an attempt to estimate the achievable performance and to analyze the performance degradation factors without actual implementation, we have derived efficiency prediction formulas for closely estimating the performance for the proposed parallelization schemes. We propose new integration and broadcasting algorithms for hypercube, ring, and n-D mesh topologies, which are more efficient than the conventional algorithms when the link setup time is relatively negligible. The concept of the proposed task and data partitioning schemes, the integration and broadcasting algorithms, and the efficiency estimation methods can be applied to many other problems that are rich in data parallelism, but without balanced exclusive partitioning     

Large-scale multi-robot task allocation via dynamic partitioning and distribution

This paper introduces an approach that scales assignment algorithms to large numbers of robots and tasks. It is especially suitable for dynamic task allocations since both task locality and sparsity can be effectively exploited. We observe that an assignment can be computed through coarsening and partitioning operations on the standard utility matrix via a set of mature partitioning techniques and programs. The algorithm mixes centralized and decentralized approaches dynamically at different scales to produce a fast, robust method that is accurate and scalable, and reduces both the global communication and unnecessary repeated computation. An allocation results by operating on each partition: either the steps are repeated recursively to refine the generalized assignment, or each sub-problem may be solved by an existing algorithm. The results suggest that only a minor sacrifice in solution quality is needed for significant gains in efficiency. The algorithm is validated using extensive simulation experiments and the results show advantages over the traditional optimal assignment algorithms.     

Adaptive Electrocardiogram Feature Extraction on Distributed Embedded Systems

Tiny embedded systems have not been an ideal outfit for high performance computing due to their constrained resources. Limitations in processing power, battery life, communication bandwidth, and memory constrain the applicability of existing complex medical analysis algorithms such as the Electrocardiogram (ECG) analysis. Among various limitations, battery lifetime has been a major key technological constraint. In this paper, we address the issue of partitioning such a complex algorithm while the energy consumption due to wireless transmission is minimized. ECG analysis algorithms normally consist of preprocessing, pattern recognition, and classification. Considering the orientation of the ECG leads, we devise a technique to perform preprocessing and pattern recognition locally in small embedded systems attached to the leads. The features detected in the pattern recognition phase are considered for the classification. Ideally, if the features detected for each heartbeat reside in a single processing node, the transmission will be unnecessary. Otherwise, to perform classification, the features must be gathered on a local node and, thus, the communication is inevitable. We perform such a feature grouping by modeling the problem as a hypergraph and applying partitioning schemes which yield a significant power saving in wireless communications. Furthermore, we utilize dynamic reconfiguration by software module migration. This technique, with respect to partitioning, enhances the overall power saving in such systems. Moreover, it adaptively alters the system configuration in various environments and on different patients. We evaluate the effectiveness of our proposed techniques on MIT/BIH benchmarks and, on average, achieve 70 percent energy saving.     

支持细粒度并行性开发的多核DSP快速核间通信机制

一些数字信号处理程序存在强数据相关性,在将这些数字信号处理程序划分到多核DSP上时,需要开发细粒度并行性,而细粒度并行性的开发需要快速的核间通信机制支持。本文提出了一种新的面向多核DSP的快速核间通信机制:标记式共享寄存器文件TSRF,TSRF由所有的DSP核共享,寄存器文件中的每个寄存器同一个有效标记位关联,该标记位提供了核间通信同步支持。本文构建了集成TSRF机制的多核DSP原型的周期精确模拟器,该多核DSP原型包含的处理器核数目为4个。通过详细模拟,我们使用数据相关性较强的数字信号处理算法:IIR滤波和ADPCM编解码,对TSRF机制的性能进行了测试,与单核DSP相比,TSDB机制性能提升分别为1.8、1.2和1.9左右。