News for hackers. Stuff that matters.

A comment on Matrix multiplication inches closer to mythic goal. Parent comment

Re:Matrix multiplication inches closer to mythic goal by sdenton4 on Tuesday March 23, 2021 @12:29PM (#26556891)
For depth:

If I have at least n^2 processors, I can send a row and column to each processor, which can compute the inner product in linear time. So O(n^2) time to coordinate the work, and O(n) to actually do it.

[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by dragontamer on Tuesday March 23, 2021 @12:35PM (#26556964)
Hmmmm. Your O(n^2) step seems unnecessary to me. Therefore: the answer is O(n) depth for the naive case.

-----------

Processors are generally assumed to be self-numbered. Ex: processor #100 knows its processor#100.

    xloc = (threadIdx.x % matrix_width);
    yloc = (threadIdx.x / matrix_width);

    performMatrixCalc(xloc,yloc);
Therefore, only O(n) time depth apparently. O(log(n)) to broadcast matrix_width to all processors, which seems to be the only communication needed to organize the calculation.
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by sdenton4 on Tuesday March 23, 2021 @12:40PM (#26557036)
Nice, thanks!
[ Parent | on HN ]