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

标签: 技术前沿, 架构设计, 知乎问答

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

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

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

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

RAM模型

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

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

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

这样,在运行一次计算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)\)修改为非并发的,则会导致网格计算失去并行能力。

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

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

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

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

作者书籍推荐