向量机器模型

[拼音]：xiangliang jiqi moxing

[外文]：vector machine model

并行计算的一种理论模型，引进这种模型的主要目的是便于从理论上对各种问题并行计算的现实可能性和并行计算时所需的时间、空间等资源作定量的分析。

一个向量机器由 k个向量和一个程序所组成。每个向量可以存储一个左边无限的 0，1序列。这个序列除了有限多位以外全都相等。也就是说，左边是一串无限多个0或一串无限多个1，只有右边有限多位是有变化的。有变化部分的位数称为这一内容的长度。把这样一个二进序列解释为整数时，左边无限多个0被解释为正号，无限多个 1被解释成负号。其余有变化的部分按普通二进制表示理解。例如向量…1110101表示-5，…0001101表示+13。两者的长度都是4。

向量机器可以采用下列各条指令来编程序：

（1）A←ɑ，把一个常向量α送入A；

（2）A←～B，把B向量内容取反码（1变成0，0变成1）后送入A；

（3）A←B∨C，B和C的相应位作逻辑加后送入A的相应位。

（4）A←B↑C（或A←B↓C），B的内容左移C位送入A。此处C的内容按整数意义理解。如果为负则表示右移，左移时右端补0，右移时移出的信息不再保留。A←B↓C表示右移。

除此之外，一个向量机器还可以判断某个向量的内容是否全0，以实现条件转移。

设W 是一个长度为 n-1的 0，1串，下面的向量机器（见图）把形为…0001W 的字转换成字。原始数据和答案都是放在A中。

向量机器每条指令的执行，都是一种并行的计算。因此，从开始运算到停机所执行的指令总条数可算作并行时间，各向量内容长度之和在运行过程中的最大值称为空间。串行时间的定义是执行各条指令的运算量的总和，而每条指令的运算量的定义为参加运算的向量的长度之和。

借助于这个模型可证明下面的并行计算论题：一个问题类如果能在T(n)的一个多项式的并行时间内计算出来，当且仅当它可以在T(n)的一个多项式的空间内被串行机器计算出来。

相关推荐: 向量机器模型