1

我有一个VTF/IDF 向量的语料库，所以它们非常稀疏。
这是一个大约 2,500 x 150,000 的数组。
我想计算语料库中每个文档之间的余弦相似度。

这几乎是我能想到的最天真的方式。我已经知道三四个优化，但我不想假设答案。我想知道在此计算中使用 Chapel 的计算效率最高的方法。目标是得到X一个对称矩阵diag(X) = 0

use Norm,
    LinearAlgebra;

var ndocs = 2500,
    nftrs = 150000,
    docs = 1..ndocs,
    ftrs = 1..nftrs,
    V: [docs, ftrs] real,
    X: [docs, docs] real;

for i in docs {
  var n1 = norm(V[i,..]);
  for j in (i+1)..ndocs {
    var n2 = norm(V[j,..]);
    var c = dot(V[i,..], V[j,..]) / (n1*n2);
    X[i,j] = c;
    X[j,i] = c;
  }
}

编译使用

chpl -I/usr/local/Cellar/openblas/0.2.20/include -L/usr/local/Cellar/openblas/0.2.20/lib -lblas cosim.chpl

== 更新 ==

这实际上应该可以编译和运行。原始代码有以下@bradcray 建议的错误

4

2 回答 2

1

以下是可以对原始实现进行的一些改进：

  • 预先计算并缓存dot(V[i, ..], V[i, ..])到i数组中，以减少重复计算。
  • 使用1..V.sizeorV.domain代替1..V.shape[1]
    • V.shape是根据域大小计算的，而不是存储为字段。
  • 通过并行计算，利用该程序令人尴尬的并行特性X

有关更多详细信息，请参阅探索这些更改及其对时间的影响的GitHub 问题。

于 2017-11-26T17:57:08.400 回答
1

[Meta：这个问题一直困扰着我，因为它长期以来没有得到回答。由于它使用了“计算效率最高”的短语，我个人一直回避它。在实践中，很难保证任何解决方案都满足该描述，因为从一台目标机器或数据集到下一台目标机器或数据集可能会发生变化。但是由于没有其他人站出来，我会发表一些评论，希望它们可能有用。]

在您的代码中，有几件事对我来说很突出：

1）除非我遗漏了什么，否则您在计算norm(V[r, ..])过程中会进行很多次冗余计算。渐近地说，这表明您正在做只需要线性工作的二次工作。我建议为每一行计算一次范数并将其存储在一个数组中以避免这种冗余计算：

var normVrow: [docs] real = [r in docs] norm(V[r,..]);

然后，在内部循环中，您可以只引用normVrow[i]or normVrow[j]。

2）由于这是 Chapel 并且您的循环似乎没有交叉循环依赖性，而不是使用串行for循环，您可能应该使用并行forall循环进行此计算。有一个问题是：

(a) 将您的外循环更改为 a forall(这将导致负载不平衡，因为整个迭代空间是三角形的)，

(b) 将两个循环都更改为forall循环（这将通过过度分解来帮助解决负载不平衡问题，但也可能会增加开销），或

(c) 使外循环成为动态调度循环以解决负载不平衡问题。

我的直觉是使用 Chapel 的动态迭代器执行选项 c：

use DynamicIters;

forall i in dynamic(ndocs) {
  ...
}

3）最后要考虑的是避免三角迭代空间，只是冗余计算X[i,j]，X[j,i]即使它们具有相同的值。这在共享内存运行中可能没有意义，但如果您在分布式数组上进行计算X，您可能会减少通信，因为这些矩阵值将由不同的处理器存储。在这种方法中，您可以使用单个forall循环进行迭代X.domain，默认情况下结果将是负载均衡的，而无需动态迭代器。

于 2017-12-09T01:04:14.910 回答