论文导读：基于图形处理器的并行邻接阵算法图形处理器用于通用计算的两个最重要的方面是算法的描述与数据的表示，本文从这两个方面来描述算法。有了数据的图形表示后调用文献［3］中的示例程序就可以实现前述并行算法。4结论受图形处理器用于通用计算的启示，基于图形处理器提出了一种新的邻接矩阵算法。
关键词：邻接矩阵，并行算法，图形处理器
1 引 言
邻接矩阵技术在图论、科学计算等领域有着极为广泛的应用[1,2,4],因此如何提高邻接矩阵中边的权值计算速度将是一个很有实际意义的工作。现代图形处理器中的图形流水线是可编程的,如最新的NVIDIAGT300就512有个流处理器，512个流处理器就意味着数据可以进行512路的并行运算，大大提升了数据运算的效率，且随着图形处理器性价比的提升,图形处理器已成为一个日益重要的处理器出现在普通PC上。因此,本文研究如何利用廉价但并行处理能力强大的图形处理器来解决常见的邻接矩阵的计算问题。论文格式。
2 基于图形处理器的并行邻接阵算法图形处理器用于通用计算的两个最重要的方面是算法的描述与数据的表示，本文从这两个方面来描述算法。
2.1 并行算法下面给出一种通过并行处理的方法实现的邻接矩阵算法.
令G=(V,E)是一个图，V ={v1,v2,…,vn}是顶点集，E是边集，各边权值这里暂定义为相连两点间欧几里德距离即
 （1）
其中i，j∈V，m为顶点的空间坐标。这里假定每个顶点有m维坐标即V1(x11,x12,…,x1m), V2(x21, x22,…,x2m),…, Vn(xn1, xn2,…,xnm)，则并行算法如下：
begin
for l =p to 1 step by – 1 do
forall processors Pi where 1 do
for k = to  do
for j = to  do
begin
compute the Euclidean distance dkjwhere
write dkj to the shared memory
end
end
2.2数据表示及处理如上所述本算法的核心是顶点间的欧几里德距离的计算，本文采用文献［2］的思想来实现图形处理器中的数据表示方法，首先,将要进行计算的顶点集组织成纹理图像。
假设有N 个顶点每个顶点有m维坐标即V1(x11,x12,…,x1m), V2(x21, x22,…,x2m),…, Vn(xn1, xn2,…,xnm)，被组织成图1 中的矩阵形式(称为数据点矩阵),其中:M表示矩阵的列数;L 表示矩阵的行数,N=M×L。论文格式。论文格式。矩阵中的元素a[m][n]对应于数据点V(m−1)×M+n,其中,1≤m≤L,1≤n≤M. 数据点的各个维度值将存储在各纹理点的各个通道内,由于每个纹理点限制( r, g, b,α)四个通道,高于四维的数据点将按每四维进行划分,存储在不同的纹理中。因此,一个矩阵对应于一个(或多个)纹理,并保证纹理中相同位置的纹理点对应于相同的数据点。对于不足四维的数据点,可以采用减少纹理通道的办法进行存储。
有了数据的图形表示后调用文献［3］中的示例程序就可以实现前述并行算法。
图1：数据在图形处理器中的转换
3实验分析本实验是在采用INTEL T5800 双核 CPU和NVIDIA GeForce 9300GS显卡的PC上进行。显卡具有512M内存，主机内存2G ，数据集采用文献[3]所用数据集。
实验采用的是在相同数据集下比较cpu和图形处理器运行上述算法所需时间，比较结果如图2所示
图2：CPU与GPU在不同数据集下运行时间
从图2可以看出在数据较小时CPU与GPU的运算时间相差不大，但随着数据集的增大GPU则体现其强大的并行处理能力。
4结论受图形处理器用于通用计算的启示，基于图形处理器提出了一种新的邻接矩阵算法。算法使得用普通PC完成高性能计算的任务成为了可能。此算法在有限的时间内完成了n顶点的图赋权邻接矩阵计算,为后述相关处理节约了时间。
参考文献:
[1]周水庚,胡运发 , 基于邻接矩阵的全文索引模型[J]. 软件学报,2002,13(10):1933-1942
[2]曹 锋, 周傲英 基于图形处理器的数据流快速聚类[J]. 软件学报，2007，18（2）291－302
[3]OWENS J. The GeForce 6series GPU architecture[ R ] / / GPU Gems 2: streaming architectures andtechnology trends1 [ S. l. ] : Nvidia 2005
[4]Lang X. Y. , Lu Z. H. , ChiX. B. . A parallel clusteringalgorithm of gene expression patterns. Chinese Journal of Computers, 2007,30(2) : 311-316
|
