UPDATE GPU版本
__global__ void hash (float *largeFloatingPointArray,int largeFloatingPointArraySize, int *dictionary, int size, int num_blocks)
{
int x = (threadIdx.x + blockIdx.x * blockDim.x); // Each thread of each block will
float y; // compute one (or more) floats
int noOfOccurrences = 0;
int a;
while(x < size) // While there is work to do each thread will:
{
dictionary[x] = 0; // Initialize the position in each it will work
noOfOccurrences = 0;
for(int j = 0 ;j < largeFloatingPointArraySize; j ++) // Search for floats
{ // that are equal
// to it assign float
y = largeFloatingPointArray[j]; // Take a candidate from the floats array
y *= 10000; // e.g if y = 0.0001f;
a = y + 0.5; // a = 1 + 0.5 = 1;
if (a == x) noOfOccurrences++;
}
dictionary[x] += noOfOccurrences; // Update in the dictionary
// the number of times that the float appears
x += blockDim.x * gridDim.x; // Update the position here the thread will work
}
}
这一次我只测试了更小的投入,因为我想知道我我的笔记本电脑。尽管如此,它确实奏效。但是,有必要进一步做睾丸检查。
UPDATE顺序版本
我只是做了,在不到20秒(已计数功能来生成数据)执行你的算法为3000万这个天真的版本。
基本上,它排序你的浮点数组。它将遍历已排序的数组,分析数组中连续出现的值的次数,然后将该值与其出现的次数一起放入字典中。
您可以使用排序映射,而不是我使用的unordered_map。
继承人的代码:
#include <stdio.h>
#include <stdlib.h>
#include "cuda.h"
#include <algorithm>
#include <string>
#include <iostream>
#include <tr1/unordered_map>
typedef std::tr1::unordered_map<float, int> Mymap;
void generator(float *data, long int size)
{
float LO = 0.0;
float HI = 100.0;
for(long int i = 0; i < size; i++)
data[i] = LO + (float)rand()/((float)RAND_MAX/(HI-LO));
}
void print_array(float *data, long int size)
{
for(long int i = 2; i < size; i++)
printf("%f\n",data[i]);
}
std::tr1::unordered_map<float, int> fill_dict(float *data, int size)
{
float previous = data[0];
int count = 1;
std::tr1::unordered_map<float, int> dict;
for(long int i = 1; i < size; i++)
{
if(previous == data[i])
count++;
else
{
dict.insert(Mymap::value_type(previous,count));
previous = data[i];
count = 1;
}
}
dict.insert(Mymap::value_type(previous,count)); // add the last member
return dict;
}
void printMAP(std::tr1::unordered_map<float, int> dict)
{
for(std::tr1::unordered_map<float, int>::iterator i = dict.begin(); i != dict.end(); i++)
{
std::cout << "key(string): " << i->first << ", value(int): " << i->second << std::endl;
}
}
int main(int argc, char** argv)
{
int size = 1000000;
if(argc > 1) size = atoi(argv[1]);
printf("Size = %d",size);
float data[size];
using namespace __gnu_cxx;
std::tr1::unordered_map<float, int> dict;
generator(data,size);
sort(data, data + size);
dict = fill_dict(data,size);
return 0;
}
如果您已经安装在你的机器图书馆推力,你应该这样做:
#include <thrust/sort.h>
thrust::sort(data, data + size);
,而不是这个
sort(data, data + size);
为了确保它会更快。
原贴
“我的工作具有大阵containin 10个统计应用 - 30百万浮点值的”。
“利用GPU加速这样的计算有可能(而且有意义)吗?”
是的。一个月前,我完全在GPU上进行了分子动力学模拟。内核之一计算粒子对之间的力,每个粒子接受6个阵列,每个阵列有500,000个双打,共有3百万双打(22 MB)。
所以你打算把30百万浮点数,这是约114 MB的全球内存,所以这不是一个问题,即使我的笔记本电脑有250MB。
在你的情况下计算的数量可能是一个问题?基于我对分子动态(MD)的经验,我说不。顺序MD版本需要大约25小时才能完成,而GPU需要45分钟。你说你的应用程序花了几个小时,也是基于你的代码示例,它看起来比分子动态更软。
这里的力计算示例:
__global__ void add(double *fx, double *fy, double *fz,
double *x, double *y, double *z,...){
int pos = (threadIdx.x + blockIdx.x * blockDim.x);
...
while(pos < particles)
{
for (i = 0; i < particles; i++)
{
if(//inside of the same radius)
{
// calculate force
}
}
pos += blockDim.x * gridDim.x;
}
}
的CUDA中的码的一个简单例子可以是两个二维数组的总和:
在C:
for(int i = 0; i < N; i++)
c[i] = a[i] + b[i];
CUDA中:
__global__ add(int *c, int *a, int*b, int N)
{
int pos = (threadIdx.x + blockIdx.x)
for(; i < N; pos +=blockDim.x)
c[pos] = a[pos] + b[pos];
}
CUDA中你基本上把每个迭代并除以每个线程,
1) threadIdx.x + blockIdx.x*blockDim.x;
每个块具有一个编号从0到N-1(N数最大的块),并且每个块具有螺纹的X个ID从0到X-1。
1)为每个线程根据id和线程所在的块ID计算迭代,blockDim.x是块所具有的线程数。
所以,如果你有2个街区,每一个有10个线程和N = 40,则:
Thread 0 Block 0 will execute pos 0
Thread 1 Block 0 will execute pos 1
...
Thread 9 Block 0 will execute pos 9
Thread 0 Block 1 will execute pos 10
....
Thread 9 Block 1 will execute pos 19
Thread 0 Block 0 will execute pos 20
...
Thread 0 Block 1 will execute pos 30
Thread 9 Block 1 will execute pos 39
寻找到你的代码,我做这个的,这可能是它在CUDA草案:
__global__ hash (float *largeFloatingPointArray, int *dictionary)
// You can turn the dictionary in one array of int
// here each position will represent the float
// Since x = 0f; x < 100f; x += 0.0001f
// you can associate each x to different position
// in the dictionary:
// pos 0 have the same meaning as 0f;
// pos 1 means float 0.0001f
// pos 2 means float 0.0002f ect.
// Then you use the int of each position
// to count how many times that "float" had appeared
int x = blockIdx.x; // Each block will take a different x to work
float y;
while(x < 1000000) // x < 100f (for incremental step of 0.0001f)
{
int noOfOccurrences = 0;
float z = converting_int_to_float(x); // This function will convert the x to the
// float like you use (x/0.0001)
// each thread of each block
// will takes the y from the array of largeFloatingPointArray
for(j = threadIdx.x; j < largeFloatingPointArraySize; j += blockDim.x)
{
y = largeFloatingPointArray[j];
if (z == y)
{
noOfOccurrences++;
}
}
if(threadIdx.x == 0) // Thread master will update the values
atomicAdd(&dictionary[x], noOfOccurrences);
__syncthreads();
}
您必须使用atomicAdd,因为不同块的不同线程可能会同时写入/读取noOfOccurrences,因此您必须确定互斥。
这只是一种方法,您甚至可以将外部循环的迭代转换为线程而不是块。
教程
的医生多布斯杂志由罗布农夫系列CUDA: Supercomputing for the masses优越,占地面积只是在其14个分期付款的一切。它也开始相当温和,因此相当适合初学者。
和anothers:
采取的最后一项一看,你会发现很多链接了解CUDA。
的OpenCL:OpenCL Tutorials | MacResearch
以任何机会,你有没有试过你的代码转换成C/C++?基于下面的代码片段,您正在使用C#。如果你的代码大部分时间都是为字典分配内存的话,我不会感到惊讶。 – Martin
不,但为字典分配内存只需要几ms或更少的时间,并且CPU使用率始终在93% - 98%之间,所以我认为在这种情况下内存不是(主要)性能问题。 – Mike
我真的认为你的代码应该在不使用GPU的情况下快速发展。您是否尝试过使用字典(预先分配所有内容)?不要使用foreach,而是使用。 GPU是矫枉过正的。用C重写整个事情,它会迫使你考虑内存分配。 – Martin