3
$\begingroup$

The following equation is a matrix expression where $B_i$ and $C_i^T$ are $n\times n$ matrices and k is a positive integer:

$$P = \sum_{i=1}^k B_i C_i^T $$

So $P = B_1 C_1^T + B_2 C_2^T + \cdots +B_k C_k^T $

If $B_i $ and $C_i$ are $n\times n$ matrices themselves, we have a total of 2 $\times$ k matrices that some how need to be stored in this vector architecture.

So this means P will end up being an $n\times n$ matrix after all the computation has completed.

What is the simplest possible vector processor architecture that is required to perform the matrix computation above?

Is there any literature or articles out there that discuss how this can be done?

Would appreciate all / any advise

Improve this question
$\endgroup$
7
  • $\begingroup$ the obvious approach is to distribute each matrix multiplication $B_n C_n$ over available processors in a "map" step and then sum them up in the "reduce" step. a more sophisticated approach might look for common rows/columns among the $B_n C_n$ terms and avoid repeating the same calculations but would not succeed (in improving efficiency) unless there is some commonality. the complexity in that case depends on how "different" they all are. $\endgroup$
    – vzn
    Commented Oct 30, 2012 at 4:53
  • $\begingroup$ vzn, is it possible to start simpler? For example, is there a vector architecture that just does the multiplication of lets say $B_1C_1^T + B_2C_2^T$ ? I guess i'm having trouble thinking about the problem in simpler parts first. $\endgroup$
    – user1068636
    Commented Oct 30, 2012 at 5:13
  • $\begingroup$ that seemed pretty simple to me =) ... yes of course it is possible to parallelize matrix multiplication of two matrices alone. a simple way is to do it by either rows or columns. ie different cpus compute the different rows or columns of the product matrix. and theres also papers to look for "commonality" in multiplying two matrices but thats very advanced.... $\endgroup$
    – vzn
    Commented Oct 30, 2012 at 17:20
  • $\begingroup$ doing a quick search the parallelization of matrix multiplication $BC$ is an extremely highly studied problem/algorithm with many implementations eg BLAS, LAPACK etc $\endgroup$
    – vzn
    Commented Oct 30, 2012 at 18:29
  • $\begingroup$ vzn, I reworded the problem. Also, do BLAS and LAPACK have algorithms that work with vector architectures? $\endgroup$
    – user1068636
    Commented Oct 31, 2012 at 1:33

1 Answer 1

Reset to default
1
$\begingroup$

From talking to the OP, algorithms that handle parallel matrix multiplication are apparently acceptable answers. Matrix multiplication and parallel algorithms for it are a highly studied problem in CS partly because of its widespread application e.g. in scientific computing. There are other ways to parallelize the problem given in the question, e.g. an obvious "map-reduce" that maps the separate matrices to separate processors and the reduce step does the addition.

Note also the new "scicomp" stackexchange for questions on scientific computing.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.