Implement a Parallel Quick Sort algorithm using NVIDIA GPU or equivalent ARM board.

Implement a Parallel Quick Sort algorithm using NVIDIA GPU or equivalent ARM board.

 

#include<stdio.h>


const int threshold=100;
const int m=10;
__global__ void selection_sort(int *data, int left, int right)
{
 int temp;
 //printf("in selection sort\n");
    for(int i=left; i < right;i++)
     for(int j=i+1;j < =right;j++)
      if(data[i] > data[j])
      {
       temp=data[i];
       data[i]=data[j];
       data[j]=temp;
      }
}

__global__ void partition(int *a,int left,int right,int pivot,int *al,int *ah)
{


 int l,h;
 int diff=(right-left+1)/m;
 int k1=threadIdx.x*diff+left;
 int k2=k1+diff-1;
 if(threadIdx.x==m-1)
  k2=right;
// printf("in partition %d %d and k1= %d  k2= %d \n",left,right,k1,k2);
 l=h=k1;
 for(int i=k1; i < =k2;i++)
  {
   al[i]=ah[i]=-999;
  }
 for(int i=k1; i < =k2;i++)
 {
  if(a[i] < pivot)
  {
   al[l++]=a[i];
  }
  else
  {
   if(a[i] > pivot)
   {
    ah[h++]=a[i];
   }
  }
 }


}
//__global__
void quicksort(int *a, const int left, const int right)
{
 //printf("in quick sort %d %d \n",left,right);
    if (right-left <= threshold)
    {
     int *ad;
     cudaMalloc((void **)&ad,(right-left+1)*sizeof(int));
     cudaMemcpy(ad,a,(right-left+1)*sizeof(int),cudaMemcpyHostToDevice);
        selection_sort<<<1,1>>>(ad, left, right);
        cudaMemcpy(a,ad,(right-left+1)*sizeof(int),cudaMemcpyDeviceToHost);
        return;
    }
    int pivot=a[left];
    int *al,*ah;
    int *ad;
    cudaMalloc((void **)&ad,(right-left+1)*sizeof(int));
    cudaMalloc((void **)&al,(right-left+1)*sizeof(int));
    cudaMalloc((void **)&ah,(right-left+1)*sizeof(int));

    cudaMemcpy(ad,a,(right-left+1)*sizeof(int),cudaMemcpyHostToDevice);

    partition<<<1,m>>>(ad,left,right,pivot,al,ah);

    int al_h[right-left+1],ah_h[right-left+1];

        cudaMemcpy(al_h,al,(right-left+1)*sizeof(int),cudaMemcpyDeviceToHost);

        cudaMemcpy(ah_h,ah,(right-left+1)*sizeof(int),cudaMemcpyDeviceToHost);

    int i=0,k=0;

    while(i < right-left+1)
    {
     while(al_h[i]==-999 && i < right-left+1)
       i++;
     while(al_h[i]!=-999 && i < right-left+1)
     {
      al_h[k++]=al_h[i++];
     }
    }


    //quicksort<<<1,1>>>(al,0,k-1);
    quicksort(al_h,0,k-1);
    int p=left;
    int x=0;
   // printf("array al");
        while(x < k)
        {
         a[p++]=al_h[x++];
         //printf("%d  ",a[p]);

        }
        a[p]=pivot;
    i=0;
    k=0;
    while(i < right-left+1)
    {
       while(ah_h[i]==-999 && i < right-left+1)
      i++;
        while(ah_h[i]!=-999 && i < right-left+1)
        {
         ah_h[k++]=ah_h[i++];
        }
    }
    //quicksort<<<1,1>>>(ah,0,k-1);
    quicksort(ah_h,0,k-1);
    i=0;
    p++;
        while(i < k)
        {
         a[p++]=ah_h[i++];

        }
if(p-1!=right)
{
 printf("\nsome thing wrong %d %d\n",p,right);
}
}

void qsort(int *a,int n)
{
 //quicksort<<< 1, 1 >>>(a, 0,n-1);
 //printf("in qsort\n");
 quicksort(a, 0,n-1);

}

int main()
{
 int n = 20;
 int a[20];
 time_t t;
    srand((unsigned)time(&t));


    int x,flag;
    for (unsigned i = 0 ; i < n ; i++)
    {
     x=rand()%n;
     flag=0;
     for(int j=0;j < i;j++)
     {
      if(a[j]==x)
      {
       i--;
       flag=1;
       break;
      }

     }
     if(flag==0)
      a[i]=x;
    }
    printf("\n\n original array\n");
    for(int i=0; i < n;i++)
     printf("%d\t ",a[i]);
    quicksort(a,0,n-1);
    printf("\n\n after sorting\n");
    for(int i=0; i < n;i++)
         printf("%d\t ",a[i]);


}
/*
 * output:
 * original array
7  6  4  16  8  14  10  17  2  9  1  15  19  18  11  0  5  3  12  13

 after sorting
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19
 */

Write an application to and demonstrate the change in BeagleBoard/ ARM Cortex A5 /Microprocessor /CPU frequency or square wave of programmable frequency

Write an application to and demonstrate the change in BeagleBoard/ ARM Cortex A5 /Microprocessor /CPU frequency or square wave of programmable frequency

 

#include<stdlib.h> //System() Function
#include<signal.h> //signal Handler for CNTR-C
#include<iostream>  //cout , cin
#include<string>    //string 
#include<conio.h>

using namespace std;
void delay(int num);  

int main()
{
int option;
string frq;
string command;

while(1)
        {
                                                                                
cout <<  "\n1.  Press 1 to set the Beagle Board CPU Frequency\n";               
cout <<  "2.  Press 2 to get the current CPU Frequency\n";                      
cout <<  "3.  Press 3 or CNTR-Z to exit\n";                                     
cin > >  option;                                                                  
                                                                                
switch(option)                                                                  
        {                                                                       
        case 1:                                                                 
                cout << "Please Enter the frequency in range 100-1000 (MHz)\n"; 
                cin > >  frq;                                                     
                command="cpufreq-set -f "+frq+"MHz";                            
                                                                                
                if(system(command.c_str()))                                     
                cout << "\nCannot Set the Frequency. Make sure logged in as ROOT\n";
                                                                                
                                                                                
                                                                                
        case 2:                                                                 
                                                           
                while(!kbhit())                                              
                {                                                               
                        cout << "Press any key to go Back in main menu \n";         
                                                                                
                        system("cpufreq-info | tail -2");                       
                        delay(50000);                                           
                }                                                               
        break;                                                                  
        case 3:                                                                 
                exit(0);                                                        
                                                                                
        }                                                                       
        }                                                                       
}                                                                               
void delay(int num)                                                             
{                                                                               
        int i,j;                                                                
        for(i=0; i < num;i++)                                                      
                for(j=0; j < 1275;j++);                                            
} 
OUTPUT:-
root@beaglebone:/home/debian# g++ -o cpu cpu.cpp
Cannot create temporary file in ./: Read-only file system
Aborted
root@beaglebone:/home/debian# ./cpu

1.  Press 1 to set the Beagle Board CPU Frequency
2.  Press 2 to get the current CPU Frequency
3.  Press 3 or CNTR-Z to exit
2
Press CNTR+C to Back in main menu 
  current CPU frequency is 300 MHz (asserted by call to hardware).
  cpufreq stats: 300 MHz:70.37%, 600 MHz:16.56%, 800 MHz:0.09%, 1000 MHz:12.98%)
Press CNTR+C to Back in main menu 
  current CPU frequency is 300 MHz (asserted by call to hardware).
  cpufreq stats: 300 MHz:70.40%, 600 MHz:16.55%, 800 MHz:0.09%, 1000 MHz:12.96%)
^C
1.  Press 1 to set the Beagle Board CPU Frequency
2.  Press 2 to get the current CPU Frequency
3.  Press 3 or CNTR-Z to exit
1
Please Enter the frequency in range 100-1000 (MHz)
600
Press CNTR+C to Back in main menu 
  current CPU frequency is 600 MHz (asserted by call to hardware).              
  cpufreq stats: 300 MHz:70.62%, 600 MHz:16.42%, 800 MHz:0.09%, 1000 MHz:12.87%)
Press CNTR+C to Back in main menu                                               
  current CPU frequency is 600 MHz (asserted by call to hardware).              
  cpufreq stats: 300 MHz:70.58%, 600 MHz:16.47%, 800 MHz:0.09%, 1000 MHz:12.86%)
^C                                                                              
1.  Press 1 to set the Beagle Board CPU Frequency                               
2.  Press 2 to get the current CPU Frequency                                    
3.  Press 3 or CNTR-Z to exit                                                   
3                                                                               
root@beaglebone:/home/debian# ^C                                                
root@beaglebone:/home/debian# 

Implement n-ary search algorithm using OPENMP

Implement n-ary search algorithm using OPENMP

 

#include<stdio.h>
#include<omp.h>
int e,n;
int newarr[100];

int nary(int arr[],int s);

int main(){
const int s;
printf("Enter the size of the array u wish :");
scanf("%d",&s);
printf("Enter the array in ascending order : \n");
int arr[s];
int i=0;
for(i=0; i < s;i++)
scanf("%d",&arr[i]);
                                                    
printf("Enter the element to be searched: \n");
scanf("%d",&e);
X:
printf("Enter the value of n :");
scanf("%d",&n);
if(n > s)
{
printf("Value of n exceeds size of array!\n");
goto X;
}
int ans=nary(arr,s);
if(ans==0)
printf("Value not found in the given array.\n");
else
printf("The value has been successfully found !\n");
return 0;
}

int nary(int arr[],int s)
{
if(arr[0]==e)
return 1;

if(s/n==0)
return 0;
#pragma omp parallel num_threads(n)
{
int tid= omp_get_thread_num();
int t=0,k=0,i=0;
 for(i=0; i < s; i=i+(s/n))
  if(t==tid && (arr[i] < =e && arr[(i+s/n)-1] > =e))//allotting nodes to different threads & if value lies in the given thread set.
   for(k=0; k < (s/n);k++) 
    newarr[k]=arr[k+i];//extract the thread set elements.    
 t++;
}
nary(newarr,s/n);//recursive call to the function 
}

---------OUTPUT-------------

Output--

[estudymoney@localhost ~]$ gcc -o finalnary -fopenmp finalnary.c
[estudymoney@localhost ~]$ ./finalnary
Enter the size of the array u wish :9
Enter the array in ascending order : 
1
2
3
4
5
6
7
8
9
Enter the element to be searched: 
8
Enter the value of n :3
The value has been successfully found !

Implement nxn matrix parallel multiplication using CUDA/OpenCL GPU, use shared memory

Implement nxn matrix parallel multiplication using CUDA/OpenCL GPU, use shared memory

 

#include<stdio.h>

#includelt;math.h>

#define TILE_WIDTH 2

/*matrix multiplication kernels*/

//non shared
__global__ void
MatrixMul( int *Md , int *Nd , int *Pd , const int WIDTH )
{

           // calculate thread id

           unsigned int col = TILE_WIDTH*blockIdx.x + threadIdx.x ;

           unsigned int row = TILE_WIDTH*blockIdx.y + threadIdx.y ;

           Pd[row*WIDTH + col]=0;

         for (int k = 0 ; k<WIDTH ; k++ )
         {
                  Pd[row*WIDTH + col]+= Md[row * WIDTH + k ] * Nd[ k * WIDTH + col] ;
          }

}


// main routine
int main ()
{
   const int WIDTH = 2 ;
   int array1_h[WIDTH][WIDTH] ,array2_h[WIDTH][WIDTH],result_array_h[WIDTH][WIDTH];
  int *array1_d , *array2_d ,*result_array_d ; // device array
  int i , j ;
  //input in host array
  printf("Enter matrix1\n");
  for ( i = 0 ; i < WIDTH ; i++ )
  {
     for (j = 0 ; j < WIDTH ; j++ )
     {
        scanf("%d",&array1_h[i][j]);

     }
  }
  printf("Enter matrix2\n");
    for ( i = 0 ; i < WIDTH ; i++ )
    {
       for (j = 0 ; j < WIDTH ; j++ )
       {
          scanf("%d",&array2_h[i][j]);

       }
    }

  //create device array cudaMalloc ( (void **)&array_name, sizeofmatrixinbytes) ;

  cudaMalloc((void **) &array1_d , WIDTH*WIDTH*sizeof (int) ) ;

  cudaMalloc((void **) &array2_d , WIDTH*WIDTH*sizeof (int) ) ;




  //copy host array to device array; cudaMemcpy ( dest , source , WIDTH , direction )

  cudaMemcpy ( array1_d , array1_h , WIDTH*WIDTH*sizeof (int) , cudaMemcpyHostToDevice ) ;

  cudaMemcpy ( array2_d , array2_h , WIDTH*WIDTH*sizeof (int) , cudaMemcpyHostToDevice ) ;



  //allocating memory for resultent device array

  cudaMalloc((void **) &result_array_d , WIDTH*WIDTH*sizeof (int) ) ;





  //calling kernal

  dim3 dimGrid ( WIDTH/TILE_WIDTH , WIDTH/TILE_WIDTH ,1 ) ;

  dim3 dimBlock( TILE_WIDTH, TILE_WIDTH, 1 ) ;
  MatrixMul <<<dimGrid,dimBlock>>> ( array1_d , array2_d ,result_array_d , WIDTH) ;



  cudaMemcpy(result_array_h , result_array_d , WIDTH*WIDTH*sizeof(int) ,cudaMemcpyDeviceToHost) ;

  //printf the result array
  printf("matrix 1\n");
  for ( i = 0 ; i <  WIDTH ; i++ )
   {
       for ( j = 0 ; j < WIDTH ; j++ )
      {
         printf ("%d   ",array1_h[i][j] ) ;
      }
  printf ("\n") ;
 }
  printf("matrix 2\n");
  for ( i = 0 ; i < WIDTH ; i++ )
   {
       for ( j = 0 ; j < WIDTH ; j++ )
      {
         printf ("%d   ",array2_h[i][j] ) ;
      }
  printf ("\n") ;
 }
  printf("matrix result\n");
  for ( i = 0 ; i < WIDTH ; i++ )
  {
      for ( j = 0 ; j < WIDTH ; j++ )
     {
        printf ("%d   ",result_array_h[i][j] ) ;
     }
 printf ("\n") ;
}
 system("pause") ;
}
/*
 output:
 Enter matrix1
1 1 1 1
Enter matrix2

1 1 1 1
matrix 1
1   1
1   1
matrix 2
1   1
1   1
matrix result
2   2
2   2
 */

Vedic Mathematics method to find square of 2-digit number is used in a distributed programming. Use shared memory and distributed (multi-CPU) programming to complete the task.

 

shm-client - client program to demonstrate shared memory.

#include<sys/types.h>
#include<sys/ipc.h>
#include<sys/shm.h>
#include<stdio.h>
#include<unistd.h>
#include<string.h>
 

#define SHMSZ     27

int main()
{
    int shmid;
    key_t key;
    char *shm, *s;

    /*
     * We need to get the segment named
     * "5678", created by the server.
     */
    key = 5678;

    /*
     * Locate the segment.
     */
    if ((shmid = shmget(key, SHMSZ, 0666)) < 0) {
        perror("shmget");
        return 1;
    }

    /*
     * Now we attach the segment to our data space.
     */
    if ((shm = shmat(shmid, NULL, 0)) == (char *) -1) {
        perror("shmat");
        return 1;
    }

     int i,n1;
     char n;
   s=shm;
     printf("Enter a 2 digit number : ");
     
     scanf("%2d",&n1);
     
     n=(char)n1;
     
     
     
     s++;
     *s=n;
     *shm='*';
     
     while (*shm != '%')
        sleep(1);
     s=shm;
     s++;
    for (i=0; *s != NULL && i < 4;i++){
        printf("%c",*s);
        s++;
        }
    putchar('\n');

    /*
     * Finally, change the first character of the 
     * segment to '*', indicating we have read 
     * the segment.
     */
    *shm = '$';

    return 0;
}

/*
OUTPUT-CLIENT SIDE
[root@localhost vedic]# gcc shmcli.c
[root@localhost vedic]# ./a.out
Enter a 2 digit number : 14
0196

[student@localhost vedic]$ ./a.out
Enter a 2 digit number : 34
1156



*/server side

#include<sys/types.h>
#include<sys/ipc.h>
#include<sys/shm.h>
#include<stdio.h>
#include<unistd.h>
#include<string.h>
 

#define SHMSZ     27

int main()
{
    char c;
    int shmid;
    key_t key;
    char *shm, *s;
 int i,n=52;
    /*
     * We'll name our shared memory segment
     * "5678".
     */
    key = 5678;

    /*
     * Create the segment.
     */
    if ((shmid = shmget(key, SHMSZ, IPC_CREAT | 0666)) < 0) {
        perror("shmget");
        return 1;
    }

    /*
     * Now we attach the segment to our data space.
     */
    if ((shm = shmat(shmid, NULL, 0)) == NULL) {
        perror("shmat");
        return 1;
    }
    
   
     while (*shm != '*')
        sleep(1);
    s = shm;
 
   s++;
   char m=*s;
  
   n=(int)m;
  
    int r=square(n);// called function square function 
    s=shm;
    s++;
    
    int a=1000;
    for (i=0;i < 4;i++){
        *s = (char)(r/a+48);
        r=r%a;
        a=a/10;
        s++;
        }
    s = NULL;
    *shm='%';
   
    while (*shm != '$')
        sleep(1);

    return 0;
}
int square(int n){
 int a,b;
 a=n/10;
 b=n%10;
 int res=a*a*100+a*b*2*10+b*b;
 return res;
}
/*
OUTPUT SERVER SIDE
[root@localhost vedic]# gcc shmser.c
[root@localhost vedic]# ./a.out

*/
--------OUTPUT---------



vedic_op_server:
[estudymoney@localhost ~]# gcc shmser.c
[estudymoney@localhost ~]# ./a.out
[estudymoney@localhost ~]# 


vedic_op_client
[estudymoney@localhost ~]# gedit shmcli.c
[estudymoney@localhost ~]# gcc shmcli.c
shmcli.c: In function ‘main’:
shmcli.c:61:18: warning: comparison between pointer and integer [enabled by default]
     for (i=0; *s != NULL && i < 4;i++){
                  ^
[estudymoney@localhost ~]# ./a.out
Enter a 2 digit number : 12
0144
[estudymoney@localhost ~]# 

Write an application to parse input text file concurrently and compare the result of concurrent parsing with serial parsing ( Use concurrent YACC parser)

Write an application to parse input text file concurrently and compare the result of concurrent parsing with serial parsing ( Use concurrent YACC parser).

 

file1

 ((a+b)*c)

file2

((a+b)*c

file3

((a+b)*c)()

 lex.l

 %option reentrant
%option bison-bridge
%option noyywrap
%option bison-locations
%{
  #include "parser.h"

%}

%%


"(" { return (LPAREN); }
")" { return (RPAREN); }
\n {return(N);}
.|[ \t]+   { }
%%


main.c

 #include "parser.h"
#include "lexer.h"
//to read filenames for parsing
struct fname
{
  char fn[10];
};

//to store temp. result of scanner
 struct pwc {
   char op[20];
 };


int main(int argc, char **argv) {
  int result,n,i;
  struct fname file[10];
  struct pwc mypwc;
  yyscan_t scanner; 
  FILE *f;
  yylex_init(&scanner);
  printf("\n enter no. of files:");
  scanf("%d",&n);
  printf("\n enter file names:");
  for(i=0;i<n;i++)
  {
    scanf("%s",file[i].fn);
  }

  for(i=0;i<n;i++)
  {
    printf("fname=%s ",file[i].fn);
  }


pars.y

%define api.pure true
%locations
%token-table
%glr-parser
%lex-param {void *scanner}
%parse-param {void *scanner}

%{
/* your top code here */
#include<omp.h>
int t;
%}

%token LPAREN
%token RPAREN
%token N

%%

document  :
         | document exprs N {printf("\n successful parsing by thread ID=%d\n",omp_get_thread_num()); }
;
exprs
    :
    | expr exprs
;
expr
    : parens
;
parens
    : LPAREN exprs RPAREN
;

%%

int yyerror() {
    printf("\nparse error: thread ID=%d\n",omp_get_thread_num());

}


Execution Steps


[student@localhost conYacc]$ lex --header-file=lexer.h lex.l
[student@localhost conYacc]$ bison --defines=parser.h pars.y
[student@localhost conYacc]$ gcc -fopenmp main.c lex.yy.c pars.tab.c
[student@localhost conYacc]$ ./a.out

 enter no. of files:3

 enter file names:file1 file2 file3
fname=file1 fname=file2 fname=file3
 in parallel=0

 in parallel=1

parse error: thread ID=1

 successful parsing by thread ID=0

 in parallel=2

 successful parsing by thread ID=2

Implement an calculator (64 bit Binary Multiplication) application using concurrent lisp

 Implement an calculator (64 bit Binary Multiplication) application using concurrent lisp

 

defvar a)
(defvar b)

(defvar c)
(defvar d)
(write-line " enter two numbers")
(setf a(read))
(setf b(read))
(sb-thread:make-thread(lambda()(progn(sleep 0)
(setf c(+ a b))
(print"addition")
(print c))))

(sb-thread:make-thread(lambda()(progn(sleep 0)
(setf c(- a b))
(print"Subtraction")
(print c))))


(sb-thread:make-thread(lambda()(progn(sleep 0)
(setf c(* a b))
(print"Multiplication ")
(print c))))


(sb-thread:make-thread(lambda()(progn(sleep 0)
(setf c(/ a b))
(print"Division")
(print c))))

---------------------------------------------O/P-------------------------------------------------------
pg@pg-17:~$ sbcl
This is SBCL 1.1.14.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* (load "calci.lisp")
 enter two numbers
2347686465465
5675677667576

"addition"
8023364133041
"Subtraction"
-3327991202111
"Multiplication "
13324711642510134674262840
T
*
"Division"