含义和解决方法

为了值得使用多线程来优化该乘法运算,现在我们假设这些都有几千行和几千列的大矩阵。通常,非稀疏矩阵在内存中是用一个大数组表示的,第一行的所有元素后面是第二行的所有元素,以此类推。为了实现矩阵相乘,现在就有三个大数组了。为了获得更优的性能,你就需要注意数据存取部分,特别是第三个数组。

有很多在线程间划分工作的方法。假设你有比处理器更多的行例,那么你就可以让每个线程计算结果矩阵中某些列的值,或者让每个线程计算结果矩阵中某些行的值,或者甚至让每个线程计算结果矩阵中规则矩形子集的值。

回顾8.2.3节和8.2.4节,你就会发现读取数组中的相邻元素比到处读取数组中的值要好,因为这样减少了缓存使用以及假共享。如果你使每个线程处理一些列,那么就需要读取第一个矩阵中的所有元素以及第二个矩阵中相对应的列中元素,但是你只会得到列元素的值。假设矩阵是用行顺序存储的,这就意味着你从第一行中读取N个元素,从第二行中读取N个元素,以此类推(N的值是你处理的列的数目)。别的线程会读取每一行中别的元素,这就很清楚你应该读取相邻的的列,因此每行的N个元素就是相邻的,并且最小化了假共享。当然,如果这N个元素使用的空间与缓存线的数量相等的话,就不会有假共享,因为每个线程都会工作在独立的缓存线上。

另一方面,如果每个线程处理一些行元素,那么就需要读取第二个矩阵中的所有元素,以及第一个矩阵中相关的行元素,但是它只会得到行元素。因为矩阵是用行顺序存储的,因此你现在读取从N行开始的所有元素。如果你选择相邻的行,那么就意味着此线程是现在唯一对这N行写入的线程;它拥有内存中连续的块并且不会被别的线程访问。这就比让每个线程处理一些列元素更好,因为唯一可能产生假共享的地方就是一块的最后一些元素与下一个块的开始一些元素。但是值得花时间确认目标结构。

第三种选择一划分为矩形块如何呢?这可以被看做是先划分为列,然后划分为行。它与根据列元素划分一样存在假共享问题。如果你可以选择块的列数目来避免这种问题,那么从读这方面来说,划分为矩形块有这样的优点:你不需要读取任何一个完整的源矩阵。你只需要读取相关的目标矩阵的行与列的值。从具体方面来看,考虑两个1000行和1000列的矩阵相乘。就有一百万个元素。如果你有100个处理器,那么每个线程可以处理10行元素。尽管如此,为了计算这10000个元素,需要读取第二个矩阵的所有元素(一百万个元素)加上第一个矩阵相关行的10000个元素,总计1010000个元素;另一方面,如果每个线程处理100行100列的矩阵块(总计10000个元素) ,那么它们需要读取第一个矩阵的100行元素( 100 x 1000=100000元素)和第二个矩阵的100列元素(另一个100000个元素)。这就只有200000元素,将读取的元素数量降低到五分之一。如果你读取更少的元素,那么发生缓存未命中和更好性能的潜力的机会就更少了。

因此将结果矩阵划分为小的方块或者类似方块的矩阵比每个线程完全处理好几行更好。当然,你可以调整运行时每个块的大小,取决于矩阵的大小以及处理器的数量。如果性能很重要,基于目标结构分析各种选择是很重要的。

你也有可能不进行矩阵乘法,那么它是否适用呢?当你在线程间划分大块数据的时候,同样的原则也适用于这种情况。仔细观察数据读取方式,并且识别影响性能的潜在原因。在你遇到的问题也可能有相似的环境,就是只要改变工作划分方式可以提高性能而不需要改变基本算法。

好了,我们已经看到数组读取方式是如何影响性能的。其他数据结构类型呢?

8.3.2其他数据结构中的数据访问方式

从根本上说,当试图优化别的数据结构的数据访问模式时也是适用的。

1、在线程间改变数据分配,使得相邻的数据被同一个线程适用。

2、最小化任何给定线程需要的数据。

3、确保独立的线程访问的数据相隔足够远来避免假共享。

当然,运用到别的数据结构上是不容易的。例如,二叉树本来就很难用任何方式来再分,有用还是没用,取决于树是如何平衡的以及你需要将它划分为多少个部分。同样,树的本质意味着结点是动态分配的,并且最后在堆上不同地方。

现在,使数据最后在堆上不同地方本身不是一个特别的问题,但是这意味着处理器需要在缓存中保持更多东西。实际上这可以很有利。如果多个线程需要遍历树,那么它们都需要读取树的结点,但是如果树的结点至包含指向该结点持有数据的指针,那么当需要的时候,处理器就必须从内存中载入数据。如果线程正在修改需要的数据,这就可以避免结点数据与提供树结构的数据间的假共享带来的性能损失。

使用互斥元保护数据的时候也有同样的问题。假设你有一个简单的类,它包含一些数据项和一个互斥元来保护多线程读取。如果互斥元和数据项在内存中离得很近,对于使用此互斥元的线程来说就很好;它需要的数据已经在处理器缓存中了,因为为了修改互斥元已经将它载入了。但是它也有一个缺点:当第一个线程持有豆斥元的时候,如果别的线程试图锁住互斥元,它们就需要读取内存。互斥元的锁通常作为一个在互斥元内的存储单元上试图获取互斥元的读一修改一写原子操作来实现的,如果互斥元已经被锁的话,就接着调用操作系统内核。这个读一修改一写操作可能导致拥有互斥元的线程持有的缓存中的数据变得无效。只要使用互斥元,这就不是问题。尽管如此,如果互斥元和线程使用的数据共享同一个缓冲线,那么拥有此互斥元的线程的性能就会因为另一个线程试图锁住该互斥元而受到影响。

测试这种假共享是否是一个问题的方法就是在数据元素间增加可以被不同的线程并发读取的大块填充数据例如,你可以使用:



 

（编辑：宜春站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!