一种适用于网格计算的主动存储计算机模型
保留所有版权，请引用而不是转载本文（原文地址 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的每个存储单元具有可执行能力。进而将网格中的节点转化为了一个或者几个存储单元。
