超标量编程 101(矩阵相乘)第 5 部分(共 5 部分)

In 第 4 部分中,我们了解了在双核至强 5570 系统上用 QuickThread 并行标签转置组方法执行矩阵相乘的效果。这些双核至强 5570 系统配有 2 个插槽和 2 个 L3 高速缓存,每个高速缓存供 4 个核心(8 条线程)共享;每枚处理器配有 4 个 L2 高速缓存和 4 个 L1 高速缓存,每个高速缓存供 1 个核心和 2 条线程共享。我们发现:

图 18(第 4 部分的图 17)


英特尔多核测试实验室非常友好,为我使用他们的系统提供了一些时间。 /en-us/

在四处理器英特尔至强 7560上运行同一方法(无 Cilk++),每枚处理器配有 8 个核心和超线程技术(共 32 个核心,64 条线程),我们发现:

图 19


在该图表中,我们看不到扩展的平缓部分。这是因为在 N=2048 时的问题规模完全包含在系统高速缓存当中。请注意,以上图表代表着高速缓存密集型串行方法的扩展情况。

将这种方法与高速缓存密集型串行转置方法进行比较时,我们发现了一系列的不同结果:

图 20


N=1500 到 1700 范围内,斜率发生剧烈变化,主要是因为串行转置方法的参考数据性能显著下降,而不是 PTTx 中的性能提升。

对扩展系数(并行性能/硬件线程数)的分析结果通常决定着是否购买。我们看看下面的扩展系数图表:

图 21


我们发现,随着问题规模的增加,我们看到扩展系数有一个正斜率。太棒了!简直令人难以置信。请记住,这种串行方法既不是高速缓存密集型方法,也不是有效的对比基准。

当我们计算出相对于高速缓存友好型串行转置方法的扩展系数时,我们发现了完全不同的画面:

图 22


该图表将真正令你的程序员灰心丧气。经过一番努力,我们发现,对于高速缓存密集型串行转置方法的扩展系数直到 N = 1824 时才开始提供回报(系数大于 1)。

通过比较双核英特尔至强 5570 处理器的扩展系数与串行转置方法的扩展系数,我们发现:

图 23


正如预期的那样,两个系统都可以在不同的问题规模上实现超级扩展。这是因为每个系统上的高速缓存内存容量各不相同。

尽管购买的处理器越多,扩展系数提供的投资回报越高,但是当一个处理器架构与不同的处理器架构相比较时,它的扩展系数毫无意义。企业应当关注整体投资回报,而且这里面包括时间因素。

分析时间因素时,我们获得了完全不同的画面。比较最快的方法(带有 SSE 内置函数的 QuickThread 并行双打转置)时,我们发现:

图 24


将时间作为成本优势的决定因素考虑在内时,我们发现,当问题规模超出具体某个阈值(N = 1400)时,成本优势比就会出现一个相当大的转变。这里需要注意的是,评估购买决策时,要使用适当规模的测试案例。成本/优势比与性能曲线不总是适用于推断。

当我们用最快的方法(带有 SSE 内置函数的 QuickThread 并行双打转置)执行更大规模的矩阵时,我们发现:

图 25


N = 3000 到 4096 的矩阵可以由 4 枚处理器(32 个核心/64 条线程)处理,而更大规模的矩阵可能需要额外的处理器和/或改变方法。

结论:

最快的方法:带 SSE 内置函数的并行双打转置,依赖 QuickThread 按高速缓存级别近似值安排亲和性线程的能力。使用高速缓存敏感性协调工作的能力可以为你的优化策略带来巨大回报。

更大规模的矩阵可以由相同数量的处理器(4x8 核心,带超线程技术)结合将会产生额外开销的额外拼接(tiling)策略,通过改进的方法处理。这就是并行程序员经常用到的分治方法。

取 N = 5200 的矩阵,将其一分为二(两个轴),生成一个 N= 2600 的区块(tile)和 4 个类似区块。这需要 4 x 2 = 8 个使用小型区块的迭代。N = 2600 的矩阵完成计算大约需要 0.33 秒,因此估计的计算时间为 0.33 x 8 = 2.64。预计比合并方法快 10 倍,但是可能还不足以达到你的目的。

分治方法是最佳策略吗?

这取决于“最佳”的具体含义。

从编程工作的相对性能回报来讲,这可能是最佳策略。然而,在分析图 18(第 4 部分的图 17)和比较 Cilk++ 与 QuickThread 并行双打 XMM 方法时,我们已经证明,通过关注高速缓存局部性,具体而言就是 L1、L2 和 L3 高速缓存中的内容以及这些内容何时存在于高速缓存之中,你可以再获得 1.4 到 2.5 倍的性能提升。

我将尝试制定我认为可以有效利用系统高速缓存的策略。虽然以下图表不会显示具体的方法,但是它将演示一般处理计划。

当前的并行双打(转置)方法依据 L3 高速缓存划分工作,随后是 L2 高速缓存区域,接下来采用 L1 高速缓存友好型路径计算出结果。该策略在矩阵规模达到执行路径开始从 L3 高速缓存中驱逐数据时尤其有效。我假设采用一种与并行双打(转置)方法沿着同一路径执行的方法,但是对远离对角线的空间进行裁剪,你可以最大限度减少 L3 高速缓存驱逐。下图阐释了一个穿过当前 L3 工作区的经过裁剪的 L2 路径。


图 26


在以上图表中,一般执行路径沿着箭头方向。彩色(红色)单元是已经算出结果的输出单元。白色单元是还没有算出结果的输出单元。

在当前的并行双打(转置)方法中,以上所有单元都是彩色的,在针对大型矩阵推荐的方法中,处理对角线 N.B 时,裁剪技巧会限制被计算的输出单元与对角线之间的距离。上图是一个简化的 1P 系统。

处理大型矩阵时,如果计算包括空单元,那么计算首先会允许将 L2 高速缓存驱逐到 L3 高速缓存,然后达到某个规模时,再允许驱逐 L3 高速缓存。图 25 可能可以证实这一点(假设)。

图 27


在图 27(带箭头的图 25)中,红色箭头表示 L2 高速缓存驱逐,蓝色箭头表示 L3 高速缓存驱逐。


回到图 26。计算完图 26 中的输出单元时,我们会发现:

图 28


X 代表输出 L2 高速缓存区域中已经算出结果的单元。蓝色单元代表 m2t 阵列中的依然位于 L2 高速缓存中的列(存储为行),红色单元代表 m1 阵列中位于 L2 高速缓存中的行单元。此外,底部行中(不带颜色的)某些区域和最右侧的列依然位于 L1 高速缓存中。其余未标记 X 的白色单元可能在/不在 L3 高速缓存中。

下一个计算序列(需要验证)应当是图 29 中的箭头所指的序列:

图 29


当你沿着箭头方向朝第一个对角线移动时,输出矩阵的红色和蓝色顶端应当按交替序列处理。

在上文提到的分治方法(拼接)中,您可以处理 4 个小型区块,每个区块的处理速度提升两倍,或者小型区块的处理速度提升 8 倍(该区块规模可能最适合 L2 高速缓存)。拼接方法可以利用 L2 高速缓存中的剩余数据,带来 6 到 8 倍小型矩阵运行时,而不是 8 倍运行时间。

在推荐的方法(叫做交叉对角线)中,对于图 28 和图 29 中显示的规模范围,根据我先前使用并行双打转置方法的经验,估计可能会将小型矩阵的运行时间提升 1.5 到 2 倍。分治方法(拼接)可能是最佳方法,它可以将处理速度提升 4 倍。应当强调的一点是,实际差异可能不同于估计值。如上文所述,推断通常不会根据现有数据构成的曲线进行。

我希望我这一系列的文章可以为你提供深刻见解。本文未能详细描述 QuickThread 并行双打转置 XMM 方法,但是代码可以体现细节信息。如果你希望获得一份代码和 QuickThread 演示许可,请通过以下电子邮件地址与我联系。QuickThread 可以在 Windows 和 Linux 系统上运行。x32 和 x64 适用于 Windows,但只有 x64 适用于 Linux(Ubuntu 和 Red Hat)。

Jim Dempsey
jim@quickthreadprogramming.com
www.quickthreadprogramming.com

有关编译器优化的更完整信息,请参阅优化通知
类别: