如何将输入矩阵分解成子矩阵进行并行GPU处理？

Question

我是stackoverflow的新人，我很高兴发表我的第一个问题。实际上，我是编程领域的新手，但我有一些基本知识，我实际上是在使用Python来解决一个分类问题。我有一大组数据（在我的实际问题中，n=60326），每个向量大约有416维。我需要计算这些不同向量之间的曼哈顿距离，以便根据相似性对我的数据集进行分类（取一个随机参考向量，并将距离介于0和1之间的最接近向量合并在一起）我已经熟悉Kmeans和基本的ML聚类算法…我的实际问题是我需要加速时间使用GPU（CUDA）在开始分类之前首先计算距离矩阵，它的大小为n²（60326 x 60326，我们可以将其减少到n²/2，因为它是一个对称矩阵），所以我的实际问题是如何实现CUDA在这种情况下，我已经安装了CUDA包与Python。在

我从并行CPU的处理开始，它提供了一个内存错误

import pandas as pd
import time  
import time
import numpy as np
import random
from scipy.spatial import distance
from sklearn.metrics.pairwise import pairwise_distances
signatures=pd.read_csv("C:\\Users\\YMH1\\Documents\\Reduce Java code\\BOBST.txt", sep=' ',header=None,usecols=[*range(2,417)])
PartName = pd.read_csv('C:\\Users\\YMH1\\Documents\\Reduce Java code\\misumi_new.txt', sep=' ', header=None, usecols=[*range(0,1)])
signatures_vector=np.array(signatures)
PartName_vector=np.array(PartName)
D = pairwise_distances(X = signatures_vector, metric = 'manhattan', n_jobs = -1)
print(D)

现在，我正在尝试实现CUDA，因为它加快了时间，所以我编写了以下代码：

^{pr2}$

我的问题是，当我们使用CUDA时，如何定义曼哈顿规范，在def manhattan内部要做什么修改 非常感谢你

Answer 1

My question is how to define the manhattan norm when we use CUDA, what are the modifications to be made inside the def manhattan

根据documentation，manhattan距离度量是元素差的绝对值的两个向量之和。在

你可能遇到的一个问题是内存空间。如果我们假设距离度量（即矩阵元素）的输出被表示为一个普通的python数量，这可能会占用8个字节的内存。对于指定的维度（60326），这意味着矩阵将占用60326*60326*8字节，这几乎是30GB。即使我们假设你只存储了其中的一半，即使我们假设是32位的绝对差异之和，这仍然需要超过7GB的存储空间。在

当我试图使用sckit learn方法运行这样的测试时，我遇到了麻烦，即使是在一台拥有128GB系统内存的机器上：

# cat t5.py
import numpy as np
import random
from scipy.spatial import distance
from sklearn.metrics.pairwise import pairwise_distances

vector_length = 416
num_signatures = 60000
sig_pattern = np.array([0,1,2,3], dtype=np.float32).reshape(4,1)
signatures = np.tile(sig_pattern,(num_signatures, vector_length//sig_pattern.shape[1]))
E = pairwise_distances(signatures, metric = 'manhattan', n_jobs = -1)
print(E[:8,:8])
# time python t5.py

Traceback (most recent call last):
  File "t5.py", line 17, in <module>
    E = pairwise_distances(signatures, metric = 'manhattan', n_jobs = -1)
  File "/root/anaconda2/lib/python2.7/site-packages/sklearn/metrics/pairwise.py", line 1247, in pairwise_distances
    return _parallel_pairwise(X, Y, func, n_jobs, **kwds)
  File "/root/anaconda2/lib/python2.7/site-packages/sklearn/metrics/pairwise.py", line 1096, in _parallel_pairwise
    for s in gen_even_slices(Y.shape[0], n_jobs))
  File "/root/anaconda2/lib/python2.7/site-packages/sklearn/externals/joblib/parallel.py", line 789, in __call__
    self.retrieve()
  File "/root/anaconda2/lib/python2.7/site-packages/sklearn/externals/joblib/parallel.py", line 699, in retrieve
    self._output.extend(job.get(timeout=self.timeout))
  File "/root/anaconda2/lib/python2.7/multiprocessing/pool.py", line 572, in get
    raise self._value
multiprocessing.pool.MaybeEncodingError: Error sending result:
'[array([[ 0.,  416.,  832., ...,  416.,  832., 1248.],
       [ 416.,    0.,  416., ...,    0.,  416.,  832.],
       [ 832.,  416.,    0., ...,  416.,    0.,  416.],
       ...,
       [ 416.,    0.,  416., ...,    0.,  416.,  832.],
       [ 832.,  416.,    0., ...,  416.,    0.,  416.],
       [1248.,  832.,  416., ...,  832.,  416.,    0.]])]'. Reason: 'OverflowError('cannot serialize a string larger than 2 GiB',)'

real    31m47.361s
user    405m28.155s
sys     8m19.851s

在这种情况下，在我的机器上进行计算似乎需要30分钟。输出测试矩阵看起来大致正确，但是python抛出了一个错误，因为一些中间表示是>；2GB。在

内存大小问题也是numba/cuda实现中需要考虑的重要问题之一。在

然而，要执行的操作相对简单。根据我的测试，它可以比numpy/scikit学习方法运行得快得多。在

下面是一个成功的例子：

^{pr2}$

在本例中，我将signatures向量限制为60000个，而不是60320个，因为较大的数字会导致输出矩阵太大，无法容纳16GB Tesla P100 GPU的可用内存。如果您的GPU内存少于16GB，则此代码将无法正常工作。您需要将问题缩小到更小的签名向量数。将向量分成两组，并在两组之间进行距离计算，以填充整个矩阵，这应该相对简单。在

然而，在我的测试机器上的numba代码只需11秒就可以运行，并且对于我正在打印的输出矩阵的非常小的16x16块似乎产生了相同的结果。在

如果我分析一下这段代码，我会发现GPU内核在大约3秒钟内运行，从GPU到CPU的巨大输出矩阵的数据传输时间大约需要6秒，其余的大约是python开销的2秒。在

实际的GPU算法是面向块的。每个块负责将8个矢量与整个矢量阵列进行比较。每个块首先将8个向量加载到共享内存中，然后遍历整个向量数组，根据这8个向量计算曼哈顿距离。块使用块跨步循环来遍历整个数组。在每个循环迭代结束时，与当前比较相对应的8个曼哈顿距离写入输出数组。在

此外，对代码进行了细微的更改，因此只计算对角线上方的矩阵输出值。由于计算是分块进行的，因此不计算对角线上方没有元素的块。这样可以将处理时间减少大约一半，但完整的输出矩阵仍在内存中。因此，上面16x16输出的左下象限全部为零，因为8x8象限完全“低于”对角线，因此跳过了对它的处理，因为问题中已经指出了类似情况。在