Rinnakkaiskäyttöinen kone
Vuonna tietojenkäsittelytiede, rinnakkainen hajasaantikone tai vaunut lyhyitä , on kone analysointiin rinnakkaisten algoritmien . Se on rekisterikone, jota on laajennettu käsittämään komennot samanaikaisesti. Kuten kaikissa rekisterikoneiden malleissa, PRAM: issa on erilaisia muunnelmia. Kaikille malleille yhteinen idea on, että useat rekisterit voivat suorittaa laskutoimituksia samanaikaisesti ja tallentaa tuloksen muistisoluihin . PRAM palvelee muun muassa. vuonna vaativuusteoriassa määrittelemään luokkaan NC tehokkaasti rinnakkain ratkeava ongelmia.
Esimerkki toteutuksesta
Vaikka suppeammassa merkityksessä olevat rekisterikoneet tukevat vain hyvin yksinkertaisia käskyjä , voidaan määritellä vastaavat rekisterikoneet , joiden ohjelmat voidaan määrittää korkean tason ohjelmointikielellä . Komennojen rinnakkainen käsittely voidaan nyt tehdä ottamalla käyttöön uusi lause, joka näyttää tältä:
- varten <ehto> pardo <ohjeet>
pardo tarkoittaa rinnakkain tekemistä . Esimerkki:
- i = 1-100 pardo x i : = 0
Tämä ohje alustaa 100 muistipaikkaa arvolla 0 samanaikaisesti. Esimerkiksi x voidaan ajatella matriisina, jonka kentät on indeksoitu 1: stä 100: een. Yleisempi merkintätapa x i ei sisällä tällaisia toteutuksen yksityiskohtia . Annetulla esimerkillä ei tietenkään ole erityisen suurta käytännön merkitystä. Siksi tässä on hyödyllisempi esimerkki, joka osoittaa PRAMin kyvyt hyvin:
Annetaan luettelo n eri arvosta, jotka tallennetaan lajittelemattomina muistisoluihin x 1 - x n . Etsimme sitä x i: tä, joka sisältää suurimman arvon. Yllättäen tämä haku voidaan suorittaa rinnakkain PRIORITY-CRCW-PRAM-laitteella (katso alla), joka ei vaadi prosessoreiden aktivointia, minkä tahansa kokoiselle n: lle koko vakiona :
for i=1 to n pardo
bi := 1
for i,j=1 to n pardo
if xj > xi
then
bi := 0
fi
for i=1 to n pardo
if bi = 1
then
m := i
fi
Toisen silmukan jälkeen bi: llä on arvo 1 vain, jos x i on suurin. Kaikilla muilla b j: llä j with i on arvo 0. I, jolla on b i = 1, on siis haettu indeksi ja löytyy ohjelman suorittamisen jälkeen m. Suurin käytettäessä lajittelemattoman luettelo kaikista pituus on n voidaan näin ollen laskea jatkuvasti vaivaa, eli O (1) aika.
Eri PRAM-mallit
SIMD- ja MIMD-rattaat
Edellä kuvattu pardo-käsky mahdollistaa tietyn käskyn samanaikaisen suorittamisen eri muuttujilla ajanjakson sisällä . Tällaisia rinnakkaismalleja kutsutaan lyhytaikaisesti yhden käskyn monidatamalleiksi tai SIMD: ksi . Jos eri komennot ovat sallittuja sisällä aikajakso, tätä kutsutaan usean käskyn useita tietoja mallin ( MIMD ). Pardon lausunto on liian suppeasti määritelty tällaiselle mallille.
Samanaikainen luku- ja kirjoitusoikeus samanlaisille muistisoluille
On määriteltävä, sallitaanko samanaikaisen luku- ja kirjoitusoikeuden samanlaisille muistisoluille vai ei. Edellä oleva maksimihakualgoritmi vaatii molempia: Toisessa pardo-käskyssä eri prosessorit käyttävät samanlaisia muistisoluja x i samanaikaisesti , jotta niitä voidaan verrata toisiinsa, ja muistisolua b i käytetään samanaikaisesti kirjoittamista varten . Et aina halua sallia tällaisia vapauksia. Sen vuoksi tehdään ero:
- CRCW PRAM: samanaikainen lukeminen, samanaikainen kirjoittaminen - samanaikainen luku- ja kirjoitusoikeus mahdollista
- CREW PRAM: Samanaikainen luku, yksinomainen kirjoitus - samanaikainen lukuoikeus, mutta vain yksinomainen kirjoitusoikeus sallittu
- EREW PRAM: Yksinomainen luku-, kirjoitus- - vain yksinoikeus luku- ja kirjoitusoikeus sallittu
Esimerkiksi EREW: n tapauksessa vain yhdellä prosessorilla voi olla luku- tai kirjoitusoikeus tiettyyn muistisoluun. Muuten ohjelma lopetetaan .
Kirjoitusoikeus CRCW-tiedostoihin
CRCW PRAM: n tapauksessa on vielä selvitettävä, mitä tapahtuisi samanaikaisen kirjoitusoikeuden tapauksessa, kun eri prosessorit haluavat kirjoittaa erilaisia arvoja muistisolulle. On 3 tilaa:
- common: Vain identtisten arvojen kirjoittaminen on sallittua.
- mielivaltainen: Satunnaisarvo valitaan ja kirjoitetaan.
- prioriteetti: Prosessori, jolla on pienin osoite, saa kirjoitusoikeuden.
Erityisillä algoritmeilla PRAM: n eri muunnelmat johtavat erilaisiin resurssien kulutuksen monimutkaisuuteen . Esimerkiksi edellä mainittu maksimihakualgoritmi riippuu samanaikaisesta luku- ja kirjoitusoikeudesta, so. CRCW PRAM: sta, kuten on kuvattu. Ratkaisu vakiona ei olisi mahdollista PRAM: lla, joka ei salli tätä. Mikä PRAM-malli valitset tiettyä tutkimusta varten, riippuu siis analyysitavoitteista, joita tavoitat sillä.
