| Maksimin määrääminen rinnakkaiskoneissa | |
| Authors: | Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala |
| Published in: | Tietojenkäsittelytiede 2 (1991), 36-48 |
| Abstract: | Esittelemme tässä katsauksessa rinnakkaisalgoritmien
suunnitteluperiaatteita tarkastelemalla yksinkertaista
tietojenkäsittelyetehtävää, jossa N:stä luvusta
on etsittävä suurin. Maksimi on helppo löytää
selaamalla kertaalleen syötteenä saatavat luvut. Tämän
peräkkäisalgoritmin suoritusaika on kertaluokkaa
N. Rinnakkaiskoneessa, jossa käytettävissä on useita
prosessoreja, maksimi voidaan määrätä nopeammin.
Käytämme rinnakkaiskoneen mallina rinnakkaista hajasaantikonetta ja esitämme kolme siinä toimivaa maksimin määräämisalgoritmia. Näistä ensimmäinen vaatii ajan, joka on kertaluokkaa log N, kun käytössä on N / log N prosessoria; toinen toimii vakioajassa, kun käytössä on N2 prosessoria; ja kolmannen suoritusaika on kertaluokkaa loglog N, kun käytössä on N / loglog N prosessoria. Viimeinen ratkaisu on nopein mahdollinen siinä tapauksessa, että haluamme työoptimaalisen algoritmin, ts. että suoritusajan ja prosessorien määrän tulo on lineaarinen. |
| Related: |  HTML (Later version) |
| BibLATEX: | @article{AKK1991J,
author = {Yrj\"{o} Auramo and Jyrki Katajainen and Juhani Kulmala},
title = {Maksimin m\"{a}\"{a}r\"{a}\"{a}minen rinnakkaiskoneissa},
journaltitle = {Tietojenk\"{a}sittelytiede},
number = {2},
year = {1991},
pages = {36--48},
}
|