并行计算

部分内容来自《给产品经理讲技术》

并行计算指一台计算机或一个计算系统（如分布式系统）可以在同一时刻执行两个或者两个以上的任务。并行计算在计算机世界中有两种实现方式：时间上的并行和空间上的并行。

所谓时间上的并行，是指流水线技术。流水线技术是指，在重复执行一项任务时，可以把它细分成很多小任务，让这些小任务重叠执行，来提高整体的运行效率。计算机中的CPU在执行指令的时候，也是用的流水线原理。首先，它把一条指令的执行过程拆分成5个部分：取指令、译码、取操作数、运算和写结果。前三步由控制器来做，后两步由运算器完成。那流水线模型用在这里就是，当执行完一条指令的前三步之后，并不是等运算器执行完后两步才继续工作，而是马上开始着手执行下一条指令的前三步。这样所有指令一条一条进来，运算器和控制器同时工作，互不干扰，大大提高了CPU的运行速度。

空间上的并行，简而言之就是“人多力量大”，通过增加硬件资源投入的方式解决效率问题，在单机系统上的解决方案就是增加核的数量。这是目前并行计算的焦点。

在海量数据处理中，为提高算法的速度，你需要让它们能够在多个内核中并行地执行。在并行计算下，数据处理速度的提升并非线性的，因此即便你的笔记本电脑装备了两个而不是一个内核，算法的速度也不可能提高一倍，其中的原因有两个：

1、并行性管理开销，假设你要对一个包含1000 个元素的数组进行排序，如何在两个内核之间分配这项任务呢？如果让每个内核对其中500个元素进行排序，再将两个排好序的数组合并成一个有序数组，那么合并也是需要时间的

2、负载均衡，假设你需要完成10 个任务，因此你给每个内核都分配5个任务。但分配给内核A的任务都很容易，10 秒钟就完成了，而分配给内核B的任务都很难，1分钟才完成。这意味着有那么50 秒，内核B在忙死忙活，而内核A却闲得很！你如何均匀地分配工作，让两个内核都一样忙呢？

因此实现并行计算的前提条件是被执行的任务可以被拆分成多个可独立执行的子任务。系统进行调度的基本单位是线程，进程是资源分配的最小单位，在没有引入线程以前，进程既是最小资源分配单位，也是最小调度单位。后来引入了线程，最小调度单位就是线程（线程是系统分配处理器时间资源的基本单位），资源分配和调度分开了，目的是为了更好的利用CPU。CPU把所有的时间分成

若干个小片，把每一个小片不断地分给不同的线程执行，保证每个程序都有机会执行，不会有程序一直霸占CPU。若一个程序有更多的线程（一个进程至少有一个线程，它称为主线程），那么这个程序中的多个线程获得CPU的概率就更高，获得的时间就更多，执行速度也会更快。所以多线程程序的核心是开启更多的线程，获得更多的CPU时间片，让程序更快完成。

多核操作系统就是将相互独立的线程和进程分配到不同核心上，达到并行计算的目的。虽然用户日常使用的应用程序不是由专门的并行计算语言编写的，但是在操作系统的帮助下，用户依然可以享受到多核并行计算对性能带来的提升。

分布式计算、云计算这些概念都是对并行计算的包装。例如，Apache基金会开发的分布式系统基础架构  Hadoop，其基本原理就是将用户的输入转化为大量可以并行的MapReduce操作，然后分配给集群上的各个主机并行执行。

mapreduce

有一种特殊的并行算法正越来越流行，它就是分布式算法，它以MapReduce为代表。分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理

念：映射（map ）函数和归并（reduce）函数。

       映射函数很简单，它接受一个数组，并对其中的每个元素执行同样的处理。具体到计算任务中，就是如果有100 台计算机，map 能够自动将工作分配给这些计算机去完成。

       在Python中可使用内置的map函数模拟映射，如

>>> map(lambda x: x*2,[1,2,3,4])

[2, 4, 6, 8]

>>> 

归并函数理念是将很多项归并为一项。映射是将一个数组转换为另一个数组，而归并是将一个数组转换为一个元素。

在Python中可使用内置的reduce函数模拟归并，如

>>> reduce(lambda x,y:x+y,[1,2,3,4])

10

>>>