GPU에서 통계 애플리케이션의 이 코드를 실행할 수 있습니까?
저는 배열에 약 1천만에서 3천만 개의 부동소수점 값을 포함하는 통계 애플리케이션을 연구하고 있습니다.
중첩 루프에서 배열에 대해 서로 다르지만 독립적인 계산을 수행하는 몇 가지 방법, 예:
Dictionary<float, int> noOfNumbers = new Dictionary<float, int>();
for (float x = 0f; x < 100f; x += 0.0001f) {
int noOfOccurrences = 0;
foreach (float y in largeFloatingPointArray) {
if (x == y) {
noOfOccurrences++;
}
}
noOfNumbers.Add(x, noOfOccurrences);
}
현재 응용 프로그램은 C#으로 작성되고 Intel CPU에서 실행되며 완료하는 데 몇 시간이 걸립니다.저는 GPU 프로그래밍 개념과 API에 대한 지식이 없기 때문에 다음과 같은 질문을 참조하십시오.
- GPU를 활용하여 이러한 계산 속도를 높일 수 있습니까?
- 예: 튜토리얼을 알고 있거나 샘플 코드(프로그래밍 언어는 중요하지 않음)를 받은 사람이 있습니까?
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 순차 버전
저는 방금 30,000,000개의 요소를 가진 배열에 대한 알고리즘을 20초 이내에 실행하는 이 단순한 버전을 만들었습니다(데이터를 생성하는 함수에 의해 소요되는 시간 포함).
이 단순한 버전은 먼저 플로트 배열을 정렬합니다.그런 다음 정렬된 배열을 검토하고 지정된 횟수를 확인합니다.value이 값은 배열에 표시된 다음 표시된 횟수와 함께 사전에 저장됩니다.
사용할 수 있습니다.sorted 대신에 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);
확실히 더 빠를 것입니다.
원본 게시물
저는 천만에서 삼천만 개의 부동 소수점 값을 포함하는 큰 배열을 가진 통계 애플리케이션을 연구하고 있습니다.
GPU를 활용하여 이러한 계산 속도를 높일 수 있습니까?
.달 전 저는 Dynamic 했습니다. 달 전 에 에 GPU 대 완 히 분 역 시 이 니 션 다 습 레 실 했 을 행 뮬 학 한 자 전 저 는 해 ▁a 니 다 습 했 ulation ▁on ▁an 한 , 실 ▁i 행 ▁molecular ▁gpu 에 달 ▁a▁ran중 입 쌍 사 이 의 힘 계 한 커 널 중 습 니 었 수 되 다 신 로 터 미 라 파 가 나 하 자 산 을 ▁parameter ▁as , 니 ▁one 다 습 었 ▁received , ▁of ▁kernels 입 ▁between ▁calcul ▁pairs ▁which ated ▁the ▁the6 로하하배열다하나나로 합니다.500,000총, 총합.3 달러는 두 배가 됩니다.(22 MB).
그래서 만약 당신이 그것을 넣을 계획이라면.30백만 개의 부동 소수점, 약114 MB글로벌 메모리의 경우 문제가 되지 않습니다.
당신의 경우, 계산 횟수가 문제가 될 수 있습니까?Molecular Dynamic (MD)에 대한 저의 경험에 근거하여, 저는 아니라고 말할 것입니다.순차적인 MD 버전은 다음과 같습니다.25이 GPU를 사용하는 하는 데 되는 시간 »45회의록.당신은 당신의 애플리케이션이 몇 시간이 걸렸다고 말했고, 코드 예제에서도 MD보다 부드러워 보입니다.
힘 계산 예제는 다음과 같습니다.
__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에서 코드의 간단한 예는 두 개의 2D 배열의 합일 수 있습니다.
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;
각 블록에는 다음이 있습니다.ID0N-1 수)이며, 각 은 (N개의 블록 수)를 가집니다.'X'가 있는 수ID0X-1.
- 각 스레드가 해당 스레드를 기반으로 계산할 루프 반복에 대한 를 제공합니다.
ID리고블록그.ID스레드가 있는 블록Dim.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: 롭 파머의 대중을 위한 슈퍼컴퓨팅은 훌륭하고 14편의 모든 것을 다룹니다.그것은 또한 다소 부드럽게 시작하기 때문에 꽤 초보자 친화적입니다.
기타 항목:
마지막 항목을 보면 CUDA를 배울 수 있는 많은 링크를 찾을 수 있습니다.
OpenCL: OpenCL 튜토리얼 | MacResearch
병렬 처리나 GPGPU에 대해서는 잘 모르지만, 이 구체적인 예에서는 입력 어레이를 100만 번 반복하는 것보다 한 번만 통과하면 많은 시간을 절약할 수 있습니다.대규모 데이터 세트의 경우 가능하면 일반적으로 단일 경로로 작업을 수행할 수 있습니다.여러 개의 독립적인 계산을 수행하는 경우에도 동일한 데이터 세트를 초과하는 경우 동일한 경로로 모든 계산을 수행하는 속도가 향상될 수 있습니다. 이러한 방식으로 더 나은 참조 지역을 얻을 수 있습니다.하지만 코드의 복잡성이 증가했기 때문에 그럴 가치가 없을 수도 있습니다.
게다가, 당신은 정말 그렇게 반복적으로 부동 소수점 숫자에 작은 양을 더하고 싶지 않을 것이고, 반올림 오차가 더해질 것이고 당신은 당신이 의도한 것을 얻지 못할 것입니다.입력이 반복 패턴과 일치하는지 확인하기 위해 아래 샘플에 if 문을 추가했지만 실제로 필요하지 않으면 생략합니다.
C#은 모르지만 샘플의 단일 패스 구현은 다음과 같습니다.
Dictionary<float, int> noOfNumbers = new Dictionary<float, int>();
foreach (float x in largeFloatingPointArray)
{
if (math.Truncate(x/0.0001f)*0.0001f == x)
{
if (noOfNumbers.ContainsKey(x))
noOfNumbers.Add(x, noOfNumbers[x]+1);
else
noOfNumbers.Add(x, 1);
}
}
이게 도움이 되길 바랍니다.
GPU를 활용하여 이러한 계산 속도를 높일 수 있습니까?
- 확실히 그렇습니다. 이러한 종류의 알고리즘은 일반적으로 GPU가 매우 잘하는 대규모 데이터 병렬 처리에 이상적인 후보입니다.
예: 튜토리얼을 알고 있거나 샘플 코드(프로그래밍 언어는 중요하지 않음)를 받은 사람이 있습니까?
GPGPU의 길을 가고 싶을 때는 CUDA 또는 OpenCL이라는 두 가지 대안이 있습니다.
CUDA는 많은 도구로 성숙하지만 NVidia GPU 중심입니다.
OpenCL은 NVidia 및 AMD GPU, CPU에서 실행되는 표준입니다.그래서 당신은 정말로 그것을 선호해야 합니다.
튜토리얼을 위해 Rob Farber의 코드 프로젝트에 대한 훌륭한 시리즈가 있습니다: http://www.codeproject.com/Articles/Rob-Farber#Articles .
특정 용도의 경우 OpenCL을 사용하여 제작된 히스토그램에 대한 샘플이 많습니다(많은 샘플이 영상 히스토그램이지만 원리는 동일합니다).
C#을 사용할 때 OpenCL과 같은 바인딩을 사용할 수 있습니다.넷 아니면 클라우드.
어레이가 너무 커서 GPU 메모리에 저장할 수 없는 경우에는 블록 분할하여 각 부품에 대해 OpenCL 커널을 쉽게 다시 실행할 수 있습니다.
위 포스터의 제안 외에도 여러 코어에서 병렬로 실행하려면 TPL(Task Parallel Library)을 사용합니다.
위의 예에서는 병렬을 사용할 수 있습니다.각 및 ConcurrentDictionary에 대해, 그러나 배열이 각각 사전을 생성하는 청크로 분할되어 단일 사전으로 축소되는 더 복잡한 맵 축소 설정은 더 나은 결과를 제공합니다.
모든 계산이 GPU 기능에 올바르게 매핑되는지는 모르겠지만, 계산을 GPU 코어에 매핑한 다음 부분 결과를 단일 결과로 줄이기 위해 지도 축소 알고리즘을 사용해야 하므로 덜 친숙한 플랫폼으로 이동하기 전에 CPU에서 이 작업을 수행하는 것이 좋습니다.
메모리에서 '더 큰 FloatingPointArray' 값을 검색해야 한다는 점을 고려할 때 GPU를 사용하는 것이 적합한지 확신할 수 없습니다.GPU가 자체 포함 계산에 더 적합한 것으로 알고 있습니다.
이 단일 프로세스 애플리케이션을 여러 시스템에서 실행되는 분산 애플리케이션으로 전환하고 알고리즘을 조정하면 사용 가능한 시스템 수에 따라 속도가 상당히 빨라질 것이라고 생각합니다.
당신은 고전적인 '분할과 정복' 접근법을 사용할 수 있습니다.제가 취할 일반적인 접근법은 다음과 같습니다.
하나의 시스템을 사용하여 'largeFloatingPointArray'를 해시 테이블 또는 데이터베이스로 사전 처리합니다.이 작업은 단일 경로로 수행됩니다.부동 소수점 값을 키로 사용하고 배열의 발생 횟수를 값으로 사용합니다.최악의 경우 각 값이 한 번만 발생하지만 그럴 가능성은 거의 없습니다.응용 프로그램이 실행될 때마다 large FloatingPointArray가 계속 변경되면 메모리 내 해시 테이블이 적합합니다.정적인 경우 테이블을 Berkeley DB와 같은 키 값 데이터베이스에 저장할 수 있습니다.이것을 '찾아보기' 시스템이라고 부릅니다.
다른 시스템에서는 이를 '메인'이라고 부르고, 작업 덩어리를 생성하여 N개의 시스템에 작업 항목을 '산포'하고, 사용 가능해지면 결과를 '수집'합니다.예를 들어 작업 항목은 시스템이 작업해야 하는 범위를 나타내는 두 개의 숫자만큼 단순할 수 있습니다.시스템이 작업을 완료하면 발생한 배열을 다시 전송하고 다른 작업 덩어리에서 작업할 준비가 됩니다.
큰 FloatingPoint Array를 통해 계속 반복하지 않기 때문에 성능이 향상됩니다.룩업 시스템이 병목 현상을 일으키는 경우 필요한 만큼의 시스템에 복제할 수 있습니다.
충분한 수의 시스템이 병렬로 작동하므로 처리 시간을 몇 분으로 줄일 수 있습니다.
저는 C에서 병렬 프로그래밍을 위한 컴파일러 작업을 하고 있습니다. 종종 마이크로서버라고 불리는 다중 코어 기반 시스템을 대상으로 하며, 시스템 내의 여러 '시스템 온 어 칩' 모듈을 사용하여 구축될 것입니다.ARM 모듈 공급업체로는 Calxeda, AMD, AMCC 등이 있습니다.인텔도 이와 유사한 제품을 제공할 것입니다.
저는 그러한 응용 프로그램에 사용될 수 있는 컴파일러 버전을 가지고 있습니다.컴파일러는 C 함수 프로토타입을 기반으로 여러 시스템에 걸쳐 프로세스 간 통신 코드(IPC)를 구현하는 C 네트워킹 코드를 생성합니다.사용 가능한 IPC 메커니즘 중 하나는 socket/tcp/ip입니다.
분산 솔루션 구현에 도움이 필요하면 기꺼이 논의하겠습니다.
2012년 11월 16일 추가.
저는 알고리즘에 대해 조금 더 생각해 보았습니다. 저는 이것이 한 번의 패스로 해야 한다고 생각합니다.그것은 C로 작성되어 있고 당신이 가지고 있는 것에 비해 매우 빠를 것입니다.
/*
* Convert the X range from 0f to 100f in steps of 0.0001f
* into a range of integers 0 to 1 + (100 * 10000) to use as an
* index into an array.
*/
#define X_MAX (1 + (100 * 10000))
/*
* Number of floats in largeFloatingPointArray needs to be defined
* below to be whatever your value is.
*/
#define LARGE_ARRAY_MAX (1000)
main()
{
int j, y, *noOfOccurances;
float *largeFloatingPointArray;
/*
* Allocate memory for largeFloatingPointArray and populate it.
*/
largeFloatingPointArray = (float *)malloc(LARGE_ARRAY_MAX * sizeof(float));
if (largeFloatingPointArray == 0) {
printf("out of memory\n");
exit(1);
}
/*
* Allocate memory to hold noOfOccurances. The index/10000 is the
* the floating point number. The contents is the count.
*
* E.g. noOfOccurances[12345] = 20, means 1.2345f occurs 20 times
* in largeFloatingPointArray.
*/
noOfOccurances = (int *)calloc(X_MAX, sizeof(int));
if (noOfOccurances == 0) {
printf("out of memory\n");
exit(1);
}
for (j = 0; j < LARGE_ARRAY_MAX; j++) {
y = (int)(largeFloatingPointArray[j] * 10000);
if (y >= 0 && y <= X_MAX) {
noOfOccurances[y]++;
}
}
}
언급URL : https://stackoverflow.com/questions/13301309/can-should-i-run-this-code-of-a-statistical-application-on-a-gpu
'programing' 카테고리의 다른 글
| 각 면에 2개의 Y 축이 있고 척도가 서로 다른 gg 그림 (0) | 2023.06.13 |
|---|---|
| 장기간 실행 중인 데이터베이스 작업을 취소하는 방법은 무엇입니까? (0) | 2023.06.13 |
| ActiveSheet(액티브 시트) 또는 Select(선택)를 사용하지 않고 여러 시트를 동시에 PDF로 내보내기 (0) | 2023.06.13 |
| 워드프레스 웹사이트에서 REST API를 활성화하려면 어떻게 해야 합니까? (0) | 2023.06.08 |
| 다른 ipynb 파일에서 ipynb 파일을 가져오시겠습니까? (0) | 2023.06.08 |