级别： 初级 James H. Kaufman (kaufman@almaden.ibm.com), OptimalGrid 研究员
Tobin J. Lehman (Toby) (toby@almaden.ibm.com), OptimalGrid 研究员
Glenn Deen (glenn@almaden.ibm.com), OptimalGrid 研究员
John Thomas (jthomas@cruzio.com), OptimalGrid 研究员
2004 年 3 月 04 日 在本文中，我们将介绍 OptimalGrid，它是 IBM Almaden Research Center 的网格研究员的研究原型。OptimalGrid 是旨在简化创建并管理大规模、已连接的并行网格应用程序的中间件。它优化性能并包括自动网格功能。您不必是网格基础结构专家就可以使用它。您提供表示基本问题算法的代码，而 OptimalGrid 便会管理其它的每件事情 ― 问题划分、问题块部署、运行时管理、并行性的动态级别、动态负载均衡甚至系统容错与恢复。OptimalGrid 系统被设计成使非网格基础结构专家的开发人员可以轻松获得网格计算的巨大潜能。
简介
网格计算是支持大量（通常是）不同种类的机器把一个问题分成几部分来处理的方法，最近，该领域已经引起了人们极大的兴趣。
为了充分利用网格计算的出现所带来的极大机会，网格的使用必须变得简单。
开发人员应该能够创建支持网格的并行应用程序，而他们自己无需成为网格或高性能计算方面的专家。
另外，网格应用程序（或者甚至更大型的网格系统）应该能够对它们本身及其使用的资源进行重新配置，
以响应网格环境中的动态变化。
早期的网格系统（如 CONDOR 或 SETI@home）提供了在数十、数百、数千或者甚至数百万台机器上远程执行程序块的功能。
虽然这为网格和分布式计算提供了极好的基础，但我们需要更多的功能。CONDOR 和 SETI@home 是支持独立并行问题的系统示例，
在这些系统中，可以独立计算每个问题块。这些系统缺乏管理关联的问题（问题块是相互有关系的）的能力。
它们既没有提供问题块的复杂管理、解决问题块之间的相关性、提供问题块需求的表示，也没有使问题本身适应可用的计算资源中的动态更改。
OptimalGrid 是简化网格上相连的并行应用程序的创建和管理的一种尝试。它不是工具箱；而是一个独立而完整的中间件，提供支持网格的协作框架和问题解决环境。
它是 Globus 所提供的 OGSI 基础结构和需要将已互连的问题分布在网格上的应用程序之间的一个层。OptimalGrid 将在几乎所有的网格基础结构上运行，而只要求在联网的机器上安装 Java 运行时。
其设计目的是优化性能，以充分利用现有的网格基础结构。
本文为对此感兴趣的普通读者提供了主要 OptimalGrid 组件的高级概述并描述了体系结构。
另一篇教程为想要了解如何使用 OptimalGrid 的开发人员提供了更详细的信息。
动机 — 隐藏复杂性
桌面和服务器机器的价格／技术曲线已经使计算循环变得丰富且便宜，
从而打开了通往实际的网格计算和用于计算设施和服务的各种模型的大门。
网格计算 ― 一种支持大量（通常是）不同种类的机器把一个问题分成几部分［1-4］来处理的方法 ― 将以先前无法想象的规模来提供低成本的计算资源。现在，
有大量的商业和科学的应用程序可供使用，这些应用程序要么需要大量的计算，要么需要大量的计算资源（如大量的内存或磁盘）。
在历史上，要创建大规模的相连的并行应用程序一直相当困难，因为那需要专门知识并有权使用昂贵的资源。
为网格创建这类应用程序增加了甚至更多的复杂性。今天，
使用网格来解决这些复杂问题要求应用程序开发人员知道他们想要用于部署的网格基础结构，
并要求他们设计可以适应网格环境的定制应用程序。
实现遍布网格的并行计算这一梦想不仅需要建立如 OGSA [12]（开放网格服务体系结构，Open Grid Services Architecture）之类的标准和如 Globus [1] 之类的工具，而且它还需要有效隐藏创建和部署真正并行的网格应用程序复杂性的中间件，从而使应用程序开发人员容易地构建和运行相连的并行问题。
使网格变得易于使用这项成就将给从制造设计到医学的各种领域带来一场革命。
到目前为止，使用计算网格处理的最简单的一类应用程序一直是过于“独立并行”（有时称为“尴尬并行”）的问题。
威斯康星-麦迪逊大学的 CONDOR 系统 [5] 是提供远程执行服务的首批系统之一，用于独立而完整的程序或用于并行程序块集。
SETI@home项目和
Folding@home
蛋白质折叠（protein folding）项目也是这类应用程序的示例。
这些应用程序以简单的“分散／聚集”方式工作，并且不需要参与计算的网格节点之间进行通信。
虽然这种问题很适合于网格的分布式计算功能，但要创建这类问题还是很容易的。
这种应用程序一般不需要也不使用自主功能，就能积极地管理并最有效地利用可用资源。
如故障节点或丢失数据集之类的问题通常只要通过重新运行计算就可以解决。
这些问题块之间连接的缺乏允许对故障做出这种简单响应，因为不影响正在其它节点上执行的计算。
更大且更一般的一类应用程序可被描述为“关联的并行”问题。这些问题包括有限元模型问题（而且其子集是单元自动操作问题，如 The Game of Life）[8]。
有限元模型（Finite Element Model，FEM）问题普遍存在于商业领域，可以通过一组众所周知的技术来解决。各种不同的专业领域都有 FEM 问题，这些领域包括物理学、金融系统、生命科学和复杂的仿真。
在这些应用程序种类中，单元或个别问题块被连接成相邻的邻居。为了计算单元的未来（下一个）状态或属性，有必要交流所有相邻（连接）单元的状态。
在本文中，我们介绍了 OptimalGrid，这是 IBM Almaden Research Center 的一个研究项目。
我们设计了 OptimalGrid 来简化网格环境中大规模已连接的并行应用程序的创建和管理。
为了简化这种已连接的并行应用程序在网格上的创建，我们将这个问题分为两个步骤。第一步涉及对应用程序和应用程序数据进行划分。
从概念上讲，大规模已连接的并行应用程序将不“适合”一台机器以及不能在一台机器上有效地运行。
必须对它进行划分，以利用多台机器。在许多情况下，这是最具有智力挑战的步骤。OptimalGrid 中间件在装入时完成的“自动问题构建”操作中隐藏了该步骤的复杂性。
如果有人将并行应用程序视为一个图，其上的节点包含数据、方法和指向邻居的指针，
那么问题就是要将该图划分成大小合适的块，以便在单个网格节点上运行。
该对象模型和问题划分的方法在
OptimalGrid 对象模型和问题划分方法中讨论。
部署网格应用程序中的第二步涉及在运行时管理应用程序。
要有效地使用网格环境，必须适应可用网格资源中的更改并对应用程序动态地进行负载均衡。
这需要实时诊断和应用程序性能度量以及向可以决定如何管理应用程序的协调程序提供反馈。请参阅
自主功能一节中的更多详细信息。
在
运行时优化中，我们简要地描述了 OptimalGrid 在解决连接问题时使用的运行时优化步骤。
OptimalGrid 对象模型和问题划分方法
首先，让我们讨论 OptimalGrid 对象模型和单元间通信。
OptimalGrid 对象模型
OptimalGrid
的目的是简化已连接的并行网格应用程序的创建。
它既不受限于科学工程领域，也不受限于空间问题的解决方案。
要理解 OptimalGrid 对象模型，考虑可以用有限元建模（Finite Element Modeling）来解决的一类问题会很有用。
对于离散元素已定义了与其邻居的连接关系的任何问题，都可以用这一技术解决。
例如，使用相互依赖的经济元素的金融模拟可以通过使用 FEM 方法进行构建。FEM 模型不局限于两维或三维。
通过将空间划分成“小型”有限区域或元素从数字上解决有限元模型（FEM）问题，
其中，“小型”一般由问题中最小的相关长度规模来定义。
图 1
演示了由一组离散节点建立的连续固体对象模型，每个节点都有特定属性。
根据所处理的问题，这些最小区域可能表示固体中的原子、晶体单位粒子或者只是颗粒。
图 1：将固体对象分解成有限元
要使 OptimalGrid 系统的方法直观化，考虑简单的两维问题是最容易的，
如
图 2所示。在该示例中，我们假设
最近的邻居连通性，以便每个元素都与其四个最近的邻居相连。
采用
周期边界条件，边元素也有四个邻居（有些位于问题图的远边缘）。
采用非周期边界条件，边元素有两个或三个邻居，这取决于它们的位置。
图 2：原始问题单元
我们将最小的问题块（在这种情况下是单个元素）定义为原始问题单元（Original problem Cell，OpC）。从理论上讲，OpC 代表
应用程序图上的节点，它包含数据、方法和指向其它 OpC 的指针。OptimalGrid 对象模型通过使用抽象的 OpC 来实现解决问题的代码。
用户实现一小组由 OpC 抽象类（OpC Abstract Class）定义或要求的方法。
这些方法描述单元与其邻居的连通性，并指定由该单元使用从相连邻居（自动）获得的本地数据和信息执行的计算。
一般情况下，单个 OpC 对象非常小，只需很少的内存和极小的计算能力就可执行。OptimalGrid 系统聚集了 OpC 的集合或组，这些 OpC 相互连接以形成
OpC 集合。
一旦创建了 OpC 集合，其大小对于问题的生命期就是固定的。
负载均衡是通过在网格节点之间交换 OpC 集合来完成的（每个节点一次处理一个或多个集合）。
我们选择使用这种体系结构，而不使用个别 OpC 级别的负载均衡，从而避免了无效和额外的记帐开销。
需要网格计算功能的问题通常有相当多的 OpC。
如果每个 OpC 都被个别跟踪和管理，那么优化由上千个节点（每个节点有百万个 OpC）构成的网格是不切实际的。
当然，对于特殊类型的问题，可以将 OpC 集合定义为只有一个 OpC 的集合。
定义：
图（map）是元素之间连接的描述。
问题划分这一步定义了 OpC 集合，以使负载均衡变得实际有效。
应用程序是以这样一种方式划分的：当稍后在节点之间交换 OpC 集合时，通信成本将不会任意增加。
一个或多个 OpC 集合定义被分配到计算节点的“问题块”。
包含一组 OpC 集合的问题块对象被定义为可变问题划分（Variable problem partition，Vpp）。
定义：
可变问题划分（或称为 Vpp）是一组被分配到网格节点的 OpC 集合。包含在 Vpp 中的 OpC 集合的数目是可变的。
单元间通信
如
图 3 所示，每个单元或 OpC 都可以与多个邻居通信。
因此，OpC 集合和 Vpp 也与邻居共享数据 ― 包括在远程机器上处理的邻居。
图 3. 单元间通信
如果 N 维单元问题有“关系密切的邻居”连通性，那么其中的 OpC 通常需要与维数为 N-1 的集合通信。
正如说明的那样，将 OpC 分组成大小永不改变的 OpC 集合。OpC 集合被依次动态地分配到 Vpp，以在公共的网格节点上执行。OpC 集合中的单元通过使用内存中（Java 对象引用）通信来彼此直接通信。OpC 集合边缘上的单元将通过使用内存中的通信来与邻近的 OpC 集合边缘通信（如果它们都在同一个计算节点上（如在同一个 Vpp 中））。
如果 OpC 集合不在同一个 Vpp 中，那么数据在现有网络的基础结构上进行通信。OptimalGrid 系统试图使解决问题时所需的网络通信量最小。
OptimalGrid 系统使用分布式白板模型，在该模型中，客户机有权访问一个或多个共享全局消息板，
这与使用多个点对点通信连接不同。这是 Tuplespace 通信系统的公共元素 [9] [10]。OptimalGrid 系统使用 TSpaces[11]，TSpaces 还提供了与 Tuplespace 通信系统耦合在一起的轻量级数据库系统。
图 4 中给出的示例是一个很一般的示例，所有节点只有一个白板。
如果所有节点都只使用了一个白板，那么系统的可伸缩性就相当有限。取而代之的是，使用一组分布式白板。
图 4. 基本的 TupleSpace 操作
白板节点至 Vpp 节点通信的最佳比率取决于要解决的实际问题。
必须考虑如在边缘和序列通信期间报告的数据量之类的因素。这是由 OptimalGrid 系统的另一个组件自动执行的配置步骤：问题构建器（problem Builder）。问题构建器在程序装入时运行（如果还未划分问题的话）。
它在最初将问题分配给网格上的节点时运行。问题构建器检查问题并确定解决问题所需的最佳网格节点数；
它在自我优化中扮演重要角色。
可以推测，应用程序数据可能太大了，将不适合单个机器的内存。OptimalGrid 根据下列过程对问题进行自动划分：
- 确定应用程序实例的复杂性（所有 OpC 的数目和大小）
- 确定可用网格节点的数目
- 使用基于已知 OptimalGrid 性能和缩放的算法来预测要使用的最佳网格节点数
- 可选地与用户进行交互，以选择步骤 3 中定义的最佳块数的划分，
或将问题划分成一些其它的块数目（在这种情况下，OptimalGrid 预测计算时间）。该步骤稍后会按照随需应变（on-demand）服务模型中的某个服务级协定来强制执行。
- 创建预定义空 OpC 集合间相关性的空间过滤器
- 过滤器（需要很少内存）被应用于应用程序数据（可能驻留在文件系统上），以连续生成 OpC 集合对象
- 用户可以在应用程序实例启动之前可选地应用 Vpp 数据初始化程序类来定制 OpC 的状态
- 程序启动
自主程序管理器
OptimalGrid 系统使用称为自主程序管理器（Autonomic program Manager，ApM）的组件。在运行时为分配到问题的网格节点之一指定 ApM 功能。
通过使用由 Vpp 生成的检测性能和诊断数据，ApM 充当应用程序协调程序来指挥和优化 Vpp。ApM 决定将 OpC 集合动态地分配给 Vpp。
分布式白板的使用使之易于实现，而无需增加大量代价较高的通信或数据管理开销。ApM 控制着 OptimalGrid 中的自主功能。ApM 设计的一个组成部分是添加
可插入策略模块的能力，
允许对问题引入特定的优化目标，如服务级协定（Service Level Agreement，SLA）目标、性能目标和恢复目标。ApM 不是网格协调程序。它不会试图管理物理网格。
将为每个应用程序实例创建一个 ApM 实例，它适应网格环境的变化，以优化可用于该特定应用程序实例的资源范围内的应用程序。
自主功能
使不同种类的分布式系统上复杂的关联的问题和谐地结合起来很困难，甚至连内行的管理员都无法管理。
因此，我们的系统要尽可能地自我复原和自我组织，这一点很重要。
为此，我们已经创建了具有许多检测块和一定知识量的系统，而且该系统具有维护平衡性能并对各种故障作出反应的规则。
随着时间的过去，在运行许多试验并与我们的客户沟通之后，我们希望大大地增加这方面的知识。
检测
启用自主功能要求度量系统性能并
反馈给 ApM。检测 OptimalGrid 系统以考虑到基于真实事件进行有效的管理。
这允许 OptimalGrid 根据预测的活动和实时产生的实际结果做出决定。
如
图 5所示，诊断和性能度量在轻量级
检测包装器（Instrumentation Wrapper）中进行传送，
该包装器可以封装作为网格应用程序正常执行的一部分传送的消息。
图 5. 提供运行时性能数据的 Vpp 检测
自我配置
当 OptimalGrid 系统对其自身进行初始化以解决问题时，它从网格检索可用计算节点的列表。
连同该列表一起，它还获得一组来自每个计算机节点的规格化性能度量。
可以从节点上的现有数据文件读取该信息，也可以通过运行节点上一组简单的自我测试生成该信息。
性能信息和可用节点数被传递到问题构建器，该构建器使用要解决的问题的特征知识，
计算了计算节点数的初始最佳分配和每个节点上 OpC 集合在 Vpp 中的分布。
最佳网格节点数未必就是可用的网格节点数。网格节点提供了计算能力和内存。
包含在单个网格节点上的所有 OpC 之间的通信都是在内存中执行的，且速度非常快。
当问题延伸到两个或两个以上的节点时，必须考虑额外的网络通信成本。
通过使用理解问题图的算法以及诸如计算功能、内存和网络等待时间之类的因素，
问题构建器创建了可用网格节点中最需要的网格节点的资源划分。问题构建器的目的是要设计将在现有网格基础结构中产生
最佳性能的
网格计划
和
问题计划。
自我优化
定义：计算问题中所有 OpC 值的一个轮回是一个
循环。
在一个循环结束时，每个 OpC 的值被传递到该 OpC 的所有邻居。Vpp（连接到远程网格节点）边缘上的 OpC 通过白板与其它 Vpp 上的 OpC 通信。
在许多应用程序中，计算一个循环的实际时间相当短 ― 几微秒。为了支持从故障节点的恢复，必须定期记录集合中所有 OpC 的值。
然而，在每个循环结束时做到这一点的通信成本（可能是每微秒）会对性能产生巨大的影响。
为了减少通信成本，在每个循环结束时只传递边缘 OpC 的值。
内部 OpC 的值在一组循环或一个序列结束时传递或
在日志中记录。考虑到为某个特定问题选择最佳长度，一个序列中的循环数是可配置的。
如呈现电影画面之类的问题需要在每次循环结束时编写所有 OpC，
因此，长度序列为 1 个循环。
其它问题（如计算一组相关的方程式，它们将最终为整个问题产生单值）只需要在足够短的时间间隔记录内部 OpC，
以顾及从故障节点快速恢复。
定义：
序列是可配置的循环数。在序列结束时，Vpp 中所有 OpC 的总状态（值）被写入白板。
配置序列长度的能力提供了以适合于不同应用程序的方法优化网络通信量及配置日志记录状态的能力。
在每次循环和每个序列结束时存储到白板上的数据，对于恢复功能很有用，如
自我复原一节中所讨论的那样。
计算和网络优化
OptimalGrid 中间件
从每个节点正在处理的特定 Vpp 方面提供了该节点的运行时性能度量。这些度量包括计算成本、通信成本和等待时间（通过白板所添加的时间戳记获得）。性能度量在轻量级检测包装器中被编码，
并且可以与应用程序所要求发送的任何消息一起传递。
例如，诊断度量包括在每个节点在每次循环结束时发送到白板的简单时钟元组中。白板在这里扮演另一个重要角色。因为可以读消息（与仅“接受”相反），所以白板上的消息对于多个组件是可视的并且甚至可以进行广播。
为了动态负载均衡，自主程序管理器（ApM）或问题协调程序可以通过检测包装器中的数据监控性能。
通过咨询可插入的规则引擎，ApM 可以在网格节点之间重新分配 Vpp 及在 Vpp 之间重新分配 OpC 集合等。
这些重新分配是根据计算性能和／或网络性能进行的。从理论上讲，要优化每个网格节点的使用，应该充分利用每个节点。
花在“等待消息”上的任何时间都应该用于 Vpp 核心内的计算，而且任何消息都应该正好在网格节点完成核心计算时到达。
在一系列执行（其间在 OpC 之间发生了一次或多次交互迭代）之后，OptimalGrid 系统评估每个计算节点的性能，然后通过重新指派 OpC 集合在 Vpp 中的分配来重新平衡被分配到每个计算节点的 Vpp 大小。
自我复原
OptimalGrid 系统使用的分布式白板使系统能够在一个序列期间出现一个或多个计算节点故障时进行自我复原。白板包含 OpC 边缘集合的历史值，
这些 OpC 边缘集合来自所有处理问题的 Vpp。
在一个序列期间丢失网格节点不会导致丢失已经由网格执行的完整计算。
相反，所丢失的是故障计算节点上的 Vpp 内的内部 OpC 的结果。
在检测计算节点的故障时，故障 Vpp 中的 OpC 集合被重新分配到现有 Vpp。
从最后一次成功序列结束时记录的最后一个 Vpp 状态开始，节点能够扮演“同步更新”并重新执行 Vpp 中的 OpC。
在这个同步更新阶段，该 Vpp 能够使用来自其邻居的先前报告和存储的边缘结果。
因此，在同步更新阶段只需重新计算故障 Vpp 中丢失的 OpC。
这是可行的，因为来自邻居的必需边缘是已知的，并且可以通过使用它们的数据库功能在白板上使用它们。
不可避免的是，根据问题的已连接性本质，其它计算节点在这个同步更新阶段必须保持空闲，但这种短暂延迟比从头开始重新启动问题解决方案更可取。这个延迟长度可通过改变序列持续时间来配置，以允许应用程序开发人员针对通信成本权衡故障恢复时间。
一旦重新计算了丢失的 OpC 集合，网格就再次准备继续处理整个问题。
运行时优化
当运行问题时，OptimalGrid 执行下列步骤：
-
第一个序列：当第一个序列中的循环完成时，Vpp 将其所包含的所有 OpC 写入其相关联的白板。Vpp 还将其性能检测结果写入白板。
现在，白板保存了这个用于所有 Vpp 的序列的最终结果。现在可以清除前一个序列中循环的边缘结果，
因为执行故障节点恢复时不再需要它们了。这样，就完成了第一个序列。
-
再优化问题：在序列结束时，自主程序管理器评估序列的结果。
然后，通过使用序列所遇到的实际性能结果，它将 OpC 集合重新分配到 Vpp。
将花更长时间才能完成分配任务的网格节点中的部分 OpC 集合从其 Vpp 中除去，
然后将它们分配给性能更好的节点。
然后，通知 Vpp 进行另一个循环／序列。
-
故障反应：
如果在循环结束时节点无法将其边缘 OpC 集合写入白板，那么 ApM 将通过“时钟”消息检测它。
对于何时采取行动来处理它，可能有不同的选项。丢失边缘的结果将在问题 OpC 之间传播，
就象每次循环时波纹从故障边缘移开一组 OpC 一样。
因此，在必须暂停整个系统以考虑到对丢失的 Vpp 作出反应之前，有可能继续处理许多循环。
在恢复捕捉阶段，由 ApM 处理 Vpp 的丢失。
-
获取结果：在执行了必需的序列数之后，问题是完成了。
数据结果驻留在白板上。该数据可以读取，也可以存储，以供用户检索。然后，系统将已分配的节点重新释放给网格。
状态和未来计划
位于圣何塞的 IBM Almaden Research Center
在继续积极地研究着 OptimalGrid 项目。未来发行版将包括开放网格服务体系结构（OGSA）和自动部署与配置工具的集成支持。
有关 OptimalGrid 使用的更详细信息，请参阅
教程。
结束语
OptimalGrid 系统的设计目的是为非网格基础结构专家的开发人员带来轻松进行网格计算的巨大潜能。通过将如自我配置、自我优化和自我复原这样的自主功能包括到 OptimalGrid 的核心体系结构，OptimalGrid
尝试交付一种能够处理真实连接的问题的健壮系统，以满足各类用户需求并提供高级别的可靠性。
参考资料
作者简介  | | | James H. Kaufman 是 IBM Almaden Research Center 分布式和群集系统部的一名专职研究成员。Kaufman 博士获得了康奈尔大学的物理学学士学位及 U.C.S.B. 的物理学博士学位，Kaufman 博士为 IBM 的好几个研究领域作出了贡献。
他是美国物理学会（American physical Society）会员。他目前的研究领域包括分布式计算（Distributed Computing）、模拟与建模（Simulation and Modeling）和网格中间件（Grid Middleware）。
您可以通过
kaufman@almaden.ibm.com 与 James Kaufman 联系。
|
| | | Tobin J. Lehman（Toby）于 1986 年加入 IBM Almaden Research Center，
在这之前，他刚获得威斯康星州麦迪逊大学的博士学位。Toby 的研究项目包括基于服务器的备份系统、对象-关系数据库系统、大对象管理、驻留内存的数据库系统、Tuplespace 系统和计算网格。Toby 目前正致力于一种自主的网格计算基础结构，
该基础结构用于解决不同种类的因特网机器集合上的非常大型的连接的问题。您可以通过
toby@almaden.ibm.com与 Toby Lehman 联系。
|
| | | Glenn Deen 是一名高级软件工程师，他是 IBM Almaden Research Center 的 OptimalGrid 研究团队的一名成员。
从 1989 年加入 IBM 以来，他参与了安全性体系结构和分布式计算。他目前参与的领域包括 XML 和网格计算。
可以通过
glenn@almaden.ibm.com与他联系。
|
| | | John Thomas 是 IBM 的一名 Java 开发人员。他先前是 IBM Almaden TSpaces 项目的主要程序员之一。他目前是 Almaden Research Center 的 OptimalGrid 项目的一名成员。
他住在 Santa Cruz 并在那里工作，可以通过
jthomas@cruzio.com与他联系。
|
对本文的评价
| 
