I have to parallel MergeSort an array and i only could do serial. I've read some papers and forums but can't figure out how to sort array on the GPU side only CPU side.
import pycuda.driver as drv
import pycuda.autoinit
from pycuda.compiler import SourceModule
import numpy as np
import time
mod = SourceModule(open("/home/pphs16/merge_vjezba.cu").read())
mergeGPU = mod.get_function("mergeGPU")
def mergeCPU_ekvGPU(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * (n1)
R = [0] * (n2)
for i in range(0, n1):
L[i] = arr[l + i]
for j in range(0, n2):
R[j] = arr[m + 1 + j]
i = 0
j = 0
k = l
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def mergeSortCPU_ekvGPU(arr, l, r):
if l < r:
# kao i (l+r)//2
m = l+(r-l)//2
# sortiranje pevi i druge polovice
mergeSortCPU_ekvGPU(arr, l, m)
mergeSortCPU_ekvGPU(arr, m+1, r)
mergeCPU_ekvGPU(arr, l, m, r)
# GPU sort
def mergeSortGPU(arr, l, r):
if l < r:
# isto kao (l+r)/2
m = l+(r-l)//2
# Sortiranje prve 2 polovice
mergeSortGPU(arr, l, m)
mergeSortGPU(arr, m + 1, r)
mergeGPU(drv.Out(gpu_rez), drv.In(arr), np.int32(l), np.int32(m), np.int32(r), block=(1,1,1), grid=(1,1))
arr = gpu_rez
# Glavni kod
#arr = [11, 99, 2, 15, 7, 38, 8, 55]
arr = np.random.randint(1, 20, 10).astype(np.int32)
print("\nZadani niz je: ")
print(arr)
print("Length: ", len(arr))
gpu_rez = np.empty(10).astype(np.int32)
start_time2 = time.time()
mergeSortGPU(arr, 0, len(arr) - 1)
end_time2 = time.time() - start_time2
start_time = time.time()
mergeSortCPU_ekvGPU(arr, 0, len(arr) - 1)
end_time = time.time() - start_time
print("\nSortirani niz GPU: \n", gpu_rez, '\nVrijeme na GPU: ', end_time2)
print("\nSortirani niz CPU: \n", arr, '\nVrijeme na CPU: ', end_time)
That's the CPU side in python and next code is my CUDA GPU side.
__global__ void mergeGPU(int *dest, int *src, int l, int m, int r)
{
__shared__ int cache[10];
const int tid = threadIdx.x;
cache[tid] = src[tid];
const size_t n1 = m - l + 1;
const size_t n2 = r - m;
int L[10], R[10];
for (int i = 0; i < n1; i++)
{
L[i] = src[l + i];
}
for (int j = 0; j < n2; j++)
{
R[j] = src[m + 1 + j];
}
int i, j, k;
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
src[k] = L[i];
i++;
}
else {
src[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
src[k] = L[i];
i++;
k++;
}
while (j < n2) {
src[k] = R[j];
j++;
k++;
}
/*
for (int n = 0; n < 500; k++)
{
dest[n] = src[n];
}
*/
src[tid] = cache[tid];
}
I tried to use threadIdx.x and other things also change block and grid numbers but no luck. Please help.