Chapter5

Chapter5: DLP and TLP

福林分类法：

横向的方法是计算一个加法就计算一个乘法，这样存在RAW的问题，同时多功能流水线需要不停转换，效率较低。

换用纵向的方法，即计算完加法才计算乘法。

数据依赖存在，但是RAW延误少，效率更高。

理论上其实在加法的部分做完后，如\(k_1\)，\(k_2\)后，就可以开始计算乘法了，这部分是可以加速的，我们后面提到。

我们也需要空间来存储\(k\)，但是如果\(N\)很大，buffer放不下，我们就需要对\(k\)进行一个分组，即组内纵向，组间横向。

共\(s+1\)组。

总结一下，共三种方式：

• Horizontal processing method
• Vertical processing method
• Vertical and horizontal (grouping) processing method

SIMD: vector processor

CRAY-1

有12个单功能流水线，若干个vector register，流水线可以真正意义做到并行。

Improve the Performance of the Vector Processor

• 最直接：增加功能部件以减少结构冲突

  + 向量的链接技术：向量寄存器之间可以相互链接，从而实现向量寄存器之间的数据传输

  举个\(D=A*(B+C)\)的例子。

  

  前两条是完全可以并行的，第三条与前两条虽然没有结构冲突，但是需要等待结果，因此不能完全并行。

  但是我们可以使用分割元素的思路，例如B+C的第一个元素处理完之后立刻给乘法器进行mul，这样我们实现了并行(同时乘法的运算周期也更长对吧)。

  

  • 三个串行运行

    + 前两个并行，最后一个串行

    + 一起并行，当然不是完全的并行

    

    不完全的并行可以体现在乘法器总是慢一拍。

  这个\(1+6+1+(N-1)\)理解成\(N\)长度的火车往里进就可以了。

• 循环的处理

  就是说\(N\)太大的时候我们没办法全放入buffer，因此只好分段处理，这时需要一个循环。 + 多处理器系统

SIMD: array processor 阵列处理器

\(N\)个处理器，每个处理器希望连接到其他处理器。如果是简单的直接连接，必要\(N^2\)复杂度。

我们进行下方这种结构的改进：

基本结构：

• 分布式的 distributed memory

  

  

  ICN: 内部互联网络

  processor尽量访问自己的memory + 集中共享式的 centralized shared memory

  

  

二者的不同：

• 分布式的processor与memory直接相连，集中共享式则是通过ICN与processor相连
• 分布式ICN主要连接processor，集中共享式则连接processor与memory

单级立方体网络

定义的Cube函数：

\(Cube_i(P_{n-1}...P_1) = P_{n-1}P_{n-2}...\overline{P_i}...P_1\)

类似这样：

经此方法，我们实现了使用\(logN\)的复杂度来实现内连接。

就算n>8，也是成立的。

PM2I

\(PM2_i(j) = (j + 2^i) mod N\) 和 \(PM2_{-i}(j) = (j - 2^i) mod N\)

那对于8而言，我们i可以取0 1 2，共5个函数(因为正负2是同一个函数其实)

shuffle exchange

\(shuffle(P_{n-1}P_{n-2}...P1) = P_{n-2}...P_1P_{n-1}\)

\(n = logN\)

显然经过n次变换就回到初始状态了。

再增加exchange函数，因为这个时候0/7还是孤立的。exchange是\(Cube_0\)。

最远距离：\(2n-1\)