Rinnakkaismuisti - Parallel RAM

In Computer Science , joka on rinnakkainen random-access kone ( rinnakkainen RAM tai PRAM ) on yhteinen-muisti abstrakti kone . Kuten nimestään käy ilmi, PRAM on tarkoitettu rinnakkaislaskennan analogiseksi hajasaantikoneelle (ei pidä sekoittaa hajasaantimuistiin ). Samalla tavalla kuin peräkkäisten algoritmien suunnittelijat käyttävät RAM-muistia algoritmisen suorituskyvyn (kuten aikakompleksisuuden) mallintamiseen, rinnakkaisalgoritmisuunnittelijat käyttävät PRAM-mallia rinnakkaisten algoritmien suorituskyvyn mallintamiseen (kuten aikakompleksisuus, jossa prosessoreiden määrä oletetaan yleensä myös ilmoitettu). Samoin kuin tavassa, jolla RAM-malli laiminlyö käytännön asioita, kuten välimuistin käyttöajan päämuistiin verrattuna, PRAM-malli laiminlyö sellaiset ongelmat kuin synkronoinnin ja tiedonsiirron , mutta tarjoaa minkä tahansa määrän (ongelman koosta riippuen) prosessoreita. Esimerkiksi algoritmin hinta arvioidaan käyttämällä kahta parametria O (aika) ja O (aika × prosessorin numero).

Luku- / kirjoitusristiriidat

Luku- / kirjoitusristiriidat, joita yleisesti kutsutaan lukituksiksi samaan jaettuun muistipaikkaan samanaikaisesti, ratkaistaan ​​jollakin seuraavista strategioista:

  1. Yksinoikeus lukea yksinoikeudella (EREW) - jokainen muistisolu voidaan lukea tai kirjoittaa vain yhdelle prosessorille kerrallaan
  2. Rinnakkaislukukirjoitus (CREW) - useat prosessorit voivat lukea muistisolun, mutta vain yksi voi kirjoittaa kerrallaan
  3. Eksklusiivinen samanaikainen kirjoitus (ERCW) - ei koskaan otettu huomioon
  4. Samanaikainen luku samanaikainen kirjoitus (CRCW) - useat prosessorit voivat lukea ja kirjoittaa. CRCW PRAM -laitetta kutsutaan joskus samanaikaiseksi pääsykoneeksi .

Tässä E ja C tarkoittavat vastaavasti yksinoikeutta ja vastaavaa. Luku ei aiheuta ristiriitoja, kun samanaikainen kirjoitus määritellään edelleen seuraavasti:

Common - kaikki prosessorit kirjoittavat saman arvon; muutoin on laitonta
Mielivaltainen - vain yksi mielivaltainen yritys onnistuu, toiset jäävät eläkkeelle
Prioriteetti - prosessorin sijoitus osoittaa, kuka kirjoittaa
Toinen tyyppinen matriisinpienennystoiminto, kuten SUMMA, Looginen JA MAX.

Useita yksinkertaistavia oletuksia tehdään ottaen huomioon PRAM: n algoritmien kehittäminen. He ovat:

  1. Koneessa olevien prosessorien lukumäärää ei ole rajoitettu.
  2. Mihin tahansa muistipaikkaan pääsee tasaisesti mistä tahansa prosessorista.
  3. Järjestelmän jaetun muistin määrää ei ole rajoitettu.
  4. Resurssikilpailu puuttuu.
  5. Näille koneille kirjoitetut ohjelmat ovat yleensä SIMD- tyyppisiä .

Tällaiset algoritmit ovat hyödyllisiä ymmärtämään samanaikaisuuden hyödyntämistä, jakamalla alkuperäinen ongelma samanlaisiksi alaongelmiksi ja ratkaisemaan ne rinnakkain. Muodollisen P-RAM-mallin käyttöönoton Wyllien vuonna 1979 tekemässä opinnäytetyössä oli tarkoitus kvantifioida rinnakkaisten algoritmien analyysi Turingin koneen analogisella tavalla . Analyysi keskittyi MIMD-mallintamiseen CREW-mallin avulla, mutta osoitti, että monet variantit, mukaan lukien CRCW-mallin toteuttaminen ja SIMD-koneella toteutaminen, olivat mahdollisia vain jatkuvalla yleiskustannuksella.

Toteutus

PRAM-algoritmeja ei voida rinnastaa CPU: n ja dynaamisen RAM-muistin (DRAM) yhdistelmään, koska DRAM ei salli samanaikaista käyttöä; mutta ne voidaan toteuttaa laitteistona tai lukea / kirjoittaa kenttäohjelmoitavan porttiryhmän (FPGA) sisäisiin staattisiin hajasaantimuistilohkoihin (SRAM ), se voidaan tehdä CRCW-algoritmilla.

PRAM (tai RAM) -algoritmien käytännön relevanssin testi riippuu kuitenkin siitä, tarjoaako niiden kustannusmalli tehokkaan abstraktin joistakin tietokoneista; kyseisen tietokoneen rakenne voi olla aivan erilainen kuin abstrakti malli. Tieto lisättävistä ohjelmisto- ja laitteistokerroksista on tämän artikkelin ulkopuolella. Mutta artikkelit, kuten Vishkin (2011), osoittavat, kuinka PRAM: n kaltaista abstraktiota voidaan tukea eksplisiittisellä monisäikeisellä (XMT) paradigmalla, ja artikkelit, kuten Caragea & Vishkin (2011), osoittavat, että PRAM-algoritmi maksimaaliselle virtausongelmalle voi tarjota voimakkaita nopeuksia samaan ongelmaan verrattuna nopeimpaan sarjaohjelmaan. Artikkeli Ghanim, Vishkin & Barua (2018) osoitti, että PRAM-algoritmit sellaisenaan voivat saavuttaa kilpailukykyisen suorituskyvyn jopa ilman ylimääräisiä ponnisteluja heittääksesi ne monisäikeisiksi ohjelmiksi XMT: lle.

Esimerkkikoodi

Tämä on esimerkki SystemVerilog- koodista, joka löytää taulukon maksimiarvon vain kahdessa kellojaksossa. Se vertaa kaikkia matriisin elementtien yhdistelmiä ensimmäisellä kellolla ja yhdistää tuloksen toisella kellolla. Se käyttää CRCW-muistia; m[i] <= 1ja maxNo <= data[i]kirjoitetaan samanaikaisesti. Samanaikaisuus ei aiheuta ristiriitoja, koska algoritmi takaa, että sama arvo kirjoitetaan samaan muistiin. Tämä koodi voidaan suorittaa FPGA- laitteistolla. 

module FindMax #(parameter int len = 8)
                (input bit clock, resetN, input bit[7:0] data[len], output bit[7:0] maxNo);
    typedef enum bit[1:0] {COMPARE, MERGE, DONE} State;
                    
    State state;
    bit m[len];
    int i, j;
    
    always_ff @(posedge clock, negedge resetN) begin
        if (!resetN) begin
            for (i = 0; i < len; i++) m[i] <= 0;
            state <= COMPARE;
        end else begin
            case (state)
                COMPARE: begin
                    for (i = 0; i < len; i++) begin
                        for (j = 0; j < len; j++) begin
                            if (data[i] < data[j]) m[i] <= 1;
                        end
                    end
                    state <= MERGE;
                end
                
                MERGE: begin
                    for (i = 0; i < len; i++) begin
                        if (m[i] == 0) maxNo <= data[i];
                    end
                    state <= DONE;
                end
            endcase
        end
    end
endmodule

Katso myös

Viitteet

  • Eppstein, David; Galil, Zvi (1988), "Yhdistelmälaskennan rinnakkaiset algoritmiset tekniikat", Annu. Rev. Comput. Sci. , 3 : 233–283, doi : 10.1146 / annurev.cs.03.060188.001313
  • JaJa, Joseph (1992), Johdatus rinnakkaisalgoritmeihin , Addison-Wesley, ISBN 0-201-54856-9
  • Karp, Richard M .; Ramachandran, Vijaya (1988), Tutkimus rinnakkaisalgoritmeista jaettuja muistikoneita varten , Kalifornian yliopisto, Berkeley, EECS-laitos, tekniikka. Edustaja UCB / CSD-88-408
  • Keller, Jörg; Christoph Keßler; Jesper Träff (2001). Käytännön PRAM-ohjelmointi . John Wiley ja Pojat. ISBN 0-471-35351-5.
  • Vishkin, Uzi (2009), Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 sivua (PDF) , luokan muistiinpanot rinnakkaisalgoritmeista vuodesta 1992 lähtien Marylandin yliopistossa, College Parkissa, Tel Avivin yliopistossa ja Technion
  • Vishkin, Uzi (2011), "Yksinkertaisen abstraktion käyttö tietojenkäsittelyn keksimiseksi rinnakkaisuuden puolesta", ACM : n viestintä , 54 : 75–85, doi : 10.1145 / 1866739.1866757
  • Caragea, George Constantin; Vishkin, Uzi (2011), "Lyhyt ilmoitus: Parempia nopeuksia rinnakkaiselle maksimivirtaukselle", Proceedings of the 23. ACM symposium on Parallelism in algorithms and architecture - SPAA '11 , s. 131, doi : 10.1145 / 1989493.1989511 , ISBN 9781450307437
  • Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (2018), "Easy PRAM-pohjaisia korkean suorituskyvyn rinnakkaisohjelmointi ICE", IEEE Transactions on Rinnakkaiset ja hajautetut järjestelmät , 29 (2): 377-390, doi : 10.1109 / TPDS.2017.2754376 , HDL : 1903 / 18521

Ulkoiset linkit