CN101064685A - 代理分配方法和设备 - Google Patents

Abstract

本发明披露了一种代理分配程序、方法和设备。本发明的目的在于快速并适当地分配代理。提供了一种用于在包括多个互连节点的计算机上分配代理的程序，每个节点具有CPU和存储器，所述程序使所述计算机的每个节点执行以下步骤：存储在所述节点上驻留的代理和与该代理进行过通信的节点之间传送的数据的数量；为每个代理确定节点M，该节点M导致所传送的数据量在所述代理被传递到所述节点M时最大程度地减少；把所述代理添加到包含要被传递到所述节点M的候选代理的代理列表中；以及把代理列表上的代理传递到节点M。

Description

代理分配方法和设备

技术领域

本发明涉及用于在多节点环境中分配代理的方法，更具体地说，涉及用于减小节点间的网络负载的代理分配方法。

背景技术

当今，大量的代理在包括节点的计算机上运行，每个节点具有CPU和存储器，它们通过快速网络(多节点计算机)互连，以执行对复杂的物理和经济现象的模拟。代理是表示自主行动的个人行动实体或经济实体的程序的一部分(对象部件)。

为了在多节点计算机上进行模拟，必须向多个节点分配代理。当属于一个节点的代理向另一个节点上的代理发送消息或者从其接收消息时，在节点之间便产生通信量。因为在节点之间传送的数据的数量影响到整个系统的性能，从而需要一种用于减少通信量的方法。

已知有几种常规的现有方法，例如减少通信路径的长度从而减少流过网络的数据量的方法，以及在节点间分配在分布环境下执行的应用程序以平衡通过这些节点的CPU和网络负载的方法。然而，这些方法中的任何一种方法都无法提供一种能够在代理间频繁相互通信的情况下、例如在使用数百万个代理执行模拟的环境中，以少量的计算来快速且适当地分配大量代理的方法。

[专利文献1]已公开的未审查专利申请No.2004-7578

发明内容

本发明便是为了解决上述的技术问题而作出的，本发明的目的在于：

-在计算机上快速而适当地分配代理，

-减少节点之间的通信量，

-减少节点之间的网络负载，以及

-向相同节点分配相互频繁通信的代理。

为实现上述目的，本发明提供一种用于在包括多个互连节点的计算机上分配代理的方法，每个节点具有CPU和存储器，所述方法包括：在每个节点内，存储在所述节点上驻留的代理和与该代理进行过通信的节点之间传送的数据的数量；为每个代理确定节点M，该节点M导致所传送的数据量在所述代理被传递到所述节点M时最大程度地减少；把所述代理添加到包含要被传递到所述节点M的候选代理的代理列表中；以及把代理列表上的代理传递到节点M。

在存储因与节点进行通信而传送的数据量的步骤中，根据在驻留于该节点上的代理和已经与该代理进行过通信的另一个代理之间传送的数据量来计算并存储在该代理和节点之间传送的数据量。

在确定节点M的步骤中，针对每个代理确定节点M，该节点M在该代理从当前节点传递到另一个节点时导致通信量最大程度地减少，减少量为在作为代理传递目的地的节点所传送的数据量减去在当前节点所传送的数据量。

在传递步骤中，在代理列表上按照通信量的减少量递减的顺序对代理排序，并从当前节点向节点M传递代理列表中较高顺序的预定数量的代理。

依据本发明，代理在多节点计算机上被适当地分配，以减少节点间的网络负载。由于节点间的通信量不断减少，可以灵活地解决代理间的通信量随时间而改变的情况。

附图说明

图1表示多个节点的示例性物理配置；

图2表示一个节点的示例性硬件配置；

图3表示在三维环面上的节点网络的示例性配置；

图4是在4个节点间执行通信的例子；

图5是代理管理程序的流程图；以及

图6表示在虚拟环境中的代理。

符号说明

120  多节点计算机

310  节点

410  节点

600  虚拟环境

610  代理

620  代理

具体实施方式

下面参照附图详细说明用于实现本发明的优选实施例。

本发明的节点一般包括两个芯片和一个存储器，如图2的110所示。一个芯片包括一个中央处理单元和两个浮点单元。存储器和两个芯片相连。两个芯片的作用如下：在某些情况下，一个芯片负责执行计算、另一个芯片执行通信，而在另一些情况下两个芯片都用于进行计算。多个节点的例举性物理配置如图1所示。图1的计算卡代表本发明中的节点。16个计算卡构成一个节点卡，32个节点卡构成一个机柜(Rack)，64个机柜构成一个多节点计算机120。这些节点通过快速网络互连，从而形成在三维环面上的网络，如图3所示。节点310对应于图1的计算卡。在本发明中不使用与三维环面上的节点之间的距离相关的信息。

代理是在节点上运行的对象部件，可从一个节点向另一个节点传递。图6表示使用多个代理的模拟概况。虚拟环境600被建立在多节点计算机12上。多个节点和大量代理一起执行复杂的物理或经济现象的模拟。代理610包括表示变量和数据的内部模型以及用于确定所述内部模型的部分(函数)。代理按照确定结果而行动。所述行动包括计算、存储、消息发送和接收。消息被发送到其它代理620、630或从其它代理620、630接收消息。

在依据本发明的方法中，每个代理记录与该代理通信的代理(节点)以及通信量。根据该信息，在所有节点间交换预定数量的代理。图4表示在4个节点间进行通信的例子。节点410和其它节点进行通信。节点之间的通信包括代理与节点之间的通信。在几百万个代理和节点之间将产生巨大的通信量。减少代理和节点之间的通信量将直接导致减少节点间的通信量。

管理如此大量的代理的传递的程序在每个节点上运行，并向另一个节点传递合适的代理。管理程序使用数量少于由大量代理使用的资源的数量的资源，简单且操作迅速，因此其对整个系统性能的影响是小的。管理程序的处理可以由专用硬件来实现。

图5表示代理管理程序的流程图。在步骤510，存储每个代理和节点之间的通信量。在步骤520，确定要向其传递代理的节点M。然后在步骤530，把该代理添加到要向节点M传递的候选代理列表中。最后在步骤540，向节点M发送代理列表中顺序较高的预定数量的代理。在每个节点上执行所述处理。应当注意，作为代理传递目的地的节点M不是一个特定的节点；代理可被传递给任何节点。

现在详细说明处理的流程。一组代理用A表示，一组节点用C表示，属于节点k∈C的一组代理用B_kA表示，在代理i和i’∈A之间传送的数据量用T(i，i’)表示。

在步骤510，获得在给定节点k上的每个代理和属于每个节点的代理之间传送的数据量S并将其存储在节点k上。

[公式1]

$S(i,B_{k^{\′}})=\underset{i^{\′}\∈B_{k^{\′}}}{\mathrm{\Σ}}T(i,i^{\′})$

在步骤520，如果代理i被传递到节点k∈C，则按照下式获得将被减少的传送数据量。

ΔR(i，B_k，B_k’)＝S(i，b_k)-S(i，b_k’)

应注意获得了使ΔR(i，B_k’，B_k)最大化的k_max。

[公式2]

$k_{\max }=\underset{k^{\′}}{\arg \max }\mathrm{\ΔR}(i,B_k,B_{k^{\′}})$

在步骤530，代理i被添加到要传递到节点k_max的候选代理组中：

[公式3]

${\mathrm{Bpool}}_{k{\→k}_{\max }}\⋐A$

在步骤540，以值ΔR(i，B_k，B_k’)递减的顺序对每个节点k’∈C从Bpool_k→_k’中选择一组预定数量的代理B_k→_k’，并将其发送到节点k’(对应于流程图中的节点M)。

通过以规则的时间间隔对每个节点执行上述处理，可以把代理重新分配给合适的节点。如可以由上述的流程图看出的，每个节点只存储由属于该节点的代理产生的通信量，并只检查属于该节点的代理以选择代理进行交换。因此，依据本发明的方法不需要在节点之间进行复杂的协商，并且能够以相当少量的计算来快速地执行操作。

Claims (6)

1.一种用于在包括多个互连节点的计算机上分配代理的方法，每个节点具有CPU和存储器，所述方法包括：

在每个节点内，

存储在所述节点上驻留的代理和与该代理进行过通信的节点之间传送的数据的数量；

为每个代理确定节点M，该节点M导致所传送的数据量在所述代理被传递到所述节点M时最大程度地减少；

把所述代理添加到包含要被传递到所述节点M的候选代理的代理列表中；以及

把代理列表上的代理传递到节点M。

2.如权利要求1所述的方法，其中在存储因与节点进行通信而传送的数据量的步骤中，根据在驻留于该节点上的代理和已经与该代理进行过通信的另一个代理之间传送的数据量来计算并存储在该代理和节点之间传送的数据量。

3.如权利要求1所述的方法，其中在确定节点M的步骤中，针对每个代理确定节点M，该节点M在该代理从当前节点传递到另一个节点时导致通信量最大程度地减少，减少量为在作为代理传递目的地的节点所传送的数据量减去在当前节点所传送的数据量。

4.如权利要求1所述的方法，其中在传递步骤中，在代理列表上按照通信量的减少量递减的顺序对代理排序，并从当前节点向节点M传递代理列表中较高顺序的预定数量的代理。

5.一种用于在包括多个互连节点的计算机上分配代理的设备，每个节点具有CPU和存储器，所述设备包括：

在每个节点内，

用于存储在所述节点上驻留的代理和与该代理进行过通信的节点之间传送的数据的数量的装置；

用于为每个代理确定节点M的装置，所述节点M导致所传递的数据量在所述代理被传递到节点M时最大程度地减少；

用于把所述代理添加到包含要被传递到所述节点M的候选代理的代理列表中的装置；以及

用于把代理列表上的代理传递到节点M的装置。

6.一种用于在包括多个互连节点的计算机上分配代理的程序，每个节点具有CPU和存储器，所述程序使所述计算机的每个节点执行以下步骤：

存储在所述节点上驻留的代理和与该代理进行过通信的节点之间传送的数据的数量；

为每个代理确定节点M，该节点M导致所传送的数据量在所述代理被传递到所述节点M时最大程度地减少；

把所述代理添加到包含要被传递到所述节点M的候选代理的代理列表中；以及

把代理列表上的代理传递到节点M。

Images