g**********t
发帖数: 475 | 1 我有一个程序要反复计算几百个（约500个）64 x 64的实对称矩阵的所有的
eigenvalues/eigenvectors。自己用CUDA实现了一个Jacobi algorithm with chess
tournament ordering。具体来说，每个block(含有32个threads)处理一个矩阵，这32
个threads并行消去一个矩阵中的32个off-diagonal elements，直到算法收敛。结果无
误，计算单个矩阵所花的时间也和最近的一篇paper里的数据接近。但是这个算法和CPU
上的library比没有太大的优势。在同时处理这500个矩阵的情况下，和GSL里面高度优
化的函数比较(用单CPU)，用GPU仅仅快了一倍。我觉得主要是Jacobi algorithm对于这
个大小的矩阵效率太差，而GSL里面的函数用的好像是QR decomposition，虽然只有一
个thread但是效率很高。有没有比较适合我的问题的能在GPU上高效执行的算法？有没
有什么paper/code可以参考的？先谢谢了。 |
s*****e
发帖数: 10 | 2 你的matrix太小了。小矩阵得计算，CPU上可以很好得cache，SIMD也能优化上，所以
GPU没有优势。
GPU计算得优势主要优势在于computation and memory access balance。或者说memory
access hidden. 如果同样得code CPU能很好得cach得话，GPU就没有比较大得优势了。
你这个计算，我觉得应该是3倍左右的提升，不知道为什么你才1倍。再优化试试。
32
CPU
【在 g**********t 的大作中提到】
: 我有一个程序要反复计算几百个（约500个）64 x 64的实对称矩阵的所有的
: eigenvalues/eigenvectors。自己用CUDA实现了一个Jacobi algorithm with chess
: tournament ordering。具体来说，每个block(含有32个threads)处理一个矩阵，这32
: 个threads并行消去一个矩阵中的32个off-diagonal elements，直到算法收敛。结果无
: 误，计算单个矩阵所花的时间也和最近的一篇paper里的数据接近。但是这个算法和CPU
: 上的library比没有太大的优势。在同时处理这500个矩阵的情况下，和GSL里面高度优
: 化的函数比较(用单CPU)，用GPU仅仅快了一倍。我觉得主要是Jacobi algorithm对于这
: 个大小的矩阵效率太差，而GSL里面的函数用的好像是QR decomposition，虽然只有一
: 个thread但是效率很高。有没有比较适合我的问题的能在GPU上高效执行的算法？有没
: 有什么paper/code可以参考的？先谢谢了。
|
I******c
发帖数: 163 | 3 我觉得也可以把矩阵放到shared memory里去啊。 |
I******c
发帖数: 163 | 4 如果一个数需要8byte去存贮的话，64*64的矩阵需要32kb的shared memory。现在的gpu
都有48kb／sm的shared memory了。 |
g**********t
发帖数: 475 | 5 我觉得主要是Jacobi method的效率太差了，虽然很容易并行，但是对于我这种大小的
矩阵，其他的算法，比如QR algorithm可能更合适。就拿计算单个64 x 64的矩阵来说
，GPU上我的程序(Jacobi method)实际比CPU(用GSL，貌似是QR decomposition类的算
法)慢6、7倍，只有在计算很多的矩阵时GPU才能快一倍(2x提升)。我觉得主要是Jacobi
method不大适合我的矩阵大小。不知道QR decomposition类的算法能不能在GPU上高效
实现？
memory
了。
【在 s*****e 的大作中提到】
: 你的matrix太小了。小矩阵得计算，CPU上可以很好得cache，SIMD也能优化上，所以
: GPU没有优势。
: GPU计算得优势主要优势在于computation and memory access balance。或者说memory
: access hidden. 如果同样得code CPU能很好得cach得话，GPU就没有比较大得优势了。
: 你这个计算，我觉得应该是3倍左右的提升，不知道为什么你才1倍。再优化试试。
:
: 32
: CPU
|
g**********t
发帖数: 475 | 6 矩阵是cache在shared memory里的，已经考虑了bank conflict。用的是单精度浮点，
cache了两个矩阵（一个放原始矩阵，一个放eigenvectors），大概用了32k的shared
memory。可能这也是个影响效率的原因，因为shared memory用的太多了，每个SM只能
launch一个block。
【在 I******c 的大作中提到】
: 我觉得也可以把矩阵放到shared memory里去啊。
|
s*****e
发帖数: 10 | 7 如果单个计算GPU是CPU的1／6， 那么throughput就大概是
GPU SM ＃ ／ CPU core ＃ ＊ ratio ＊ 8 ＝
16 ／4 ＊ 1／6 ＊ 8 ～＝ 5。 所以如果你把memory access hide 好的话，应该是4
到5倍。我做过这个类似的计算，实际就是大概3到4倍。你的程序还需要好好优化。特
别是这个8 blocks per sm.
从你下面的回帖，可以看出你对occupation没有很好的优化。
如果你是用CUDA 4.0的话，compiler帮你做了一些优化，所以你的效率大概是
5／8 ＊ 2 ～＝ 2 倍。make sense to your observation。 ：－）
Good luck
Jacobi
【在 g**********t 的大作中提到】
: 我觉得主要是Jacobi method的效率太差了，虽然很容易并行，但是对于我这种大小的
: 矩阵，其他的算法，比如QR algorithm可能更合适。就拿计算单个64 x 64的矩阵来说
: ，GPU上我的程序(Jacobi method)实际比CPU(用GSL，貌似是QR decomposition类的算
: 法)慢6、7倍，只有在计算很多的矩阵时GPU才能快一倍(2x提升)。我觉得主要是Jacobi
: method不大适合我的矩阵大小。不知道QR decomposition类的算法能不能在GPU上高效
: 实现？
:
: memory
: 了。
|
