pdf课件

课程包括了4个project：

1. SIMD and multi-core Parallelism
2. CUDA programming on NVIDIA GPUS
3. Parallel Programming via a Shared-Address Space Model
4. Parallel Programming via a Message Passing Model

在做project时候你会尝试很多方法提升性能，但是许多方法都是无效的，你需要思考为什么这些方法是无效的，并记下来。然后，有些方法可以使得你的性能提升了2或3倍，你也需要思考为什么它会快2或3倍，而不是4或者5倍，因此做project的时候请仔细写下你的整个思考以及尝试过程。

A Brief History of Parallel Computing

为什么处理器变快了？

1. 更宽的数据位宽
   1. 4bits ->8->16->32->64
2. 更加高效的流水线技术(piplining)
   1. 3.5 cycles per instruction(CPI)>1.1CPI
3. 探索指令级并行(Instruction-level parallelism, ILP)
   1. 如超标量（superscalar），达到4CPI
      1. 超标量芯片中有多个ALU，在一个时钟周期访问多条指令。
4. 更快的时钟频率
   1. 10MHZ->200MHZ->3GHZ

增加时钟频率是最简单粗暴的一种提升性能的方法，但是随着时钟频率的增加，人们发现芯片单位面积消耗的能量指数级增加，导致芯片越来越热，如下图是2001年发布的一张图片，横轴是年份，纵轴是芯片单位面积的耗能

image.png

可以看到如果按照之前发展趋势的话，在2010年，芯片的温度将和太阳一样，因此人们意识到依靠增加时钟频率提高性能的方式已经走到头了。

下图是晶体管密度，时钟频率，能耗，以及指令集并行（ILP）的发展趋势，
可以看到大约2003年之后，后三者已经不怎么发展了，之后的时钟频率大致在3GHZ，能耗在100w，ILP在4CPI左右，只有晶体管密度仍然在指数级增长,

image.png

提升单个cpu核的性能已经不容易了，但由于晶体管密度变大，单个cpu核的面积变小，因此cpu上可以放置更多的多个cpu核，这使得并行计算成为了现在加快软件运行的最佳方式之一。(这句话我自己的理解)
如下图中的intel Xeon 有61个x86核

image.png

下图的NVIDIA GPU GTX 980 有数千个cores

image.png

现在的超级计算机有几十万个cpu cores， gpu cores。
在2004年之前，让你程序变得更快的方法是等6个月，去买一台新电脑。 而现在，你需要做的是写可以并行计算的程序。

What is a parallel computer?

parallel computer的定义：
A parallel computer is a collection of processing elements that cooperate to solve problems quickly

该定义有两个重点:
第一是"a collection of processing elements", 说明有多个处理单元
第二是"cooperate, quickly"， 说明parallel computer通过多个处理单元的合作来提升计算的性能、效率。

加速比（speedup）：
用来衡量P个cores的加速性能，公式为speedup = 1个core的执行时间/P个cores的执行时间。

为了探究有那些因素会影响并行的效率，老师开展了5个有意思的实验：

1. 1个人计算16个卡片上的数字，花费56秒
2. 2个人计算16个卡片上的数字，每个人8个卡片，花费34秒
3. 4个人计算16个卡片上的数字，每个人的卡片数不一样，有的人大于4张，花费39秒
4. 4个人计算16个卡片上的数字，但允许他们对得到的卡片数量进行重新均匀分配，总花费34秒
5. 教室中的150个人计算150个数字，总共花费95秒，策略是:
   1. 每一排的每个人都告诉右边的人ta以及ta左边所有人的总和数字
   2. 每排最右边的人告诉前一排的人，ta排以及后面排的总和数字

实验1中每一张卡片的用时大概在3.5秒

实验2中每张卡片的计算时间大约在2.125, 超过3.5秒的一半。
一般而言P个core的执行时间大于1个core的1/P倍，这是因为在并行时会多出额外步骤，如多个core之间的通信，这些步骤都会消耗时间。在实验中，每个人计算好后都需要先在纸上写下他的数字，然后再求和。该过程中，“写下”就是额外的步骤，并且由于纸和笔资源只有一个，需要互斥使用，又导致了额外的时间开销。

实验3中每张卡片的计算时间为2.4秒，远远大于3.5秒的1/4，这就是负载不均衡。有些人分配的卡片数少，因此很快完成计算任务，而有些人则分配的任务过多，最终的耗时由最慢人决定。

实验4中每个卡片的计算时间为2.1秒，好于实验3。在该实验中，4个人对收到的任务进行重新分配，实现负载均衡。但负载均衡也是额外的需要消耗时间的步骤，会降低加速比，并且纸笔还是需要互斥访问，因此4人的耗时和实验2差不多。

实验5中的每个数字计算时间为0.6秒，虽然快了很多，但离理论加速比1/150，还差的很远。究其原因是绝大多数人在完成自己的任务后都在等待，并且等了很多时间，整个过程中的大部分时间都花在两两人的通信上，导致加速比不高。

course theme

接下来说一下课程的几个主题：
课程的主题1： 设计和编写大规模的并行程序
探究并行：

1. 将任务分解为小的任务，使得小任务可以安全地并行处理
2. 将任务分配给cores
3. 管理cores之间的通信和同步

课程主题2： 并行计算机的硬件具体实现：计算机是如何实现并行的(工作原理)
实现高效抽象的机制：

1. 实现机制的性能特征(Performance characteristics of implementations)
   1. 没完全搞懂这条啥意思，可能是指探索为什么这种实现机制是性能高效的？
2. 设计时的权衡利弊：性能，便利(convenience)以及花费(cost)

为什么我们需要知道硬件实现？

1. 机器的特性对并行性能很重要
2. 因为你在学这门注重高效和性能的课

课程主题3：思索高效
快！=高效

快是指时间少，而高效看重的是加速比.

高效从程序员的视角指：充分利用了机器提供给程序员的能力（capabilities）。

高效从硬件设计者角度指：将合适的能力（capabilities）加入到系统，这里的capabilities指性能除以花费，即单位cost所获得的的性能，花费可以指芯片大小，提供的功耗等。

从上文我们可以看到CPU设计思路有过一次重大变化：

1. 2004年之前：在芯片预算范围内性能最大化
   1. 越来越激进的指令级并行策略
   2. 越来越高的时钟频率
   3. 越来越大的功耗
2. 2004年之后：
   1. 芯片面积差不多了，重点在增加单位面积的性能
   2. 更加关注能耗（电池寿命，数据中心（？节能环保）），重点增加单位能耗的性能
   3. 结论：更加关注core的高效性。

总结

1. 现在，单线程的程序性能很难提高了
   1. 为了使得程序更快，必须利用多核性能，这就意味这你必须知道如何写并行代码
2. 并行编程是具有挑战性的
   1. 要求任务的切分，通信以及同步
   2. 了解机器硬件特性是重要的
3. 我想你会发现现代计算机的处理能力比你想象的要大得多，只要你使用它!
4. 欢迎来到15-418！

扩展

时钟频率和功耗

本节主要参考这篇文章
时钟频率和平常说的CPU频率是多少GHZ中的频率是一个东西，1s除以时钟频率就是时钟周期。

直接给出公式，频率和功耗的关系是：

其中P是功耗，C可以看做一个常数，V是电压，f是频率.
看上去频率和功耗成正比，好像功耗也不是增加的很快，但是晶体管的硬件每次翻转时有一定时间的延迟，称为门延迟。如果频率过高，导致时钟周期接近甚至小于门延迟，晶体管会来不及改变状态，造成错误。因此频率提高时，需要加大CPU电压以缩小门延迟，这就导致了功耗近似于频率的3次方。
下图是i7-2600K频率和功耗的关系：

image.png

可以看到功耗大致是频率的幂函数。
当然上面的公式是简化了的，不过对于理解"为什么不能通过增加频率提升性能"这个问题还是足够了。

顺便一提，win下使用throttlestop软件可以调整CPU的功耗限制，电压等设置，我一般使用它来解锁功耗墙。