Ich schreibe Implementierung von Sieve of Eratosthenes https: //en.wikipedia.org/wiki/Sieve_of_Eratosthene) auf der GPU. Aber so etwas gibt es nicht -http: //developer-resource.blogspot.com/2008/07/cuda-sieve-of-eratosthenes.htm

Methode

Erstellen eines n-Element-Arrays mit den Standardwerten 0/1 (0 - prime, 1 - no) und Weiterleiten an die GPU (ich weiß, dass dies direkt im Kernel möglich ist, aber in diesem Moment ist dies kein Problem).Jeder Thread im Block überprüft ein Vielfaches einer einzelnen Zahl. Jeder Block prüft die gesamten sqrt (n) Möglichkeiten. Jeder Block == anderes Intervall.Markieren Sie ein Vielfaches als 1 und übergeben Sie die Daten zurück an den Host.

Code

#include <stdio.h>
#include <stdlib.h>
#define THREADS 1024

__global__ void kernel(int *global, int threads) {
    extern __shared__ int cache[];

    int tid = threadIdx.x + 1;
    int offset = blockIdx.x * blockDim.x;
    int number = offset + tid;

    cache[tid - 1] = global[number];
    __syncthreads();

    int start = offset + 1;
    int end = offset + threads;

    for (int i = start; i <= end; i++) {
        if ((i != tid) && (tid != 1) && (i % tid == 0)) {
            cache[i - offset - 1] = 1;
        }
    }
    __syncthreads();
    global[number] = cache[tid - 1];
}


int main(int argc, char *argv[]) {
    int *array, *dev_array;
    int n = atol(argv[1]);
    int n_sqrt = floor(sqrt((double)n));

    size_t array_size = n * sizeof(int);
    array = (int*) malloc(n * sizeof(int));
    array[0] = 1;
    array[1] = 1;
    for (int i = 2; i < n; i++) {
        array[i] = 0;
    }

    cudaMalloc((void**)&dev_array, array_size);
    cudaMemcpy(dev_array, array, array_size, cudaMemcpyHostToDevice);

    int threads = min(n_sqrt, THREADS);
    int blocks = n / threads;
    int shared = threads * sizeof(int);
    kernel<<<blocks, threads, shared>>>(dev_array, threads);
    cudaMemcpy(array, dev_array, array_size, cudaMemcpyDeviceToHost);

    int count = 0;
    for (int i = 0; i < n; i++) {
        if (array[i] == 0) {
            count++;
        }
    }
    printf("Count: %d\n", count);
    return 0;
}

Run: ./sieve 10240000

Es funktioniert korrekt, wenn n = 16, 64, 1024, 102400 ..., aber für n = 10240000 erhalte ich ein falsches Ergebnis. Wo ist das Problem?