毕业设计（论文）文献译文：并行与分布式仿真中的研究挑战

毕业设计（论文）--文献翻译原文题目ResearchChallengesinParallelandDistributedSimulation译文题目并行与分布式仿真中的研究挑战专业姓名学号指导教师并行与分布式仿真中的研究挑战RICHARDM.FUJIMOTO,GeorgiaInstituteofTechnology摘要并行与分布式仿真领域从20世纪70年代和80年代就发展壮大起来，目前仍然是一个活跃的研究领域。介绍了该领域研究的简要概述。未来研究课题的领域，包括大规模系统和复杂网络的问题驱动仿真、图形处理单元硬件和云计算环境的开发、系统管理和优化的预测性在线模拟、移动平台和数据中心的电力及能源消耗、以及异构仿真的组成。引言与历史观点并行与分布式仿真领域出现于20世纪70年代和80年代两个不同的研究团体。一方面，并​​行离散事件仿真（PDES）团体关注于通过开发高性能计算平台来加速离散事件仿真的执行。在大致相同的时间框架内，分布式仿真团体形成，成为国防社会的重点研究和开发工作，专注于通过本地和广域网互连的计算机执行互连仿真。尽管离散事件仿真与分布式仿真的工作有很大差异，但仍存在很多共同的问题。在这里，我们将并行与分布式仿真非正式地定义为一个领域：专注于通过网络在平台范围从紧密耦合并行计算机到松散耦合计算机的多个处理器上执行仿真程序。需要特别强调的是离散事件仿真常用于系统分析。1.1并行离散事件仿真离散事件仿真涉及在高性能计算系统中，跨多个处理器为某个离散事件仿真程序分配单个执行。这样平台包括共享内存多处理器和基于消息的群集计算机。离散事件仿真的中心目标通常是加速仿真的执行。随着时间的推移，离散事件仿真捕获实际或预想的系统的行为。不像其他仿真以时间流逝的模式运行和演变，系统的状态一步到下一个。在离散事件仿真中，系统状态的变化发生在不同的，通常离散的模拟时间点内。一个连续的离散事件仿真程序包括两个基本概念：捕获正被建模的系统状态的状态变量以及事件计算或简单地将状态变量从一个状态转换到下一个状态的事件。在离散事件仿真中，模拟状态的改变的发生仅通过事件计算。每个事件都包含一个代表状态转变发生的仿真时间点的时间戳。例如，机场的模拟可能包括表示跑道状态的状态变量（例如空闲或忙碌），以及其他方面，如等待起飞或着陆的飞机数量。活动可能对应于飞机到达或离港。并行离散事件仿真程序可以被看作是通过交换时间戳的消息进行交互的许多顺序离散事件仿真的集合。每个消息表示一个模拟器为另一个模拟器调度（发送）的事件。每个顺序模拟器被称为逻辑进程或LP。例如，可以通过创建每个机场的顺序仿真，并允许每个模拟器调度事件（即，发送消息）到其他模拟器，来构建全球空中交通系统的仿真。在机场模拟器之间传输的信息，可能代表飞机从一个机场到达另一个机场。PDES中的大部分工作都集中在PDES程序的同步。同步问题专注于确保一个PDES程序的执行，能够精确地或在某些情况下近似地产生与相同程序顺序执行一致的结果，其中所有事件都在另一个时间戳的命令之后被处理。可以看出，这可以通过确保来实现每个LP以时间戳顺序处理事件，包括从其他处理器接收的消息（或事件;在这里，我们使用同义的术语消息和事件）。同步算法大致分为两类：保守型和乐观型。保守算法，如Chandy/Misra/Bryant算法[Bryant1977;Chandy和Misra1978]使用阻止LP执行的机制，直到它可以保证不再接收到具有更小时间戳的事件。这需要规定一个前置值。如果LP正处于时间T，其前置值为L，则LP稍后发送的任何消息必须具有的时间戳至少为T+L。可以将前置值与链接相关联，而不是逻辑进程。所有保守算法都依赖于一个足够大的前置值来实现事件的并发处理。最后，在类保守算法中，一些算法使用全局屏障同步来管理执行。显着例子是有界滞后[Lubachevsky1989]和YAWNS[Nicol，Michealetal.1989]算法。虽然保守算法采取预防措施来确保LP始终在时间戳顺序中处理事件，乐观算法允许事件被无序处理，但是利用回滚机制从这样的错误中恢复。时间扭曲[Jefferson1985]是第一个乐观同步算法，目前仍然是最广泛使用的乐观算法。在保守和乐观算法里有着广泛的文学。在Fujimoto中更详细地介绍了大部分的工作[2000，2015]。1.2分布式仿真分布式仿真涉及跨越计算平台的仿真执行，其平台是比并行电脑更广泛的平台。并行仿真中执行仿真的处理器驻留在机房内的机柜中，与并行仿真相反，分布式仿真可以执行一组通过局域网互连的机器，全球分布式计算机通过互联网或嵌入物理环境的预测仿真进行通信，例如监测城市交通的传感器网络。运用分布式仿真系统的中心目的是允许地理分布资源的开发，如设备或分布式仿真练习中的人，或通过实时数据近似地执行仿真以预测运营系统的未来状态。一个中心问题，往往也是利用分布式仿真的主要动机为，渴望集成在不同计算机上运行的模拟器设备进入单一模拟环境。大部分早期分布式仿真工作专注于训练系统坦克模拟器，飞行模拟器，电子计算机力量和其他各种可以创建人员可嵌入其中的分布式虚拟环境以训练假设场景和情况的模型。同步，也称为分布式仿真文学中的时间管理，也是分布式仿真中的一个问题，它不是唯一的问题，通常不是最重要的一个。大部分早期的分布式仿真的研究关注于模拟器的分布信息以有效和及时的方式参与到分布式仿真。大部分的工作涉及通信协议，如多路广播机制或方法以减少大量需要通过技术使用来传达的数据，如推算[Miller和Thorpe1995]或数据分发管理[MorseandZyda2001]技术。因为分布式仿真的重点在于已经实现了个别发达模拟器之间的互操作性，大量的努力集中在开发互连仿真标准。这导致了分布交互式仿真（DIS）（IEEE）标准1278.1-19951995，IEEE标准1278.2-19951995）和高级架构（HLA）（IEEEStd1516-20102010，IEEEStd1516.1-20102010，IEEEStd1516.2-20102010）标准。在Fujimoto[2000]和Tolk[2012]进行讨论的分布式仿真研究社区解决了许多技术问题。本文的其余部分组织如下。下一节简要介绍一下目前和未来六个方面的研究并行与分布式仿真需要的额外工作，并根据目前的技术趋势和应用争辩为什么每个这些领域都是适时的。第3节是本文的主体。通过提出每一个在这一领域的总体挑战、讨论先前的工作、突出重点研究问题和尚未得到圆满解决的问题，它更加详细地讨论了这六个研究领域。虽然这些挑战中的一些仅与PDES或分布式仿真相关，但跨越两个领域。最后，第5节提供了关于并行与分布式仿真领域未来的总结性结论。主要研究挑战并行与分布式仿真领域在过去四十年不断发展和演变。今天，这一领域面临着许多新的挑战，一方面这些挑战源于新应用的需求，另一方面由于其所运作的基础硬件和软件系统的重大变化。在列举的六个领域定义了技术挑战，如果有重大进展可能产生跨越多个应用领域的影响，所以亟待解决：大型复杂网络的应用驱动，可扩展模拟。迄今为止关于大规模、大量并行仿真的研究侧重于证明PDES技术对合成工作负载的能力。我们倡导以应用驱动的方式展示大规模的能力模拟以获得对现实世界网络规模的行为的新见解。例如，一个挑战是创建具有偏斜节点度分布的不规则拓扑网络的大规模仿真。利用图形处理单元（GPU）开发异构机器体系结构。GPU在从大型超级计算机到集群和台式机的平台中变得越来越普遍。越来越多的研究一直在探索开发并行离散事件仿真应用的相关设备。如果成功，在这一领域的研究可能使PDES为某些类别的问题去实现新的性能水平。通过更简单的模型开发和云计算平台，使并行与分布式仿真可以广泛可用。开发高效的并行仿真代码的难度仍然是一个挑战，并且简化软件开发和维护的技术也是迫切需要的。云计算能够为几乎所有用户提供并行与分布式仿真技术，而不会产生购买和运行高性能计算平台的费用，这是一个过去长期存在的问题，阻止了并行与分布式仿真技术的广泛采用。在线决策使用实时分布式仿真。无处不在的计算、无线传感器网络和大量的数据的出现，使仿真能够以诸如智能城市等新兴领域的前所未有的规模嵌入到操作系统中。在操作系统的在线管理和优化中，分布式仿真能发挥重要作用。节能和省电的并行与分布式仿真。电力和能源消费已经成为计算的主要问题。它影响移动计算平台的电池寿命，是数据中心的主要费用。然而，到目前为止，并行与分布式仿真领域的电力和能源消耗很少得到重视。关于并行与分布式仿真的电力和能源特性，或如何有效地管理程序执行的这些方面，知之甚少。分布式仿真的快速组合。快速构建单独开发的仿真，仍然是一个艰巨的挑战。虽然已经取得了许多进展，例如，在创建支持软件框架和标准的技术方面。然而，针对不同目的编写单独开发的仿真仍然是一个耗时的任务，或者甚至不可能。这一领域的重要性在不断增加，认识到在许多情况下，必须使用非还原性方法来整体研究系统，而不是其孤立的构成部分。根据最近的技术趋势和应用需要，我们认为这些领域的每一个研究都是适时的。关键因素激励着前三个领域关注底层计算平台的重要技术变化。这种现象对并行与分布式仿真来说并不陌生。事实上，并行离散事件仿真随着商业多处理器系统的可用性而出现，分布式仿真源于计算机网络的进步以及其他技术。大容量并行超级计算机包含超过百万个核心，GPUs，并且云计算在过去十年中已经显现出重要性，激发了并行与分布式仿真的研究，以开发这些平台。最近的趋势，如物联网和“大数据”对于并行与分布式仿真的未来有很大的影响。随着移动计算的出现和传感器网络等技术的发展，在线决策越来越重要。并行与分布式仿真是数据分析开发的补充。虽然纯粹来自数据分析的模型在许多情况下提升了提供预测能力的潜力，但这些模型不包括对被调查系统的行为描述，这些描述对于假设实验或分析足够数据或正确数据不能用的情况分析（例如，由于隐私或其他问题）而言是必要的。同时，电力和能源消耗已成为计算领域（包括移动计算平台和数据中心）的重要考虑因素。最后，虽然仿真的组成仍然是分布式仿真中多年存在的一个长期问题，新兴应用领域比如智能城市，它要求系统的建模系统突出该技术日益增长的重要性。在开发方法和标准方面取得了许多进展，以使仿真能够进行互操作。然而，我们远远没有实现方法，使得其单独开发的模型可以轻松地以“即插即用”的方式组合，并确保所得到的模型是有效的。六个研究挑战在下文中，我们更详细地回顾了每个这些领域的正在进行的工作以及尚未解决的关键研究挑战。我们开始讨论每一个拥有挑战的领域，试图在该领域进行研究。3.1复杂网络的大规模并行离散事件仿真挑战1.创建可扩展性。现实的大规模不规则系统的仿真，例如复杂网络，并展示其为现实世界系统创造新见解的能力。第一个挑战的核心是创造可信的现实网络的仿真模型，其规模为了深入了解他们的行为。多年来，已经取得了许多成功的成果，展示了PDES技术加速离散事件仿真执行的能力。例如，Fujimoto等人[2003]检查了超级计算机上计算机通信网络的分组级仿真。并行模拟器在2003年使用1,536个处理器在超级计算机上执行的保守同步算法，每秒可以产生高达超过2亿事件（eps）的性能。相比之下，在顺序机器上执行的可比模拟器产生的性能小于20万次。2007年，通过合成基准称为PHOLD的研究使用16,384处理器机器[Perumalla2007]上的乐观同步算法获得了超过5.29亿eps的性能，2009年，通过65,536个处理器实现了122.6亿eps的性能[Bauer等。2009]，都使用IBMBlueGene机器。2013年，Barnes等[2013]能够使用近200万个蓝色基因/Q机核心达到5040亿个eps。对具体应用的大规模模拟的研究包括流行病传播[Bissetetal。2009年;Perumalla和Seal2010;Perumalla等人2014]和电磁信号传播[Baueretal。2009年]。为此，我们使用事件/第二个度量，因为以后引用的研究集中在每个事件计算量适量的应用程序，该度量对于没有此属性的应用程序不太有用。在Fujimoto[2003]、Perumalla[2007]、Bauer[2009]、Barnes[2013]等人报道的研究，分别产生了138K[2003]，32K[2007]，187K[2009]和256K[2013]eps/core的单核事件发生率。这表示跨越10年的时间里单核性能方面只有双重的改善。这些数据表明，今天的性能改进几乎完全由并行性的增加驱动。这并不奇怪。由于2005年以来，由于散热的物理限制，处理器时钟频率仅有小幅增长，导致自2005年以来，超级计算机体系结构中的核心数量爆炸式增长。从20世纪90年代到2005年间的大部分时间里，最强大的超级计算机只包含数千的核心。今天最强大的机器包含数百万。刚才引用的研究在很大程度上集中于自下而上的技术手段。由此我们认为这些研究集中在理解PDES技术本身的可扩展性和局限性，这在很大程度上独立于应用。但是重要的是，需要一种关于具体的应用问题的选择性的自上而下的问题驱动的方法。这些研究将集中在回答特定问题领域的重要问题和这些应用的突出特性，称之为新的并行化方法。最近在计算机网络仿真方面的工作包括Kunzetal。[2016]和金和尼科尔[2015]。为了说明这一点，考虑网络拓扑的问题。前面所述的研究集中在高度规则的合成网络拓扑，例如圆形，环形或完全连接的网络。PDES拓扑是每个节点表示LP的图形，并且每个连接两个LP的链路表明，这些LP可以通过在它们之间发送消息来进行通信。这里，我们假设无向弧，对发送和接收LP不进行区分。前面描述的基准测试研究都采用了一种常规的网络拓扑结构，例如环形线圈，其中工作负载可以在网络上均匀分布，几乎没有困难。实际上，很少有现实世界的应用展现出这样的理想特性。过去十年的大量研究侧重于在现实应用中出现的网络拓扑。通常，有实际价值的网络是非常不规则的。已经观察到一类称为无规模网络的拓扑[Barabasi和Albert1999]常常出现。无规模网络是节点度数遵循幂律分布的网络。无规模网络的一个显着特征是，大量的节点（被称为集线器节点）包含大的节点度，而大多数节点（通常称为叶节点）包含相对较小的节点度。无规模网络是具有偏斜节点度分布的网络的一个明确例子。近年来，无规模网络受到了很多的关注，因为已经观察到许多现实世界的系统包含至少近似的无规模属性的网络[WangandChen2003]。例如，人们普遍认为互联网的自治系统（AS）级的拓扑结构是无规模的[Faloutsosetal。1999;Siganos等人2003;张等人2011]。在系统生物学的广泛领域、复杂生物系统的研究里，蛋白质-蛋白质相互作用网络的研究已被证明遵循无规模分布[Kitano2002]。一些金融网络，如同业支付网络，显示出无规模的行为[Soramakietal。2007年]。据报道，社会网络、维网、超导体的内部结构、航空运输网络以及诸如表征疾病传播的人类互动网络，都在不同程度上呈现出无规模属性。虽然其他网络没有遵循幂律分布，但似乎他们的节点度分布很歪斜。例如，初步研究表明互联网的路由器级拓扑遵循幂律，但最近的工作报告说，拓扑由工程和经济因素以及物理节点和链路容量约束驱动，导致节点度分布是偏斜的，但是不遵循幂律[Li，Aldersonetal。2004年]。路由器级拓扑在网络边缘包含许多高级路由器，用于将许多低带宽连接的流量与具有较少数量高带宽链路的大容量路由器的网状核心进行聚合。网络拓扑对并行离散事件仿真在并行性和同步算法上的效率，有着很大的影响。例如，Guclu等人[2004]，配置在环形拓扑中的LP网络增加了每个LP的一个附加链路，用于同步目的，以创建小世界拓扑，以提高可扩展性。根据经验观察到，通信网络的模拟中事件级并行性的分布，可能导致严重的负载不平衡[Liu和Chien2004]。在Dobrescu等人[2008]PDNS实验中，并行版本的NS2仿真[Rileyetal。2004]来模拟无规模网络，报道了使用少量处理器实现加速的一些成功，但注意到仅使用六个处理器的仿真网络流量，有适度的减缓。在D'Angelo和Ferretti[2009]中，并行无规模网络仿真中的负载分配问题，在模拟八卦协议中，有被检查和评估。在Pienta和Fujimoto[2013]中研究了幂律拓扑与并行仿真器性能之间的关系，通过两种分析模型和模拟观察，非常大的网络模拟可能产生非常有限的并行性。例如，包含数万个网络节点的无规模网络通常表现出少于百倍的并行性。最后，其他工作考察了无规模网络生成中的并行性[Hruzetal。2010;Yoo和Henderson2010]和使用本地和全局同步技术的混合同步方法[LiuandRong2012]。对于一些PDES同步算法，无规模网络是一个具有挑战性的测试用例。它们有问题的一个原因是因为无规模网络拥有所谓的小世界属性。小世界网络的区别在于网络中两个随机选择的节点之间的平均最小路径长度非常小；即使对于包含数百万个节点的网络，该长度也可能只有几个跳数。幂律分布的特征在于参数λ，其决定了将发生的高度节点的数量。在的情况下，自然无规模网络的