乐观策略下并行离散事件仿真动态负载划分优化算法

动态负载划分是提高并行离散事件仿真运行性能的有效途径之一.现有研究往往孤立地考虑计算负载平衡和通信负载优化,使得复杂应用背景下整体性能低下.论文综合考虑仿真模型计算负载和交互模式,提出了一个基于带权重无向图有限容量k划分问题的并行离散事件仿真负载划分模型,并配合一套通用的仿真运行性能度量方法,提出了一个基于顶点交换的启发式局部搜索近似划分算法,实现了在计算负载平衡的前提下系统通信负载最优化,其近似解与全局最优解比值不小于(1-1/|N|)(1-ε).实验证明了该动态负载划分算法的有效性和实用性.     

异构集群下基于标签传播的大规模图划分算法

近年来,大规模图数据处理在众多领域得到广泛应用,图划分算法是分布式图计算系统的基础,但大规模图在异构集群中的划分尚未得到充分研究。为此,针对异构集群,提出基于标签传播的大规模图划分算法(heterogeneous label propagation, HLP),根据计算节点负载能力进行图划分,以实现负载均衡和边割率最小化为目标。HLP算法规避了传统标签传播中顶点迁移的步骤,提高了算法效率。实验结果表明,HLP算法在分区质量以及划分效率方面均有较好表现。     

基于复杂连续系统并行仿真的自动任务划分

有效地进行任务划分、控制并行粒度,才能充分利用并行计算机的资源,通过对复杂连续系统仿真程序特点的分析,提出了以状态方程为核心、以右函数段的计算为主要对象的自动任务划分算法,使用结果表明具有很好的并行效果。     

基于规范划分集的并行循环计算划分

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

基于最小割划分的数模混合仿真系统通信性能优化方法

数模混合仿真是理解真实电网运行情况,支撑电网安全保障的重要手段.复杂的电网拓扑与硬实时的仿真需求对其计算性能提出了很高的要求.目前数模混合仿真多采用并行计算技术提高计算性能.随着处理器和集群技术的发展,异构集群系统逐渐成为高性能计算系统的主要构建方式.针对多层次的系统架构,已有的电网划分方式无法充分利用集群计算能力.如何应对多层次核间通信延迟变化问题,及引入设备交互导致的节点资源不对称问题是数模混合仿真任务划分与映射的新挑战.针对中国电力科学研究院自研电磁暂态仿真系统ADPSS,基于最小割划分设计了两阶段的电网划分与进程映射一体化优化算法,在计算负载均衡和最小化通信上取得更好的平衡,进一步降低了电磁暂态仿真的通信时间.同时,该算法有效解决了集群节点资源不对称情况下的任务优化映射问题.通过在西北和华东真实电网算例上的模拟测试,所提出算法较ADPSS默认划分与映射算法取得了平均40％和50％的通信性能提升,平均10％和12％的总体计算性能提升.     

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

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

一种基于代表元的划分算法

划分是把程序中不同的计算和数据分配到并行处理系统的不同处理机来充分利用并行系统的计算资源、提高程序处理速度的一种优化技术.划分的效果对程序在并行系统上的执行效率将产生至关重要的影响,因此划分问题一直是并行领域研究的一个热点.但是应用程序的一些特性,如非紧密嵌套循环、一条语句对非只读数组的多次引用间存在重叠、不同语句对同一数组不同步长的引用,给有效解决划分问题设置了极大的障碍.已有的划分算法无法对具有这些特征的程序进行自动划分.虽然在对具有这些特征的程序进行手工优化过程中,存在一些直观上的划分策略,但这些策略无法应用到编译器中来指导编译器完成对程序的自动划分.文中根据这类程序的特点,提出了一种基于代表元的划分算法.该算法通过使用程序中对划分计算产生实际影响的数组引用作为代表元素构造各种划分的限制条件,完成程序的划分.同时通过寻找最大一致性数据划分方向有效减少了程序划分过程中的数据重组织通信.该算法已经在AFT2004中实现,并对应用程序获得了很好的效果.     

一种基于路径优化的推测多线程划分算法

推测多线程(speculative multithreading,简称SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,基于控制流图和分支预测技术的线程划分方法,不可避免地会受到划分路径上所存在的控制依赖和数据依赖的制约.目前,在传统的线程划分算法中存在的一个重要问题是,在对划分路径进行选取时只考虑了控制依赖影响却不能有效地综合考虑数据依赖的影响,进而导致不能选取最佳的划分路径.因此,针对传统方法中这种依赖评估方法效率低下的问题,设计并实现了一种基于路径优化的线程划分算法.该算法通过引入基于程序切片技术的预计算方法,建立一种路径评估方法来评估程序间的控制和数据依赖.同时,引入控制线程体大小的启发式规则,以便有效地解决负载不平衡的问题.基于Olden测试集的测试结果表明,所提出的算法可以有效地对非规则程序进行划分,其平均加速比可以达到1.83.     

一种改进的并行保存划分算法

在计算需求量很大的电路模拟中，经常使用并行模拟技术来减少模拟时间。并行模拟中的划分被认为是提高模拟性能的有效途径。本文研究了针对并行逻辑模拟的一种优秀的启发式多层次划分算法——并行保存划分算法，针对其缺点做出了一些改进，得到一种新的划分算法。并将这种算法放到并行逻辑模拟框架SAVANT／TYVIS／WARPED中进行了验证，得到了较好的结果。     

基于高清编码的自适应Slice划分算法

对于多核高清视频实时编码系统,提出一种自适应Slice划分算法。该算法基于码率控制和熵编码复杂度模型,通过Intra预测得到当前编码图像的纹理复杂度分布,预测编码图像的计算复杂度分布,通过自适应Slice划分实现多核间计算复杂度均匀分配,从而提高多核并行编码效率。实验结果表明,与固定宏块数的Slice划分算法相比,该算法能更有效地提高并行加速比。     

量子模拟器优化综述

近年来, 不断发展的量子计算已成为众人关注的焦点. 然而, 量子硬件存在稀缺性和噪声等问题, 这使得研究量子算法、验证量子芯片等行为都依赖运行在经典计算机上的量子模拟器. 本文讨论了不同量子模拟器使用的主要模拟方法, 并讨论了主流的全振幅状态向量模拟器和基于张量网络的量子模拟器的各种优化. 最后, 我们总结了量子模拟器的现状和未来发展方向.     

Bounds on the multi-clients incremental computing for homogeneous decreasing computation sequences

This paper studies the performance of network-based incremental computing under various message sequences. We show the bounds on the time needed to compute the tasks requested by multiple clients. Our simulation result shows that the expected performance of random message sequences is close to the optimal performance.     

基于CPU-GPU混合加速的SPH流体仿真方法

基于光滑粒子流体力学SPH的流体仿真是虚拟现实技术的重要研究内容,但SPH流体仿真需要大量的计算资源,采用一般计算方法难以实现流体仿真的实时性。流体仿真通常由物理计算、碰撞检测和渲染等部分组成,借助GPU并行加速粒子的物理属性计算和碰撞过程使SPH方法的实时流体仿真成为可能。为了满足流体仿真应用中的真实性和实时性需求,提出一种基于CPU GPU混合加速的SPH流体仿真方法,流体计算部分采用GPU并行加速,流体渲染部分采用基于CPU的OpenMP加速。实验结果表明,基于CPU GPU混合加速的SPH流体仿真方法与CPU实现相比,能显著地减少流体仿真单帧计算时间且能更快速地完成渲染任务。     

On the Effectiveness of Superconcurrent Computations on Heterogeneous Networks

Concurrent computing on networked collections of computer systems is rapidly evolving into a viable technology that is attractive from the economic, performance, and availability perspectives. Several software infrastructures that support such heterogeneous network-based concurrent computing have evolved, and are in use for production-quality high-performance computing. In this paper, we describe such a system, and present our experiences with its use for massively concurrent computing in the application domain of polymer physics. The application involves stochastic simulation of polymer chains for measuring scale-invariant phenomena at critical disorder. The parallelization is achieved through the EcliPSe toolkit, and conducted on a flexible, tree-structured virtual machine made up of arbitrary and heterogeneous computing nodes dispersed across the country. These nodes cooperate to perform the simulation and pool results together in real time, at intermediate nodes in a tree, culminating at a central node which controls the parallel simulation. The advantage of the tree-structure is that it allows for a fault-resilient, flexible environment for long-running parallel simulations. We present results on performance, price-performance, and toolkit-based parallelization, and compare these against equivalent computations on a Cray/Y-MP.     

基于Hadoop分布式计算平台的磁流体动力学模型仿真研究

在Hadoop分布式云计算平台上进行科学计算仿真,具有节省软硬件投资、缩短模拟时间等研究意义。针对需要高计算能力的磁流体动力学(MHD)仿真问题,设计了一种基于Hadoop分布式计算平台的MHD仿真器。首先,将Spark和HAMA两种分布式并行计算模型整合到Hadoop生态系统中,分别用于支持内存计算和整体同步并行计算。然后,将Hadoop集群构建成Master-Slave对等结构,解决全局同步和局部同步问题。最后,在Hadoop集群上,利用有限体积法和黎曼问题来求解MHD方程。实验结果表明,该仿真器能够精确模拟MHD,同时大大缩短了仿真计算时间。     

基于ParaViewWeb架构的GPU高性能运算实现

针对智能手机、平板电脑等移动终端计算能力有限的问题,提出一种基于网络的通用计算服务平台。该平台以服务的方式为移动终端提供远程计算支持,增强其进行复杂运算的能力。利用ParaViewWeb架构的可扩展性,将高性能GPU通用计算与ParaViewWeb架构结合,在保留ParaViewWeb原有的三维数据分析与可视化功能的基础上,扩展其远程调用服务器GPU运算资源的能力。选取医学图像滤波算法为实验对象,验证了该平台的有效性,结果表明对比本地应用,基于网络的应用取得了显著加速。     

基于网络的分布并行虚拟计算机DPVM的总体设计

基于网络的分布式并行计算技术提供高性能、低成本的计算资源。该文介绍所构造的一个基于网络的分布并行虚拟计算机DPVM。它由虚拟机层、通信层和基本类层组成,以浏览器方式提供用户界面;允许计算机加入系统,提供空闲计算资源,或登录到系统上,获得计算资源;采用Java作为程序设计语言,支持平台无关的分布并行计算。     

基于计算网格的机器人分布式仿真系统

基于计算网格技术,构建了机器人分布式三维图形仿真系统,经对PUMA 560工业机器人进行动力学仿真计算表明,计算网格技术提高了机器人三维图形仿真系统的计算能力．     

网络计算管理研究

相对巨型机而言,基于网络的群机系统因其费用小、可靠性好、升级方便等特点,在解决某些高性能计算问题时完全可以代替巨型机,而且随着网络技术的发展及分布式理论的成熟,它将比巨型机有更可观的发展及应用前景。网络计算管理是群机系统能否充分发挥出优势的关键因素。该文介绍了网络计算管理的研究意义、发展阶段和趋势,从评价标准、关键技术和系统结构等方面介绍了网络计算管理的研究内容,并根据比较,选择介绍了几个性能较好的软件产品。