压缩稀疏列矩阵的并行构造
Parallel Construction of Compressed Sparse Column Matrix
具有 m 列的压缩稀疏列矩阵 (csc)，定义为 here。
它有三个数组：Data、Indices 和 Indptr。
- indptr 是一维数组，大小为 m+1
- indices 是矩阵中所有非零项的行索引。
- indices[indptr[i]:indptr[i + 1]] 是第 i 列的所有非零条目的行索引。这些非零条目的值在 data[indptr[i]:indptr[i + 1]]
中定义
具有 n 行的压缩稀疏行 (csr) 矩阵具有类似的 definition。
问题：
Cpu 从事 n 个工作。第 p 个作业为具有 n 行和 m 列的稀疏矩阵（csc 或 csr）的第 q 行生成数据。 p和q不一定要相等，只要哪个job对应哪一行被记录即可。
如何有效地从作业中收集数据并生成 csc 矩阵？
当前解决方案：
方法 A.
- 创建名为 shared_data、shared_indices、shared_indptr（它们定义了一个 csr 矩阵）、shared_ordering 的空数组。 shared_data 和 shared_indices 的大小取决于对非零条目数量的估计。设置 shared_indptr[0] = 0。这些数组由作业共享。
- 非零条目数 (count_nz) 和输入 csr 矩阵的行数 (count_row) 的计数器也由作业共享。
- 访问 1 和 2 中描述的资源需要获取锁。
- 每个作业都知道它试图放入 csr 矩阵的非零条目 (job_indices) 的列索引。它还知道非零条目的值 (job_data) 和非零条目的数量 (job_nz)。
- 每个作业都尝试获取锁。
- 获取锁后，作业将执行以下操作。然后释放锁
.
after acquiring lock
shared_data[counter_nz:(counter_nz + job_nz)] = job_data
shared_indices[counter_nz:(counter_nz + job_nz)] = job_indices
shared_indptr[count_row + 1] = shared_indptr[count_row] + job_nz
shared_ordering[counter_row] = job_id
counter_nz += job_nz
counter_row += 1
release lock.
通过包装共享数组创建一个 csr 矩阵对象（如 scipy.sparse.csr_matrix((shared_data, shared_indices, shared_indptr)）。
将csr转换为csc矩阵（目标是制作csc矩阵而不是csr矩阵...）
这种方法的问题是锁确实会降低性能。这就像十几个人试图使用同一个工具来处理项目的不同部分。
方法 B
每个cpu做m个作业，按照A中描述的方法构建一个csc矩阵。这种方式占用更多内存，但生成矩阵的速度更快。
方法 C
一个 cpu 从事 m 工作并构建 csc 矩阵。在 12 cpu 机器上，这比方法 A 花费的时间大约多两倍。
方法 D（更新 06/05/2016）
有 s cpu 个内核。最终 csc 矩阵的 shared_data、shared_indptr 和 shared_indices 数组以及 shared_ordering 数组由所有 cpu 核心共享。无需锁。每个 cpu 核心运行一个子进程（而不是一直启动和停止子进程）每个 cpu 核心进程 m 个作业的 1/s，每个 cpu 构造一个小的 csc 矩阵A中描述的方法。 cpu完成所有作业后，它将放入其小csc矩阵的三个数组中的每一个的数据的三种大小广播给其他cpu。一旦 cpu 从所有其他 cpu 接收到此信息（有 s - 1 个信息要从其他 cpu 接收），它会计算其小 csc 矩阵的三个数组的位置在最终 csc 矩阵的三个数组中。然后它将它的小 csc 矩阵复制到共享 csc 矩阵。
之后，cpu向其他cpu发送信号。一旦 cpu 收到 s - 1 个信号，它就会开始下一个循环。 （可能不需要第二次同步。）
希望同步比 A 中的锁浪费的时间少得多。而且这种方法可以从 1 cpu 核心线性扩展到 12 cpu 核心。如果谁有这方面的经验，欢迎提出建议。
方法 D 的缺点是它使用的内存量是保存最终 csc 矩阵所需内存量的两倍。一半的内存用于共享数组。另一半被小 csc 矩阵的所有数组使用......这似乎没问题。在方法 B 中，每个 cpu 只能使用大约 1/s 的整个内存。方法 D 更好。
可以将小矩阵的数组保留为缓冲区，这样就不会浪费时间重新创建 numpy 数组。
我正在尝试使用 B 并优化每个 cpu 核心的每个作业的内存使用。但是，如果方法 A 可以通过更智能的锁设计避免降低性能，我会使用 A...我想我会选择 D。
相关问题：
Efficiently populate SciPy sparse matrix from subset of dictionary
听起来你创建了一个csr矩阵，然后直接修改3个属性数组。您可以通过附加到现有数组来实现。虽然我操作过 csr 的 data 属性，但我没有直接更改其他属性的经验。如果没有稀疏代码反对，似乎很难可靠地做到这一点。
另一种方法是先构建3个数组，然后再构建csr。而不是对每一行使用 np.append，附加到列表，然后使用 np.concatenate 加入它们。
如果您使用 coo 样式的输入，您可以按任何顺序追加行。一项工作不必知道前几行中有多少项。
coo 样式输入特别适用于有限元刚度矩阵，其中元素矩阵重叠。而coo输入可以直接进入csc.
我最近在这里讨论了从块构建稀疏矩阵：
和
tile operation to create a csr_matrix from one row of another csr_matrix
lil 适用于增量工作，因为属性是列表的两个对象数组 - 每行一个列表。所以更新只需要用新列表替换两个空列表——一个指针操作。但我认为 lil 到 csc 比 coo 到 csc 慢（但我没有测试过）。
具有 m 列的压缩稀疏列矩阵 (csc)，定义为 here。
它有三个数组：Data、Indices 和 Indptr。
- indptr 是一维数组，大小为 m+1
- indices 是矩阵中所有非零项的行索引。
- indices[indptr[i]:indptr[i + 1]] 是第 i 列的所有非零条目的行索引。这些非零条目的值在 data[indptr[i]:indptr[i + 1]] 中定义
具有 n 行的压缩稀疏行 (csr) 矩阵具有类似的 definition。
问题：
Cpu 从事 n 个工作。第 p 个作业为具有 n 行和 m 列的稀疏矩阵（csc 或 csr）的第 q 行生成数据。 p和q不一定要相等，只要哪个job对应哪一行被记录即可。
如何有效地从作业中收集数据并生成 csc 矩阵？
当前解决方案：
方法 A.
- 创建名为 shared_data、shared_indices、shared_indptr（它们定义了一个 csr 矩阵）、shared_ordering 的空数组。 shared_data 和 shared_indices 的大小取决于对非零条目数量的估计。设置 shared_indptr[0] = 0。这些数组由作业共享。
- 非零条目数 (count_nz) 和输入 csr 矩阵的行数 (count_row) 的计数器也由作业共享。
- 访问 1 和 2 中描述的资源需要获取锁。
- 每个作业都知道它试图放入 csr 矩阵的非零条目 (job_indices) 的列索引。它还知道非零条目的值 (job_data) 和非零条目的数量 (job_nz)。
- 每个作业都尝试获取锁。
- 获取锁后，作业将执行以下操作。然后释放锁
.
after acquiring lock
shared_data[counter_nz:(counter_nz + job_nz)] = job_data
shared_indices[counter_nz:(counter_nz + job_nz)] = job_indices
shared_indptr[count_row + 1] = shared_indptr[count_row] + job_nz
shared_ordering[counter_row] = job_id
counter_nz += job_nz
counter_row += 1
release lock.
通过包装共享数组创建一个 csr 矩阵对象（如 scipy.sparse.csr_matrix((shared_data, shared_indices, shared_indptr)）。
将csr转换为csc矩阵（目标是制作csc矩阵而不是csr矩阵...）
这种方法的问题是锁确实会降低性能。这就像十几个人试图使用同一个工具来处理项目的不同部分。
方法 B
每个cpu做m个作业，按照A中描述的方法构建一个csc矩阵。这种方式占用更多内存，但生成矩阵的速度更快。
方法 C
一个 cpu 从事 m 工作并构建 csc 矩阵。在 12 cpu 机器上，这比方法 A 花费的时间大约多两倍。
方法 D（更新 06/05/2016）
有 s cpu 个内核。最终 csc 矩阵的 shared_data、shared_indptr 和 shared_indices 数组以及 shared_ordering 数组由所有 cpu 核心共享。无需锁。每个 cpu 核心运行一个子进程（而不是一直启动和停止子进程）每个 cpu 核心进程 m 个作业的 1/s，每个 cpu 构造一个小的 csc 矩阵A中描述的方法。 cpu完成所有作业后，它将放入其小csc矩阵的三个数组中的每一个的数据的三种大小广播给其他cpu。一旦 cpu 从所有其他 cpu 接收到此信息（有 s - 1 个信息要从其他 cpu 接收），它会计算其小 csc 矩阵的三个数组的位置在最终 csc 矩阵的三个数组中。然后它将它的小 csc 矩阵复制到共享 csc 矩阵。
之后，cpu向其他cpu发送信号。一旦 cpu 收到 s - 1 个信号，它就会开始下一个循环。 （可能不需要第二次同步。）
希望同步比 A 中的锁浪费的时间少得多。而且这种方法可以从 1 cpu 核心线性扩展到 12 cpu 核心。如果谁有这方面的经验，欢迎提出建议。
方法 D 的缺点是它使用的内存量是保存最终 csc 矩阵所需内存量的两倍。一半的内存用于共享数组。另一半被小 csc 矩阵的所有数组使用......这似乎没问题。在方法 B 中，每个 cpu 只能使用大约 1/s 的整个内存。方法 D 更好。
可以将小矩阵的数组保留为缓冲区，这样就不会浪费时间重新创建 numpy 数组。
我正在尝试使用 B 并优化每个 cpu 核心的每个作业的内存使用。但是，如果方法 A 可以通过更智能的锁设计避免降低性能，我会使用 A...我想我会选择 D。 相关问题： Efficiently populate SciPy sparse matrix from subset of dictionary
听起来你创建了一个csr矩阵，然后直接修改3个属性数组。您可以通过附加到现有数组来实现。虽然我操作过 csr 的 data 属性，但我没有直接更改其他属性的经验。如果没有稀疏代码反对，似乎很难可靠地做到这一点。
另一种方法是先构建3个数组，然后再构建csr。而不是对每一行使用 np.append，附加到列表，然后使用 np.concatenate 加入它们。
如果您使用 coo 样式的输入，您可以按任何顺序追加行。一项工作不必知道前几行中有多少项。
coo 样式输入特别适用于有限元刚度矩阵，其中元素矩阵重叠。而coo输入可以直接进入csc.
我最近在这里讨论了从块构建稀疏矩阵：
和
tile operation to create a csr_matrix from one row of another csr_matrix
lil 适用于增量工作，因为属性是列表的两个对象数组 - 每行一个列表。所以更新只需要用新列表替换两个空列表——一个指针操作。但我认为 lil 到 csc 比 coo 到 csc 慢（但我没有测试过）。