CMU15-418notes(19-23)

视频：https://www.bilibili.com/video/BV1Rh4y1F7aU/?spm_id_from=333.788&vd_source=463e5b3e4b18e5453477b57388c2e427

课程主页：http://15418.courses.cs.cmu.edu/spring2016/lectures

Lecture 19: Heterogeneous Parallelism and Hardware Specialization

Amdahl定律说明了并行优化的效果与并行的部分有关，如果在一个处理器上，所有的核都用于并行的部分，串行部分的影响就可能很大。在处理器上使用不一样的核，例如一个fat core处理串行部分，一些小核处理并行部分，会有更好的效果。如下图，perf(r)是fat core的性能，他也承担了一些并行计算的部分。

所以异构实现的系统可以更好的分配任务，提高计算效率，这个思想很早就在现代处理器中应用了。例如Intel主力Skylake处理器(2015年时，6代i7)，处理器包含了GPU(核显)，多级缓存及多个核，采用异构核心设计。

移动的系统也有类似的结构，而且整体不再被称为处理器，而是SoC(systemonchips)；超算可以也采用异构方式搭建。

本节剩余的部分介绍了一些系统设计的问题，主要是在设计计算机时需要考虑功耗和散热问题。GPU，DSP等专用处理器可以在特定情景提供高性能和低功耗。降低功耗的方式有两种：使用专用的处理器；减少数据移动(数据传输也是计算的重要成本，减少数据传输既能提高性能，也能降低功耗。)

最后是关于异构系统的挑战，异构系统带来了软件迁移和维护上的问题，调度问题也变得更加复杂，设计合适的算法将计算映射到合适的处理器本身也有很大的难度，还不能适应新算法等变化。

Lecture 20: Domain-Specific Programming Systems

由于有多种并行编程模型，多种硬件，软件的编写和维护变得更加困难。本节的内容就是关于使用特定领域的编程系统，实现高性能的同时提供高可扩展性(SQL是一个例子)。本节介绍的特定领域程序系统有两个，Liszt(用于科学计算)和Halide(用于图像处理)。

由于本节都是对上述两个系统的大致介绍。直接来到总结部分：

• 现代机器有更多的并行化和异构
• 许多软件只使用机器的一小部分性能
  • 为这些机器调整程序很有挑战性
  • 调整程序的工作在机器之间不能迁移
• 使用特定领域编程环境实现更好的性能和可移植性

Lecture 21: Domain-Specific Programming on Graphs

如果要设计一个新的编程系统，要考虑的问题至少有两个：

• 需要简便表达和高效执行的最基本的操作是什么
• 对于这些操作，最关键的优化是怎样的

本节以图计算为例，继续介绍领域专用编程模型。

PageRank是图计算的一个重要算法。PageRank的基本思想就是rank由相邻点的rank决定。

GraphLab是描述图中的迭代计算的系统，嵌入C++中，运行在共享内存机器或集群，定义了一个图系统和顶点上的计算。

使用GraphLab只需要定义怎样更新顶点，调度和并行化由系统完成。顶点通过signal来更新，直到收敛。

Summary：

考虑图计算的实现，实际上有一个问题是图的计算总是低计算强度的，并且对于大图来说，数据可能无法放到内存中，优化很困难。有两个方式对大图计算来优化：

• 重新组织图结构来增加局部性
• 压缩图

为了增加局部性，一种方式是将图分为多个块，并将其数据按照顶点id进行排序，这样每个块的相邻数据都是连续的数据：

当需要计算时，将与本块相关的数据全部都加载到内存，就拥有了全部的需要的信息。

GraphChi系统就以这样的方式实现，采用滑动窗口，每次从磁盘读入需要的数据。并在更新后广播数据。

另一个优化图计算的方式是进行压缩。例子是将边进行排序，通过计算diff来减少边的出顶点需要的字节，然后进行存储：

Lecture 22: Parallel Deep Neural Networks

深度神经网络已经彻底改变了人工智能和机器学习领域，取得了巨大的成功。

深度神经网络和神经网络的区别在于有更多的隐藏层。各个层的功能不同，有卷积层，池化层，全连接层等。

卷积层的最简单实现就是嵌套循环完成运算，但是这样并不能最大利用局部性，在矩阵乘法中我们就学过使用分块来提高局部性，卷积也可以通过修改计算方式提高局部性。如果嵌套循环，每个卷积block的数据只算一次，下次计算会有新的一列，如果将每个卷积block的数据排列为一行，行与行之间存在关联性，有更好的局部性(这里没太理解比起嵌套循环的优势)，将权重矩阵转为向量，原计算就转为矩阵向量乘；如果有多个权重矩阵，就有多个向量，转为了矩阵乘法。

为了减少网络的访存，有很多对网络数据压缩的方式。

采用以上的这些压缩可以显著减少model size。

Summary：

深度神经网络训练需要大量的数据，DNN有初始的权重，将数据输入后，计算输出的损失值并求和，然后调整权重，使损失值更小来提高模型的准确性。梯度下降是一种寻找最小值的方法，通过不断更新参数来降低损失。在计算时通常分成小的批次，进行并行计算，并使用反向传播来计算参数的导数。

在深度神经网络领域，仍然存在很多未解决的问题，例如网络结构的设计、数据表示的精度等。

TensorFlow和其他类似的框架为构建和训练深度神经网络提供了便利。

Lecture 23: Implementing

Implementing Message Passing

本节介绍MPI系统中的一些实现细节。

首先是消息传输的发送和接收有同步和异步两种选择。

上面的这种异步存在的问题是如果不断有消息传输，接收者就需要非常大的缓冲区。保守的方式是先发送一个信号，接收者准备好接收后，发送者再通过一个软件中断来进行传输数据。

不过对于保守方式，消息传递的速度会降低，即使传输一个非常简短的消息，也需要三次消息才能传输。当然，可以结合以上两种方式，预先分配一个限定大小的缓冲区，然后根据消息的大小决定是使用缓冲区，还是采用保守方式发送数据。

最后是实现MPI的挑战总结：

Implementing Parallel Runtimes

这一部分的内容主要是关于以下两个问题：

• 使用并行API的开销
• 运行时并行是如何工作的

本节的内容是基于OpenMP和cilk的。这两个都是基于pthread实现的。提供了更高级、更丰富的描述并行性的方式。

这部分的内容很宽泛零散，不做记录了。