关于并行编程算法的问题

利用CUDA编程得到向量中的元素的最大值,同时得到处理这个最大值的线程号

LZ您好:

请您重新详细叙述您的问题,感谢配合。

祝您编码顺利~

呵呵好的,我在做找出一个向量中的最大值,和这个最大值在这个向量中的位置,
我的做法是先求出向量所有元素的平均值,比这个平均值小的让此位置处的元素为0,
做个循环知道求出最大值,和找到其位置,请问这样是不是速度最快的

LZ您好:

1:根据您新给出的问题叙述,您的问题可以适当进行并行化处理的。

2:无法评价您的实现方法,敬请谅解。

祝您好运~

显然这样不是最快的。

最快的方法我认为是这样的:

(1)将向量(假设有N个元素), 上M个线程处理,然后每个线程处理K个,求出这K个里面的最大值。
(2)现在每个线程都有一个可能的值,这个值至少在这个K个里面是最大的。
(3)现在您一共有M个可能的值了。最大的值必然在这M个值之中。

(4)上一个单block的kernel, 用上述的方法处理这M个值(假设您的block现在有M’个线程), 您将得到M’个可能的值了。(此M’和您的block形状有关,但应该不超过1024, 下文使用1024叙述)
(5)此block执行同步一次。
(6)使用1024个元素的shared memory中的数组,将这1024个值写入。然后大家开始规约:
线程0-511分别比较[512]-[1023]位置,进行大小选择。同步一次。
线程0-255分别比较[256]-[511]位置,进行大小选择。同步一次。
线程0-127分别比较[128]-[255]位置,进行大小选择。同步一次。

线程0-1分别比较[2]-[3]位置,进行大小选择。同步一次。
线程0比较[1]位置,进行最终选择。

如此您就知道最大值是什么了。无需您那样的麻烦,低效率。以及,在比较的过程中,别忘记保存索引编号(您需要的)。

您也可以采用其他变种方式进行比较。
举个例子说,可以合并到一个kernel中,每个warp分别进行多次线程独立的比较,然后在warp内部进行规约,而不是上文那样的将规约放到最后,这样虽然麻烦点,点可以提高总体效率。(其实提高不了太多的)。

以上方法请您参考。

我最初也是这么想的用归约,但是我发现这样做无法保存索引号


这个和是否保存索引号有关系么?
既然你可以:
if( a > b)
{
max = a;
}
为何你不可以顺便写上:
if( a > b)
{
num_max = a;
id_max = a_id;
}
呢?

你想想是吧。

呵呵,我做并行编程也不是很久,我现在有点不明白,在kernel函数的代码中定义一个变量来存放最大值的地址,每一个线程都会执行这个kernel代码,也就是每一个线程都会的到一个值写入这个变量中,最后这个变量的值是哪个线程的结果。如果是个共享型数组,这个好理解,但是是个变量该怎么理解,是不是这个if()中应该有线程ID的关系式的真伪来判断是否写入这个变量值

呵呵,我做并行编程也不是很久,我现在有点不明白,在kernel函数的代码中定义一个变量来存放最大值的地址,每一个线程都会执行这个kernel代码,也就是每一个线程都会的到一个值写入这个变量中,最后这个变量的值是哪个线程的结果。如果是个共享型数组,这个好理解,但是是个变量该怎么理解,是不是这个if()中应该有线程ID的关系式的真伪来判断是否写入这个变量值

LZ您好:

kernel的代码是每个线程都执行的,那么kernel里面直接定义的变量也自然是每个线程私有的。

祝您编码顺利~

我知道这是私有的,但是这个变量写不写入值,可以用他的Thread ID来判断那个线程写入那个不写入吧

global void zhuzhenwu(…)
{
int a; //这个a只能本线程写入

}

所以您的“我知道这是私有的,但是这个变量写不写入值,可以用他的Thread ID来判断那个线程写入那个不写入吧”问题无法理解。

随意您“怎么判断”,别的线程是写不到这里的(包括您试图&a, 然后将指针传给其他线程进行写入也没用)。

哦那您看看我对最大值,及位置提取是这么编的
//下一步找出大于20的数中的最大值,和位置
do
{
if(s_s[tid]<maxVa)
{
s_s[tid]=0;
}
__syncthreads();

    if(s_s[tid]!=0)
    {
	   atomicAdd((int*)&sum,1);
    }//求出不为零的个数
    __syncthreads();

	s_mid[tid]=s_s[tid];

	int i=blockIdx.x/2;
	while(i!=0)
	{
		if(tid<i)
		{
			s_mid[tid]+=s_mid[tid+i];
			__syncthreads();
			i/=2;
		}
	}
	if(tid==0)
	{
		maxVa=s_mid[0]/sum;
	}//归约求平均
}while(s_s[tid]<maxVa);

if(s_s[tid]!=0)
{
	thread=tid;
}

}

既然楼主对多个楼层的建议反复无视,始终坚持原始做法。

那么我无法提供任何参考意见了。

(显然的,你不尊重我,我不能尊重你)

呵呵,谢谢了,我按您的算法去编编试试