[Question]: Usage of Graph Algorithms and Any Slowdowns?

[nv-rliu]

Hi there,

I'm interested in understanding if nipype depends on any graph algorithms from its usage of NetworkX? If so,

• What algorithms are used for what purpose?
• What graph sizes are they being used with?
• Have users experienced any slowdowns or issues with algorithms provided by NetworkX? (Speed, algorithm availability, etc)

Furthermore, would users be interested in accelerated nx algorithms via a GPU backend? This would involve zero code change.

Any insight into this topic would be greatly appreciated! Thank you.

[effigies]

Graphs may be on the order of thousands of nodes, rarely tens of thousands in my experienced. The purpose is establishing data dependencies, verifying that the resulting graph is acyclic, and generating a topologically sorted list of nodes.

@HippocampusGirl is the most likely person I know of to have actually profiled to see if networkx is in any way a bottleneck.

[HippocampusGirl]

Hi @nv-rliu,
I don't think networkx was ever a bottleneck, even when I created graphs with tens of thousands of nodes. You can see my (somewhat out of date) profiles in #3260 and #3184 that most of the time is spent on the custom logic that is used to transform workflows into a DAG for execution.
I think the only graph algorithm in use in Nipype that isn't available in networkx is the one used to actually execute the DAG. The current implementation uses sparse scipy matrices to decide which jobs are candidates to be run next.

nipype/nipype/pipeline/plugins/base.py

Line 145 in 44551d3

jobs_ready = np.nonzero(~self.proc_done & (self.depidx.sum(0) == 0))[1]

[nv-rliu]

Hi @HippocampusGirl

Thank you for the insight. I wanted to see if there's any part of the project (graph algs) that could benefit from being accelerated via GPU. Please let me know if something ever comes up!