一种适用于网格计算的主动存储计算机模型

保留所有版权，请引用而不是转载本文（原文地址 https://yeecode.top/blog/80/ ）。

图灵机作为一种基础的理论模型，在解决可计算性问题上十分重要。但是，在实际使用中，这种模型过于简单。通常，在算法设计和分析领域，我们使用随机访问计算机模型RAM（Random Access Machine）。但是，在网格计算中，RAM模型过于基础，因此产生了众多其他模型。

本文讨论一种适用于网格计算的主动存储计算机模型CAM（Computer with Active Memory），包括其提出背景，使用范围，局限性等。本文主要内容参考中科院计算所徐志伟等人编著的《网格计算技术》一书以及徐志伟先生的论文《一种主动存储计算机模型》。

同时，我们也对徐志伟先生所提的理论进行了一些修改，包括将字长等元组从模型中删除，修改了一些定义等。但具体思想仍由原作给出。

RAM模型

RAM模式是我们展开讨论的基础，因此我们先形式化定义RAM模型。

一个RAM计算机C可以定义为一个三元组，\(C=(P,M,Ci)\)，其中：

• P是计算机的处理器
• M是计算机的存储器。存储器M中包含众多的存储单元，我们依次记为\(M(0),M(1),M(2)……\)，因此M是以上各个存储单元的集合，即\(M= \{ M(0),M(1),M(2)…… \} \)。
• Ci是计算机的指令集。指令集Ci能够覆盖完成图灵机的操作，例如可以是下列指令的集合：load,store,add,subtract,multiply,divide,jump,jzero,halt。

在计算机C上执行一次计算Q可以被定义为一个四元组，\(Q=(C,R,I,O)\)，其中：

• C为计算机
• R为有限条指令组成的程序
• I是M的一个有限子集，其中存储有输入数据
• O是M的一个有限子集，用于存储输出数据

这样，在运行一次计算Q时，计算机C可以按照R的指令，从I中取出输入数据进行一系列运算，并将结果存入O中。

如果最后R调用了halt函数，则计算机最后停机，此时O中就是计算结果；如果Q不能结束，则Q是一个发散计算，例如流处理。

CAM模型

在讨论CAM模型之前，我们先粗略介绍网格计算中涉及的两个基本的参与者：

• 客户机：计算命令的发起者
• 服务器：网格中的一个节点，是计算命令的执行者

另外，这两个概念是相对的。在不同的计算任务中，以上角色都可以互换，而且我们对其中的一些协调层角色进行了省略。

使用RAM模型来进行网格计算是十分复杂的，这需要客户机完成大量的数据发送、任务下发工作，服务器完成大量的数据接收、计算等工作。因此，提出了CAM模型。

一个CAM计算机D是一个三元组，\(D=(P,M,CI)\),其中这三个元素我们分别介绍。

P

P是计算机的处理器。要注意，这里的处理器不仅仅包含客户机的处理器，也包含网格上各个服务器的处理器。

M

M是计算机的存储器。同样的，不仅包含客户机的存储器，也包含网格上各个服务器的存储器。这些存储器统一编号，即也有\(M={M(0),M(1),M(2)……}\)。

另外要注意，CAM中的存储器M中的每个存储单元内部是划分区域的，例如将其划分为三个区域。这样，\(M(1)\)包含三个区域，我们分别记为\(M(1,in)\),\(M(1,f)\),\(M(1,out)\)。其中，我们可以让\(M(1,in)\)存储输入数据，让\(M(1,f)\)存储计算函数，让\(M(1,out)\)存储输出结果。对于每个存储单元都遵循这样的三个区域划分。

因此，对于任意一个\(M(i)\)，它包含了一个\(M(i,in)\)存储输入数据，一个\(M(i,f)\)存储计算函数，一个\(M(i,out)\)存储输出结果。于是，仅依赖这些信息，它可以完成一个计算。我们也让\(M(i)\)具有运行能力。

当运行\(M(i)\)时，实际是触发了下面的计算：

$$M(i,out)=(M(i,f))(M(i,in))$$

因此不同于RAM中的存储器，这里的存储器具有执行能力。

CI

CI是计算机的指令集合，该集合是RAM中指令集合Ci的超集。

例如，在CI中存在\(Execute M(i)\)表示触发运行\(M(i)\)，这条指令是Ci中没有的。

另外要注意，\(Execute M(i)\)指令在计算机中仅代表触发运行\(M(i)\)，而不需要等\(M(i)\)运行结束。因此，如果存在下面的指令序列：

a;
Execute M(i);
b;

则不等\(Execute M(i)\)执行结束，便会触发指令\(b\)。这种定义实际是在发挥计算网格的并行计算能力。

CAM模型讨论

相比于RAM，CAM是RAM的扩充，其P变为一个集群，M具有了运行能力，CI扩充了命令集合。

其中最重要的一点是M具有了运算能力，我们可以将其看做一个包。只要将包中的内容发送给网格中的一个节点\(i\)，然后使用\(Execute M(i)\)指令触发它，便可以在节点\(i\)上并发地进行这个任务。

例如，下面的程序片段便完成了任务下发、执行、回收的过程：

MOV InputData M(7,in);
MOV Function M(7,f);
Execute M(7);
MOV M(7,out) LocalFile;

但是CAM理论并不完善，因为各个节点之间的计算往往是有依赖关系的。例如，节点7的结果作为节点9和节点17的输入等。按照\(Execute M(i)\)指令的定义，这种异步执行的方式不能满足这种要求。

而如果将\(Execute M(i)\)修改为非并发的，则会导致网格计算失去并行能力。

因此，我们可以设计两条指令:

• \(sExecute M(i)\):表示串行执行
• \(pExecute M(i)\):表示并行执行

对于存在依赖的计算任务采用串行执行。通过两种指令的选用，保证系统的并行能力和节点关联能力。

这种CAM的模型中，最重要的思想实际是M中存储单元的分区设计思想，使得M的每个存储单元具有可执行能力。进而将网格中的节点转化为了一个或者几个存储单元。

可以访问个人知乎阅读更多文章：易哥（https://www.zhihu.com/people/yeecode），欢迎关注。

作者书籍推荐