Sammanfattning — Detta papper presenterar en tidsstämpel algoritm för körning parallellisering av allmänna DOACROSS loopar som har indirekta tillträdesmönster. Algoritmen följer INSPEKTOR/EXECTOR-systemet och utnyttjar parallellism på en finkornig minnesreferensnivå. Den har en parallell inspektör och förbättrar tidigare algoritmer av samma generalitet genom att utnyttja parallellism bland på varandra följande läsningar av samma minneselement. Två varianter av algoritmen beaktas: Den ena tillåter delvis samtidiga avläsningar (PCR) och den andra tillåter helt samtidiga avläsningar (FCR). Analyser av deras tidskomplexitet härleder ett nödvändigt villkor med avseende på iteration arbetsbelastning för körtid parallellisering. Experimentella resultat för en Gaussian eliminering slinga, samt en omfattande uppsättning syntetiska slingor på en 12-vägs SMP-server, visar att tidsstämpel algoritmer överträffar iterationsnivå parallellisering tekniker i de flesta testfall och få hastighetshöjningar över sekventiell körning för slingor som har tung iteration arbetsbelastning. PCR algoritmen presterar bäst eftersom det gör en bättre avvägning mellan att maximera parallellismen och minimera analysen overhead. För loopar med ljus eller okända iteration laster, en alternativ spekulativ körtid parallellisering teknik föredras.
Xu och Chaudhary REF utvecklade en tidsstämpel algoritm för run-time parallellisering av DOACROSS loopar med indirekta åtkomstmönster.
Time stamp algorithms for runtime parallelization of DOACROSS loops with dynamic dependences
{'venue': 'IEEE Trans. Parallel Distrib. Syst.', 'journal': 'IEEE Trans. Parallel Distrib. Syst.', 'mag_field_of_study': ['Computer Science']}