Najkratšia cesta, PSA

Paralelná synchrónna architektúra (PSA):

• O(N) krokov s O(N2) procesormi

• transformujeme program tak, ze vycleníme priradenia, ktoré sa môzu vykonat naraz; je ich N3, rozdelíme ich na N skupín po N2 priradení.

• Program P1’

  initially ? || i, j :: d[i, j] = W[i, j] ?
  
  assign
  ?  k :: ? ||i, j :: d[i, j] := min(d[i, j], d[i, k] + d[k, j]) ?

end{P1’}

• Uvazujeme, ze máme architektúru s N2 procesormi a urcíme poradie vykonávania priradení

• Program {parallel Floyd?Warshall} P4

  declare k: int
  
  initially ? || i, j :: d[i, j] = W[i, j] ? || k = 0
  assign
  ? ||i, j :: d[i, j] := min(d[i, j], d[i, k] + d[k, j])? if k < N
  
  || k := k + 1 if k < N

end{P4}

• program P4: potrebuje O(N) krokov

Previous slide

Next slide

Back to first slide

View graphic version