Complexity of the pipeline computation of a family of inner products |
| |
Authors: | Maurice Tchuente |
| |
Institution: | CNRS-IMAG, Laboratoire TIM3, BP 68 38402 Saint Martin d''Hères Cedex, France |
| |
Abstract: | We are interested in the minimum time T(S) necessary for computing a family S = { < Si, Sj >: ? Si, Sj?Rp, (i, j) ?E } of inner products of order p, on a systolic array of order p × 2. We first prove that the determination of T(S) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time T(S) + 1 is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomial time. |
| |
Keywords: | Inner product pipeline computation systolic array complexity partition problem NP-complete eulerian multigraph polynomial time algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|