Det senaste arbetet med schemaläggning av algoritmer har resulterat i påvisbara gränser för det utrymme som tas av parallella beräkningar i förhållande till det utrymme som tas av sekventiella beräkningar. Resultaten för online-versioner av dessa algoritmer har dock begränsats till beräkningar där trådar endast kan synkroniseras med förfader eller syskontrådar. Sådana beräkningar omfattar inte Ianguages med futures eller användarspecificerade synkroniseringskonstmyntor. Här utökar vi resultaten till språk med synkroniseringsvariabler. Sådana språk inkluderar språk med terminer, såsom Multilisp och Cool, liksom andra språk som ID. Huvudresultatet är en ordinerad schemaläggningsalgoritm som, med tanke på en beräkning med w-arbete (totala operationer), u-synkroniseringar, en djup (kritisk sökväg) och SI sekventiellt utrymme, WiIl kör i O(w/P + en log@i)/p + d log(pd) tid och SI + O(pd Iog(pd)) utrymme, på en p-processor CRCW PRAM med en hämta-och-lägga primitiv. Detta inkluderar alla tid- och rymdkostnader för både beräkningen och schemaläggaren. Schemaläggaren är inte förebyggande i den meningen att den endast flyttar en tråd om tråden hänger på en synkronisering, gafflar en ny tråd eller överskrider en tröskel vid tilldelning av utrymme. För specialfallet där beräkningen är en planar graf med vänster-till-höger synkronisering kan schemaläggningsalgoritmen genomföras i 0( w/P+~log p) tid och SI + O(pd log p) utrymme. Dessa är de första icke-triviala rymdgränser som beskrivs för sådana språk. Många parallella språk möjliggör dynamisk finkornig parallellism och lämnar uppgiften att kartlägga parallellismen på processorer till genomförandet. Sådana språk inkluderar både data-parallel språk såsom HPF [24] Det har varit en stor mängd arbete på hur man schemalägga beräkningar för att minimera körtid. Detta arbete går åtminstone tillbaka till Grahams resultat [21]. På senare tid, utöver tiden, har det funnits en betydande oro för rymden. Denna oro har delvis motiverats av den höga minnesanvändningen av många implementationer av språk med dynamisk parallellism, och av det faktum att parallella beräkningar ofta är "minnesbegränsade. Ett dåligt schema kan kräva exponentiellt mer utrymme än ett bra schema [1 1]. Tidiga lösningar på rymdproblemet övervägde olika heuristiker för att minska antalet aktiva trådar [10, 23, 34, 16, 26]. Senare arbete har övervägt bevisbara gränser för rymdanvändning. Tanken är att relatera det utrymme som krävs av det parallella utförandet till det utrymme SI som krävs för det sekventiella utförandet. Burton [11] visade först att för en viss klass av beräkningar det utrymme som krävs för en parallell implementation på p processorer kan bindas av p~SI (s1 utrymme per processor). Blumofe och Leiserson [8, 9] visade sedan att denna rymdgräns kan upprätthållas samtidigt som man uppnår goda tidsgränser. De visade att en helt strikt beräkning som utför totalt w operationer (arbete) och har en kritisk väglängd (djup) av d kan genomföras för att köras i O(w/p + d) tid, vilket är inom en konstant faktor för optimal. Dessa resultat användes för att begränsa den tid och det utrymme som användes för programspråket Cilk [7]. Blelloch, Gibbons och Matias [4] visade att för inhägnade beräkningar kan tidsgränserna "upprätthållas samtidigt som utrymmet avgränsas av SI + O (pd), vilket för tillräcklig parallellism är bara en additiv faktor över det sekventiella utrymmet. Detta användes för att avgränsa utrymmet för NESL-programmeringsspråket [5]. Narlikar och Blelloch [30] visade att samma gräns kan uppnås på ett icke förebyggande sätt (trådar flyttas endast från en processor vid synkronisering, gaffel eller tilldelning av minne) och gav experimentella resultat som visar teknikens effektivitet. Allt detta arbete har emellertid begränsats till beräkningar där trådar endast kan synkroniseras med sina syskon- eller förfaderstrådar. Även om detta är en relativt allmän klass, omfattar det inte språk baserade på terminer [23, 27, 12, 14, 13], språk baserade på mild eller spekulativ utvärdering [1, 32] eller språk med allmänna användardefinierade synkroniseringsbegränsningar [33]. I denna DaDer visar vi hur man utökar resultaten till suD-.. portsynkronisering baserad på write-once synkronisering variabler. En write-once synkronisering variabel är en variabel (minnesplats ) som kan skrivas av en tråd och läsas av ett antal andra trådar. Om den läses före 12
Blelloch m.fl. REF presenterar variabeln write-once synkronisering, som är en variabel (minnesplats) som kan skrivas med en tråd och läsas av ett antal andra trådar.
Space-efficient scheduling of parallelism with synchronization variables
{'venue': "SPAA '97", 'journal': None, 'mag_field_of_study': ['Computer Science']}