Skip to content

Instantly share code, notes, and snippets.

@zsrinivas

zsrinivas/Lagrange interpolation.cpp

Created November 7, 2016 07:23
Show Gist options
  • Save zsrinivas/00e22965fd5ef05ecd0645bb19e5a937 to your computer and use it in GitHub Desktop.
Save zsrinivas/00e22965fd5ef05ecd0645bb19e5a937 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
correct dot product.c
#include <mpi.h>
#include <stdio.h>
const int N=2000;
double dotProduct(double *x, double *y, int n) {
int i;
double prod = 0.0;
for (i = 0; i < n; i++) {
prod += x[i]*y[i];
}
return prod;
}
int main(int argc, char *argv[]) {
int i;
double prod;
int my_rank;
int num_procs;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &num_procs);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
int local_N = N / num_procs; //assuming N is totally divisible by num_procs
double local_x[local_N];
double local_y[local_N];
for(i = 0; i < local_N; i++) {
local_x[i] = 0.01 * (i + my_rank * local_N);
local_y[i] = 0.03 * (i + my_rank * local_N);
}
double local_prod;
local_prod = dotProduct(local_x,local_y,local_N);
MPI_Reduce(&local_prod, &prod, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
if (my_rank == 0) {
printf("dotProduct = %f\n", prod);
}
MPI_Finalize();
return 0;
}
Raw
dotProduct.c
#include <stdio.h>
#include <string.h>
#include "mpi.h"
int main(int argc ,char *argv[])
{
int my_rank,p,src,dest,tag=0,s=0,x;
int a[] = {1,2,3,4,5};
int b[] = {1,2,3,4,5};
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
MPI_Comm_size(MPI_COMM_WORLD,&p);
dest = 0;
if(my_rank != 0)
{
x = a[my_rank]*b[my_rank];
MPI_Send(&x,1,MPI_INT,dest,tag,MPI_COMM_WORLD);
}
else
{
s = a[my_rank]*b[my_rank];
for(src = 1;src < p;src++)
{
MPI_Recv(&x,1,MPI_INT,src,tag,MPI_COMM_WORLD,&status);
s+=x;
}
printf("%d\n",s);
}
MPI_Finalize();
}
Raw
gather_scatter 2.c
#include <stdio.h>
#include <mpi.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char* argv[])
{
float x[5] = {0.0,1.0,3.0,4.0};
float f[5] = {1.0,3.0,49.0,129.0};
float x = 0.3, res = 0,pass[4],recv[2];
int my_rank,p;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &p);
// Scatter the random numbers to all processes
MPI_Scatter(x, 2, MPI_FLOAT, pass, 2, MPI_FLOAT, 0, MPI_COMM_WORLD);
float l = 0,num = 1.0,den = 1.0,mul;
for(j=0;j<2;j++)
{
float x0 = pass[0],num = 1.0,den = 1.0;
for(i=0;i<3;i++)
{
if(i == j)
continue;
num *= (0.3-pass[i]);
den *= (x0 - pass[i]);
}
res += ((num/den)*f[j]);
}
//gather
MPI_Gather(&res, 1, MPI_FLOAT, recv, 1, MPI_FLOAT, 0,MPI_COMM_WORLD);
if (world_rank == 0) {
cout<<"The value of the function at 0.3 is : "<<recv[0]+recv[1];
}
MPI_Finalize();
return 0;
}
Raw
gather_scatter.c
#include <stdio.h>
#include <mpi.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char* argv[])
{
float x[5] = {0.0,1.0,3.0,4.0};
float f[5] = {1.0,3.0,49.0,129.0};
float x = 0.3, res = 0,pass[4],recv[2];
int my_rank,p;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &p);
// Scatter the random numbers to all processes
MPI_Scatter(x, 2, MPI_FLOAT, pass, 2, MPI_FLOAT, 0, MPI_COMM_WORLD);
float l = 0,num = 1.0,den = 1.0,mul;
for(j=0;j<2;j++)
{
float x0 = pass[0],num = 1.0,den = 1.0;
for(i=0;i<3;i++)
{
if(i == j)
continue;
num *= (0.3-pass[i]);
den *= (x0 - pass[i]);
}
res += ((num/den)*f[j]);
}
//gather
MPI_Gather(&res, 1, MPI_FLOAT, recv, 1, MPI_FLOAT, 0,MPI_COMM_WORLD);
if (world_rank == 0) {
cout<<"The value of the function at 0.3 is : "<<recv[0]+recv[1];
}
MPI_Finalize();
return 0;
}
Raw
Lagrange interpolation.cpp
//Here is the program for Lagrange Interpolation using Broadcast
#include<stdio.h>
#include<string.h>
#include "mpi.h"
int main(int argc,char *argv[])
{
int my_rank;
int p,i;
int source;
int x[5];
int y[5];
int X=3;
float sum;
int tag = 0;
int temp1,temp2;
float temp;
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
MPI_Comm_size(MPI_COMM_WORLD,&p);
if(my_rank==0)
{
for(i=0;i<5;i++)
scanf("%d",&x[i]);
for(i=0;i<5;i++)
scanf("%d",&y[i]);
}
MPI_Bcast(x,5,MPI_INT,0,MPI_COMM_WORLD);
MPI_Bcast(y,5,MPI_INT,0,MPI_COMM_WORLD);
temp1=1;
for(i=0;i<5;i++)
{
if(my_rank==i);
else
temp1*=(X-x[i]);
}
temp2=1;
for(i=0;i<5;i++)
{
if(my_rank==i);
else
temp2*=(x[my_rank]-x[i]);
}
temp=(float)temp1/(float)temp2;
temp=temp*(float)y[my_rank];
MPI_Reduce(&temp,&sum,1,MPI_FLOAT,MPI_SUM,0,MPI_COMM_WORLD);
if(my_rank == 0)
printf("%f",sum);
MPI_Finalize();
return 0;
}
Raw
lagrange.cpp
#include<stdio.h>
#include"mpi.h"
int main()
{
int rank,p,tag=0;
MPI_Init(NULL,NULL);
MPI_Comm c = MPI_COMM_WORLD;
MPI_Comm_rank(c,&rank);
MPI_Comm_size(c,&p);
float arr[10],ans[5];
if(rank == 0)
{
printf("Enter the x's and y's\n");
for(int i=0;i<10;i++)
scanf("%f",&arr[i]);
}
{
float temp=1;
MPI_Bcast(arr,10,MPI_FLOAT,0,c);
for(int i=0;i<10;i+=2)
{
if(2*rank != i)
{
temp *= (0.3 - arr[i])/(arr[2*rank] - arr[i]);
}
}
temp *= arr[2*rank+1];
MPI_Gather(&temp,1,MPI_FLOAT,ans,1,MPI_FLOAT,0,c);
}
if(rank == 0)
{
float value=0;
for(int i=0;i<5l;i++)
value+= ans[i];
printf("The interpolation value is : %f\n",value);
}
MPI_Finalize();
return 0;
}
Raw
last lab.txt
#include <stdio.h>
#include <string.h>
#include "mpi.h"
int main(int argc, char* argv[])
{
int my_rank,p, src, dst, tag=0,i,tmp;
char message[] = "hello";
MPI_Status status;
MPI_Init (&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &p);
int a[] = {1,2,3,4,5,6,7,8};
int b[8] = {0};
int ind_s[8]= {0,2,4,6,1,3,5,7},ind_e[8]= {1,0,3,2,5,4,7,6};
for(i = 0;i<3;i++)
{
for(src)
MPI_Send(a[my_rank], size_of(int), MPI_INT , ind_s[my_rank], tag, MPI_COMM_WORLD);
MPI_Recv(b[my_rank], size_of(int), MPI_INT , ind_s[my_rank], tag, MPI_COMM_WORLD);
}
}
Raw
mat_vec_mul.c
#include<stdio.h>
#include "mpi.h"
int main(int argc,char *argv[])
{
int my_rank;
int p;
int destination=0;
int m[10][10],v[10],n,i,j;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
MPI_Comm_size(MPI_COMM_WORLD,&p);
if(my_rank==0)
{
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d",&m[i][j]);
printf("%d ",m[i][j]);
}
for(i=0;i<n;i++)
{
scanf("%d",&v[i]);
}
}
MPI_Bcast(&n,1,MPI_INTEGER,0,MPI_COMM_WORLD);
MPI_Bcast(v,n,MPI_INTEGER,0,MPI_COMM_WORLD);
int localData[10],r[10];
MPI_Scatter(m,n,MPI_INTEGER,localData,n,MPI_INTEGER,0,MPI_COMM_WORLD);
int result=0;
printf("\n\nrank =%d n=%d\n",my_rank,n);
for(i=0;i<n;i++)
{
printf("l=%d v=%d\n",localData[i],v[i]);
}
for(i=0;i<n;i++)
{
result += localData[i]*v[i];
}
printf("rank = %d result=%d \n",my_rank,result);
MPI_Gather(&result,1,MPI_INTEGER,r,1,MPI_INTEGER,destination,MPI_COMM_WORLD);
if(my_rank==0)
{
printf("the result is\n");
for(i=0;i<n;i++)
{
printf("i=%d %d\n",i,r[i]);
}
}
MPI_Finalize();
}
Raw
oddEvenSortMPI.c
//Odd-Even Sort
//Source: http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#define N 1000
int compare(const void *, const void *);
void mergeArrays(int *, int *, int *, int, int);
int computeNeighbor(int, int, int);
int main(int argc, char ** argv)
{
int i, j, n, rank, size;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
int numElements = N/size;
int * arr = (int *) malloc(sizeof(int)*numElements);
int * temp = (int *) malloc(sizeof(int)*numElements*2);
int * recvArr = (int *) malloc(sizeof(int)*numElements);
int * fullArr = NULL;
if(rank == 0)
fullArr = (int *) malloc(sizeof(int)*N);
//Fill array in descending order
int start = rank*numElements;
int end = start+numElements;
for(i = 0, j = start; i < numElements; i++, j++)
arr[i] = N-j;
//Sort array with odd-even sort
//Sort local values
qsort(arr, numElements, sizeof(int), compare);
//Begin iterations
for(n = 0; n < size; n++) {
MPI_Barrier(MPI_COMM_WORLD);
int neighbor = computeNeighbor(n, rank, size);
if(neighbor >= 0 && neighbor < size)
{
//Send my values to my neighbor and receive values from my neighbor
MPI_Sendrecv(arr, numElements, MPI_INT, neighbor, n,
recvArr, numElements, MPI_INT, neighbor, n,
MPI_COMM_WORLD, &status);
//If my rank < my neighbor's rank, keep the smaller values
if(rank < neighbor){
mergeArrays(arr, recvArr, temp, numElements, 1);
//Else keep the larger values
} else {
mergeArrays(arr, recvArr, temp, numElements, 0);
}
}
}
MPI_Barrier(MPI_COMM_WORLD);
MPI_Gather(arr, numElements, MPI_INT, fullArr, numElements, MPI_INT, 0, MPI_COMM_WORLD);
if(rank == 0)
{
for(i = 0; i < N; i++)
printf("%d ", fullArr[i]);
printf("\n");
}
free((void *) arr);
free((void *) recvArr);
free((void *) temp);
MPI_Finalize();
return 0;
}
int compare(const void * a, const void * b)
{
if( *((int *)a) < *((int *)b) ) return -1;
else if( *((int *)a) == *((int *)b) ) return 0;
else return 1;
}
int computeNeighbor(int phase, int rank, int size)
{
int neighbor;
if(phase % 2 != 0) { //odd phase
if(rank % 2 != 0) { //odd rank
neighbor = rank + 1;
} else { //even rank
neighbor = rank - 1;
}
} else { //even phase
if(rank % 2 != 0) { //odd rank
neighbor = rank - 1;
} else { //even rank
neighbor = rank + 1;
}
}
if(neighbor < 0 || neighbor >= size)
neighbor = -1;
return neighbor;
}
void mergeArrays(int * arr, int * neighborArr, int * temp, int size, int low_or_high)
{
int i, j, k;
i = j = k = 0;
//Assume arrays are already sorted
for(i = 0, j = 0, k = 0; i < size*2; i++)
{
if(j < size && k < size)
{
if(arr[j] < neighborArr[k])
{
temp[i] = arr[j];
j++;
} else {
temp[i] = neighborArr[k];
k++;
}
} else if(j < size) {
temp[i] = arr[j];
j++;
} else {
temp[i] = neighborArr[k];
k++;
}
}
if(low_or_high % 2 != 0)
for(i = 0; i < size; i++)
arr[i] = temp[i];
else
for(i = size, j=0; j < size; i++,j++)
arr[j]= temp[i];
}
Raw
oddeventranspositionsort.c
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
int merge(double *ina, int lena, double *inb, int lenb, double *out) {
int i,j;
int outcount=0;
for (i=0,j=0; i<lena; i++) {
while ((inb[j] < ina[i]) && j < lenb) {
out[outcount++] = inb[j++];
}
out[outcount++] = ina[i];
}
while (j<lenb)
out[outcount++] = inb[j++];
return 0;
}
int domerge_sort(double *a, int start, int end, double *b) {
if ((end - start) <= 1) return 0;
int mid = (end+start)/2;
domerge_sort(a, start, mid, b);
domerge_sort(a, mid, end, b);
merge(&(a[start]), mid-start, &(a[mid]), end-mid, &(b[start]));
for (int i=start; i<end; i++)
a[i] = b[i];
return 0;
}
int merge_sort(int n, double *a) {
double b[n];
domerge_sort(a, 0, n, b);
return 0;
}
void printstat(int rank, int iter, char *txt, double *la, int n) {
printf("[%d] %s iter %d: <", rank, txt, iter);
for (int j=0; j<n-1; j++)
printf("%6.3lf,",la[j]);
printf("%6.3lf>\n", la[n-1]);
}
void MPI_Pairwise_Exchange(int localn, double *locala, int sendrank, int recvrank,
MPI_Comm comm) {
/*
* the sending rank just sends the data and waits for the results;
* the receiving rank receives it, sorts the combined data, and returns
* the correct half of the data.
*/
int rank;
double remote[localn];
double all[2*localn];
const int mergetag = 1;
const int sortedtag = 2;
MPI_Comm_rank(comm, &rank);
if (rank == sendrank) {
MPI_Send(locala, localn, MPI_DOUBLE, recvrank, mergetag, MPI_COMM_WORLD);
MPI_Recv(locala, localn, MPI_DOUBLE, recvrank, sortedtag, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
} else {
MPI_Recv(remote, localn, MPI_DOUBLE, sendrank, mergetag, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
merge(locala, localn, remote, localn, all);
int theirstart = 0, mystart = localn;
if (sendrank > rank) {
theirstart = localn;
mystart = 0;
}
MPI_Send(&(all[theirstart]), localn, MPI_DOUBLE, sendrank, sortedtag, MPI_COMM_WORLD);
for (int i=mystart; i<mystart+localn; i++)
locala[i-mystart] = all[i];
}
}
int MPI_OddEven_Sort(int n, double *a, int root, MPI_Comm comm)
{
int rank, size, i;
double *local_a;
// get rank and size of comm
MPI_Comm_rank(comm, &rank); //&rank = address of rank
MPI_Comm_size(comm, &size);
local_a = (double *) calloc(n / size, sizeof(double));
// scatter the array a to local_a
MPI_Scatter(a, n / size, MPI_DOUBLE, local_a, n / size, MPI_DOUBLE,
root, comm);
// sort local_a
merge_sort(n / size, local_a);
//odd-even part
for (i = 1; i <= size; i++) {
printstat(rank, i, "before", local_a, n/size);
if ((i + rank) % 2 == 0) { // means i and rank have same nature
if (rank < size - 1) {
MPI_Pairwise_Exchange(n / size, local_a, rank, rank + 1, comm);
}
} else if (rank > 0) {
MPI_Pairwise_Exchange(n / size, local_a, rank - 1, rank, comm);
}
}
printstat(rank, i-1, "after", local_a, n/size);
// gather local_a to a
MPI_Gather(local_a, n / size, MPI_DOUBLE, a, n / size, MPI_DOUBLE,
root, comm);
if (rank == root)
printstat(rank, i, " all done ", a, n);
return MPI_SUCCESS;
}
int main(int argc, char **argv) {
MPI_Init(&argc, &argv);
int n = argc-1;
double a[n];
for (int i=0; i<n; i++)
a[i] = atof(argv[i+1]);
MPI_OddEven_Sort(n, a, 0, MPI_COMM_WORLD);
MPI_Finalize();
return 0;
}
Raw
parallel odd even sort.cpp
/*
* File: parallel_odd_even.c
* Purpose: Implement parallel odd-even sort of an array of
* nonegative ints
* Input:
* A: elements of array (optional)
* Output:
* A: elements of A after sorting
*
* Compile: mpicc -g -Wall -o parallel_odd_even parallel_odd_even.c
* Run:
* mpiexec -n <p> parallel_odd_even <g|i> <global_n>
* - p: the number of processes
* - g: generate random, distributed list
* - i: user will input list on process 0
* - global_n: number of elements in global list
*
* Notes:
* 1. global_n must be evenly divisible by p
* 2. DEBUG flag prints original and final sublists
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <mpi.h>
// const int RMAX = 1000000000;
const int RMAX = 100;
/* Local functions */
void Usage(char* program);
void Print_list(int local_A[], int local_n, int rank);
void Merge_split_low(int local_A[], int temp_B[], int temp_C[],
int local_n);
void Merge_split_high(int local_A[], int temp_B[], int temp_C[],
int local_n);
void Generate_list(int local_A[], int local_n, int my_rank);
int Compare(const void* a_p, const void* b_p);
/* Functions involving communication */
void Get_args(int argc, char* argv[], int* global_n_p, int* local_n_p,
char* gi_p, int my_rank, int p, MPI_Comm comm);
void Sort(int local_A[], int local_n, int my_rank,
int p, MPI_Comm comm);
void Odd_even_iter(int local_A[], int temp_B[], int temp_C[],
int local_n, int phase, int even_partner, int odd_partner,
int my_rank, int p, MPI_Comm comm);
void Print_local_lists(int local_A[], int local_n,
int my_rank, int p, MPI_Comm comm);
void Print_global_list(int local_A[], int local_n, int my_rank,
int p, MPI_Comm comm);
void Read_list(int local_A[], int local_n, int my_rank, int p,
MPI_Comm comm);
/*-------------------------------------------------------------------*/
int main(int argc, char* argv[]) {
int my_rank, p;
char g_i;
int *local_A;
int global_n;
int local_n;
MPI_Comm comm;
double start, finish;
MPI_Init(&argc, &argv);
comm = MPI_COMM_WORLD;
MPI_Comm_size(comm, &p);
MPI_Comm_rank(comm, &my_rank);
Get_args(argc, argv, &global_n, &local_n, &g_i, my_rank, p, comm);
local_A = (int*) malloc(local_n*sizeof(int));
if (g_i == 'g') {
Generate_list(local_A, local_n, my_rank);
} else {
Read_list(local_A, local_n, my_rank, p, comm);
}
# ifdef DEBUG
Print_local_lists(local_A, local_n, my_rank, p, comm);
# endif
start = MPI_Wtime();
Sort(local_A, local_n, my_rank, p, comm);
finish = MPI_Wtime();
if (my_rank == 0)
printf("Elapsed time = %e seconds\n", finish-start);
# ifdef DEBUG
Print_local_lists(local_A, local_n, my_rank, p, comm);
fflush(stdout);
# endif
Print_global_list(local_A, local_n, my_rank, p, comm);
free(local_A);
MPI_Finalize();
return 0;
} /* main */
/*-------------------------------------------------------------------
* Function: Generate_list
* Purpose: Fill list with random ints
* Input Args: local_n, my_rank
* Output Arg: local_A
*/
void Generate_list(int local_A[], int local_n, int my_rank) {
int i;
srandom(my_rank+1);
for (i = 0; i < local_n; i++)
local_A[i] = random() % RMAX;
} /* Generate_list */
/*-------------------------------------------------------------------
* Function: Usage
* Purpose: Print command line to start program
* In arg: program: name of executable
* Note: Purely local, run only by process 0;
*/
void Usage(char* program) {
fprintf(stderr, "usage: mpirun -np <p> %s <g|i> <global_n>\n",
program);
fprintf(stderr, " - p: the number of processes \n");
fprintf(stderr, " - g: generate random, distributed list\n");
fprintf(stderr, " - i: user will input list on process 0\n");
fprintf(stderr, " - global_n: number of elements in global list");
fprintf(stderr, " (must be evenly divisible by p)\n");
fflush(stderr);
} /* Usage */
/*-------------------------------------------------------------------
* Function: Get_args
* Purpose: Get and check command line arguments
* Input args: argc, argv, my_rank, p, comm
* Output args: global_n_p, local_n_p, gi_p
*/
void Get_args(int argc, char* argv[], int* global_n_p, int* local_n_p,
char* gi_p, int my_rank, int p, MPI_Comm comm) {
if (my_rank == 0) {
if (argc != 3) {
Usage(argv[0]);
*global_n_p = -1; /* Bad args, quit */
} else {
*gi_p = argv[1][0];
if (*gi_p != 'g' && *gi_p != 'i') {
Usage(argv[0]);
*global_n_p = -1; /* Bad args, quit */
} else {
*global_n_p = strtol(argv[2], NULL, 10);
if (*global_n_p % p != 0) {
Usage(argv[0]);
*global_n_p = -1;
}
}
}
} /* my_rank == 0 */
MPI_Bcast(gi_p, 1, MPI_CHAR, 0, comm);
MPI_Bcast(global_n_p, 1, MPI_INT, 0, comm);
if (*global_n_p <= 0) {
MPI_Finalize();
exit(-1);
}
*local_n_p = *global_n_p/p;
} /* Get_args */
/*-------------------------------------------------------------------
* Function: Read_list
* Purpose: process 0 reads the list from stdin and scatters it
* to the other processes.
* In args: local_n, my_rank, p, comm
* Out arg: local_A
*/
void Read_list(int local_A[], int local_n, int my_rank, int p,
MPI_Comm comm) {
int i;
int *temp = NULL;
if (my_rank == 0) {
temp = (int*) malloc(p*local_n*sizeof(int));
printf("Enter the elements of the list\n");
for (i = 0; i < p*local_n; i++)
scanf("%d", &temp[i]);
}
MPI_Scatter(temp, local_n, MPI_INT, local_A, local_n, MPI_INT,
0, comm);
if (my_rank == 0)
free(temp);
} /* Read_list */
/*-------------------------------------------------------------------
* Function: Print_global_list
* Purpose: Print the contents of the global list A
* Input args:
* n, the number of elements
* A, the list
* Note: Purely local, called only by process 0
*/
void Print_global_list(int local_A[], int local_n, int my_rank, int p,
MPI_Comm comm) {
int* A = NULL;
int i, n;
if (my_rank == 0) {
n = p*local_n;
A = (int*) malloc(n*sizeof(int));
MPI_Gather(local_A, local_n, MPI_INT, A, local_n, MPI_INT, 0,
comm);
printf("Global list:\n");
for (i = 0; i < n; i++)
printf("%d ", A[i]);
printf("\n\n");
free(A);
} else {
MPI_Gather(local_A, local_n, MPI_INT, A, local_n, MPI_INT, 0,
comm);
}
} /* Print_global_list */
/*-------------------------------------------------------------------
* Function: Compare
* Purpose: Compare 2 ints, return -1, 0, or 1, respectively, when
* the first int is less than, equal, or greater than
* the second. Used by qsort.
*/
int Compare(const void* a_p, const void* b_p) {
int a = *((int*)a_p);
int b = *((int*)b_p);
if (a < b)
return -1;
else if (a == b)
return 0;
else /* a > b */
return 1;
} /* Compare */
/*-------------------------------------------------------------------
* Function: Sort
* Purpose: Use odd-even sort to sort global list.
* Input args: local_n, my_rank, p, comm
* In/out args: local_A
*/
void Sort(int local_A[], int local_n, int my_rank,
int p, MPI_Comm comm) {
int phase;
int *temp_B, *temp_C;
int even_partner; /* phase is even or left-looking */
int odd_partner; /* phase is odd or right-looking */
/* Temporary storage used in merge-split */
temp_B = (int*) malloc(local_n*sizeof(int));
temp_C = (int*) malloc(local_n*sizeof(int));
/* Find partners: negative rank => do nothing during phase */
if (my_rank % 2 != 0) {
even_partner = my_rank - 1;
odd_partner = my_rank + 1;
if (odd_partner == p) odd_partner = -1; // Idle during odd phase
} else {
even_partner = my_rank + 1;
if (even_partner == p) even_partner = -1; // Idle during even phase
odd_partner = my_rank-1;
}
/* Sort local list using built-in quick sort */
qsort(local_A, local_n, sizeof(int), Compare);
for (phase = 0; phase < p; phase++)
Odd_even_iter(local_A, temp_B, temp_C, local_n, phase,
even_partner, odd_partner, my_rank, p, comm);
free(temp_B);
free(temp_C);
} /* Sort */
/*-------------------------------------------------------------------
* Function: Odd_even_iter
* Purpose: One iteration of Odd-even transposition sort
* In args: local_n, phase, my_rank, p, comm
* In/out args: local_A
* Scratch: temp_B, temp_C
*/
void Odd_even_iter(int local_A[], int temp_B[], int temp_C[],
int local_n, int phase, int even_partner, int odd_partner,
int my_rank, int p, MPI_Comm comm) {
MPI_Status status;
if (phase % 2 == 0) { /* Even phase, odd process <-> rank-1 */
if (even_partner >= 0) {
MPI_Sendrecv(local_A, local_n, MPI_INT, even_partner, 0,
temp_B, local_n, MPI_INT, even_partner, 0, comm,
&status);
if (my_rank % 2 != 0)
Merge_split_high(local_A, temp_B, temp_C, local_n);
else
Merge_split_low(local_A, temp_B, temp_C, local_n);
}
} else { /* Odd phase, odd process <-> rank+1 */
if (odd_partner >= 0) {
MPI_Sendrecv(local_A, local_n, MPI_INT, odd_partner, 0,
temp_B, local_n, MPI_INT, odd_partner, 0, comm,
&status);
if (my_rank % 2 != 0)
Merge_split_low(local_A, temp_B, temp_C, local_n);
else
Merge_split_high(local_A, temp_B, temp_C, local_n);
}
}
} /* Odd_even_iter */
/*-------------------------------------------------------------------
* Function: Merge_split_low
* Purpose: Merge the smallest local_n elements in local_A
* and temp_B into temp_C. Then copy temp_C
* back into local_A.
* In args: local_n, temp_B
* In/out args: local_A
* Scratch: temp_C
*/
void Merge_split_low(int local_A[], int temp_B[], int temp_C[],
int local_n) {
int ai, bi, ci;
ai = 0;
bi = 0;
ci = 0;
while (ci < local_n) {
if (local_A[ai] <= temp_B[bi]) {
temp_C[ci] = local_A[ai];
ci++; ai++;
} else {
temp_C[ci] = temp_B[bi];
ci++; bi++;
}
}
memcpy(local_A, temp_C, local_n*sizeof(int));
} /* Merge_split_low */
/*-------------------------------------------------------------------
* Function: Merge_split_high
* Purpose: Merge the largest local_n elements in local_A
* and temp_B into temp_C. Then copy temp_C
* back into local_A.
* In args: local_n, temp_B
* In/out args: local_A
* Scratch: temp_C
*/
void Merge_split_high(int local_A[], int temp_B[], int temp_C[],
int local_n) {
int ai, bi, ci;
ai = local_n-1;
bi = local_n-1;
ci = local_n-1;
while (ci >= 0) {
if (local_A[ai] >= temp_B[bi]) {
temp_C[ci] = local_A[ai];
ci--; ai--;
} else {
temp_C[ci] = temp_B[bi];
ci--; bi--;
}
}
memcpy(local_A, temp_C, local_n*sizeof(int));
} /* Merge_split_low */
/*-------------------------------------------------------------------
* Only called by process 0
*/
void Print_list(int local_A[], int local_n, int rank) {
int i;
printf("%d: ", rank);
for (i = 0; i < local_n; i++)
printf("%d ", local_A[i]);
printf("\n");
} /* Print_list */
/*-------------------------------------------------------------------
* Function: Print_local_lists
* Purpose: Print each process' current list contents
* Input args: all
* Notes:
* 1. Assumes all participating processes are contributing local_n
* elements
*/
void Print_local_lists(int local_A[], int local_n,
int my_rank, int p, MPI_Comm comm) {
int* A;
int q;
MPI_Status status;
if (my_rank == 0) {
A = (int*) malloc(local_n*sizeof(int));
Print_list(local_A, local_n, my_rank);
for (q = 1; q < p; q++) {
MPI_Recv(A, local_n, MPI_INT, q, 0, comm, &status);
Print_list(A, local_n, q);
}
free(A);
} else {
MPI_Send(local_A, local_n, MPI_INT, 0, 0, comm);
}
} /* Print_local_lists */
Raw
sum of n numbers.cpp
#include <stdio.h>
#include <string.h>
#include "mpi.h"
int main(int argc, char* argv[])
{
int i,myrank,res,p,src,dst,tag = 0,ar[100];
char message[100];
for(i=0;i<100;i++)
ar[i] = i;
MPI_Status status;
MPI_Init (&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
dst = 0;
MPI_Comm_size(MPI_COMM_WORLD,&p);
if(myrank != 0)
{
//sprintf(message, "");
int interval = 100/(p-1),x,y;
x = interval*(myrank-1);
y = interval*(myrank)-1;
if(y > 99)
y = 99;
res = 0;
for(i=x;i<=y;i++)
res+=ar[i];
MPI_Send(&res, sizeof(res), MPI_INT, dst, tag, MPI_COMM_WORLD);
}
else
{
int sum = 0;
for(src = 1; src < p;src++)
{
MPI_Recv(&res, 4, MPI_INT, src, tag, MPI_COMM_WORLD, &status);
printf("sum recieved from the process: %d is %d\n",src, res);
sum+=res;
}
printf("the total sum is %d\n",sum);
}
MPI_Finalize();
}
Raw
trapezoidal 2.c
#include <stdio.h>
#include<string.h>
#include <mpi.h>
#include<math.h>
void Get_data(int p, int my_rank, double* a_p, double* b_p, int* n_p);
double Trap(double local_a, double local_b, int local_n,
double h);
double f(double x);
int main(int argc, char* argv[]) {
int my_rank;
int p;
double a;
double b;
int n;
double h;
double local_a;
double local_b;
int local_n;
double my_area;
double total;
int source;
int dest = 0;
int tag = 0;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &p);
Get_data(p, my_rank, &a, &b, &n);
h = (b-a)/n;
local_n = n/p;
local_a = a + my_rank*local_n*h;
local_b = local_a + local_n*h;
my_area = Trap(local_a, local_b, local_n, h);
if (my_rank == 0) {
total = my_area;
for (source = 1; source < p; source++) {
MPI_Recv(&my_area, 1, MPI_DOUBLE, source, tag,
MPI_COMM_WORLD, &status);
total = total + my_area;
}
} else {
MPI_Send(&my_area, 1, MPI_DOUBLE, dest,
tag, MPI_COMM_WORLD);
}
if (my_rank == 0) {
printf("With n = %d trapezoids, our estimate\n",
n);
printf("of the area from %f to %f = %.15f\n ",
a, b, total);
}
MPI_Finalize();
return 0;
}
void Get_data(int p, int my_rank, double* a_p, double* b_p, int* n_p) {
int q;
MPI_Status status;
if (my_rank == 0) {
printf("Enter a, b, and n\n");
scanf("%lf %lf %d", a_p, b_p, n_p);
for (q = 1; q < p; q++) {
MPI_Send(a_p, 1, MPI_DOUBLE, q, 0, MPI_COMM_WORLD);
MPI_Send(b_p, 1, MPI_DOUBLE, q, 0, MPI_COMM_WORLD);
MPI_Send(n_p, 1, MPI_INT, q, 0, MPI_COMM_WORLD);
}
} else {
MPI_Recv(a_p, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(b_p, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(n_p, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
}
}
double Trap(
double local_a ,double local_b ,int local_n ,double h ) {
double my_area;
double x;
int i;
my_area = (f(local_a) + f(local_b))/2.0;
x = local_a;
for (i = 1; i <= local_n-1; i++) {
x = local_a + i*h;
my_area = my_area + f(x);
}
my_area = my_area*h;
return my_area;
}
double f(double x) {
double return_val;
return_val = sin(x);
return return_val;
}
Raw
trapezoidal.c
#include <stdio.h>
#include<string.h>
#include <mpi.h>
void Get_data(int p, int my_rank, double* a_p, double* b_p, int* n_p);
double Trap(double local_a, double local_b, int local_n,
double h);
double f(double x);
int main(int argc, char* argv[]) {
int my_rank;
int p;
double a;
double b;
int n;
double h;
double local_a;
double local_b;
int local_n;
double my_area;
double total;
int source;
int dest = 0;
int tag = 0;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &p);
Get_data(p, my_rank, &a, &b, &n);
h = (b-a)/n;
local_n = n/p;
local_a = a + my_rank*local_n*h;
local_b = local_a + local_n*h;
my_area = Trap(local_a, local_b, local_n, h);
if (my_rank == 0) {
total = my_area;
for (source = 1; source < p; source++) {
MPI_Recv(&my_area, 1, MPI_DOUBLE, source, tag,
MPI_COMM_WORLD, &status);
total = total + my_area;
}
} else {
MPI_Send(&my_area, 1, MPI_DOUBLE, dest,
tag, MPI_COMM_WORLD);
}
if (my_rank == 0) {
printf("With n = %d trapezoids, our estimate\n",
n);
printf("of the area from %f to %f = %.15f\n",
a, b, total);
}
MPI_Finalize();
return 0;
}
void Get_data(int p, int my_rank, double* a_p, double* b_p, int* n_p) {
int q;
MPI_Status status;
if (my_rank == 0) {
printf("Enter a, b, and n\n");
scanf("%lf %lf %d", a_p, b_p, n_p);
for (q = 1; q < p; q++) {
MPI_Send(a_p, 1, MPI_DOUBLE, q, 0, MPI_COMM_WORLD);
MPI_Send(b_p, 1, MPI_DOUBLE, q, 0, MPI_COMM_WORLD);
MPI_Send(n_p, 1, MPI_INT, q, 0, MPI_COMM_WORLD);
}
} else {
MPI_Recv(a_p, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(b_p, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, &status);
MPI_Recv(n_p, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
}
}
double Trap(
double local_a ,double local_b ,int local_n ,double h ) {
double my_area;
double x;
int i;
my_area = (f(local_a) + f(local_b))/2.0;
x = local_a;
for (i = 1; i <= local_n-1; i++) {
x = local_a + i*h;
my_area = my_area + f(x);
}
my_area = my_area*h;
return my_area;
}
double f(double x) {
double return_val;
return_val = x*x + 1.0;
return return_val;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment