如何将对角矩阵沿一个轴拆分为相等数量的项目?
How to split diagonal matrix into equal number of items each along one of axis?
我有一个非常大的对角矩阵,我需要拆分它以进行并行计算。由于数据局部性问题,遍历矩阵并在 n 线程之间拆分每个 n-th 计算是没有意义的。目前,我按以下方式划分 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)
您对实现或库函数有什么建议吗?
我认为你应该更新你的 split_matrix
方法,因为它 return 比你想要的少一个分割范围(设置 cpu_cnt=4
将 return 仅 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
任务,在其中添加将执行此计算的所有 indices/entries。然后你初始化你的并行工作者(例如使用multiprocessing
)并让他们开始。这个工作人员现在从 queue
中挑选一个元素,计算结果,将其存储(例如在另一个 queue
中)并继续下一个项目,依此类推。
如果这对您的数据不起作用,我认为您无法再改进。
在对一侧进行大量几何计算后,我得出了以下分区,它在每个垂直(或水平,如果需要的话)分区中给出大致相同数量的矩阵点。
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
我有一个非常大的对角矩阵,我需要拆分它以进行并行计算。由于数据局部性问题,遍历矩阵并在 n 线程之间拆分每个 n-th 计算是没有意义的。目前,我按以下方式划分 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)
您对实现或库函数有什么建议吗?
我认为你应该更新你的 split_matrix
方法,因为它 return 比你想要的少一个分割范围(设置 cpu_cnt=4
将 return 仅 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
任务,在其中添加将执行此计算的所有 indices/entries。然后你初始化你的并行工作者(例如使用multiprocessing
)并让他们开始。这个工作人员现在从 queue
中挑选一个元素,计算结果,将其存储(例如在另一个 queue
中)并继续下一个项目,依此类推。
如果这对您的数据不起作用,我认为您无法再改进。
在对一侧进行大量几何计算后,我得出了以下分区,它在每个垂直(或水平,如果需要的话)分区中给出大致相同数量的矩阵点。
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