\"\" \"\" \"\"
Go backward to Matrix Multiplication
Go up to Top
Go forward to Hypercube Algorithm
RISC-Linz logo

Ring Algorithm

See Quinn, Figure 7-15.
  1. Load A[i] and B[i] on every processor P[i].
  2. For all P[i] do:
    p = (i+1) mod N
    j = i
    for k=0 to N-1 do
      C[i][j] = A[i] * B[j]
      j = (j+1) mod N 
      Receive B[j] from P[p]
    
  3. Collect C[i]
Point-to-point communication -> Step 2 takes O(N) time.
Author: Wolfgang Schreiner
Last modification: November 15, 1996