1

我有一个非常大的对角矩阵，我需要对其进行拆分以进行并行计算。由于数据局部性问题，遍历矩阵并在n个线程之间拆分每个第n个计算是没有意义的。目前，我正在按以下方式划分k x k对角矩阵，但它在计算数量方面产生不相等的分区（最小的部分比最大的部分长几倍）。

def split_matrix(k, n):
    split_points = [round(i * k / n) for i in range(n + 1)] 
    split_ranges = [(split_points[i], split_points[i + 1],) for i in range(len(split_points) - 1)]
    return split_ranges

import numpy as np
k = 100
arr = np.zeros((k,k,))
idx = 0
for i in range(k):
    for j in range(i + 1, k):
        arr[i, j] = idx
        idx += 1


def parallel_calc(array, k, si, endi):
     for i in range(si, endi):
         for j in range(k):
             # do some expensive calculations

for start_i, stop_i in split_matrix(k, cpu_cnt):
     parallel_calc(arr, k, start_i, stop_i)

您对实现或库功能有什么建议吗？

4

2 回答 2

1

在一侧进行了多次几何计算后，我得出了以下分区，该分区在每个垂直（或水平，如果需要）分区中给出了大致相同数量的矩阵点。

def offsets_for_equal_no_elems_diag_matrix(matrix_dims, num_of_partitions):
    if 2 == len(matrix_dims) and matrix_dims[0] == matrix_dims[1]:  # square
        k = matrix_dims[0]
        # equilateral right angle triangles have area of side**2/2 and from this area == 1/num_of_partitions * 1/2 * matrix_dim[0]**2 comes the below
        # the k - ... comes from the change in the axis (for the calc it is easier to start from the smallest triangle piece)
        div_points = [0, ] + [round(k * math.sqrt((i + 1)/num_of_partitions)) for i in range(num_of_partitions)]
        pairs = [(k - div_points[i + 1], k - div_points[i], ) for i in range(num_of_partitions - 1, -1, -1)]
        return pairs
于 2017-09-15T13:27:26.917 回答
0

我认为你应该更新你的split_matrix方法，因为它返回的分割范围比你想要的少（设置cpu_cnt=4将只返回3元组，而不是4）：

def split_matrix(k, n):
    split_points = [round(i * k / n) for i in range(n+1)] 
    return [(split_points[i], split_points[i + 1],) for i in range(len(split_points) - 1)]

编辑：如果您的数据位置不是那么字符串，您可以尝试以下操作：创建一个queue任务，在其中添加应执行此计算的所有索引/条目。然后你初始化你的并行工作者（例如使用multiprocessing）并让他们启动。这个工人现在从 中挑选一个元素queue，计算结果，将其存储（例如在另一个中queue）并继续下一个项目，等等。

如果这不适用于您的数据，我不认为您可以再改进。

于 2017-09-15T10:41:02.287 回答