一、大数据对计算的影响

1.处理量对性能的影响

大数据从体量上增加了算法的处理对象，处理量的增加影响算法的空间复杂度和时间复杂度。

2.算法结构的影响

大数据可能影响算法中输入输出的参数，对原来算法的结构提出更高的要求。

（1）算法中预留的参数位置用尽，导致算法无法适应数据维度的变化

（2）对输入参数次序的影响，导致算法计算结果为“伪结果”

       二、并行计算

其基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来进行并行计算。

1.提高计算机性能的主要手段

（1）提高集成度

（2）提高处理器字长

（3）流水线等微体系结构技术

（4）提高处理器频率

2.为何要进行并行计算

（1）VLSI集成度不可能无限制提高

（2）处理器的指令级并行度提升接近极限-->CPU墙

（3）处理器速度和存储器速度差异越来越大（处理器性能2年翻一倍，存储器性能6年翻一倍）-->存储墙

（4）功耗和散热大幅增加超过芯片的承受能力-->功耗墙

3.为什么要进行并行计算

（1）越来越多的研究领域和应用领域将需要使用并行计算技术

（2）并行计算技术将对传统计算技术产生革命性的影响

（3）软件开发/程序设计人员面临挑战

4.并行计算分类

（1）弗林（Flynn）分类

SISD:单指令单数据流------->传统的单处理器串行处理

SIMD:单指令多数据流------->向量机，信号处理系统

MISD:多指令单数据流------->很少使用

MIMD:多指令多数据流------->最常用，TOP500基本都属于此类型

（2）按并行类型分类

数据并行级:一个大的数据块划分为小块，分别由不同的处理器/线程处理

任务并行级：一个大的计算任务划分为子任务分别由不同的处理器/线程来处理

位级并行（Bit-Level Parallelism）

指令级并行（ILP:Instruction-Level Parallelism）

线程级并行（Thread-Level Parallelism）

（3）按存储访问结构划分

共享内存

分布共享存储体系结构

分布式内存

（4）按系统类型划分

多核/众核并行计算系统MC

对称多处理系统SMP:多个相同类型处理器通过总线连接并共享存储器

大规模并行处理MPP：专用内联网连接一组处理器形成一个计算机系统

集群（Cluster）：网络连接的一组普通商用计算机构成的计算机系统

网格（Grid）：用网络远程连接远距离分布的一组异构计算机构成的计算机系统

（5）按计算特征分类

数据密集型并行计算

计算密集型并行计算------>气象预报

数据密集与计算密集混合型并行计算------->3D电影渲染