GPU 上稀疏线性系统的解决方案，来自 nvidia 的论文

Question

我正在阅读一篇关于在 GPU 上求解线性系统（稀疏）的 Nvidia 文章。我陷入了

chainPtrHost

数据结构的构建中。我明白它的作用，但我不明白它是如何构造的。有人提到它取决于多个级别的并行性，但似乎没有解释如何确定它。

有人知道如何建造吗？

参考论文：GPU上预条件迭代方法中稀疏三角线性系统的并行求解

Answer 1

我的理解是，人们只是在主机上按顺序迭代各个级别，如下所示，非常基本的、未经测试的 C++ 片段：

#include <vector>

std::vector<int> create_chains(const std::vector<int> &levels, int threshold) {
    const int num_levels = static_cast<int>(std::size(levels) - 1);
    
    std::vector<int> chains{};
    chains.reserve(std::size(levels)); // optional optimization to avoid re-allocation

    bool no_open_chain = true;

    for (int idx = 0; idx < num_levels; ++idx) {
        const int num_rows = levels[idx + 1] - levels[idx];
        const bool new_single_link_chain = (num_rows > threshold);

        if (no_open_chain || new_single_link_chain) { // new chain starts here
            chains.push_back(idx + 1); // 1-based index
        }

        no_open_chain = new_single_link_chain;
    }
    chains.push_back(num_levels + 1); // 1-based end of last chain

    return chains;
}

threshold

的正确值取决于单块求解器内核的实现。如果每个线程在一行上操作，并且对占用/共享内存等的块大小没有无限制，则它可能是

1024

，即每个块的最大线程数（行）。