庆祝分布式计算多样性的发展成果

Celebrating Diversity in Volunteer Computing
庆祝分布式计算多样性的发展成果

January 20, 2009

作者：
David P. Anderson
University of California, Berkeley

Kevin Reed
IBM

< 资料来源：University of California, Berkeley >

本文讨论 BOINC 系统如何处理分布式计算中资源与任务的多样性。获得第42届夏威夷国际系统科学协商会最佳论文奖。

概要

志愿者提供计算资源的系统是高度多样化的，无论在软件和硬件的类型、速度、可用性、可靠性、网络连通性和其他性质上。同样的，将被执行的任务可能会随着志愿者们的硬件和完成任务所需时间的各异而大不相同。为了最大限度的提高系统性能，系统的任务选择策略必须同时适应这些多样性。在本文中我们针对 World Community Grid（由 IBM 主办的大型志愿者计算项目）和 BOINC （WCG 所基于的中间件系统）来对计算资源的多样性进行讨论。然后我们讨论在 BOINC 调度程序中有效地把不同任务匹配给不同主机的技术。

介绍

志愿者计算是一种分布式计算，它是让一般市民志愿者参与并提供计算和存储资源的计算项目。BOINC 是一个为志愿者计算的软件平台。BOINC 正被各种项目所应用，如物理、分子生物学、医学、化学、天文学、气候动力学、数学和各种游戏的研究。目前已有50个项目和580000位志愿者的计算机提供着平均 1.2 PetaFLOPS 的计算能力。

相对于其他类型的高性能计算，志愿者计算有着高度的多样性。志愿者的计算机在软件和硬件的类型、速度、可用性、可靠性和网络连通性上有着很大的不同。同样的，计算程序和任务在资源要求和时间限制上也是有很大差异。

这些多样性给 BOINC 提出了很多的要求。其中最重要的是任务选择问题：当一个客户端连接到 BOINC 的调度服务器，这时服务器必须根据一套复杂的标准机制，从数据库中可能多达百万的任务里面做出选择，把对于该客户端“最佳”的任务挑选出来。而且，服务器必须在每秒钟应付数以百计这类请求。

在本文中，我们以 IBM 主办的 World Community Grid（基于BOINC的大型志愿者计算项目）为背景来讨论这个问题。第2节介绍 BOINC 的架构。第3节概述了参与 World Community Grid 的志愿者的计算机以及所支持的应用。第4节我们讨论使用 BOINC 调度服务器处理差异任务和不同主机的技术。这项工作获得了自然科学基金会授予奖项：OCI-0721124

BOINC 的模型与结构

BOINC 的模型包含项目方与志愿者。项目方是需要计算资源的组织（通常是学术机构）。各个项目是独立的，他们各自运营自己的 BOINC 服务器。

志愿者通过在自己计算机（主机）上运行 BOINC 客户端软件参与到项目。志愿者可以对每个主机添加任何一个项目。并可以对每个项目制定资源配额。

一个 BOINC 服务器是与之相关的数据库的中心，并相应于以下抽象 BOINC 计算模型：

平台：一个运行环境，通常是操作系统和处理器类型的类型结合（Windows/x86），或者是虚拟环境（VMWare/x86 或 Java）。
应用程序：抽象的计算程序，独立于平台或版本。
应用程序版本：一个可执行程序。与应用程序，平台，版本号，和一个或多个文件（主程序，库，数据）相关的。
任务：一个需要完成的计算工作。与应用程序（不是应用程序版本或者平台）和一组输入文件相关的。
任务实例：任务在特定主机上的执行。每个任务实例与应用程序版本（选择任务时发出）和一组输出文件相关的。

志愿者返回的计算结果并非总是正确的，由于硬件故障（特别是在超频使用的计算机上）或是恶意志愿者试图破坏项目或为了获得积分而不进行实际运算。这样，结果验证通常是需要的。

BOINC 支持多种结果验证技术，最基本的就是冗余计算，在这种情况下会把任务实例发送给两个不同的主机。如果结果一致，它们就被认为是正确的。否则会进一步发送任务实例到其他主机，到获得一致的结果，或者达到实例的数量限制。

World Community Grid 上的主机与应用的多样性

World Community Grid 是由 IBM 公司主办的大型志愿者计算项目，目前已有超过390000名志愿者参与。自2004年11月项目开始以来，他们贡献了超过167000年的计算时间。目前从全部志愿者的计算机上平均提供着 170 TeraFLOPS 的计算能力。

参与到 World Community Grid 的计算机在处理器、操作系统、内存、硬盘、网络带宽、可用性、错误率和周转时间都有着很大差异。图表1显示了这些差异的分布。

在本文撰写之时，World Community Grid 有6个正在运行的子项目，它们都对硬盘空间、计算能力、内存和带宽有着不同的要求。图表2显示这些差异。

根据各个应用的特性使用了不同的结果验证技术。

The Human Proteome Folding 和 Nutritious Rice 应用不使用冗余验算。因为结果在统计分布上是预先确定的，无效结果会显示为离群值。为了检验结果副本，每个任务都包含一个微小的独特的计算，并可以在服务器进行检查。

Help Conquer Cancer，FightAIDS@Home 和 Discovering Dengue Drugs 应用则使用冗余计算。

BOINC 的任务选择

当 BOINC 客户端加入到一个项目，它将周期性的发送调度请求到项目服务器。请求的信息中包括了对主机和它的当前工作量（处于队列中的和正在计算中的任务）的描述，报告最近完成的任务并请求新的任务。回复的信息中可能包含了一组新的任务。为了减少调度请求的频率和适应长时间离线的主机，服务器可能会发送多个任务给客户端。

BOINC 项目的数据库可能包含数以百万计的任务，其服务器可能每秒需要处理几十或几百个调度请求。理想情况下，对于一个（给定的）任务请求我们希望能扫描整个任务列表并根据标准（将会在后文讨论）发送针对该主机“最佳”的任务。而在现实中这是不可行的，数据库的开销将高得惊人。

取而代之的，BOINC 使用了以下的架构：

在分配的共享内存部分维持一个大体有1000个任务的缓冲区。
通过一个可从数据库中提取任务的“供给器”程序，来对这个缓冲区周期性的进行补充。
调度器以 Apache CGI 程序运行，在给定的时间可能有数十或者数百个实例运行着，每个实例都在缓冲区扫描所有任务并确定最佳一个。

这个设计提供了很高的性能，服务器能在每秒发送数百个任务[1]。它还提供必要的多样性支持：如果任务缓冲区足够的大，它将很可能会包含一个更加适合于给定客户端的任务。

这个“基准”任务选择策略是：

从一个随机点开始，对任务缓冲区进行扫描，针对每个任务做可行性检查。这个过程并不需要访问数据库。例如：检查主机是否有足够的内存与硬盘空间，和它是否能在限期内完成这个任务。
如果某个任务通过了这些检查，那么锁定它，然后进行需要访问数据库的检查。例如：该任务的其他任意一个实例都没有被发送给属于这个志愿者的任何一台主机。
继续扫描直到有足够的任务被选择以满足主机的工作请求。本节的剩余部分，我们将描述如何改进这一基准策略以处理不同类型的多样性。

多平台结构

在早期版本的 BOINC，一个客户端对应一个单一的平台。客户端在调度请求信息中报告这个平台，然后调度器会发送给它基于该平台的应用程序版本。

当基于Intel处理器的苹果电脑发布之后，这个模型就崩坏了，这种计算机能够通过模拟来执行 PowerPC 二进制文件。这种主机应该宣称自己（的平台）是Intel/Mac麽？如果是这样的话那么这种主机将无法从只有 PowerPC/Mac 可执行文件的项目那里得到任何任务。同样，Linux/x64 和 Windows/x64 的主机通常也能执行 Linux/x86 和 Windows/x86 二进制文件，以及一些基于 BSD 的系统能运行 Linux 二进制文件。

为了应付这些情况，我们允许主机支持多种平台；BOINC 客户端会在开始运行时对主机进行检测，并生成一个信息列表。调度请求信息里包含了一个平台列表。这个列表按平台的预期执行速度来降序排列，然后调度服务器将发送对应这个被认为是最快的平台的应用程序。

协处理器和多核处理器

最初的 BOINC 是假定一个程序运行于一个 CPU。在多处理器下，客户端会为每个 CPU 运行一个程序。最近，BOINC 已扩展到使程序运行于多个处理器或使用如图形处理器（GPUs）和 Cell 处理器的SPEs协处理器中。

这对任务挑选引入了新的挑战：如果对于一个给定的平台，一个应用程序有多个不同的变体（版本），那么该把哪个版本发送给这一特定主机呢？这项决定可能需要特定的应用程序的信息，比如一个并行程序的加速比随 CPU 个数变化而变化的函数。

BOINC 会如下处理：一个项目对于一个特定的平台可能有多个程序版本（如一个单线程版本，一个多线程版本，和GPUs版本）。每个版本会标记为一个“计划类别”。

BOINC 客户端已经扩展到可以检查是否存在特定的协处理器（如支持 CUDA 的 GPUs[8]），并在调度请求中报告这些信息。

调度程序同项目提供的程序计划函数相连。计划类别和主机的描述，包括CPU和协处理器的信息，会被传递给这个函数。它将返回给定类别的应用程序在这台主机上所能达到的预期 FLOPS，所要使用的 CPU 的平均数目，所要使用的协处理器。对于给定的任务，调度器会检查所有可用的程序版本，并使用其中预期性能最高的一个。

调度器回复包含了每个程序版本的资源使用情况，在调度应用程序的时候会顾及这些信息（例如，它不会尝试在只有一个可用的GPU时同时运行两个都需要使用GPU的程序）。

志愿者对程序的选择

一个项目会有多个程序。默认情况下任务的分配不会考虑他们的程序。然而，有多个机制可以限制或控制任务在程序上的分配。

首先，项目可以根据程序间给定的比率对任务进行分配。例如，每发送10个任务，6个会分配到程序1，4个会分配到程序2。这是通过供给器执行的，它对不同的程序分别进行数据库列举，并根据比率在缓存中穿插任务。

其次，项目可以允许志愿者来选择特定的应用程序，然后他们将只会收到适于这些应用程序的任务（志愿者也可选中如下选项：如果他们所选中的应用程序此时没有任务了，那么他们将允许接收其他任何应用程序的任务）。

最后，程序可能被指定为“Beta 测试”，志愿者可以选择“Beta 测试人员”选项。当 Beta 测试工作可用时，测试人员将会收到测试任务。

数值差异的处理

在第2节所述的验证机制要求有决定两个结果是否相同的能力。这可能是困难的，因为在不同主机之间有数值变化；不同的处理器类型、编译器输出和数学库都能引起数值上的差异。

如果一个程序的数值是稳定的，通常能够作出一个“模糊对比”。然而对于不稳定的程序（如模拟混沌系统）这是不可能的，因为一些小的的偏差就会导致结果有很大的差别。

为了解决这个问题，BOINC 提供了一种称为同质冗余(HR)[6]的机制。一个项目可以定义一个或多个HR类型。各个HR类型由一组具有等价关系的主机组成，这关系基于主机的操作系统和处理器，并被一个可自行定制的函数（BOINC提供了一些默认的HR类型，不过项目能够自行定义）来进行计算。

程序可以关联一个HR类型；在这个HR类型中被认定是等价的多个主机来说，程序被假定为能够计算出完全相同的结果。

当一个任务实例发送到主机，调度器只会把任务的其他副本发送给在HR类型上（与第一台主机）等价的其他主机。在这种情况下，这个任务称为是被该HR级别所托管。

在此会引入一个问题：任务缓冲区可能被那些已经被特定的HR等级所托管的任务所填满。当属于其他HR等级的主机请求工作的时候，将无法得到可用的任务。我们解决这个问题如下：

通过一个“普查”程序从数据库中周期性列举所有主机，并建立一个表，对于每一个HR类型，给出该类型主机的近期平均积分。
对于每个HR级别，在任务缓冲区有确定数量（N）个槽位的任务对应于这个级别；N是跟该等级的近期平均积分成正比的，并至少为1.
在任务缓冲区有一小部分槽位是预留给未托管的任务。当供给器要从数据库中列举J任务，它必须检查J的HR级别的任务配额是否已满，如果已满将不添加J任务到缓冲区。

任务大小的制定

主机的运算能力是由它的处理器速度和可用性决定的；如第3节所示，在 World Community Grid 中，它有着两个数量级的变化。

在许多程序中，任务大小（如每个任务需要的 FLOPS）是可以任意设置的。那么项目应如何设置任务大小？如果任务太大，缓慢的主机将无法在限期内完成任务；如果任务太小，服务器将可能超出负荷。

最理想的，我们希望能够在调度请求中选择一个特定的间隔T（比方说，1天），然后向每个主机发送一个任务，并且主机能在T时间完成。实现这一目标的要求是：

项目必须生成适当大小的任务。
BOINC 调度器必须考虑到任务大小。

（我们）可以通过用普查程序（参4.4节）计算主机运算能力的平均值与标准差来达成第二个目标。供给器读取这些信息并将它存储于共享内存段中。供给器同时还周期性的对当前共享内存中的任务大小进行平均值和标准差计算。

给定主机的运算能力对于平均值有X标准差，调度器会试图发送对于平均任务大小有X标准差的任务。

自适应的冗余计算

如第3节h)图表所示，不同主机有着不同的错误率，大多数主机有接近零的错误率。虽然对于建立主机的可信度，冗余计算是必要的，但会变得低效。

BOINC 提供自适应的冗余计算选项，调度程序对每个主机维持着一个动态的错误率E(H)。如果E(H)是大于恒值K，那么对于这个主机的所有任务都是需要冗余计算的。如果E(H)<K，那么对H的任务做随机的冗余计算，当E(H)接近0时冗余计算的可能也趋于0。 E(H)的初始估计值将会充分的大，因此新的主机在获得无需冗余计算的资格之前，必须正确完成一定数量的任务。

这项策略并不能排除结果错误的可能性，但适当的参数可以使错误降低到一个可接受的水平，同时减少了冗余计算的开销。

快速完成重试

如果任务实例超时或无效，一个额外的“重试”实例会被生成。只有当重试完成之后，其他实例才能获得积分，并在之后从服务器删除任务文件。只有快速的完成了重试，才是令人满意的（否则其他实例无法得到分数，任务文件无法删除...）。

为了达到这样的目标/要求(指能够快速的完成)，BOINC 会标记出那些有着快速返回有效计算结果的历史的主机。重试（的副本）将会优先发送给这些主机。因为这些主机被认为是能够快速的返回结果。（此外重试的）任务实例的（截止）期限也会被缩减，这是为了确保重试工作能够被优先处理并快速返回。

基于计分的调度

在前面所述，我们根据主机类型的不同和任务的多样性，对任务分配列出了若干数量的标准。那么如何把这些标准结合到一个单独的任务策略中？

这里用到了一个计分函数S(J,H)。任务分配策略实际上是发送给（主机）H那些能够让（函数）S(J,H)取得最大值的被缓存的（任务）J。默认的计分函数是以下项的线性组合：

H可用的最快程序版本的预期 FLOPS（尝试对可用的快速程序发送任务）
如果志愿者选择了J任务的计算程序，返回1，否则0（尝试对志愿者选择的程序发送任务）。
如果J是已经托管给H所属的同质冗余级别，返回1，否则0（尝试优先完成已被托管的任务而不是生成新的）。
- (A-B)^2，其中A是任务大小，B是主机的速度，用标准差单位表示（参见4.5节）
J的硬盘和内存需求（避免对拥有大量资源的主机发送资源需求量小的任务）。
如果我们决定发送一个无需冗余计算的任务给（主机）H，或（任务）J没有其他副本，返回1，否则0。

项目方可以调整这些项的权重，或者替换掉整个计分函数。

特定任务

有些项目可能需要 BOINC 并不知道的信息来做出调度决定。例如，客户端是否已经安装了一个特定的软件包。

为了处理这样的情况，BOINC 允许项目提供“探测任务”，这个任务将在项目所拥有的主机上运行且仅运行一次。任务的输出资料（通常是一个 XML 文件）会保存在数据库的主机记录中，并可以作为项目自定义的积分函数中的参考（量）。（4.8节）

主机处罚机制

有些主机由于多种原因，他们尝试运行的所有任务实例都即时错误了。这些主机在几分钟之内经历了从服务器申请任务实例，遭遇错误，然后向服务器告知自己的错误的过程，并陷入了这样过程的循环。这将使一台主机因为重复的获取新任务和上报错误，而导致在短期内下载极大量的数据。

BOINC 处理这一问题是通过允许项目方对特定的主机设置每日可下载任务实例数量的极限（极限是根据主机可用的处理器个数来确定）如果主机在一天内达到它的极限，那么它直到第二天才能下载到新的任务。此外，如果主机报告一个错误的任务实例，那么它的每日极限会减少一个。因此，如果一个主机一直都只有错误那么它的最终极限就是一天一个任务。一旦该主机的问题修复了，它开始返回正确的任务实例结果，当成功的结果返回，那么它的任务极限将双倍提升直到达到项目的极限限制。

匿名平台机制

此时，我们已经假定项目提供了可执行文件给志愿者。项目如果提供程序的源代码（例如，他们是开源的）了呢？那么志愿者可以自行编译计算程序。以下几个原因可能导致志愿者会这么做：

他们的计算机平台并不被项目所支持。
由于安全原因，他们只运行有他们安全审核并亲自从源代码汇编出来的程序。
为了增加效能，他们希望用特定的编译器或编译器选项进行编译。
为了增加效能，他们希望修改程序（他们可能做的并不正确，但这会被 BOINC 的冗余机制发现）。

BOINC 通过它的匿名平台机制支持用户编译的程序。基本思想是客户端的调度请求不去指定平台，而以提供该主机当前的应用程序列表来取而代之。服务器将发送可以使用这些应用程序版本的任务。（但不会发送新版本的官方程序）

要使用这个机制，志愿者必须创建一个XML文件来描述可用程序版本，并存放在 BOINC 目录层次下的特定地方。

结论

我们已经描述了匹配不同任务和不同主机所遇到的困难，并说明了 BOINC 如何解决这个问题。

这些机制正在运作于 World Community Grid 和其他 BOINC项目上，他们似乎工作良好。然而我们目前无法量化它们工作的究竟有多好。想要在大型的志愿者计算项目中进行有控对照试验是非常困难的。因为有许多因素是无法控制的，而且拙劣的机制会浪费大量资源，甚至造成志愿者流失。

为了弥补这种情况，我们目前正在开发一个模拟器，使我们能够研究服务器策略。模拟器对主机和志愿者群体使用轨迹驱动（注：所谓轨迹驱动是指利用实际测量事件的时间点来驱动计算机仿真系统）或统计模型，包括了诸如主机流失、可用性和可靠性。服务器部分使用现行 BOINC 的代码，使用模拟时间而不是真实时间进行改写以达到最大的保真度。

在这里描述到的某些机制正处于早期开发阶段。例如在同时具有支持多CPU和协处理器版本的程序的情况下，将发送在独立上运行最快的那个程序版本。（注：比如协处理器版本的计算程序比CPU版本的计算程序要快，那么将会发送前者，不发送后者）。。这并不一定是最佳——可能更好的是发送一个CPU任务和一个 GPU任务（因为他们可以同时执行），而不是两个GPU任务。

参考文献

[1] Anderson, D.P., E. Korpela, and R. Walton. High-Performance Task Distribution for Volunteer Computing. First IEEE International Conference on e-Science and Grid Technologies. 5-8 December 2005, Melbourne

[2] Anderson, D.P. “BOINC: A System for Public-Resource Computing and Storage”. 5th IEEE/ACM International Workshop on Grid Computing, pp. 365-372, Nov. 8 2004, Pittsburgh, PA.

[3] F. Cappello, S. Djilali, G. Fedak, T. Herault, F. Magniette, V. Neri and O. Lodygensky. Computing on Large Scale Distributed Systems: XtremWeb Architecture, Programming Models, Security, Tests and Convergence with Grid. FGCS Future Generation Computer Science, 2004.

[4] A. Chien, B. Calder, S. Elbert, and K. Bhatia. Entropia: architecture and performance of an enterprise desktop grid system. J. Parallel Distrib. Comput. 63(2003) 597-610.

[5] S.M. Larson, C.D. Snow, M. Shirts and V.S. Pande. “Folding@Home and Genome@Home: Using distributed computing to tackle previously intractible problems in computational biology”. Computational Genomics, Horizon Press, 2002.

[6] Taufer, M., D. Anderson, P. Cicotti, C.L. Brooks III. “Homogeneous Redundancy: a Technique to Ensure Integrity of Molecular Simulation Results Using Public Computing”. Heterogeneous Computing Workshop, International Parallel and Distributed Processing Symposium 2005, Denver, CO, April 4-8, 2005.

[7] Sarmenta, L.F.G. and S. Hirano. “Bayanihan: Building and Studying Web-Based Volunteer Computing Systems Using Java”. Future Generation Computer Systems, 15(5/6), 1999.

[8] Schatz, M.C., Trapnell, C., Delcher, A.L., Varshney, A. (2007). High-throughput sequence alignment using Graphics Processing Units. BMC Bioinformatics 8:474.

[9] Raman, R, M. Livny, and M. Solomon, Matchmaking: Distributed Resource Management for High Throughput Computing, IEEE HPDC'98, pp. 140-147, July 1998.