关于dnadist
Dnadist是Phylip的一个组件，是用来计算核酸序列相似度矩阵的一个程序。
This program uses nucleotide sequences to compute a distance matrix, under four different models of nucleotide substitution. It can also compute a table of similarity between the nucleotide sequences. The distance for each pair of species estimates the total branch length between the two species, and can be used in the distance matrix programs Fitch, Kitsch or Neighbor. This is an alternative to using the sequence data itself in the maximum likelihood program Dnaml or the parsimony program Dnapars.
寻找热点
找到耗时最长的过程是程序加速优化的基础。经过反复观察Profile, dnadist这个程序的热点和程序的输入参数大小是有关系的。Dnadist输入参数主要有基因序列数SPP，基因长度SITES，以下以SPPxSITES的形式说明测试数据的尺寸。
Fig1:100×1000000的热点图
Fig2:762×8107的热点图
使用CUDA优化的过程
一开始使用了模拟生成的数据得到了Fig1的热点，因此把优化重点放在了dnadist_sitesort这个过程，这个过程实际就是一个排序的过程。使用CUDA实现了一个基于合并排序(Mergesort)的基因排序后，100×1000000的模拟数据运行时间从107s减少到了84s。(应该注意的是合并排序并不是一种最快的CUDA排序方法，而且大量线程同步开销较大)
后来拿到两个真实的计算数据(762×8107, 1423×10372)后重新Profile了热点得到Fig2. 然后开始优化makev函数，makev函数被调用了N=SPP*(SPP-1)/2次，每次调用makev得到两个基因序列之间的距离。这N次调用是数据无关的，所以决定在GPU上并行的进行这N次调用。每个makev需要较大的空间存放临时计算结果，同时也有较多的临时变量和参，因此需要根据设备限制灵活安排。
| Device resource for one thread | Device Limit | Schedule | |
| 32-bit Register | ~80 | 16384/block | 128register/thread128threads/block |
| Shared memory | >64Bytes | 16384Bytes/block | |
| Global memory | >3*endsite*sizeof(double) | ~4GB/grid(Tesla C1060) | Dynamic |
Fig3
考虑到这个例子中每个makev函数之间没有数据通讯，在实验中还用OpenMP+CUDA在两块Tesla计算卡上进行的并行运算。
测试平台
| CPU | Intel i7 920 |
| RAM | 6GB |
| CUDA Device | 2 Tesla C1060 |
Fig4 测试平台
结果如下(括号后为加速比)
| Case | Original code on CPU | 1 Tesla C1060 | 2 Tesla C1060 |
| 762×8107 | 310s | 246s(1.26) | 118s(2.62) |
| 1423×10372 | 1260s | 994s(1.26) | 480s(2.62) |
Fig5 CUDA优化结果对比
使用OpenMP优化
在优化makev的过程可以看到，虽然N次makev调用间有很好的独立性可以在GPU上大规模并行，但是makev函数内部却有一个迭代判断的过程，这个过程在GPU上运行效率较低，导致CUDA优化后的程序加速比并不大，所以随后我又采用OpenMP在多线程上并行调用makev。测试平台同上（CPU为4核8线程），优化后的结果：
| Case | Original code on CPU (single thread) | OpenMP 8 threads |
| 762×8107 | 310s | 66s(4.7) |
| 1423×10372 | 1260s | 246s(5.1) |
Fig6 OpenMP优化结果
另外：
在Linux下Intel Compiler和GCC的多线程性能有较大差别
| Case | Original code(GCC) | Original code (Intel Compiler) | OpenMP(Intel Compiler) |
| 762×8107 | 310s | 299s(1.04) | 35s(8.85) |
| 1423×10372 | 1260s | 1238s(1.01) | 136s(9.2) |
0 Comments.