UPDATE GPU Versione
__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
}
}
Questo quello che ho appena provato per gli ingressi più piccoli, perché sto testando ho il mio computer portatile. Tuttavia, ha funzionato. Tuttavia, è necessario fare ulteriori testicoli.
UPDATE sequenziale Versione
Ho appena fatto questa versione ingenua che esegue l'algoritmo per 30 milioni in meno di 20 secondi (funzione già conteggio per generare dati).
Fondamentalmente, ordina la tua gamma di galleggianti. Percorrerà la matrice ordinata, analizzando il numero di volte in cui un valore appare consecutivamente nell'array e quindi inserirà questo valore in un dizionario insieme al numero di volte in cui appare.
È possibile utilizzare la mappa ordinata, anziché la unordered_map che ho utilizzato.
Heres il codice:
#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;
}
Se avete la spinta Libreria installata in te macchina che si dovrebbe usare questo:
#include <thrust/sort.h>
thrust::sort(data, data + size);
invece di questo
sort(data, data + size);
Di sicuro sarà più veloce.
originale Messaggio
"Sto lavorando su un'applicazione statistica che ha una vasta gamma contenent 10 - 30 milioni di valori in virgola mobile".
"È possibile (e ha senso) utilizzare una GPU per accelerare tali calcoli?"
Sì, lo è. Un mese fa ho inserito una simulazione Molecular Dynamic interamente sulla GPU. Uno dei kernel, che calcola la forza tra coppie di particelle, riceve 6 array ciascuno con 500.000 doppi, per un totale di 3 milioni di doppi (22 MB).
Così si sta pianificando di inserire 30 milioni di punti float, si tratta di circa 114 MB di memoria globale, quindi questo non è un problema, anche il mio portatile ha 250 MB.
Il numero di calcoli può essere un problema nel tuo caso? Sulla base della mia esperienza con la Molecular Dynamic (MD), dico di no. La versione sequenziale di MD richiede circa 25 ore per essere completata mentre in GPU sono necessari 45 minuti. Hai detto che la tua applicazione impiega un paio d'ore, anche in base all'esempio di codice che sembra più morbido rispetto alla Dinamica molecolare.
Ecco l'esempio di calcolo forza:
__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;
}
}
Un semplice esempio di codice nel Cuda potrebbe essere la somma di due matrici 2D:
In c:
for(int i = 0; i < N; i++)
c[i] = a[i] + b[i];
In 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];
}
In Cuda fondamentalmente preso ciascuno per iterazione e dividere per ciascun filo,
1) threadIdx.x + blockIdx.x*blockDim.x;
Ogni blocco avere un ID da 0 a N-1 (N il numero massimo di blocchi), e ciascun blocco hanno un numero X di fili con un id da 0 a X-1.
1) Fornisce l'iterazione che ogni thread calcolerà in base al suo id e al blocco id in cui si trova il thread, il blockDim.x è il numero di thread di un blocco.
Quindi, se si dispone di 2 blocchi ciascuna con 10 thread e un N = 40, il:
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
Guardando al tuo codice che ho fatto questa bozza di quello che potrebbe essere in 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();
}
Devi usare atomicAdd perché thread diversi da blocchi diversi possono scrivere/leggere noOfOccurrences allo stesso tempo, quindi devi essere sicuro dell'esclusione reciproca.
Questo è solo un approccio che è possibile fornire le iterazioni del ciclo esterno ai thread anziché ai blocchi.
Tutorial
Il Dr Dobbs Journal serie CUDA: Supercomputing for the masses da Rob Farmer è eccellente e copre quasi tutto nelle sue quattordici rate. Inizia anche piuttosto delicatamente ed è quindi abbastanza amichevole per i principianti.
e anothers:
Date un'occhiata sul l'ultimo elemento, si trovano molti link per saperne di CUDA.
OpenCL: OpenCL Tutorials | MacResearch
Per caso, hai provato a convertire il codice in C/C++? In base allo snippet di codice riportato di seguito, stai utilizzando C#. Non sarei sorpreso se il tuo codice impiegasse molto tempo ad allocare memoria per il dizionario. – Martin
No, ma l'allocazione della memoria per il dizionario richiede solo pochi ms o meno e l'utilizzo della CPU è sempre compreso tra 93% - 98%, quindi penso che la memoria non sia il problema di prestazioni (principale) in questo caso. – Mike
Penso davvero che il tuo codice dovrebbe essere velocissimo senza usare una GPU. Hai provato ad allontanarti dall'uso di un dizionario (preallocato di tutto). Non usare foreach ma per. GPU è eccessivo. Riscrivi tutto in C, ti costringerà a pensare all'assegnazione della memoria. – Martin