Abstract-Scheduling pipeline-parallel program, definieras som en graf av steg som kommunicerar explicit genom köer, är utmanande. När programmet är regelbundet och den underliggande arkitekturen kan garantera förutsägbara genomförandetider, flera tekniker finns för att beräkna högt optimerade statiska scheman. Dessa scheman medger dock inte lastbalansering i körtid, så variation som införs av programmet eller den underliggande hårdvaran orsakar obalans i belastningen, vilket hindrar prestanda. Å andra sidan fungerar befintliga system för dynamisk finkornig lastbalansering (t.ex. uppgiftsstöld) inte bra på pipeline-parallellprogram: de kan inte garantera minnesavtrycksbegränsningar och schemalägger inte tillräckligt komplexa grafer eller grafer med ordnade köer. Vi presenterar en schemaläggning implementation för pipeline-parallel program som utför finkornig dynamisk belastning balansering effektivt. I synnerhet implementerar vi den första verkliga körtiden för GRAMPS, en nyligen föreslagen programmeringsmodell som fokuserar på att stödja oregelbundna pipeline- och dataparallellapplikationer (i motsats till klassiska stream-programmeringsmodeller och schemaläggare, som kräver att programmen ska vara regelbundna). Task-stealing med perstage köer och köpolicyer, tillsammans med en mottrycksmekanism, gör det möjligt för oss att upprätthålla strikta footprint gränser, och ett bufferthanteringssystem som bygger på paket-stealing tillåter lowoverhead och locality-medveten dynamisk tilldelning av ködata. Vi utvärderar vår körtid på en multikärnig SMP och finner att den ger låg överhead schemaläggning av oregelbunden arbetsbelastning samtidigt som lokaliteten upprätthålls. Vi visar också att GRAMPS schemaläggaren överträffar flera andra vanliga schemaläggningsmetoder. Specifikt, medan en typisk uppgift-stealing schemaläggare utför på samma sätt som GRAMPS på enkla grafer, det gör betydligt sämre på komplexa; en kanonisk GPGPU schemaläggare kan inte utnyttja rörledning parallellism och lider av stora minnesavtryck; och en typisk statisk, strömmande schemaläggare uppnår något bättre lokalitet, men lider betydande belastning obalans på en generell multi-core på grund av finkornig arkitektur variabilitet (t.ex., cache missar och SMT).
Sanchez och Al. REF använder aktivitet stjäla med per-steg köer och en kö backpressure mekanism för att möjliggöra dynamisk belastning balansering för rörledning parallellism.
Dynamic Fine-Grain Scheduling of Pipeline Parallelism
{'venue': '2011 International Conference on Parallel Architectures and Compilation Techniques', 'journal': '2011 International Conference on Parallel Architectures and Compilation Techniques', 'mag_field_of_study': ['Computer Science']}