Tölvumál - 01.10.1986, Blaðsíða 18

Ef besti runualgóritininn fyrir ákveðið vandamál tekur
timann m getum við ekki gert okkur vonir um samhliða
algóritma, með n undirtölvum, en sem tekur skemmri
tima en m/n. (Ef við hefðum samhliða algóritma, sem
tæki minni tima en m/n þá fengjum við runu algóritma,
sem tæki styttri tima en m, með þvi að taka n sem 1.)
Það tekst þó ekki alltaf að finna samhliða algóritma,
sem tekur stysta mögulega tima, eins og sést á seinna
dæminu hér á undan.
Raunhæf líkön nauðsynleg
Nú gætu menn sagt að likanið, sem við notum sé
óraunhæft og að það verði aldrei byggð tölva, sem er
eins og þetta likan. Það er eflaust satt að það
verður aldrei framleidd tölva, sem er alveg eins og
likanið hér að ofan. Það sem hins vegar skiptir máli
er að það sé nógu raunhæft, til þess að hægt sé að
nota algóritma, sem hannaðir eru fyrir likanið, á
raunverulegum samhliða tölvum og að timinn, sem hann
taki sé af sömu stærðargráðu og á líkaninu. Hið eina
sem er óraunhæft við likanið, sem notað er i þessari
grein, er að við gerum ráð fyrir óbundnum fjölda
undirtölva. Ef fjöldi undirtölva í samhliða tölvum
þróast eins og fjöldi minnishófa i venjulegum tölvum,
þá getum við alveg eins gert ráð fyrir að hafa
óbundinn fjölda undirtölva á sama hátt og við nú
venjulega gerum ráð fyrir að hafa óbundinn fjölda
minnishólfa i venjulegum tölvum. í flestum samhiða
algóritmum er líka hægt að notast við færri
undirtölvur en gert er ráð fyrir, það tefur bara
algóritmann hlutfallslega.
Þeir sem áhuga hafa á að lesa meira um þetta efni er
bent á janúar tölublað timaritsins "Computer", 1982,
sem gefið er út af IEEE. Einnig eru tvær ágætar
yfirlitsgreinar i september 1984 tölublaði "Computing
Surveys".
Hjálmtýr Hafsteinsson
18