Skip to main content
deleted 13 characters in body
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

You asked two questions. I'll answer the firstcan do this as a parallel sum. You want to compute

$$w_i = \sum_{j=1}^P e_{ij} v_j,$$

where processor $j$ has the vector $v_j$.

One way to do this is to have each processor compute $e_{ij} v_j$ locally. Then, use a binary tree to compute the sum. In particular, processor 1 sends $e_{i1} v_1$ to processor 2, which computes the sum $e_{i1} v_1 + e_{i2} v_2$; processor 3 sends $e_{i3} v_3$ to processor 4, which computes the sum $e_{i3} v_3 + e_{i4} v_4$; and so on. Then, processor 2 sends $e_{i1} v_1 + e_{i2} v_2$ to processor 4, which computes the sum $e_{i1} v_1 + e_{i2} v_2 + e_{i3} v_3 + e_{i4} v_4$; and so on. Repeat until you have computed the final sum. Basically, this is just parallel sum of some vectors (parallel aggregation).

This requires sending $\Theta(NP)$ data over the network, and $\Theta(\log P)$ rounds of communication. Each processor only needs memory for $\Theta(N)$ data. So, it looks like it meets all your requirements. It may still be hard on the network, but that seems unavoidable given what you are trying to compute. You'll do this $P$ times, to compute $w_1,\dots,w_P$, so in total it will require $\Theta(NP^2)$ data on the network, $\Theta(P \log P)$ rounds of communication (though they can be parallelized down to $\Theta(\log P)$ if the network is fast enough), and $\Theta(N)$ space on each processor.

You asked two questions. I'll answer the first. You want to compute

$$w_i = \sum_{j=1}^P e_{ij} v_j,$$

where processor $j$ has the vector $v_j$.

One way to do this is to have each processor compute $e_{ij} v_j$ locally. Then, use a binary tree to compute the sum. In particular, processor 1 sends $e_{i1} v_1$ to processor 2, which computes the sum $e_{i1} v_1 + e_{i2} v_2$; processor 3 sends $e_{i3} v_3$ to processor 4, which computes the sum $e_{i3} v_3 + e_{i4} v_4$; and so on. Then, processor 2 sends $e_{i1} v_1 + e_{i2} v_2$ to processor 4, which computes the sum $e_{i1} v_1 + e_{i2} v_2 + e_{i3} v_3 + e_{i4} v_4$; and so on. Repeat until you have computed the final sum. Basically, this is just parallel sum of some vectors (parallel aggregation).

This requires sending $\Theta(NP)$ data over the network, and $\Theta(\log P)$ rounds of communication. Each processor only needs memory for $\Theta(N)$ data. So, it looks like it meets all your requirements. It may still be hard on the network, but that seems unavoidable given what you are trying to compute. You'll do this $P$ times, to compute $w_1,\dots,w_P$, so in total it will require $\Theta(NP^2)$ data on the network, $\Theta(P \log P)$ rounds of communication (though they can be parallelized down to $\Theta(\log P)$ if the network is fast enough), and $\Theta(N)$ space on each processor.

You can do this as a parallel sum. You want to compute

$$w_i = \sum_{j=1}^P e_{ij} v_j,$$

where processor $j$ has the vector $v_j$.

One way to do this is to have each processor compute $e_{ij} v_j$ locally. Then, use a binary tree to compute the sum. In particular, processor 1 sends $e_{i1} v_1$ to processor 2, which computes the sum $e_{i1} v_1 + e_{i2} v_2$; processor 3 sends $e_{i3} v_3$ to processor 4, which computes the sum $e_{i3} v_3 + e_{i4} v_4$; and so on. Then, processor 2 sends $e_{i1} v_1 + e_{i2} v_2$ to processor 4, which computes the sum $e_{i1} v_1 + e_{i2} v_2 + e_{i3} v_3 + e_{i4} v_4$; and so on. Repeat until you have computed the final sum. Basically, this is just parallel sum of some vectors (parallel aggregation).

This requires sending $\Theta(NP)$ data over the network, and $\Theta(\log P)$ rounds of communication. Each processor only needs memory for $\Theta(N)$ data. So, it looks like it meets all your requirements. It may still be hard on the network, but that seems unavoidable given what you are trying to compute. You'll do this $P$ times, to compute $w_1,\dots,w_P$, so in total it will require $\Theta(NP^2)$ data on the network, $\Theta(P \log P)$ rounds of communication (though they can be parallelized down to $\Theta(\log P)$ if the network is fast enough), and $\Theta(N)$ space on each processor.

Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

You asked two questions. I'll answer the first. You want to compute

$$w_i = \sum_{j=1}^P e_{ij} v_j,$$

where processor $j$ has the vector $v_j$.

One way to do this is to have each processor compute $e_{ij} v_j$ locally. Then, use a binary tree to compute the sum. In particular, processor 1 sends $e_{i1} v_1$ to processor 2, which computes the sum $e_{i1} v_1 + e_{i2} v_2$; processor 3 sends $e_{i3} v_3$ to processor 4, which computes the sum $e_{i3} v_3 + e_{i4} v_4$; and so on. Then, processor 2 sends $e_{i1} v_1 + e_{i2} v_2$ to processor 4, which computes the sum $e_{i1} v_1 + e_{i2} v_2 + e_{i3} v_3 + e_{i4} v_4$; and so on. Repeat until you have computed the final sum. Basically, this is just parallel sum of some vectors (parallel aggregation).

This requires sending $\Theta(NP)$ data over the network, and $\Theta(\log P)$ rounds of communication. Each processor only needs memory for $\Theta(N)$ data. So, it looks like it meets all your requirements. It may still be hard on the network, but that seems unavoidable given what you are trying to compute. You'll do this $P$ times, to compute $w_1,\dots,w_P$, so in total it will require $\Theta(NP^2)$ data on the network, $\Theta(P \log P)$ rounds of communication (though they can be parallelized down to $\Theta(\log P)$ if the network is fast enough), and $\Theta(N)$ space on each processor.