冬日取暖最佳方式 — 利用闲置的计算资源

最近突发奇想,想到自己有几台电脑,性能都不错但是经常闲置,包括实验室的服务器也不是每时每刻都在充分利用资源,因此完全可以跑一些别的程序来利用。我最先想到的就是以前做电脑压力测试的 Prime95 程序,然后一搜发现这里面还是有不少门道的。本文介绍一下如何利用你家电脑闲置的性能,将其贡献给科学事业,并且在冬天的夜晚让它的散热成为一大取暖来源~哈哈哈哈

GIMPS

我最先测试的程序是 Prime95,Prime95 是梅森素数搜索计划(Great Internet Mersenne Prime Search, GIMPS)的 Windows 客户端。这个计划旨在利用互联网的计算资源来寻找梅森素数。形如 $2^p-1$($p$ 为素数)的数被称为梅森数,如果这个梅森数也是素数那么就被称为梅森素数。梅森素数是目前寻找大素数最高效的目标,人类发现最大的质数前几名都来自于 GIMPS 发现的梅森素数。

如果你不想知道很多信息,只想直接开冲,那么你只需要从 GIMPS 官网下载 Prime95(Windows)/mprime(Linux),解压后双击直接开跑就可以了。如果你希望了解这个程序具体在干什么,或者想青史留名找到新的梅森素数,那么请接着往下读这一节~

PrimeNet

首先需要介绍一下 GIMPS 的分布式计算网络,名字叫 PrimeNet。PrimeNet 负责分发计算任务和收集计算结果。由于梅森素数的形式是 $2^p-1$,因此 PrimeNet 中把 $p$ 称为 Exponent(指数),验证每个指数对应的梅森数是否为素数是独立的。目前 PrimeNet 中对于每个指数有如下几种计算任务,括号内为 PrimeNet 中的缩写:

  • Trial Factor (TF): 暴力遍历素数,测试每个素数是否是当前梅森数的因数。
  • P-1 Test (PM1): Pollard $p-1$ 测试法,可以在一定范围内寻找到一个因数 $q$,前提是 $q-1$ 是高度复合的(也被称为 smooth,意思是由很多很多小的质因数合成的合数)
  • P+1 Test (PP1): Williams $p+1$ 测试法,跟 P-1 测试类似,但是寻找的因数 $q$ 需满足 $q+1$ 高度复合。
  • Lucas-Lehmer Test (LL): 一种验证梅森数是否为质数的算法,该算法虽然很简单,但是非常耗时。
  • Double Check (D): 由于计算机在运算过程中可能会非常罕见地产生差错(这也是为什么人们需要 ECC 内存),因此为了确保素性判断正确,PrimeNet 会让另外一台计算机重新计算 Lucas-Lehmer,但是使用不同的初始参数,以验证计算的正确性。
  • Probable Prime Test (PRP): 这个测试也是一种 Lucas-Lehmer 测试,但是使用了一种改进的验证方法。该算法会在测试过程中生成一个无法仿造的证明文件,这个证明文件可以由另一台计算机很快验证,大大减少了运算量。
  • Proof Verification (CERT): 即验证 PRP 生成的证明的任务

除了这些任务之外,PrimeNet 还衍生出了因数分解的任务,即尝试对质数验证失败的梅森数进行完整因数分解,在这个过程中也有可能发现非常大的质数,被称为 co-factor。因数分解任务有如下两种:

  • Elliptic Curve Factorization (ECM): 利用椭圆曲线分解法进行因数分解,可以寻找一定范围以内的因数
  • Probable Prime Cofactor Test (PRP-CF): 对于梅森数除去找到的因数还剩下的因数进行素性测试,这个剩下的数通常仍然非常大,因为因数分解的方法通常只能找到几十位的因数,再大的因数实在太难计算了。
    目前 PrimeNet 中因数分解的任务只分配给指数为四千万以下的梅森数。另外,以上这些任务只是大类,实际上 PrimeNet 中的任务划分更细一点,比如 TF 会分为普通 TF 和 TF-LMH,后者优先选择 TF 进展比较小的指数进行分解。

PrimeNet 中目前验证一个梅森数的完整流程大概如下:

1
TF 2~2^63 -> TF 2^63 ~ 2^64 -> ... -> TF到2^78左右 -> PM1 -> PRP

将验证分为这么多步的原因主要还是为了减少计算量,TF 和 PM1 在测试小因数的时候比较快,而 Lucas-Lehmer 虽然可以直接测试梅森数的素性,但是用 TF 和 PM1 粗筛可以大大减少计算量。这里 TF 计算的上限和 PM1 测试的范围都是 PrimeNet 根据找到因数的概率和计算耗时之间权衡之后算出来的。

在早期 PRP 证明的算法还没有出现的时候(2020 年以前),完整流程实际上是 TF -> PM1 -> LL -> DC,因此目前 PrimeNet 还有大量积攒的 LL 测试没有被双重验证果,因此目前发现的梅森素数 M74207281、M77232917、M82589933 的顺位还没有被确定。

PrimeNet 的整体进展可以在 GIMPS 官网的任务分配表中中查看,这个表中展示了每一个范围中指数的状态。

最右边的一大列 Available 指的是还没有被认领的任务,右边第二列 Assigned 指的是已被认领的任务,左边 Composite 里面 F 指的是找到因数的梅森数、DC 指的是验证过的 LL/PRP 测试为合数的梅森数,右边 Status Unproven 中 LL/PRP 这一列指的是 LL 测试还没有被验证的指数,ERR 指的是 LL 计算中出现错误的,而 NO-LL 则是完成了 P-1 测试后还没有经过 LL/PRP 测试的指数。

客户端

在了解了计算任务的种类之后,接下来就是选择下载合适的客户端了。GIMPS 除了官方的 Prime95 之外还有不少第三方实现的客户端。如果你想用 CPU 跑的话,直接使用官方的 Prime95/mprime 客户端即可;如果你的电脑有 GPU,那么你可以选择 GPU 客户端,比较常用的有 mfaktc (NVIDIA) /mfakto (AMD) /gpuowl (通用)。我主要使用的是 gpuowl,因为它的代码最近仍然有更新,编译方便,并且支持 P-1 和 PRP 测试,而 mfaktc 和 mfakto 只能进行 TF。不过 gpuowl 在 windows 上不太好编译。

在使用客户端之前,首先可以在 GIMPS 官网上注册一个账户,这个账户即你在 PrimeNet 中的账户,在使用客户端的时候把用户名提供给客户端,这样可以让 PrimeNet 统计你的贡献。PrimeNet 的贡献统计以 GHz-days(GHD)为单位,每个任务的 GHD 数值通过一定的公式进行估算的,并不是直接统计你的 CPU 频率乘上你所花费的时间。据我的经验,如果你想拥有最高的 GHD/day,使用 CPU 的话比较划算的是 TF 任务,而使用 GPU 的话比较划算的 PRP 任务。

另外注册账户之后,你还可以选择一个 Team 加入,这样你的贡献值同样会被计算到 Team 中。目前我加入的 GIMPSChina 团队近年的贡献量排名第三,可喜可贺!

关于客户端的使用上,各个客户端基本都是解压之后即可使用,或者编译后使用。使用 Prime95 客户端的话程序会自动下载新的计算任务,你只需要设置 CPU 和内存的占用情况即可。如果你要跑 TF/DC/PRP 任务,那么只需要设置线程数即可,如果要跑 PM1,那么需要设置内存上限至少为 1G,并且越高越好。内存的设置在菜单里 Resource Limit 一栏的 Advanced 项目里面。而用 gpuowl 的话需要手动申请任务,在 Github 主页上有说明具体的使用方法。注意新的 PrimeNet 账户在一段时间(两三天)内是没法提交手动申请任务的结果的,需要管理员审核后才能提交,原因是之前有人恶意提交错误结果,具体情况参见这个 GIMPS 论坛的帖子

其他素数寻找项目

GIMPS 是最早的互联网寻找素数的项目,后来受 GIMPS 的影响产生了很多新的项目,例如 SRBaseGPU72 以及 PrimeGrid。SRBase 旨在寻找形如 $k*b^n\pm 1$ 的素数,其中 $k$ 为偶数,$b$ 为基;GPU72 旨在利用 GPU 扩大梅森数的分解范围(提高到 10 亿,PrimeNet 目前只搜索到 1 亿);PrimeGrid 则是一系列质数寻找项目的集合。这些项目之间通常会相互分享因数分解的结果。另外,在 PrimePages 网站上有统计目前已知的各个形式的最大质数,在 Mersenne.ca 网站上有更详细的梅森数计算结果统计。

BOINC

除了 GIMPS 之外另一个更广为人知的志愿科学计算项目则是伯克利的 Berkeley Open Infrastructure for Network Computing (BOINC)。这一项目给科学计算提供了统一的计算分发框架,里面有不少大型合作项目,涵盖数学、物理、天文、生物等多方面。

使用教程

参与 BOINC 的计算就更加简单了,首先你需要安装一个 BOINC 客户端,在官网上可以下载到。在安装完成之后,只需要在项目列表里面选择自己喜欢的项目即可参加。通常每个项目都有自己的网站,并且你需要在网站上注册账号,以便于该项目追踪你的贡献,这个步骤在你选择想参加的项目之后会提示你进行操作。参加项目之后,BOINC 便会开始自动分配你可以参加的项目。

BOINC 客户端同样支持资源占用的限制,并且支持在电脑有操作的时候暂停计算任务,更加便于你利用电脑的空闲时间进行计算了。BOINC 相关项目的贡献,除了每个网站自己的统计外,还可以在第三方网站(如 Free-DCBOINCStats)上查到。

GridCoin

另外 BOINC 还有一个很吸引人的地方是,有一款加密货币叫 GridCoin 是专门设计用来回报 BOINC 参与者的。因此如果你参加了 GridCoin 的计算池,那么你为科学事业贡献的算力实际上也是在挖矿!算力和电力的无用消耗是我不喜欢加密货币,尤其是比特币的最大原因,而设计在 BOINC 之上的 GridCoin 则完美解决了这个问题,并且 GridCoin 基于 Proof of Stake,而不是现在比特币和以太坊使用的 Proof of Work,更加降低了额外的计算资源消耗。因此如果你愿意参与 BOINC 的话,可以考虑同时利用 GridCoin 来回馈自己。

在使用方法上,如果你是首次参加 GridCoin,那么你需要利用 GridCoin 的计算池来进行挖矿,这个模式被称为 Pool Crunching,除了安装 BOINC 之外你还需要在 BOINC 客户端中选择 GridCoin 支持的项目管理器(我选择的是 grcpool),这样你的计算贡献会被归到 GridCoin 计算池的名下,而这个计算池会根据你的贡献分配 GridCoin。当你有了 GridCoin 之后你也可以选择独立进行计算而不依赖于计算池,这个被称为 Solo Crunching,这个情况下你的计算贡献也会直接被各个项目统计到。具体的使用方法还请参考 GridCoin 官网


在了解这些的过程中,我还发现了一个聚集了国内志愿计算爱好者的论坛 —— 中国分布式计算论坛,这里面有很多 BOINC 和 GIMPS 的贡献者,他们会交流项目参与方法、项目更新等。看到有这么多人愿意给科学事业贡献自己的算力我还是感到很开心的,如果感兴趣的话欢迎加入这些科学计算项目~