Closed iceboy910447 closed 3 years ago
I cannot precisely execute your sample script, however I was able to eventually come to a failure condition that is consistent with your issue. Let me describe the steps I took to validate that my adaptation was reasonable, then I will describe what I think the issue and resolution would be.
1) I assume you're running in a Jupiter notebook (based on the description of the error and the syntax of the reproducing steps you provided)
2) osmnx is not installed by default in the docker containers. I assumed that if I simply added pip install osmnx
that this would install an acceptable version
3) I received an html 400 error when executing the ox.graph_from_place
call as provided above. I commented out the custom filter assuming that something in that definition might not be quite right. This allowed me to download a graph, although the graph is likely somewhat larger than you intend. Not sure why I couldn't execute your code as is... perhaps a configuration or version issue with osmnx
With these changes/assumptions, I was able to reproduce the kernel crashing that you describe. Note, as your print statements suggest, you arrive at the call to from_cudf_edgelist
. I added another print statement after that call to verify what I suspected which is that you fail during the call to from_cudf_edgelist
.
The error I was seeing is due to the fact that you set renumber=False
. If you set renumber=True
or if you do not specify the renumber
parameter then the code should work and the memory utilization should be very small (at least for this graph).
Let me describe what's happening a bit. Graph libraries tend to fall into two categories. Graph libraries (like networkx which you include in your notebook) which are focused on a simple user experience and hide details within the implementation, and graph libraries which are focused on performance. Tools like networkx either choose data structures that will work for any type of user data or they internally translate into more efficient representations without demonstrating that to the user. High performance graph libraries generally require the user to specify the graph in a form that is ready for their consumption.
cuGraph attempts to satisfy both sets of user needs, and renumbering is one of the areas where we expose underlying implementation to users so that if they know that their data is already optimally numbered then they can save the cost of renumbering their data. There are a collection of well known/used data sets in the graph analytic community that are already numbered in a way that makes executing graph analytics efficient. For those types of data sets setting renumber=False
will save unnecessary overhead.
The data I see in your cd_edge
Dataframe is not appropriate for bypassing the renumbering step. Renumbering is going to take your vertices (there are 30,925 in the unfiltered data set I downloaded... probably smaller with your filters activated) and renumber them to be in the half-open range [0, 30925). All data structures used within the SSSP algorithm are then arrays that are of size 30,925 (about 240 KB of GPU memory each). Without renumbering, the vertex ids will be used as is. The largest vertex id in the unfiltered input set is 8362075761. Consequently each temporary array created in SSSP without renumbering (haven't looked to see how many temporaries SSSP uses) would be of size 8,362,075,762 (about 64 GB of GPU memory) which far exceeds the memory capacity of your GPU.
https://docs.rapids.ai/api/cugraph/stable/api.html#cugraph.structure.graph.Graph.from_cudf_edgelist provides the documentation for this call. There is a somewhat simpler description than I described above. Please let me know if this makes sense and resolves your issue. We can certainly look into clarifying something in the documentation if you find it confusing or incomplete.
Hey,
thank you for your very detailed response.
I want to apologize for not including the fact, that i'm using this script in a jupyter notebook. You are correct in regard to that, and i do understand your explanation about the technical side. While I understood the underlying performance optimization regarding different graph libaries, i did not fully take into account the implications renumber = False
would have in regard to the memory usage.
To explain why i did use renumber = False
in my code anyways, let me explain the topic of the project for which i'm using this code. As a homework last summer i was given the task to use RAPIDS for the New York Taxi Fare Prediction Competion on Kaggle. Aside from using cuML to make prediction I also came up with the idea to use graphs of the street network and cugraph to locally calculate the shortest route between pickup and dropoff point.
Since only GPS coordinates are given, I had to write my own numba cuda function to calculate the next node to each point by my self. Back then i did not know how to map these GPS Points to the internal vertex id that is produced by renumber = True
. I still don't know how to extract the map of internal to external vertex id's if i run from_cudf_edgelist
. After i read your response i found the add_internal_vertex_id
function that might solve this problem, even though i'm still curious if there is a way to extract the map generated by renumber = True
.
Since i did not know back than how to transform those next node id's into internal node id's i did run the code with renumber = True
on the same hardware i'm using now, with the only difference that i used python` 3.7, cuda 10.1 and RAPIDs 0.16, back then. For some reason that worked just fine, even iterating these functions to make a SSSP calculation for a graph with more than 217k nodes and 570k edges did not cause an out_of_memory exception on my 11GB VRAM graphic card, even though the external vertex id were also in the same range you saw in my example code. After i read your technical explanation im very confused why it did work anyways.
Nevertheless I will try to implement your solution in my code, see if it works and report the results back to you.
Maybe inbetween you could doublecheck another observation i made when i tried to trace back the bug. When i tried to change the order of some of my code i tried to generate the graph before i calculate the nearest node for each GPS-Point and then make the SSSP call. In addition to that i also included some print
and time.sleep
calls to follow the progress of the script more closely, and when i executed the code, according to the observed time and output of my script, i was able to call from_cudf_edgelist
and complete the the nearest node calculation before the kernel died. I'm not sure if my observations are correct, since i read that SSSP for example will use streams in future versions, so maybe a delayed function call or incomplete execution caused a time difference between the acctual execution and my print statements.
I hope you can reproduce this observation and might be able to give further explanation on why my notebook seemingly worked on a previous software version.
Until then i want thank you for your time and explanation, that you provided so far!
Best regards iceboy
Let me answer the easy question first. The renumbering logic, and how it has been exposed to the user, has evolved over the last several releases. The focus has been on making it significantly more transparent to the user. I don't remember the exact sequence of updates to this functionality. For a while renumbering always happened (you couldn't turn it off), for a while it happened but it was not properly supported in all algorithms. In version 0.17 things were finally consistently supported across all algorithms. Most likely your tests in previous versions were actually using renumbering under the covers and you didn't realize it.
Regarding accessing the internal number map, the preferred method is to use the add_internal_vertex_id
method that you discovered. Anything else that you do will probably break when you migrate your code to run on a new release of cuGraph.
The current implementations (0.17 and 0.18 which will be released next month) use a python class called NumberMap to represent the translation back and forth between the external vertex identifiers (whatever they may be) and the internal vertex id (integer in the range 0..num_vertices). In these two releases the mapping between them is represented in a Dataframe that identifies the mapping.
Note that this code is actively being redesigned. Relying on the current implementation will certainly break in some future release (perhaps as early as 0.19 which will be out in the spring).
If you find that add_internal_vertex_id
is insufficient for your needs, I would recommend adding a feature request that describes what you think you need so we can create a durable API method that will be supported across releases. I would be happy to help you identify whether we have other existing APIs that could satisfy your need or if you actually need something different.
Regarding the reordering of steps, if you can provide an example of the steps you took that worked I can investigate that. I tried a few things but was not able to construct an example that worked with renumber=False
.
@ChuckHastings I'd like to thank you for your solution. I tried renumber = True
and it worked. I was surprised to see, that i still could use the external node id with the renumbered Graph in sssp()
. After I looked at the code for sssp
, i found out, that the graph has an attribute to check if the edges were renumbered. With every call of sssp()
the external and internal vertex ids are being mapped back and forth. To see how much overhead this created, i used compute_renumber_edge_list
to get that map out of a renumbered graph and use those ids instead for from_cudf_edgelist
with renumber = False
to create a second graph and used the internal id's with the sssp
call. While using this methode with several graphs i could see between 20 and 30 % shorter runtimes for a loop that simply iterating the sssp call for a list of nodes.
I'm very surprised to see this. If the vertex id's are between 0 and n where n is the number of vertexs in the graph, the resulting cudf dataframe from the sssp
call is sorted by the vertex column. Since that dataframe is allways sorted that way, it would be easy to precompute a cudf.series
during the from_cudf_edgelist
call, that maps the sorted internal vertex ID's to the external vertex id's and simply add this series as a new column to the result dataframe of the sssp
call. If we igore the predecessors as done in cugraph.traversal.sssp.shortest_path_length()
this could help to decrease the overhead generated by the mapping process. I couldn't see who the mapping process is done for cugraph.traversal.sssp.shortest_path_length()
, but if this approach is faster than the current approach, i would like to add this as feature request for a future version.
Maybe it would also be helpful for the documentation in https://docs.rapids.ai/api/cugraph/stable/api.html#cugraph.traversal.sssp.sssp to add a sentence, that in case the edgelist was renumbered the external vertex IDs still can be used for sssp()
and that the function will take care of mapping external to internal vertex ids and vice versa.
Since im relatively new to github and don't know who to add the doc tag or feature request tag on my own, would mind to add it for me, please?
At the end, i'd like to thank you again for the explanation and help to solve this issue.
Best regards iceboy
Describe the bug Dear rapids developer,
I encountered a memory spike during usage of SSSP and unexpected death of the python kernel. Spike from 2GB to above 10GB at the start of the function. The function was working during prior usage with rapids 0.16 and CUDA 10.1, even with graphs several times bigger than this one
Could you please doublecheck?
Thanks, iceboy910447
Steps/Code to reproduce bug
import nvstrings
import numpy as np import pandas as pd import cudf, cuml import dask_cudf import io, requests import math import gc import time
Plotting
import matplotlib.pyplot as plt import seaborn as sns
Learning
import cuspatial import cugraph import pandas as pd pd.version #1.1.4 import rmm rmm.mr.set_current_device_resource(rmm.mr.ManagedMemoryResource()) cudf.set_allocator(allocator="managed") import multiprocessing as mp import numpy as np import networkx as nx import osmnx as ox import requests import matplotlib import matplotlib.cm as cm import matplotlib.colors as colors %matplotlib inline ox.config(use_cache=True, log_console=True,timeout=1000) ox.version
G = ox.graph_from_place('Manhattan, New York, USA',simplify=True,truncate_by_edge=True,custom_filter='["area"!~"yes"]["highway"~"motorway|trunk|primary|secondary|tertiary|residential|motorway_link|trunk_link|primary_link|secondary_link|tertiary_link"]["highway"!~"service"]') #4503 Nodes, 9668 Edges print("Build edgelist") pd_edge = nx.to_pandas_edgelist(G) # generating a pandas dataframe containing all edgeinformations based on the given Graph print(pd_edge.dtypes) print("Build edgelist 2") pd_edge_zwei = pd_edge[["source","target","length"]] # simplification of the dataframe print(pd_edge_zwei.source.min()) print(pd_edge_zwei.target.min())
print(pd_edge_zwei.length.max()) print("Build edgelist 3") cd_edge = cudf.from_pandas(pd_edge_zwei) cd_edge.length = cd_edge.length.astype("float32") print(cd_edge.dtypes) G_zwei = cugraph.Graph() # building a cugraph Graph from the edgelist dataframe
G_zwei.from_cudf_edgelist(cd_edge, source = 'source',destination = 'target', edge_attr = 'travel_time', renumber = False)
G_zwei.add_edge_list(cd_edge['source'],cd_edge['target'],cd_edge['length'])
print("sleep wird durchgeführt") time.sleep(10) print("sleep wird beendet") G_zwei.from_cudf_edgelist(cd_edge,source='source', destination='target', edge_attr='length', renumber=False) distances = cugraph.sssp(G_zwei,42422026) # Single Source Shortest Path Calculation for one source node distances.head()
Expected behavior A clear and concise description of what you expected to happen.
Environment overview (please complete the following information) docker rapids 0.17 ubuntu 20.04 cuda 11.2
docker pull rapidsai/rapidsai-core:cuda11.0-runtime-ubuntu18.04-py3.8 docker run --gpus all --rm -it -p 8888:8888 -p 8787:8787 -p 8786:8786 \ rapidsai/rapidsai-core:cuda11.0-runtime-ubuntu18.04-py3.8
Environment details Please run and paste the output of the
cugraph/print_env.sh
script here, to gather any other relevant environment detailsClick here to see environment details