Výpocet maxima, PA
Úloha: urcit m = ?max j: 0 ? j < N:: A[j]? pre dané pole A[0..N ? 1]
Paralelná architektúra (PA):
- prvky A dáme ako listy binárneho stromu
- kazdý vnútorný vrchol má hodnotu maxima jeho synov
- koren má maximum
- strom máme v poli X[1..(2N?1)]
- j-ty vrchol má synov 2j a 2j+1
- initially X[N..(2N?1)] = A[0..N?1]
Program Maximum2
declare X: array [1..(2N?1)] of integer
always
? ||j: 0 ? j < N:: X[N+j] = A[j] ?
? j: 1 ? j < N:: X[j] = max(X[2j], X[2j+1]) ?
lahko vidno, ze X[1] = ? max j: 0 ? j < N:: A[j] ?