-
Notifications
You must be signed in to change notification settings - Fork 0
/
boruvka_thread.cpp
629 lines (447 loc) · 21.8 KB
/
boruvka_thread.cpp
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
#include <iostream>
#include <thread>
#include "lib/dset.hpp"
#include <algorithm>
#include <atomic>
#include <future>
#include "lib/queue.hpp"
#include "lib/graph.hpp"
#include "lib/utils.hpp"
#include "lib/utimer.hpp"
#include "lib/threadpool.hpp"
#define MY_EOS std::pair<uint,uint> (0,0)
/**
* @brief Compute minimum edges of the graph
*
* @param local_edges Vector of vector of edges to modify saving the minimum edges found
* @param graph The graph accessed concurrently
* @param chunk_indexes The <starting,ending> integer pair of graph edges to inspect
* @param index The index of the corresponding thread
* @return int
*
* Loop through the assigned indexes chunk_indexes and modify the local_edges at the given index thread with the minimum edges found
*/
int mapwork(std::vector<std::vector<MyEdge>> &local_edges, Graph &graph, std::pair<uint, uint> chunk_indexes, uint index) {
// local_edges.resize(graph.originalNodes);
local_edges[index].assign(graph.originalNodes, {0,0,10});
// std::cout << local_edges[index].size() << std::endl;
// Get the indexes of the edges array
uint starting_index = chunk_indexes.first;
uint ending_index = chunk_indexes.second;
// std::cout << starting_index << "," << ending_index << std::endl;
for (uint i = starting_index; i < ending_index; i++) {
// Retrieve edge from graph
MyEdge &edge = graph.edges[i];
if (local_edges[index][edge.from].weight > edge.weight) {
// Found edge with same starting node and minimum weight, update local_edge
local_edges[index][edge.from].weight = edge.weight;
local_edges[index][edge.from].from = edge.from;
local_edges[index][edge.from].to = edge.to;
}
}
return 1;
}
/**
* @brief Merge the previously local_edges
*
* @param local_edges Vector of vector of minimum edges found by previous threads
* @param global_edges Global vector of minimum edges
* @param chunk_indexes The <starting,ending> integer pair to be modified by the thread
* @return int
*
* Each thread inspect the local_edges and update the global_edges vector with the minimum edge found previously
*/
int mergework(std::vector<std::vector<MyEdge>> &local_edges, std::vector<MyEdge> &global_edges, std::pair<uint, uint> chunk_indexes) {
// Get the indexes of the local_edges array
uint starting_index = chunk_indexes.first;
uint ending_index = chunk_indexes.second;
// std::cout << starting_index << "," << ending_index << std::endl;
// For each local_edge of each thread
for (auto local_edge : local_edges) {
// Iterate through the indexes interval received
for (uint i = starting_index; i < ending_index; i++) {
if (local_edge[i].weight < global_edges[i].weight) {
// Update global_edges if the local_edges found by the thread i has a better weight
global_edges[i].weight = local_edge[i].weight;
global_edges[i].from = local_edge[i].from;
global_edges[i].to = local_edge[i].to;
}
}
}
return 1;
}
/**
* @brief Contract the union find data structure
*
* @param global_edges The minimum vector of edges found in this iteration
* @param initialComponents The disjoint sets data structure
* @param graph The graph data structure
* @param chunk_indexes The <starting, ending> integer pair to inspect in the global_edges vector
* @return int
*
* Contract the union find data structure by calling the method same and unite. If the minimum edge found among node x and y have already the same
* parent, then we don't do nothing.
* Otherwise, we call unite to fuse together the two subtrees
*/
int contractionwork(std::vector<MyEdge> &global_edges, DisjointSets &initialComponents, Graph &graph, std::pair<uint, uint> chunk_indexes) {
MyEdge NULL_CONN = {0,0,10};
// Get the indexes of the global_edges array
uint starting_index = chunk_indexes.first;
uint ending_index = chunk_indexes.second;
// Iterate through global_edges in the specific indexes
for (uint i = starting_index; i < ending_index; i++) {
// Retrieve the edge found
MyEdge edge = global_edges[i];
if (edge == NULL_CONN) {
// If edge has default value, we do nothing
}
else {
if (!initialComponents.same(edge.from, edge.to)) {
/**
* Access the UNION-FIND data structure and check if the starting node and ending node
* have the same parent.
* If not, this means that we can unify the two trees
*/
initialComponents.unite(edge.from, edge.to);
// MST_weight.fetch_add(edge.weight);
// MST_weight += edge.weight;
}
else {
/**
* Nodes have the same parent (so they are in the same component).
* We do nothing otherwise we create a cycle
*/
}
}
}
return 1;
}
/**
* @brief Filter the edges found previously
*
* @param remaining_edges Vector of vector of edges to modify
* @param initialComponents The disjoint set data structure
* @param graph The graph data structure
* @param chunk_indexes The <starting,ending> integer pair to inspect in the graph edges
* @param index The index of the corresponding thread
* @return int
*
* Loop through the edges of the graph and append the edge into the corresponding remaining_edges index if the node x and y linking the current edge does
* not belong to the same component
*/
int filteringedgework(std::vector<std::vector<MyEdge>>& remaining_edges, DisjointSets &initialComponents, Graph &graph, std::pair<uint, uint> chunk_indexes, int index) {
// Get the indexes
uint starting_index = chunk_indexes.first;
uint ending_index = chunk_indexes.second;
// Iterate through the received indexes
for (uint i = starting_index; i < ending_index; i++) {
MyEdge edge = graph.edges[i];
if ( !initialComponents.same(edge.from, edge.to) )
/**
* If the starting and the ending node of each graph's edge are not in the same component,
* then we need to keep it for the next iteration.
* Otherwise we discard it.
*/
remaining_edges[index].push_back(edge);
}
return 1;
}
/**
* @brief Filter the nodes found previously
*
* @param remaining_nodes Vector of vector of nodes to modify
* @param initialComponents The disjoint set data structure
* @param graph The graph data structure
* @param chunk_indexes The <starting,ending> integer pair to inspect in the graph nodes
* @param index The index of the corresponding thread
* @return int
*
* Inspect the given nodes indexes in the graph and check if the current node is itself a parent.
* If it is so, we save it into the remanining_nodes (only the parent node matters)
*/
int filteringnodework(std::vector<std::vector<uint>>& remaining_nodes, DisjointSets &initialComponents, Graph &graph, std::pair<uint, uint> chunk_indexes, int index) {
// Get the indexes
uint starting_index = chunk_indexes.first;
uint ending_index = chunk_indexes.second;
// Iterate through the received indexes
for (uint i = starting_index; i < ending_index; i++) {
if ( initialComponents.parent(graph.nodes[i]) == graph.nodes[i] )
/**
* If the parent node is the same as the node itself, then we need to keep it also
* for next iteration.
* Otherwise it is a child of another node and we can discard it.
*/
remaining_nodes[index].push_back(i);
}
return 1;
}
int main(int argc, char *argv[]) {
if (argc != 6) {
std::cout << "Usage ./[executable] nw number_nodes number_edges filename iters" << std::endl;
return (0);
}
short num_w = std::stoi(argv[1]);
uint num_nodes = std::atoi(argv[2]);
uint num_edges = std::atoi(argv[3]);
std::string filename = std::string(argv[4]);
int iters = std::atoi(argv[5]);
long loading_time = 0;
Graph graph;// = Graph();
{
Utimer read_time("loading graph",&loading_time);
// UNCOMMENT FOR V_E and sc-rel9
if (filename.empty()) {
graph.generateGraph(num_nodes, num_edges);
}
else {
graph.loadGraph(filename);
}
// UNCOMMENT FOR soc-youtube
// graph.loadGraphUnweighted(filename);
}
std::cout << "parallel thread; read time: " << loading_time << " usec" << std::endl;
Graph copy_graph = graph;
for (int nw = 1; nw <= num_w; nw++) {
// Instantiate the threadpool
ThreadPool pool{nw};
while (iters > 0) {
// Disjoint Union Find structure
DisjointSets initialComponents = { static_cast<uint32_t>(graph.getNumNodes()) };
std::atomic<int> MST_weight;
int iter = 0;
long total_time = 0;
while (graph.getNumNodes() != 1) {
// Vector of local MST
std::vector<std::vector<MyEdge>> local_edges (nw);
std::vector<MyEdge> global_edges;
global_edges.assign(graph.originalNodes, {0, 0, 10});
std::vector<std::future<int>> mapfutures;
long map_time;
{
Utimer timer("Map parallel time", &map_time);
uint n = graph.getNumEdges();
// Portion of edges for each worker
size_t chunk_dim{ n / nw };
// The starting index will be at zero
size_t begin = 0;
// The ending one is n if the workers are enough, otherwise the chunk_dim computed before
size_t end = nw != 1 ? std::min(chunk_dim, static_cast<size_t>(n)) : n;
if (nw == 1) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes]() -> int {
return mapwork(std::ref(local_edges), std::ref(graph), std::move( chunk_indexes ), 0);
}, 0);
mapfutures.push_back(std::move(f1));
}
else {
for (int i = 0; i < nw; i++) {
// Compute the indexes and enqueue the task into the thread pool
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes, i]() -> int {
return mapwork(std::ref(local_edges), std::ref(graph), std::move( chunk_indexes ), i);
}, i);
mapfutures.push_back(std::move(f1));
if (i == nw-2) {
// Last chunk
begin = end;
end = n;
}
else {
begin = end;
end = std::min(begin + chunk_dim, static_cast<size_t>(n));
}
}
}
// Wait for all the thread to finish
for (auto &fut : mapfutures) {
int val = fut.get();
}
}
long merge_time;
std::vector<std::future<int>> mergefutures;
{
Utimer timer("Merge time", &merge_time);
uint n = local_edges[0].size();
// Portion of edges for each worker
size_t chunk_dim{ n / nw };
// The starting index will be at zero
size_t begin = 0;
// The ending one is n if the workers are enough, otherwise the chunk_dim computed before
size_t end = nw != 1 ? std::min(chunk_dim, static_cast<size_t>(n)) : n;
if (nw == 1) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes]() -> int {
return mergework(std::ref(local_edges), std::ref(global_edges), std::move( chunk_indexes ));
}, 0);
mergefutures.push_back(std::move(f1));
}
else {
for (int i = 0; i < nw; i++) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes]() -> int {
return mergework(std::ref(local_edges), std::ref(global_edges), std::move(chunk_indexes));
}, std::move(i));
mergefutures.push_back(std::move(f1));
if (i == nw-2) {
// Last chunk
begin = end;
end = n;
}
else {
begin = end;
end = std::min(begin + chunk_dim, static_cast<size_t>(n));
}
}
}
for (auto &fut : mergefutures) {
int val = fut.get();
}
}
long contraction_time;
std::vector<std::future<int>> contractionfutures;
{
Utimer timer("Contraction time", &contraction_time);
uint n = global_edges.size();
// Portion of edges for each worker
size_t chunk_dim{ n / nw };
// The starting index will be at zero
size_t begin = 0;
// The ending one is n if the workers are enough, otherwise the chunk_dim computed before
size_t end = nw != 1 ? std::min(chunk_dim, static_cast<size_t>(n)) : n;
if (nw == 1) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes]() -> int {
return contractionwork(std::ref(global_edges), std::ref(initialComponents), std::ref(graph), std::move( chunk_indexes ));
}, 0);
contractionfutures.push_back(std::move(f1));
}
else {
for (int i = 0; i < nw; i++) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes]() -> int {
return contractionwork(std::ref(global_edges), std::ref(initialComponents), std::ref(graph), std::move( chunk_indexes ));
}, std::move(i));
contractionfutures.push_back(std::move(f1));
if (i == nw-2) {
// Last chunk
begin = end;
end = n;
}
else {
begin = end;
end = std::min(begin + chunk_dim, static_cast<size_t>(n));
}
}
}
for (auto &fut : contractionfutures) {
int val = fut.get();
}
}
long filtering_edge_time;
std::vector<std::future<int>> filtering_edgefutures;
std::vector<std::vector<MyEdge>> selected_edges (nw);
std::vector<std::vector<uint>> selected_nodes (nw);
{
Utimer timer("Filtering edges time", &filtering_edge_time);
uint n = graph.getNumEdges();
// Portion of edges for each worker
size_t chunk_dim{ n / nw };
// The starting index will be at zero
size_t begin = 0;
// The ending one is n if the workers are enough, otherwise the chunk_dim computed before
size_t end = nw != 1 ? std::min(chunk_dim, static_cast<size_t>(n)) : n;
if (nw == 1) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes]() -> int {
return filteringedgework(std::ref(selected_edges), std::ref(initialComponents), std::ref(graph), std::move( chunk_indexes ), 0);
}, 0);
filtering_edgefutures.push_back(std::move(f1));
}
else {
for (int i = 0; i < nw; i++) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes, i]() -> int {
return filteringedgework(std::ref(selected_edges), std::ref(initialComponents), std::ref(graph), std::move( chunk_indexes ), i);
}, std::move(i));
filtering_edgefutures.push_back(std::move(f1));
if (i == nw-2) {
// Last chunk
begin = end;
end = n;
}
else {
begin = end;
end = std::min(begin + chunk_dim, static_cast<size_t>(n));
}
}
}
for (auto &fut : filtering_edgefutures) {
int val = fut.get();
}
}
long filtering_node_time;
std::vector<std::future<int>> filtering_nodefutures;
{
Utimer timer("Filtering nodes time", &filtering_node_time);
uint n = graph.originalNodes;
// Portion of edges for each worker
size_t chunk_dim{ n / nw };
// The starting index will be at zero
size_t begin = 0;
// The ending one is n if the workers are enough, otherwise the chunk_dim computed before
size_t end = nw != 1 ? std::min(chunk_dim, static_cast<size_t>(n)) : n;
if (nw == 1) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes]() -> int {
return filteringnodework(std::ref(selected_nodes), std::ref(initialComponents), std::ref(graph), std::move( chunk_indexes ), 0);
}, 0);
filtering_nodefutures.push_back(std::move(f1));
}
else {
for (int i = 0; i < nw; i++) {
std::pair<uint, uint> chunk_indexes = {begin, end};
auto f1 = pool.enqueue([&, chunk_indexes, i]() -> int {
return filteringnodework(std::ref(selected_nodes), std::ref(initialComponents), std::ref(graph), std::move( chunk_indexes ), i);
}, std::move(i));
filtering_nodefutures.push_back(std::move(f1));
if (i == nw-2) {
// Last chunk
begin = end;
end = n;
}
else {
begin = end;
end = std::min(begin + chunk_dim, static_cast<size_t>(n));
}
}
}
for (auto &fut : filtering_nodefutures) {
int val = fut.get();
}
}
std::vector<MyEdge> remaining_edges;
std::vector<uint> remaining_nodes;
long filtering_time;
{
Utimer timer("Final filtering", &filtering_time);
for (auto &vect : selected_edges) {
remaining_edges.insert(remaining_edges.end(), vect.begin(), vect.end());
}
for (auto &vect : selected_nodes) {
remaining_nodes.insert(remaining_nodes.end(), vect.begin(), vect.end());
}
}
total_time += map_time + merge_time + contraction_time + filtering_edge_time + filtering_node_time + filtering_time;
graph.updateNodes(std::ref(remaining_nodes));
graph.updateEdges(std::ref(remaining_edges));
iter++;
}
std::cout << "workers: " << nw << "; iters: " << iter << "; time " << total_time << " usec" << std::endl;
graph = copy_graph;
iters--;
}
iters = std::atoi(argv[5]);
// Close threadpool
}
return (0);
}