分布式基于代理的建模

于 2010年7月21日

导言

什么是基于代理的建模，也称为 ABM？什么是分布式计算？为什么要这样做？

这些都是很容易回答的问题，对吧？令人惊讶的是，在许多圈子里，答案是响亮的“不！”。仍然有很多软件开发人员在使用纯过程式方法和 C、FORTRAN、PASCAL、Visual Basic 等语言实现应用程序。更糟糕的是，有很多人使用能够进行良好面向对象实现的语言，如 C++ 和 Java，但他们只是使用这些语言来实现过程式设计。这些人，无论出于何种原因，只是没有意识到 ABM 软件方法论提供的优势。

我们不会在此深入探讨这些优势，因为我们不想引发一场 ABM 软件设计的圣战（尽管，我们可能会暗示过程式软件工程方法是黑暗时代遗留下来的产物，目前的从业者非常像侏罗纪晚期地球上漫游的生物）。

但我们当然不想引发任何口水战。

相反，我们只想建议 ABM 方法论代表了当前解决大量当今软件设计挑战的最佳实践，然后继续讨论本文的重点，即分布式基于代理的建模。

什么是 ABM 方法论？

什么是基于代理的建模？答案非常简单，但我总是发现自己对一些顽固不化的过程式开发人员无法理解这个概念感到沮丧。以下是 ABM 方法论的全部核心内容：

基于代理的模型设计是指，要建模的现实世界实体的类似物被表示为软件代理或对象，在解决模型需要回答的问题所需的细节和分辨率级别上。 代理在模型运行时相互交互，产生关于被模拟系统的动态信息。

一些 ABM 从业者可能会对“软件代理”和“软件对象”之间的区别吹毛求疵；如果是这样，我鼓励他们在本文后面的评论区提出他们的异议。然而，这些吹毛求疵对于本文的主旨并不重要，本文的主旨是如何在分布式计算环境中开发基于代理的模型。

现在，让我们用一个真实的 ABM 实现示例来说明这意味着什么。我们将在此处使用的示例是 EpiSims，这是一个大规模分布式流行病学模拟。EpiSims 是由我在 1990 年代中期在洛斯阿拉莫斯国家实验室的团队设计和实现的。它的目的是模拟传染病在大型城市人口中的传播，并允许分析师评估各种拟议的干预策略对减缓或阻止疾病传播的影响。EpiSims 仍在全美国各地使用。

那么，EpiSims 中的软件代理是什么？它们是：

人员代理，
地点代理，人们在一天中去往并在那里相互接触的地方。地点代理有各种子类：住宅、学校、工作场所、医院、购物中心、公共交通等，以及
疾病代理。

就是这些。这些就是代理。受感染的人员代理随身携带一个疾病代理实例，该实例定义了当在某个地点发生接触时疾病如何传播给其他人员代理，因为模拟的人们会进行他们的日常活动。疾病代理还控制着疾病在其人员代理宿主中的进展。

人员代理的特征在于少量人口统计信息，例如年龄、性别、家庭结构、种族和家庭收入，这些信息已被确定为进行有效疾病干预分析所必需的。

分布式 ABM

为什么要费力开发分布式基于代理的模型？简短的答案是，有许多问题太大，无法在串行计算环境中解决。再次以 EpiSims 为例：芝加哥市人口约为 860 万，家庭超过 200 万户。这需要大量的软件代理。这种 ABM 设计表示的内存需求对于大多数单 CPU 环境来说太大了。同样，计算需求也无法由单个 CPU 提供。

那么问题就变成了：如何最好地开发一种 ABM 设计，使其能够利用当今 Linux 集群提供的数百到数千个处理器和大量分布式内存？

事实证明，在开发分布式设计时，有一些经验法则需要考虑。以下是其中一些：

尽可能均匀地分布您的 ABM。您不希望在分布式运行中出现利用不足或过度利用的计算节点。您的运行最终将受到运行配置中最慢节点的性能限制。
以最小化计算节点之间消息传递需求的方式分布您的 ABM。与板载内存带宽相比，消息带宽较慢。
简单的同步方法最容易实现，但它们通常无法很好地扩展。从简单开始，稍后根据性能需要添加复杂性。

如何开始分布式 ABM 实现

本文的以下部分描述了 ABM++，这是一个开源 (GPL) 软件框架，允许开发人员在 C++ 中实现基于代理的模型，以便部署在分布式内存 Linux 集群上。ABM++ 可以从 http://parrot-farm.net/ABM++/ 下载。该框架提供了必要的功能，使应用程序能够在分布式架构上运行。框架提供了一个 C++ 消息传递 API，它提供了在分布式对象之间发送 MPI 消息的能力。该框架还提供了一个接口，允许将对象序列化到消息缓冲区中，从而允许它们在分布式计算节点之间移动。框架提供了一种同步方法，并提供了时间步进和分布式离散事件时间更新机制。

关于开发人员如何选择设计其代理的 C++ 表示，ABM++ 完全灵活。分布式计算所需的所有功能都由框架提供；开发人员为其应用程序提供 C++ 代理实现。分布式计算功能通过简单的继承和包含由框架提供给应用程序。源代码包含应用程序目录中的一个简单工作示例，以说明如何使用该框架。

背景

ABM++ 是在 1990 年至 2005 年期间在洛斯阿拉莫斯国家实验室开发的分布式计算工具包的重新设计版本。EpiSims、TRANSIMS 和 MobiCom 是在洛斯阿拉莫斯开发的三个大型分布式基于代理的模型，它们使用了分布式工具包。该工具包在 2009 年进行了重新设计和重新实现，使其更加模块化和可扩展。

用于管理分布式代理的工具

在分布式 ABM 中，代理分布在集群中的计算节点上。在大多数应用程序中，一些代理可能是静态分布的：在初始分布之后，它们永远不会在分布式计算节点之间迁移。其他代理是动态分布的：它们可以在模拟运行时在计算节点之间迁移。作为示例，考虑一个社交网络模型的设计，该模型模拟芝加哥这样规模的城市中所有个人之间的互动，芝加哥的人口为 860 万。

此设计中的代理是：
个人，以及

城市中的地点（住宅、工作场所、学校、商店、医院等）。对于芝加哥模型，除了约 2,000,000 户住宅外，可能还需要模拟 200,000 个非住宅地点。

在此示例设计中，地点代理将是静态分布的，人员代理将是动态分布的。在模拟初始化时，所有 2,200,000 多个地点将分布在集群计算节点上。然后，当模拟运行时，人们将在 CPU 之间迁移，因为他们模拟的日常活动导致他们在模拟的一天中从一个地点移动到另一个地点。人员代理将因社交网络移动模式而在地点与其他人员代理接触，然后可以模拟任何感兴趣的人员代理交互。

ABM++ 框架提供了专门的容器类，这些容器类可以用关于所有静态分布代理所在的 CPU 的信息填充。这有助于在分布式代理之间发送消息的能力。源代码分发中包含一个示例分布式 ABM，演示了这些专用容器类的使用。

时间更新工具

框架提供了两种时间更新方法：时间步进和离散事件更新。提供的示例框架代码包含一个使用时间步进更新的示例。

同步工具

分布式 ABM 中计算节点之间的进程间通信通常会施加同步要求。在我们的示例社交网络模拟中，当人员代理在地点之间随机移动时，人员代理会在计算节点之间迁移。重要的是，在每次移动时，两个计算节点都处于相同的模拟时间，否则，如果人员代理到达一个计算节点，而该节点对当前模拟时间的概念与他刚刚离开的节点不同，则会导致因果关系错误。

当前版本的框架提供了一种使用主/从设计的同步方法。这种类型的同步的优点是简单，但缺点是无法很好地扩展到数千个计算节点。框架的未来版本将包括第二种同步方法，该方法利用随机成对计算节点方法，该方法可以很好地扩展到大型集群配置。

消息传递接口 (MPI) 的 C++ API

ABM++ 附带一个名为 MPIToolbox 的库，该库为 MPI 提供了 C++ API。此 API 提供了 MPI 的接口，其中包括用于将代理序列化到消息缓冲区中的方法，从而允许通过 MPIToolbox 在集群中的计算节点之间发送代理。MPIToolbox 的优点在于它可以透明地处理 MPI 的较低级别接口，从而简化了实现消息传递代码的任务。

一个例子

应用程序目录包含一个简单的社交网络 ABM 的完整工作实现。模拟中的代理由地点代理和人员代理组成，如上所述。地点代理软件对象是静态分布的，而人员代理在它们之间迁移。

应用程序目录中的代码旨在用作实际分布式 ABM 实现的存根或起点。特别是，DSim.[Ch]、DistribControl.[Ch] 和 ABMEvents.[Ch] 文件旨在进行修改以满足特定的应用程序要求。

示例问题陈述，要作为分布式 ABM 实现

在每个可用计算节点的每个 CPU 上创建 100 个上述类型的地点。在每个地点创建 1000 人。每 15 分钟随机将所有人发送到其他地点。假设一个人从当前地点到达另一个地点需要 15 分钟。

DSim.C
此文件包含示例模拟应用程序的 int main() 例程。


    //
    // Create an instance of a class object that will perform 
    // distributed run control
    //
    DCtl = new DistribControl();

正是在 main() 中实例化了几个框架全局变量。也是在这里设置了模拟结束时间并启动了模拟。创建的全局变量之一是 DCtl，实例化如下所示，从 DSim.C 的第 60 行开始。

DistribControl.C

此文件包含 DistribControl 类的方法定义。DCtl 对象负责理解 ABM 的分布式拓扑结构并控制模拟运行。DistribControl 类的公共方法的简要描述如下。有关实现细节，请参阅 DistribControl.C。

DistribControl::Init

在每个计算核心上创建分布式对象容器。分布式对象容器用于取消引用分布式地点对象所在的计算核心 ID。
为每个计算核心创建一个模拟控制器对象。模拟控制器对象使时间更新发生。
创建 ABMEvents::TimeStep 类的实例。控制器对象使用此 TimeStep 类来执行重新安排时间步进更新。
在每个计算核心上创建一些地点。
将驻留在该核心上的地点 ID 广播到此分布式运行中的所有其他工作进程。
与主进程同步，以便在所有工作进程都完成初始化之前，它们都不会离开 DistribControl::Init。

DistribControl::Run

此方法只是使重新安排的 ABMEvents::TimeStep 事件在每个时间间隔执行。

DistribControl::Shutdown

此方法与所有其他计算核心协调以完成分布式运行的同步关闭。

DistribControl::HandleIO

此方法仅在 MPI 主核心上调用。它使用 MPI Toolbox 方法在自旋锁中侦听传入的 MPI 消息。

DistribControl::HandleEvent

此方法在主核心和所有工作进程计算核心上运行。它是一个专门的方法，继承自 MPI Toolbox 中的 TmessageRecipient 类。它根据接收的消息类型处理所有传入消息。例如，如果消息 ID 的类型为 kReceivePerson，则 DistribControl::HandleEvent 知道消息缓冲区包含到达此计算核心的人员代理的序列化表示，并且将调用 DistribControl::ReceivePerson 方法，并将消息正文作为参数传递，从中将实例化 Person 类的新实例。

DistribControl::ReceivePerson

从作为参数传递的消息 bugger 中实例化 Person 类型的新实例。然后将人员代理插入到其目标地点。

DistribControl::SendPerson

当人员代理需要移动到新地点时，将调用此方法。如果目标地点是此计算核心本地的地点，则为该地点调用 Location::ReceivePerson。如果目标地点位于另一个计算核心上，则人员代理将被序列化为 MPIToolbox 消息，并且该消息将被发送到其目标计算核心。

DistribControl::Synchronize

调用此方法是由于 DCtl 收到了来自模拟主进程的消息，指示需要同步。此方法将处于自旋锁状态，直到它收到来自主进程的另一条消息以继续模拟。

DistribControl::AddLocationData

在 DCtl 收到类型为 kSendLocationInfo 的消息后调用此方法。消息正文包含驻留在其他计算核心上的所有分布式地点的计算核心 ID 和地点 ID。DCtl 使用此信息来取消引用分布式地点的计算核心 ID。

SocialActivity.C

此文件仅包含两个方法。

SocialActivity::CreateLocations

DistribControl::Init 调用此方法以在此计算核心上创建 100 个地点。

SocialActivity::MovePeople

这是由 Controller 对象在每个时间步调用方法。它将驻留在计算核心上的地点中的所有人员代理发送到其他随机选择的地点。请注意，此方法调用 Location::SendPerson，后者又调用 DCtl->SendPerson，因为只有 DistribControl 对象知道地点对象在集群计算核心上的分布情况。

ABMEvents.C

TimeStep::Eval

TimeStep 类用于定义每个时间步要发生的模拟活动。时间步间隔在第 42 行定义，时间步功能在第 45 行开始的 TimeStep::Eval 函数中定义。