我有一个矩阵，必须从矩阵内的先前值并行计算。如果你们中的任何人都可以给我一个提示，那就太好了。假设我有一个矩阵
| 4 5 6 7 8|
| 5 5 5 5 5|
| 6 6 6 6 6|
| 9 9 9 9 9|
这里的值将计算为位置 (1,1) 将从 (0,0)、(0,1) 和 (1,0) 三个相邻元素计算。它将是其值的最小值，依此类推。每个元素都依赖于其前三个邻居来计算其值。谁能给我一个提示如何并行完成。谢谢你。
问问题
122 次
1 回答
0
For that kind of dependency you can compute the elements of anti-diagonals in parallel. You have to initialize the topmost row and leftmost column, then proceed, for each anti-diagonal step by step:
0 0 0 0 .. 0 1 2 3 .. 0 2 3 .. 0 3 ... ..
i denoted in the schematic the pass number 0 = init, 1 = first step, 2=second step..
For example, you can compute each cell in step 2 in parallel, then compute each cell in step 3 in parallel and so on like a wave-front sweeping through the matrix (it's a known technique)
Unfortunately since there is data dependency between cells, you need to wait the step to finish before proceed to the next one. Also since the number of elements are variable, some processors will be underutilized by this method.
于 2013-05-01T05:19:40.677 回答