并行计算机体系

半导体技术的突破促进了计算机性能的飞速增长，平均每十八个月就要翻一番。性能虽然在增长，体系结构却没有多大改变。CPU和内存是计算机中的核心部件，目前的计算机体系结构中，一台计算机往往只包含少量CPU。这些CPU中的每一个都被用来独挡一面，他们个个性能强大，绝大部分甚至是所有的计算任务都依赖于一个或几个CPU。另一方面，所有的存储任务都由一个集中式的大内存完成。CPU只做计算，而内存只做存储，这样的计算机体系是一种大处理器大内存的结构。

对于一个CPU而言，它同时只能计算一个任务，那么整个体系依赖于少量这样的CPU就意味着几乎所有的任务本质上都是被串行执行的，而在我们这个世界中并行却是非常普遍的，用这样的计算机体系来处理并行问题，如果不是不可能也是非常低效的。

与串行计算机体系相对的就是并行计算机[1]，这种计算机从真正意义上来讲目前还不存在。我们不妨来设想一下，这样的并行体系不再是由少量高性能CPU和一个集中的大内存组成，而是由大量（百万、亿万级别）的比较简单的模块组成，每个模块相当于一个单片机，里面包含简单的计算和存储功能，而模块之间则高度互联，可以高速传输数据。当进行某项计算任务时，程序先交给某个计算模块，但是它不会一个人去做所有的计算，相反它会和其他模块通信，进行任务的分发，每个模块只计算一部分，彼此通过通信交流计算结果，最终的计算结果则由一个或几个模块给出。和大处理器大内存体系相比，这里的计算将是真正意义上的并行。一个任务被分成大量的子任务，每个子任务被独立的模块同时计算。

造成大处理器大内存计算体系效率低下的另一个关键因素是是计算和存储的分离。一个内存区域存放着待计算的数据，CPU首先要从内存中读取这个数据，将它和其他数据进行某种计算，算完之后需要再将计算结果存入内存中，通常情况不会只算一次，因此CPU在需要那个计算结果的时候又需要再读进来，做计算，写进去。。。 很明显这个过程极度费时，根本原因在哪里呢？就在于这里的内存只能存储，你存一个数据，一年之后再来取它还是这个数据！我们再来看一看在并行体系中会有什么不同。这里没有集中式的大内存，但是对于在进行计算的某一个模块而言，其他模块就可以看做是“内存”，模块的地址就是“内存”地址。与普通内存不同的是，当一个模块把一段数据存到某个“内存”区域之后，下次当它再来取得时候，神奇的事情发生了，数据竟然已经自己算好了（当然实际上是由那个模块算的），它所要做的就是直接获得结果！这种情况我称之为**“存储即计算”**，只要将并行体系中每个模块颗粒做的足够小，计算和存储就将完全融在一起！这就像，当你把一块糖和一块冰放在一起时，它们是彼此分离的，但是当你把糖和冰融化成细小的分子颗粒再放到一起时，它们就合二为一形成了溶液，你分不清哪里是糖哪里是水。

用Erlang模拟并行计算机

鉴于硬件上这样的并行计算机体系还未出现，我们不妨先在软件层面上进行模拟，一窥它神奇的特性。erlang语言就是被用来做模拟的软件，我们的目的是用它来模拟一个并行的计算机体系。

选择erlang是因为它本身提供了其他语言所不具备的强大的并行能力。在erlang中，一个程序往往是由大量（十万、百万）的进程组成，每个进程彼此独立，并行[2]运行，进程之间通过消息的方式传递信息。所有这些都正好是我们所需要的，用erlang来模拟上面的并行体系，概念对应的非常好。erlang中的一个进程被用来模拟并行体系中的一个计算模块，它可以做计算也可以做存储，而这些都是跟其他进程（模块）独立的；每个进程的运行是并行的，正好我们也要求每个模块能并行运行；进程之间可以建立高度发达的通信管道，正好这也是我们对模块互联的要求。

“并行计算机体系”有了，接下来的问题是什么？ 有了一台“计算机”接下来当然就是需要一套可以在这个体系上跑的“操作系统”了，schem.erl就是这样的一个“操作系统”。

schem.erl的设计

schem.erl从名称上可以看出，它使用scheme的语法，.erl表示它是跑在erlang所模拟的并行计算机体系上的（下文中不做说明时，当我们说模块时就是指erlang的进程，说通信时就是指erlang的消息接发，以此类推。从现在开始进入并行体系，忘掉这是在模拟，忘掉erlang！）。普通scheme是被设计来跑在大处理器大内存计算机体系上的，而schem.erl是被设计来跑在“并行计算机体系”上的，这是它们之间最大的区别。schem.erl的设计需要充分考虑计算机体系的并行化特点，在这里整个计算机是由大量模块组成的，计算主要是并行进行的，存储和计算是同时的...

schem.erl的结构从整体上来讲和一般的scheme解释器差不多，主要就是对S表达式做递归解析，根据几种基本的情况分别做处理，选择scheme而不是其他语言是因为scheme足够简单可以让我们更容易的看到事物的本质，同时又足够强大，让构造一个全功能的系统成为可能。关于scheme的介绍和编写在网上有很多，因为不是本文要说的重点，这里不过多讨论，下面只说schem.erl特殊的地方。

schem.erl设计最关键的一点就是要决定任务的分配问题。当一个任务需要某个模块去执行时，它如何将这个任务分割，交给其他模块去做？在目前的schem.erl中，这个判断原则是这样的：当一个模块处理到的表达式是一个过程(procedure)的时候，它将这个过程整个交给其他模块并在这个过程处做一个_标记_，然后继续去处理其它计算，当_需要_这个过程时，这个模块就通过这个标记去读取这个过程的值，此时这个过程或者已经被其它模块算好了，这种情况下取得结果继续计算，或者还没有算好，此时等待对方算好再继续其它计算。

上面这段话中有两个关键词：“标记”和“需要”。“标记”应该足够表明送出去的这个过程交给了哪个模块，这就相当于普通计算机体系中表明内存地址的变量的概念，在schem.erl的实现中我们就用对方进程的pid表示。另一个关键词是“需要”，什么时候才算是需要一个过程的值呢？了解惰性求值的读者对这个肯定不陌生，这里的需要和惰性求值里的基本一致。以下几个时刻被称为需要一个过程的值，分为以下4种情况：

1. 当计算到一个过程，并且它的操作符是原始操作符（例如+,-,*,/等解释器自带的操作符），那么这个原始过程(+ proc1 proc2 ...)的参数中如果有过程，这些过程(proc1, proc2...)的值就是需要的；
2. 当计算到一个if条件判断时（if <test> ...)，它的判断语句(<test>)如果是一个过程，则这个过程的值是需要的；
3. 当计算一个sequence表达式时(begin proc1 proc2 ...)，它的每一项如果是一个过程，则这个过程(proc1, proc2...)的值是需要的；
4. 整个程序作为一个过程($schem.erl myapp)，它(myapp)的值是需要的。

值得注意的是，仔细思考就会发现上面的这四个时刻是唯一四个真正需要串行的地方，只有在这四个地方后一项计算才依赖于前一项计算的结果，除此之外的其他任何地方都可以并且应该是并行的，我们将这种除了在本质上是串行的地方串行否则全部并行的系统称为完全并行化的系统。这种区分揭示了串行和并行的本质，我们处于如此底层的位置，因此才能将它们区分的如此清晰，就像在高倍显微镜下将物质和杂质分开一样。

在schem.erl的实现中，基本上是符合完全并行化的原则的。除了一点有出入，我们说过一个模块只有在越到过程时才会将它并行化分给其他模块，因此如果一个表达式完全是由原始操作符组成的，那么它就不会并行化，例如像这样的表达式(+ (- 2 1) (* 3 4))，虽然根据4点串行的原则这里的(- 2 1) 和 (* 3 4)应该是可以并行计算的，但因为它们都是原始表达式，因此schem.erl中对这两者的计算将由一个模块串行进行。这样做的初衷是考虑到现实中一般仅由原始操作符组成的表达式都不会太复杂，和并行分配的开销相比自己计算也许会更快一点，不过关于这个假设的合理性仍有待商榷。

关于schem.erl，解决了任务分配基本上问题就解决了，其他还有一些需要考虑的都是策略选择和运行优化方面的问题，例如实现类似尾递归的功能、lexical scope的问题等等，这些方面schem.erl有很多问题还需要解决，讨论留到他处，本文不做探讨。

下面我们就用schem.erl举一个并行化的直观例子

>>> (define (slp) (sleep 1000)) ; for distributing, we need a procedure

>>> (define (try a b)
        (if (= a 0) 1 b))

>>> (try 0 (slp))    ; return immediately
1
>>> (try 1 (slp))    ; sleep 1 second
>>>

上面这段代码可以在任何一个scheme解释器里运行，但是你会发现在一般的解释器里(try 0 (slp))在返回前会睡眠1秒钟，虽然因为(= a 0)成立(slp)其实根本就没有用，但是由于scheme在每个参数传入函数之前需要先求值，当它运行到(slp)时自然就卡在那里了，等它醒过来却发现“白睡了”。而在schem.erl中(try 0 (slp))会立即返回，因为(slp)被交给了另一个模块去运行，当前模块继续运行，发现(= a 0)于是直接就返回了。看完这个例子也许你会说如果scheme是惰性求值的也会立即返回啊，schem.erl跟惰性求值有什么区别？那么请看下面这个例子。

>>> (+ (slp) (slp))  ; sleep 1 second
It's wrong in data type of course, we know that.
We just ignore the error for the sake of demo!
Replace (slp) with (some procedures costs 1 second to return a number) if you feel sick about this.

无论你在惰性或不是惰性的scheme解释器里运行上面这个表达式，返回错误之前都会睡眠2秒，但是在schem.erl中只会睡眠1秒，现在知道并行的不同了吧？惰性求值只是把求值推后了，但终究还是要自己去求的，而并行则是推后并且不用自己去求！

一个完全并行的底层“操作系统”有了之后，是不是就意味着所有用这个"操作系统"写成的高层应用就都能实现完全并行化呢？如果是这样那就太好了，只要有了这个并行的操作系统我就可以随便写上层应用了，而且不管我怎么写最终我的应用自动都是完全并行化的。很遗憾，这不是真的，问题在哪里？就在于串行4点中的第3,4两点。这两点中表示的具体内容是由写上层应用的人决定的，而不是由schem.erl决定的。举例来说，第3点中schem.erl说的是给我一个sequence表达式如(begin (proc1) (proc2) (proc3))，我将按照顺序串行的执行它们。而具体的(proc*)是什么是由用户决定的，至于(proc1)和(proc2)之间是不是有本质上的串行关系，这只有用户才知道，如果用户把两个完全可以并行的proc放到这里，schem.erl将串行的执行它们，因此schem.erl无法代替用户自动将上层应用完全并行化。关于第4点也有同样的问题，只需要将(过程1，过程2，过程3)换成(程序1，程序2，程序3)即可，在这里一个团队中的不同用户无法保证他们的程序之间具有表示出的那种串行性。

为什么用户会把不是串行的东西理所当然的写成串行形式？这是长期被串行计算机体系熏染的结果。在几乎所有的编程语言中，程序是要串行着写的，比如在C中是这样：

int i = 1+1;
int j = 2+2;
...

在scheme中是这样：

(define i (+ 1 1))
(define j (+ 2 2))
...

但是请注意，串行着写并不意味着这是需要串行执行的！例如上面的两句就完全可以并行计算。但是在串行计算机体系中，这样做是没有问题的，因为它不提供并行运行方式，只能串行运行，怎么写无所谓。但是在schem.erl中你要是这么写，schem.erl就会认为用户是指明要让两个过程串行运行的，而这显然不是用户的意思。在串行计算机体系中你可以不思考这些（你思考了也没用，没有并行可用），但在并行体系中你应该思考一下，你的思考将决定最终你的应用的并行率。例如对于上面这两行代码，在schem.erl你就不应该按顺序写，因为按顺序写会被解释成这样(begin (define i (+ 1 1)) (define j (+ 2 2)))，而这是一个sequence的序列，里面的过程都会被串行执行。相反，你应该写成(parallel (define i (+ 1 1)) (define j (+ 2 2)))[3]，这样 schem.erl就会并行运行它们。因此类似schem.erl这样的并行底层系统，无法代替用户自动将高层应用并行化，但是它提供的原语能够促使用户去思考，并给予用户实现的可能和选择的自由。

从串行到并行有很多根深蒂固的思想需要转变过来，一旦转变过来你就会发现，原来那些只是做事的一种方式，而不是唯一方式！

[1]: 串行计算机的特征是少量CPU，大量集中式内存；并行计算机的特征是大量CPU+内存。对于一个计算机体系我们定义它的并行度 = 总CPU数量/系统总内存大小(Byte)。这个值的范围为0~1，值越大表示计算机系统的并行度越大。当并行度为0时，称为完全串行，为1时，称为完全并行。当然是两种极限情况，实际中超过某个阈值就可认为是并行体系。

[2]: 当然，在目前的计算机体系上这样的并行是分时“模拟”出来的，不过在erlang的层面上我们姑且将它当做真正的并行。

[3]: 当你打开一个文件一行一行按顺序写(proc1) \n (proc2) \n (proc3) \n ...时，schem.erl会将这个文件解析成(begin (proc1) (proc2) (proc3) ... )，这会导致过程的串行执行。那么怎么写才是告诉schem.erl解析成(parallel (proc1) (proc2) (proc3) ...)呢？这个需要精心设计一下，例如可以让schem.erl将不同文件中的过程解释成并行等等，这个设计还在进行中，你有好的建议不妨告诉我哦。