-
Notifications
You must be signed in to change notification settings - Fork 0
/
spath.c
148 lines (128 loc) · 5.18 KB
/
spath.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
/**
* CITS3402: High Performance Computing Project 2
* Parallel algorithms to solve all pair shortest path
*
* Clarifications
* The program will automatically generate an ouput file.
* The ouput file will be in binary.
* The program requires the -f flag to specify the input file.
*
* @author Bruce How (22242664)
* @date 25/10/2019
*/
#include "spath.h"
/**
* Produces a standard usage error output to stderr.
* There is an optional parameter to display an additional
* error message.
*
* @param err The optional error message
*/
void usage(char *err) {
char *usage = "\nusage: spath -f input.in\n";
if (err != NULL) {
fprintf(stderr, "%s", err);
}
printf("%s", usage);
}
/**
* Main function that checks that the user specified CLA are valid.
* Processes the graph and appropriately run the Dijkstra's algorithm
* using these variables with MPI.
*
* @param argc The number of CLA
* @param argv The list of arguments
* @return int The exit type
*/
int main(int argc, char *argv[]) {
// CLA processing
if (argc < 3) {
usage("invalid number of arguments supplied\n");
exit(EXIT_FAILURE);
}
if (strcmp(argv[1], "-f") != 0) {
usage("expected -f parameter as the second argument\n");
exit(EXIT_FAILURE);
}
// File validation
FILE *fp = fopen(argv[2], "rb");
if (fp == NULL) {
fprintf(stderr, "%s: no such file\n", argv[2]);
exit(EXIT_FAILURE);
}
int *weights; // 1D array containing the list of weights
int numV; // Number of vertices/nodes
int *spaths; // Result variable
struct timeval start, end; // Timing variables
// MPI initialisation
MPI_Status status;
int numtasks, numworkers, taskid, nodes, offset = 0;
// MPI init should not return 0 if it was successful
if (MPI_Init(&argc, &argv) != 0) {
fprintf(stderr, "error initialising MPI");
exit(EXIT_FAILURE);
}
// Gets the number of tasks and the current taskid to determine master
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
MPI_Comm_rank(MPI_COMM_WORLD, &taskid);
numworkers = numtasks - 1; // Exclude master worker
if (taskid == MASTER) {
process_graph(fp, &weights, &numV); // Read the fp and store the values accordingly
spaths = allocate(numV * numV * sizeof(int));
// Variables for workload balancing
int avgV = numV / numworkers;
int extra = numV % numworkers;
// Start the timer before Dijkstra computation
gettimeofday(&start, NULL);
// Send tasks to workers
// Broadcast to all nodes variables that aren't node independant, O(logp)
MPI_Bcast(&numV, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
MPI_Bcast(weights, numV * numV, MPI_INT, MASTER, MPI_COMM_WORLD);
for (int dest = 1; dest <= numworkers; dest++) {
// Optimal way for workload split
nodes = avgV + (dest <= extra); // Sends extra tasks to earlier workers
// Sends the appropriate variables to the workers
MPI_Send(&nodes, 1, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
MPI_Send(&offset, 1, MPI_INT, dest, FROM_MASTER, MPI_COMM_WORLD);
offset += numV * nodes;
}
// Receive tasks from workers
for (int source = 1; source <= numworkers; source++) {
MPI_Recv(&nodes, 1, MPI_INT, source, FROM_WORKER, MPI_COMM_WORLD, &status);
MPI_Recv(&offset, 1, MPI_INT, source, FROM_WORKER, MPI_COMM_WORLD, &status);
MPI_Recv(&spaths[offset], numV * nodes, MPI_INT, source, FROM_WORKER, MPI_COMM_WORLD, &status);
}
gettimeofday(&end, NULL);
// Output code
char *filename = get_filename(argv[2]);
FILE *fout = fopen(filename, "w");
if (fout == NULL) {
fprintf(stderr, "spath: failed to write to the output file\n");
MPI_Abort(MPI_COMM_WORLD, EXIT_FAILURE);
exit(EXIT_FAILURE);
}
// Binary output write, unspecified in project
output(fout, spaths, numV);
output_time(start, end);
fclose(fp);
fclose(fout);
free(spaths);
free(weights);
free(filename);
} else { // Worker code below
// Receives variables and work from master
MPI_Bcast(&numV, 1, MPI_INT, FROM_MASTER, MPI_COMM_WORLD);
weights = allocate(numV * numV * sizeof(int)); // Allocate memory before receiving weights data
MPI_Bcast(weights, numV * numV, MPI_INT, MASTER, MPI_COMM_WORLD);
MPI_Recv(&nodes, 1, MPI_INT, MASTER, FROM_MASTER, MPI_COMM_WORLD, &status);
MPI_Recv(&offset, 1, MPI_INT, MASTER, FROM_MASTER, MPI_COMM_WORLD, &status);
spaths = allocate(numV * nodes * sizeof(int)); // Allocate only the required task
dijkstra(&spaths, weights, numV, nodes, offset);
// Sends finished work back to master
MPI_Send(&nodes, 1, MPI_INT, MASTER, FROM_WORKER, MPI_COMM_WORLD);
MPI_Send(&offset, 1, MPI_INT, MASTER, FROM_WORKER, MPI_COMM_WORLD);
MPI_Send(spaths, numV * nodes, MPI_INT, MASTER, FROM_WORKER, MPI_COMM_WORLD);
}
MPI_Finalize(); // Called by master thread that MPI initialised
exit(EXIT_SUCCESS);
}