introduces parallelGraphBuilder #1178

PetholzA · 2024-01-31T12:20:20Z

part of re-upload from #1165

angriman

Thanks for the PR, I left some comments. Since we already have a GraphBuilder class which also supports edge weights, why don't we refactor that class to run in parallel instead of creating a new one?

include/networkit/graph/ParallelGraphBuilder.hpp

angriman · 2024-02-03T11:59:26Z

include/networkit/graph/ParallelGraphBuilder.hpp

+    void addEdgeParallel(index a, index b);
+
+    void addHalfEdgeParallel(Unsafe, index source, index destination);
+
+    void addHalfInEdgeParallel(Unsafe, index source, index destination);
+
+    void addHalfOutEdgeParallel(Unsafe, index source, index destination);
+
+    Graph toGraphParallel();
+
+    void addEdgesToGraphParallel(Unsafe, Graph &G);


I think that we can drop the Parallel suffix from all these functions, the class is already called ParallelGraphBuilder.

Thanks for the comments, i've refactored the parallel graph building into the existing graph builder. Therefore, the suffix might be useful to distinguish between sequential and parallel functions, what do you think?

After taking a more in-depth look at the code, I would also recommend refactoring the existing code. There is already a parallel builder, which, according to the contributor of the code, is a lot slower than the new concept.

As already indicated, the old implementation supports weights, which adds a layer of complexity due to additional conditionals (even though branch prediction will likely cause some remedy here). Also, the old implementation, when calling completeGraph (this corresponds to toGraphParallel in the new implementation) does shrinkToFit() and reset() as a final step. Would something like this also be necessary with the new refactored implementation? Does this have performance implications? What happens if the new parallel build is completed twice?

I would suggest doing the following:

Implement support for weighted edges for the new parallel builder

Benchmark the old vs. the new implementation

If the new implementation is still faster, refactor old toGraphParallel() to use the new toGraphParallel.

For the refactoring step, I also left some other comments.

@fabratu I agree with your points. About 3., assuming that the parallel implementation is faster than the sequential, why don't we just implement a single toGraph function which runs in parallel, and drop toGraphSequential and toGraphParallel? I don't see the point of maintaining two different functions that achieve the same goal.

networkit/cpp/graph/ParallelGraphBuilder.cpp

include/networkit/graph/ParallelGraphBuilder.hpp

networkit/cpp/graph/ParallelGraphBuilder.cpp

angriman · 2024-02-03T20:16:35Z

networkit/cpp/graph/ParallelGraphBuilder.cpp

+
+void ParallelGraphBuilder::addHalfEdgeParallel(Unsafe, index a, index b) {
+    assert(a != b);
+    outEdgesPerThread[omp_get_thread_num()][a % omp_get_max_threads()].emplace_back(HalfEdge{a, b});


If you use emplace this should be enough, same for the other functions below:

Suggested change

outEdgesPerThread[omp_get_thread_num()][a % omp_get_max_threads()].emplace_back(HalfEdge{a, b});

outEdgesPerThread[omp_get_thread_num()][a % omp_get_max_threads()].emplace_back(a, b);

the current implementation of ´HalfEdge` does not have such a constuctor

Good idea to add it then. Improves readability.

fabratu · 2024-02-08T17:28:25Z

include/networkit/graph/GraphBuilder.hpp

+     * @param parallel If set to @c true, the graph will be build in parallel.
     */
-    GraphBuilder(count n = 0, bool weighted = false, bool directed = false);
+    GraphBuilder(count n = 0, bool weighted = false, bool directed = false, bool parallel = false);


Given the performance is increasing (as well if executed on one thread) and If the result is the same (and it should be maybe except for the order of nodes in the adjacency list) for both variants, then parallel can be set to true.

fabratu · 2024-02-08T17:29:34Z

Please also add tests for the new functions + update Python bindings/tests (if Graphbuilder has already bindings). Thx!

fabratu · 2024-02-08T21:54:00Z

networkit/cpp/graph/GraphBuilder.cpp

+    G.setEdgeCount(unsafe, numberOfHalfEdges / 2);
+}
+
+Graph GraphBuilder::toGraphParallel() {


This corresponds to toCompleteGraph in the former implementation. Only use one calling function for graph creation during refactoring.

fabratu · 2024-02-08T21:56:06Z

networkit/cpp/graph/GraphBuilder.cpp

+    outEdgesPerThread[omp_get_thread_num()][a % omp_get_max_threads()].emplace_back(HalfEdge{a, b});
+}
+
+void GraphBuilder::addEdgesToGraphParallel(Unsafe, Graph &G) {


This function only gives valid results, if addHalf/Out/In/EdgeParallel was used for adding edges. Either make sure to check this accordingly or better change the public API during refactoring.

fabratu · 2024-02-08T22:00:11Z

networkit/cpp/graph/GraphBuilder.cpp


+// Parallel functions
+
+void GraphBuilder::addEdgeParallel(node a, node b) {


See comment at function addEdgesInParallel: If the new concept is faster (also for one thread), then drop the previous addHalfEdge function (and others) in favor of the new one(s). If for the sequential case, nothing is gained, a wrapper/template is needed to distinguish between sequential and parallel insertion.

PetholzA added the code quality label Jan 31, 2024

PetholzA force-pushed the feature/20240131_generators_parallelGraphBuilder branch 2 times, most recently from 32e9c31 to 9b0793c Compare February 1, 2024 13:59

angriman requested changes Feb 3, 2024

View reviewed changes

PetholzA force-pushed the feature/20240131_generators_parallelGraphBuilder branch 2 times, most recently from 3ae8e61 to 6d75c6b Compare February 7, 2024 13:23

fabratu reviewed Feb 8, 2024

View reviewed changes

PetholzA force-pushed the feature/20240131_generators_parallelGraphBuilder branch 2 times, most recently from df989ab to e85c9d3 Compare February 9, 2024 12:18

This was referenced Feb 26, 2024

adds chungLuAlamEtAl generator + tests #1177

Merged

introduces parallel BA generator #1175

Merged

PetholzA force-pushed the feature/20240131_generators_parallelGraphBuilder branch 4 times, most recently from 923996a to 3419a30 Compare March 21, 2024 08:51

PetholzA closed this Mar 21, 2024

PetholzA force-pushed the feature/20240131_generators_parallelGraphBuilder branch from 3419a30 to 4086639 Compare March 21, 2024 16:19

PetholzA mentioned this pull request Mar 21, 2024

introduces new parallel graph builder and deprecates old one #1194

Merged

	outEdgesPerThread[omp_get_thread_num()][a % omp_get_max_threads()].emplace_back(HalfEdge{a, b});
	outEdgesPerThread[omp_get_thread_num()][a % omp_get_max_threads()].emplace_back(a, b);


		// Parallel functions

		void GraphBuilder::addEdgeParallel(node a, node b) {

introduces parallelGraphBuilder #1178

introduces parallelGraphBuilder #1178

Uh oh!

Conversation

PetholzA commented Jan 31, 2024

Uh oh!

angriman left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

fabratu commented Feb 8, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

fabratu Feb 8, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

fabratu commented Feb 8, 2024 •

edited

Loading

fabratu Feb 8, 2024 •

edited

Loading