# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     name: python3
# ---

# + [markdown] id="view-in-github" colab_type="text"
# <a href="https://colab.research.google.com/github/Sanchitraina1999/LP-I/blob/master/HPC.ipynb" target="_parent"><img src="https://colab.research.google.com/assets/colab-badge.svg" alt="Open In Colab"/></a>

# + colab={"base_uri": "https://localhost:8080/"} id="ngAgintgFLNI" outputId="da3de206-79d2-4969-9962-02c34583a159"
# !wget https://developer.nvidia.com/compute/cuda/9.2/Prod/local_installers/cuda-repo-ubuntu1604-9-2-local_9.2.88-1_amd64 -O cuda-repo-ubuntu1604-9-2-local_9.2.88-1_amd64.deb
# !dpkg -i cuda-repo-ubuntu1604-9-2-local_9.2.88-1_amd64.deb
# !apt-get update
# !apt-get install cuda-9.2

# + colab={"base_uri": "https://localhost:8080/"} id="K_mKv1POigw7" outputId="479950c7-338a-4c86-ac62-0711b63963d2"
# !nvcc --version

# + [markdown] id="3CWqT8wEN-UY"
# A1: **a) Implement Parallel Reduction using Min, Max, Sum and Average
# operations.
# b) Write a CUDA program that, given an N-element vector, find-
# • The maximum element in the vector
# • The minimum element in the vector
# • The arithmetic mean of the vector
# • The standard deviation of the values in the vector
# Test for input N and generate a randomized vector V of length N (N should be large). The program should generate output as the two computed maximum values as well as the time taken to find each value.**

# + id="XcAwTB48NYs1"
code = """#include "bits/stdc++.h"
using namespace std;

#define N 8
size_t bytes;

__global__ void min(double *array, int n) {
    unsigned int id = blockDim.x * blockIdx.x + threadIdx.x;
    int step_size = 1;

    while(n > 0) {
        if(id < n) {
            int i = (int)id * step_size * 2;
            int j = i + step_size;
            if(array[i] > array[j])
                array[i] = array[j];
        }
        step_size = step_size*2;
        n = n/2;
    }
}

__global__ void max(double *array, int n) {
    unsigned int id = blockDim.x * blockIdx.x + threadIdx.x;
    int step_size = 1;

    while(n > 0) {
        if(id < n) {
            int i = (int)id * step_size * 2;
            int j = i + step_size;
            if(array[i] < array[j])
                array[i] = array[j];
        }
        step_size = step_size*2;
        n = n/2;
    }
}


__global__ void sum(double *array, int n) {
    unsigned int id = blockDim.x * blockIdx.x + threadIdx.x;
    int step_size = 1;

    while(n > 0) {
        if(id < n) {
            int i = (int)id * step_size * 2;
            int j = i + step_size;
            array[i] = array[i] + array[j];
        }
        step_size = step_size*2;
        n = n/2;
    }
}

__global__ void mean_diff_square(double* array, double avg, int n){
    unsigned int id = blockDim.x * blockIdx.x + threadIdx.x;
    if(id < n)
        array[id] = (array[id]-avg)*(array[id]-avg);
}

int main() {
    double *array = new double [N];
    cout<<"array: ";
    for(int i=0; i<N; i++){
        array[i] = rand()%97;
        cout<<array[i]<<" ";
    }
    cout<<endl;

    double result;
    double *d_array;
    bytes = N*sizeof(double); //calculate no. of bytes for array
    cudaMalloc(&d_array, bytes);

    //MIN
    cudaMemcpy(d_array, array, bytes, cudaMemcpyHostToDevice);
    min<<<1,N/2>>>(d_array,N/2);
    cudaDeviceSynchronize();
    cudaMemcpy(&result, d_array, sizeof(double), cudaMemcpyDeviceToHost);
    cout<<"min: "<<result<<endl;

    //MAX
    cudaMemcpy(d_array, array, bytes, cudaMemcpyHostToDevice);
    max<<<1,N/2>>>(d_array, N/2);
    cudaDeviceSynchronize();
    cudaMemcpy(&result, d_array, sizeof(double), cudaMemcpyDeviceToHost);
    cout<<"max: "<<result<<endl;

    //SUM
    cudaMemcpy(d_array, array, bytes, cudaMemcpyHostToDevice);
    sum<<<1,N/2>>>(d_array,N/2);
    cudaDeviceSynchronize();
    cudaMemcpy(&result, d_array, sizeof(double), cudaMemcpyDeviceToHost);
    cout<<"sum: "<<result<<endl;

    //AVG
    double avg = result/N;
    cout<<"avg: "<<avg<<endl;

    //STD
    cudaMemcpy(d_array, array, bytes, cudaMemcpyHostToDevice);
    mean_diff_square<<<1,N>>>(d_array, avg, N);
    cudaDeviceSynchronize();
    sum<<<1,N/2>>>(d_array,N/2);
    cudaDeviceSynchronize();
    cudaMemcpy(&result, d_array, sizeof(double), cudaMemcpyDeviceToHost);
    double variance = result/N;
    cout<<"std: "<<sqrt(variance)<<endl;

    cudaFree(d_array);
    return 0;
}"""

# + id="WpS_-EoSfC3R"
file = open("main.cu", "w")
file.write(code)
file.close()

# + id="P5AFtyghfMgt"
# !nvcc main.cu

# + colab={"base_uri": "https://localhost:8080/"} id="YeFz3AjofRuA" outputId="b8e9c597-eb97-4420-bebd-3240e639f12b"
# !./a.out

# + id="l8SOACEGf_ZH" colab={"base_uri": "https://localhost:8080/"} outputId="20cd47c7-d8f2-40ee-a49e-4c19d8f81abc"
# !nvprof ./a.out

# + [markdown] id="hZjz4bRAOX6r"
# A2:  **Vector and Matrix Operations-
# Design parallel algorithm to
# Add two large vectors
# Multiply Vector and Matrix
# Multiply two N × N arrays using n2 processors**
#

# + id="u0nglFybNYyt"
code="""#include "bits/stdc++.h"
using namespace std;

#define N 8
size_t bytes;

__global__ void vector_addition(int *a, int *b, int *c, int n){
    unsigned int idx = blockDim.x * blockIdx.x + threadIdx.x;
    if(idx < n)
        c[idx] = a[idx] + b[idx];
}

int main() {
    int *a = new int[N];
    cout<<"a: ";
    for(int i=0; i<N; i++){
        a[i] = rand()%97;
        cout<<a[i]<<" ";
    }
    cout<<endl;

    int *b = new int[N];
    cout<<"b: ";
    for(int i=0; i<N; i++){
        b[i] = rand()%97;
        cout<<b[i]<<" ";
    }
    cout<<endl;

    bytes = N*sizeof(int);

    int *d_a;
    cudaMalloc(&d_a, bytes);
    cudaMemcpy(d_a, a, bytes, cudaMemcpyHostToDevice);

    int *d_b;
    cudaMalloc(&d_b, bytes);
    cudaMemcpy(d_b, b, bytes, cudaMemcpyHostToDevice);

    int *c = new int[N]{0};
    int *d_c;
    cudaMalloc(&d_c, bytes);

    int threads = 64;
    int blocks = ceil(float(N)/float(threads));

    vector_addition<<<blocks,threads>>>(d_a, d_b, d_c, N);
    cudaDeviceSynchronize();
    cudaMemcpy(c, d_c, bytes, cudaMemcpyDeviceToHost);

    cout<<"c: ";
    for(int i=0; i<N; i++) cout<<c[i]<<" ";
    cout<<endl;

    cudaFree(d_a);
    cudaFree(d_b);
    cudaFree(d_c);
    return 0;
}
"""

# + id="r1AHTAiWlgmf"
file = open("main.cu", "w")
file.write(code)
file.close()

# + id="jW4SsMZMllga"
# !nvcc main.cu

# + colab={"base_uri": "https://localhost:8080/"} id="PKdVur8Jltda" outputId="e5a1cc01-cb96-4a65-9ee8-6f4b9f538ffb"
# !./a.out

# + colab={"base_uri": "https://localhost:8080/"} id="0SC_ehHOlx8W" outputId="61a47a8e-581a-4660-e713-a2d9e5782cea"
# !nvprof ./a.out

# + id="HkIsaSnxl4Pi"
code="""#include "bits/stdc++.h"
using namespace std;

#define N 8
#define M 4
size_t bytes;

// 1xN * NxM = 1xM
__global__ void vecmat_multiplication(int* vector, int* matrix, int* result, int n, int m){
    unsigned int idx = blockDim.x * blockIdx.x + threadIdx.x;
    if(idx < m){
        int sum = 0;
        for(int i=0; i<n; i++)
            sum += vector[i]*matrix[i*m+idx];

        result[idx] = sum;
    }
}

void print_grid(int* array, int n, int m){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++)
            cout<<array[i*m+j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

int main() {
    int *vector = new int[N];
    for(int i=0; i<N; i++)
        vector[i] = rand()%97;

    int *matrix = new int[N*M];
    for(int i=0; i<N*M; i++)
        matrix[i] = rand()%97;

    cout<<"vector:"<<endl;
    print_grid(vector, 1, N);

    cout<<"matrix:"<<endl;
    print_grid(matrix, N, M);

    int *d_vector;
    bytes = N*sizeof(int);
    cudaMalloc(&d_vector, bytes);
    cudaMemcpy(d_vector, vector, bytes, cudaMemcpyHostToDevice);

    int *d_matrix;
    bytes = N*M*sizeof(int);
    cudaMalloc(&d_matrix, bytes);
    cudaMemcpy(d_matrix, matrix, bytes, cudaMemcpyHostToDevice);

    int *result = new int[M]{0};
    int *d_result;
    bytes = M*sizeof(int);
    cudaMalloc(&d_result, bytes);

    int threads = 64;
    int blocks = ceil(float(M)/float(threads));

    vecmat_multiplication<<<blocks,threads>>>(d_vector, d_matrix, d_result, N, M);
    cudaDeviceSynchronize();

    bytes = M*sizeof(int);
    cudaMemcpy(result, d_result, bytes, cudaMemcpyDeviceToHost);

    cout<<"result:"<<endl;
    print_grid(result, 1, M);

    cudaFree(d_vector);
    cudaFree(d_matrix);
    cudaFree(d_result);
    return 0;
}
"""

# + id="391lbUbymLFS"
file = open("main.cu", "w")
file.write(code)
file.close()

# + id="-RyrrezqmUk_"
# !nvcc main.cu

# + colab={"base_uri": "https://localhost:8080/"} id="854Tg7ZDmYWw" outputId="579e8231-af06-475d-85a3-5e3b7f19618d"
# !./a.out

# + colab={"base_uri": "https://localhost:8080/"} id="y1cmN8EXmbs-" outputId="b7447612-c003-4033-f4ec-cd4df115bb35"
# !nvprof ./a.out

# + id="QOKResxDmfSg"
code="""#include "bits/stdc++.h"
using namespace std;

#define M 8
#define N 8
#define K 8
size_t bytes;

// MxN * NxK = MxK
__global__ void matrix_multiplication(int *a, int *b, int *c, int m, int n, int k){
    unsigned int row = blockIdx.y * blockIdx.y + threadIdx.y;
    unsigned int col = blockIdx.x * blockIdx.x + threadIdx.x;
    if(row<m && col<n){
        int sum = 0;
        for(int i=0; i<n; i++)
            sum += a[row*n+i] * b[i*k+col];

        c[row * k + col] = sum;
    }
}

void print_grid(int* array, int n, int m){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++)
            cout<<array[i*m+j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

int main() {
    int *a = new int[M*N];
    for(int i=0; i<M*N; i++)
        a[i] = rand()%97;

    int *b = new int[N*K];
    for(int i=0; i<N*K; i++)
        b[i] = rand()%97;

    cout<<"a:"<<endl;
    print_grid(a,M,N);

    cout<<"b:"<<endl;
    print_grid(b,N,K);

    int *d_a;
    bytes = M*N*sizeof(int);
    cudaMalloc(&d_a, bytes);
    cudaMemcpy(d_a, a, bytes, cudaMemcpyHostToDevice);

    int *d_b;
    bytes = N*K*sizeof(int);
    cudaMalloc(&d_b, bytes);
    cudaMemcpy(d_b, b, bytes, cudaMemcpyHostToDevice);

    int *c = new int[M*K]{0};
    int* d_c;
    bytes = M*K*sizeof(int);
    cudaMalloc(&d_c, bytes);

    unsigned int block_size = 32;
    unsigned int grid_size = ceil(max(M,K)*N/float(block_size));
    dim3 dim_grid(grid_size, grid_size);
    dim3 dim_block(block_size, block_size);

    matrix_multiplication<<<dim_grid,dim_block>>>(d_a, d_b, d_c, M, N ,K);
    cudaDeviceSynchronize();

    bytes = M*K*sizeof(int);
    cudaMemcpy(c, d_c, bytes, cudaMemcpyDeviceToHost);

    cout<<"result:"<<endl;
    print_grid(c,M,K);

    cudaFree(d_a);
    cudaFree(d_b);
    cudaFree(d_c);
    return 0;
}
"""

# + id="MrlqOQi_myLU"
file = open("main.cu", "w")
file.write(code)
file.close()

# + id="5cLnDqy1m1OQ"
# !nvcc main.cu

# + colab={"base_uri": "https://localhost:8080/"} id="unQ32sBmm3Bd" outputId="66429ff4-1948-4ab4-8667-ac87f6eb445a"
# !./a.out

# + colab={"base_uri": "https://localhost:8080/"} id="_afMcg6Ym7Zg" outputId="46e1ab10-df6e-412a-f529-acf78ec02f76"
# !nvprof ./a.out

# + [markdown] id="eu-SG0_WPoJC"
# A3. **Parallel Sorting Algorithms-
# For Bubble Sort and Merge Sort, based on existing sequential algorithms, design and implement parallel algorithms utilizing all resources available.**

# + [markdown] id="osntNZIRnaup"
# **BUBBLE SORT**

# + id="0oMNBIwGlkqe"
code="""
#include<omp.h>
#include<iostream>

using namespace std;
void swap(int * num1, int * num2) {
  int temp = * num1;
  * num1 = * num2;
  * num2 = temp;
}
int main() {
  int n = 10;
  int a[n];
  omp_set_num_threads(2);
  for (int i = 0; i < n; i++) {
    a[i] = rand() % 100;
  }
  for (int i = 0; i < n; i++)
    cout << " " << a[i];
  cout << endl;
  int i = 0, j = 0;
  int first = 0;
  double start, end;
  start = omp_get_wtime();
  for (i = 0; i < n - 1; i++) {
    first = i % 2;
    #pragma omp parallel for
    for (j = first; j < n - 1; j++) {
      if (a[j] > a[j + 1])
        swap( & a[j], & a[j + 1]);
    }
  }
  end = omp_get_wtime();
  cout << "Result(parallel) : " << endl;
  for (i = 0; i < n; i++)
    cout << " " << a[i];
  cout << endl;
  cout << "Time parallel = " << (end - start) << endl;
  return 0;
}
"""

# + id="S4Q5eEF1nujO"
file=open("code.cpp","w")
file.write(code)
file.close()

# + id="IJuHbVZon56-"
# !g++ -fopenmp code.cpp

# + colab={"base_uri": "https://localhost:8080/"} id="99iT2FcRn9BR" outputId="0d84f944-65a6-4010-bb05-85a379175032"
# !./a.out

# + colab={"base_uri": "https://localhost:8080/"} id="IZMVhiq7n_kq" outputId="ab2b0fe4-ec6b-4e5b-dfff-4c67e939cb31"
# !nvprof ./a.out

# + [markdown] id="fCk10t8boD5H"
# **MERGE SORT**

# + id="ywEgB6peoHuu"
code="""
#include<iostream>
#include<omp.h>

using namespace std;
void printArray(int * arr, int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
void merge(int * arr, int start, int mid, int end) {
  int len = (end - start) + 1;
  int temp[len];
  int cur = 0;
  int i = start;
  int j = mid + 1;
  while (i <= mid && j <= end) {
    if (arr[i] < arr[j]) {
      temp[cur] = arr[i];
      cur++;
      i++;
    } else {
      temp[cur] = arr[j];
      cur++;
      j++;
    }
  }
  if (i <= mid) {
    while (i <= mid) {
      temp[cur] = arr[i];
      i++;
      cur++;
    }
  } else if (j <= end) {
    while (j <= end) {
      temp[cur] = arr[j];
      j++;
      cur++;
    }
  }
  cur = 0;
  for (i = start; i <= end; i++) {
    arr[i] = temp[cur];
    cur++;
  }
}
void mergeSort(int * arr, int start, int end) {
  if (start < end) {
    int mid = (start + end) / 2;
    #pragma omp parallel sections 
    {
      #pragma omp section
      mergeSort(arr, start, mid);
      #pragma omp section
      mergeSort(arr, mid + 1, end);
    }
    merge(arr, start, mid, end);
  }
}
int main(int argc, char * argv[]) {
  int size = 10;
  int a[size];
  double start, end;
  omp_set_num_threads(2);
  for (int i = 0; i < size; i++) {
    a[i] = rand() % 100;
  }
  //int a[]= {7,33,5,5,23,111,75,34,77,121,120};
  for (int i = 0; i < size; i++)
    cout << " " << a[i];
  cout << endl;
  start = omp_get_wtime();
  mergeSort(a, 0, size - 1);
  cout<<"Sorted: ";
  printArray(a, size);
  end = omp_get_wtime();
  cout << "Time parallel = " << (end - start) << endl;
  return 0;
}
"""

# + id="Q92E4diqoZNL"
file=open("code.cpp","w")
file.write(code)
file.close()

# + id="ijjif79Iobvi"
# !g++ -fopenmp code.cpp

# + colab={"base_uri": "https://localhost:8080/"} id="xrM6rmE-od2O" outputId="720d3a9a-31ac-4b70-ae30-2e5c657b3582"
# !./a.out

# + colab={"base_uri": "https://localhost:8080/"} id="cz88AXOjo6KN" outputId="170d2605-8d79-49f3-a175-2a91ae7da9c1"
# !nvprof ./a.out

# + [markdown] id="yYi0voMzPvWv"
# A4. **Parallel Search Algorithm:
# Design and implement parallel algorithm utilizing all resources available for
# •1. Binary Search for Sorted Array
# •2. Best-First Search that (traversal of the graph to reach a target
# in the shortest possible path)**

# + [markdown] id="lGjYbcm-pZCY"
# **BINARY SEARCH**

# + colab={"base_uri": "https://localhost:8080/"} id="lC0oLWX9pfiK" outputId="2158c123-82fe-40fc-ee0b-098ba5981e1d"
# !mpiCC code.cpp
# !mpirun --allow-run-as-root -np 4 ./a.out

# + [markdown] id="xkuDIV3UArhq"
# **BEST_FIRST SEARCH**

# + colab={"base_uri": "https://localhost:8080/"} id="GSR5uArSAucm" outputId="63f35e7f-24ce-43b7-9d32-5040cce21e2c"
# !g++ -fopenmp bfs.cpp
# !./a.out

StarcoderdataJupyterScriptsDedupFiltered