gpu - NetworkX all_pairs_dijkstras 的 CuGraph 实现

Question

我正在尝试将我必须的 cpu 绑定(bind)算法转换为 GPU 算法，但我遇到了 cugraph 的各种问题。其中一部分是我的无知，另一部分是 cugraph 的初期和不发达，最后一部分是我只是在搞清楚优雅的矢量化方法。

假设我有 m 个数据观测值，其中包含 n 个特征。我通过计算所有观测值的所有观测值的欧氏距离来创建距离矩阵(注意:这不是我需要帮助的部分，也不是最佳的。只需添加这部分以获得易于理解、可重现的代码)

import numpy as np

def l1_distance(arr):
    return np.linalg.norm(arr, 1)

X = np.random.randint(low=0, high=255, size=(700,4096))

W = np.empty((700,700))

for i in range(700):
    for j in range(700):
        W[i,j] = l1_distance(X[i,:] - X[j,:])

第一个挑战

import networkx as nx

def build_weighted_graph(W):
    n = W.shape[0]
    Graph = nx.DiGraph()
        for i in range(n):
            for j in range(n):
                Graph.add_weighted_edges_from([(i,j,min(W[i,j], W[j,i]))])
    return Graph

其中输入 W 矩阵是欧氏空间中的方形距离矩阵(节点最初由 x 特征组成)。例如。第 1 行第 9 行是节点 1 和节点 9 之间的距离，第 20 行第 30 行是节点 20 和节点 30 之间的距离，依此类推。图形现在在连接的节点之间绘制边，边的权重是欧氏距离测量.

我花了大约 8 个小时试图弄清楚如何将其转移到 GPU，但即使在 NVIDIA 自己的文档中，他们也声称

The code block is perfectly fine for NetworkX. However, the process of iterating over the dataframe and adding one node at a time is problematic for GPUs and something that we try and avoid. cuGraph stores data in columns (i.e. arrays). Resizing an array requires allocating a new array one element larger, copying the data, and adding the new value. That is not very efficient.

If your code follows the above model of inserting one element at atime, the we suggest either rewriting that code or using it as iswithin NetworkX and just accelerating the algorithms with cuGraph.

所以我放弃了，让那部分保持原样。算法的下一部分使用 dijkstra 算法并计算所有节点到所有其他节点的最短路径

res = dict(nx.all_pairs_dijkstra_path_length(Graph))

在 cugraphs 实现中，它们只有单一源 dijkstra，它将图形和源节点作为参数。这与 networkx 的库形成对比，networkx 的库随附上述方法并在所有节点上无处不在地应用 dijkstra。这意味着我将不得不为每个节点(更多 for 循环)迭代调用 SSSP(cugraph 的 dijkstra 实现)。

在我通过连接节点获得距离后，我创建了另一个方形距离矩阵，它现在基于通过连接节点的距离而不是最初采用欧氏距离。

D = np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            D[i,j] = res[i][j]

我这辈子都想不出如何为 GPU 向量化其中的任何一个。在正确方向上的任何帮助将不胜感激。目前对于我的算法运行的数据集，CPU 绑定(bind)算法需要大约 5 分钟才能运行 698 个节点。因此，为什么我要尝试在 GPU 方面加快速度

Answer 1

您的第一个问题——欧几里德距离矩阵的初始化——的答案似乎在 Using cupy to create a distance matrix from another matrix on GPU 中得到了解答。 ，但您当然可以使用 cuDF 和 cuGraph 优化图的创建和 Dijkstra 矩阵的计算。

要高效地创建图形，您可以构建一个列出边及其权重的 cuDF 数据框。由于欧几里德距离矩阵的结构，这很简单。 cuGraph 将此数据框作为边列表接收并返回图形。然后您可以遍历节点以计算最短的适用顶点。如果问题规模增加，这可以在以后与 Dask 并行化或分发。

对于这个问题大小，下面的代码比使用 nx.all_pairs_dijkstra_path_length 快大约 40 倍，它还包括初始距离计算。

import cupy as cp
import cudf as cd
import cugraph as cg

def build_weighted_graph_gpu(X, n):
    X_d = cp.array(X)
    G_d = cp.zeros([n, n])
    for i in range(n):
        G_d[i,:] = cp.abs(cp.broadcast_to(X_d[i,:], X_d.shape) - X_d).sum(axis=1)
    return G_d

def dijkstras_matrix_gpu(W_d):
    n = np.shape(W_d)[0]
    
    # Create a columnar dataframe describing edges
    df_g = cd.DataFrame({
        'source':      cp.array([x // n for x in range(n*n)]),
        'destination': cp.array([x % n for x in range(n*n)]),
        'weight':      cp.minimum(W_d, cp.transpose(W_d)).ravel()})
    
    graph_d = cg.Graph()
    
    graph_d.from_cudf_edgelist(df_g, source='source', destination='destination', edge_attr='weight', renumber=False)
    
    dist_d = cp.empty_like(W_d)

    for i in range(n):
        dist_d[i,:] = cp.asarray(cg.traversal.shortest_path(graph_d, i)['distance'])
    
    return dist_d

distance_matrix = dijkstras_matrix_gpu(build_weighted_graph_gpu(X))