Tölvumál - 01.10.1986, Page 15

Samlagning vektora hraðvirk
Til að gefa hugmynd um mismunin á milli venjulegrar
runu algóritma og samhliða algóritma skulum við lita
á hvernig við leggjum saman tvo vektora, A og B, sem
hvor inniheldur n tölur og setjum niðurstöðuna i
vektorinn C. Hér á eftir er lýst venjulegu runu
algóritma fyrir þetta verkefni.
FOR 1:-1 TOnDO
ClO>Ali]*Bl1];
Timinn sem það tekur venjulega tölvu að leysa þennan
algóritma er af stærðargráðunni n, þar sem hann þarf
að lita á allar n tölurnar i A og B. Samhliða
algóritminn hér á eftir gerir hins vegar ráð fyrir að
við höfum n undirtölvur og að vektorarnir A og B séu
i sameiginlegu minni. Forritið eins og það litur út
fyrir undirtölvu númer i er eftirfarandi:
CUlAIU - Btil
Allar undirtölvurnar n að tölu framkvæma þessa skipun
samtimis, hver með sinni einkennistölu. Þannig
leggur undirtölva númer 7 saman tölunúmer 7 i
vektornum A og tölu með sama númeri i vektornum B.
Timinn sem þessi algóritmi tekur er jafnlangur og það
tekur að leggja saman tvær tölur. Hann er þvi n
sinnum hraðvirkari en runu algóritminn. Jafnvel þó
að við höfum færri en n undirtölvur þá er samt hægt
að nota þennan algóritma til að auka vinnsluhraðann.
Ef við höfum aðeins tvær undirtölvur getum við til
dæmis skipt tölunum upp á milli þeirra þannig að hver
undirtölva þurfi að leggja saman n/2 tölur þá er
samhliða algóritminn tvisvar sinnum fljótari en runu
algóritminn. Það er auðvelt að sjá að hraðaaukningin
er i réttu hlutfalli við hversu margar undirtölvur
við höfum, svo framarlega sem þær eru ekki fleiri en
n.
Dæmi:
Við skulum nú lita á verkefni þar sem hraðaaukningin
er ekki alveg i réttu hlutfalli við fjölda
undirtölva. Við viljum til dæmis finna stærstu
15