-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.c
166 lines (141 loc) · 4.58 KB
/
main.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
/*
Taksinomhsh Selection Sort p > 2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Syleopoulos Anastasios
*/
#include "mpi.h"
#include <stdio.h>
#include <stdlib.h>
//#include <unistd.h> // sleep
#define _MAXNUMBER 10000 /* megistos arithmos stoixeiou */
/************** FUNCS ****************/
// gemizei pinaka me thn rand()
void FilltheArray(int *pin, int N){
int i;
for(i=0;i<N;i++)
pin[i]=rand()%_MAXNUMBER;
}
// ektupwnei ton pinaka
void Myprint(int *pin, int N, char *str){
int i;
printf("\n%s\n",str);
for(i=0;i<N;i++)
printf("%d |",pin[i]);
printf("\n");
}
/***************** MAIN **********************/
int main(int argc,char *argv[]){
int myid, numprocs;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
int i,j; // deiktes gia for
int temp; // metavliti gia thn taksinomhsh
int N, part; // N: megethos pinaka | part: megethos kommatiou
int *thesi; // pinakas deiktwn
int *A, *As; // A: mh-taksinomhmenos pinakas | As: taksinomhmenos pinakas
int *Aw; // pinakas megethous part opou tha efarmostei o selection sort
double ta,tt; // ta: arxh xronou | tt: telos xronou
/********** MASTER ***********/
if(myid == 0){
printf("Selection Sort: Parallhlo programma gia p > 2\n");
printf("Plhktrologiste to megethos tou pinaka: ");
scanf("%d",&N);
A = malloc(N*sizeof(int));
As = malloc(N*sizeof(int));
if(A==NULL || As==NULL){
printf("\nAdunamia desmeushs mnhmhs!\nTelos programmatos!\n");
exit(1);
}
FilltheArray(A,N); // gemisma pinaka me stoixeia
part = N/numprocs; // upologismos kommatiou
if(N%numprocs!=0){
printf("\nO arithmos komvwn(numprocs) den einai pollaplasio tou megethous(N) tou pinaka!\nTelos programmatos!\n");
exit(1);
}
printf("O arithmos komvwn(numprocs): %d To megethos(N): %d To kommati(part): %d\n",numprocs,N,part);
ta = MPI_Wtime(); // arxizei h xronometrish
thesi=malloc(numprocs*sizeof(int));
if(thesi==NULL){
printf("\nAdunamia desmeushs mnhmhs!\nTelos programmatos!\n");
exit(1);
}
for(i=0;i<numprocs;i++) // Anathesh timwn ston pinaka(thesi) me thn arxikh thesh tou stoixeiou kathe komvou
thesi[i]=i*part;
//Myprint(A,N,"Mh-taksinomhmenos pinakas(A)"); // ektypwsh A
}
MPI_Bcast(&part,1,MPI_INT,0,MPI_COMM_WORLD); // Apostolh se olous tous komvous to part
Aw=malloc(part*sizeof(int)); // Desmeush mnhmhs megethous part gia ton pinaka Aw
MPI_Scatter(&A[0],part,MPI_INT,&Aw[0],part,MPI_INT,0,MPI_COMM_WORLD); // Diamoirash tou mh-taksinomhmenou pinaka(A) stous pinakes Aw
/*
// Ektypwsh twn mh-taksinomimenwn kommatiwn apo kathe komvo
char name1[51];
sleep(myid*1);
sprintf(name1,"~Komvos %d -> not-sorted pinakas(Aw)",myid);
Myprint(Aw,part,name1);
sleep(numprocs-myid);
*/
/************ Selection Sort *************/
//Efagmogh ths taksinomishs ston pinaka Aw
for(i=0;i<part;i++){
for(j=i+1;j<part;j++){
if(Aw[i]>Aw[j]){
temp=Aw[i];
Aw[i]=Aw[j];
Aw[j]=temp;
}
}
}
/****************************************/
/*
// Ektypwsh twn taksinomimenwn kommatiwn apo kathe komvo
if(myid==0)
printf("\n******** SELECTION SORT DONE ********\n");
char name2[51];
sleep(myid*1);
sprintf(name2,">Komvos %d -> sorted pinakas(Aw)",myid);
Myprint(Aw,part,name2);
sleep(1);
*/
MPI_Gather(&Aw[0],part,MPI_INT,&A[0],part,MPI_INT,0,MPI_COMM_WORLD); // syllogh stoixeiwn apo tous Aw kai apothukeush ston pinaka A
// Enwsh kommatiwn kai oristikh taksinomhsh tou pinaka
/********** MASTER ***********/
if(myid==0){
//Myprint(A,N,"O pinakas(A) meta thn GATHER"); // ektypwsh A meta thn gather
//Myprint(thesi,numprocs,"pinakas deiktwn(thesi)"); // ektypwsh thesi
int tp; // tp: deikths thesis komvou
int check; // anathesh timis pou endexetai na einai h mikroterh
int done; // elegxos an exei ginei eyresh tou mikroterou (done=1)
/*
Gia kathe thesi tou taksinomhmenou pinaka(As) vriskei
to mikrotero stoixeio tou pinaka Aw tou kathe komvou.
Anathetei thn timh ston pinaka(As) kai auksanei ton deikth
thesis apo ton komvo pou vrike to stoixeio kata ena.
*/
for(i=0;i<N;i++){
tp=0;
done=0;
while(done!=1){
if(thesi[tp]<(tp+1)*part){
check = thesi[tp];
for(j=tp+1;j<numprocs;j++){
if(A[check]>A[thesi[j]] && thesi[j] < (j+1)*part){
check = thesi[j];
tp=j;
}
}
done=1;
}else{
tp++;
}
}
As[i]=A[check];
thesi[tp]++;
}
tt = MPI_Wtime(); // telos xronometrisis
printf("\nO xronos ekteleshs: %.16f\n",tt-ta);
//Myprint(As,N,"O taksinomhmenos pinakas(As)");
}
MPI_Finalize();
return 0;
}