Pipeline parallellism organiserar ett parallellt program som en linjär sekvens av stadier. Varje steg behandlar element i en dataström, som överför varje bearbetat dataelement till nästa steg, och sedan tar på sig ett nytt element innan de efterföljande stegen nödvändigtvis har avslutat sin behandling. Pipeline parallellism används särskilt i strömmande program som utför video, ljud och digital signalbehandling. Tre av 13 riktmärken i PARSEC, en populär programvaruriktmärkessvit utformad för delade minnesmultiprocessorer, kan uttryckas som pipelineparallalism. Medan de flesta concurrency plattformar som stöder rörledning parallellism använder en "konstruerad-och-run" strategi, denna artikel undersöker "on-the-fly" rörledning parallellism, där strukturen av rörledningen framträder som programmet utför i stället för att specificeras en priori. Rörledningens parallellism gör det möjligt för antalet steg att variera från iteration till iteration och beroenden att vara beroende av data. Vi föreslår enkla lingvistik för att specificera rörledning parallellism och beskriva en påvisbart effektiv schemaläggningsalgoritm, PIPER algoritm, som integrerar rörledning parallellism i en arbets-stjälande schemaläggare, vilket gör det möjligt rörledning och gaffel-join parallellism att godtyckligt bo. PIPER-algoritmen stryper automatiskt parallellismen, vilket förhindrar "runa" rörledningar. Med tanke på en rörledningsberäkning med T 1-arbete och T-pann (kritisk längd), utför PIPER beräkningen på P-processorer i T P ≤ T 1 /P + O(T ∞ + lg P) förväntad tid. PIPER begränsar också stapla utrymme, se till att det inte växer obundet med körtid. Vi har införlivat rörledning parallellism i ett Cilk-baserat system för att stjäla tid i arbetet. Vår prototyp Cilk-P implementation utnyttjar optimeringar som "lazy möjliggör" och "beroendevikning". Vi har överfört de tre PARSEC-riktmärken som visar rörledning parallellism för att köra på Cilk-P. En av dessa, x264, kan inte lätt utföras av system som stöder endast konstruktion-och-run rörledning parallellism. Benchmark resultat indikerar att Cilk-P har låg serie overhead och god skalbarhet. På x264, till exempel, Cilk-P uppvisar en hastighetsökning på 13,87 över sin respektive serie motsvarighet när du kör på 16 processorer.
Lee och Al. REF beskriver Piper, en flexibel algoritm som stöder godtyckligt förankrad rörledning och gaffel-join parallellism för dynamiska linjära rörledningar.
On-the-Fly Pipeline Parallelism
{'venue': 'TOPC', 'journal': None, 'mag_field_of_study': ['Computer Science']}