5.3并行计算的局限性在线视频

好 这张图实际上反映了

局部性的这样一个概念

我们来看上面的

这样的一个矩阵乘法

那么如果我们用第一行

去乘后面的这个矩阵

然后得到矩阵的这个

后面这一行

那么可以看到第一行的

这个横着的这个访问

应该说都是连续访问

而我们用第一行去乘

后面这个矩阵的时候

会是按列访问的

那么按列访问就是一个

局部性很差的这样一个访问

我们刚才提到局部性好

会使得cache命中

那么我们在上面的这个

例子里面这个横着的访问

应该说它都会cache命中

而竖着的这个访问

就会造成cache失效

那么cache失效

我们刚才已经说过

一个cache miss（音00：48）

它的访问时间

会是cache命中访问时间的

10倍左右

所以这是一个

性能上非常大的差别

那么为了解决这个问题

实际上人们提出了

这个矩阵乘里面的分块算法

也就是说

我们不是一次把整个的矩阵元素

就是按照矩阵本身的

这个顺序全都算出来

而是我们把它分成不同的小块

那么分块运算

它相对来说就可以得到

更高的局部性

所以也就能得到更好的性能

那么我们刚才也提到了一个

并行计算的重大挑战

是容错性

那么容错性对应的

这个计算系统的性质

实际上就是它的高可用性

那么我们现在说大数据处理系统

我们都知道像谷歌的

这个系统它都是通过

商业的服务器

直接买来以后搭建的

那么这种商业的服务器

比起定制的这种高端的计算机

应该来讲它本身的故障率

就比较高

所以我们说大数据处理系统

通常是由大量

不可靠服务器组成的

那这个时候在这个

大数据系统中

高可用性就显得更加的重要

那么比如说我们怎么去

处理一个十天的

大数据处理任务

你在运行的时候在第八天

有一台机器坏掉了怎么办

那么一种方法大家可以说

我可以重新执行

但是重新执行的话

如果你跑到第七天的时候

又坏掉了怎么办

那下面这个图

大家其实可以看到

这是一个整个系统的

平均无故障时间这个纵轴

是讲的它的平均无故障时间

而横轴讲的是机器数

这写的number of nodes

就是节点数也就是

我们可以把它对应成机器数

也就是说当机器数达到

一千左右的时候

我们可以看到它的这个

平均无故障时间

也就是我们看这条红线

这条红线它的

平均无故障时间

系统的平均无故障时间

大概也就是一百小时左右

也就是我们刚才说的

你要在这样的系统上

跑十天程序

那你已经会遇到

很多很多的故障了

那么更进一步

如果说我们单机的这个

平均无故障时间

达到一百万小时

这已经是很高的行进

这条绿线即使在这个时候

如果我们是一万个节点

那这个时候它的这个系统的

平均无故障时间

大概也是在一百小时左右的

所以也就是说我们在

单机的平均无故障时间

很高的情况下

如果节点数很高 很大

系统规模很大

我们仍然会全系统的

平均无故障时间仍然会非常短

所以说在这样的一个系统上

重新计算不一定能够解决问题

也就是你可能断的重新计算

系统会不断的失效

那么你就永远也算不完

你这样的一个任务

所以我们一定要有

一些其它的方法来进行容错

那么传统有一些容错的方法

比如说传统的容错计算机

它是通过多个执行部件

计算同一任务

然后比较它们的这个结果

那么比如说有三个执行部件

同时在执行同一个任务

最后如果有一个

和另外两个不一样

我们就可以知道这个不一样的

一个不一样的结果是错的

而另外两个是对的

那么要达到这样的一个

三个执行部件

同时执行同一个任务

这样的一种形势

实际上需要非常严格的同步

也就是我这里面列的叫锁步法

英文叫lock step

这个对整个系统

设计的要求非常高

成本也非常高

而且也会对性能

产生比较大的影响

所以这种方法

是不适用于这个大数据处理的

那么另外一个方法是在

软件工程中提到的

叫做多版本编程方法

也就是同样一个计算任务

我用多个人或者用多个版本

多种方式去编

那么比较它们的结果

如果结果一样的话

那说明结果是对的

如果不一样的话 选多数的

那么这个方法实际上

大家也可以看到

它实际上适应的是

软件方面的容错

而对于这个系统故障

它并不能够做有效的处理

所以这种方法也是不适用的

所以现在比较流行的方法

是这个检查点设置与恢复的方法

也就是说我把你这个

程序的整体的状态

能够把它保存下来

那么保存下来以后

如果系统在遇到故障的时候

我需要把这个你之前

保存的这个状态把它读出来

从你保存状态的

这个地方开始执行

而不是每次都从头执行

这样的话就能够达到

一定程度的可行性

但是大家也可以想象

这种方法也是有

很大的局限性的

那么一个系统你要把它

当前的状态保存下来

实际上是需要很大的I/O量

而且有的系统

由于它在频繁地做计算和通信

它的状态是什么

本身也是一个很困难的问题

所以这方面虽然有了

很多的研究工作

但是还是在它的

正确性和它的性能

两个方面实际上

都还与到很大的挑战

所以高可用性一直是

大规模分布式处理系统

里面的一个重要的问题