I detta arbete tar vi upp problemet med schemaläggning av slingor med beroenden i samband med spekulativ parallellisering. Vi visar att schemaläggningsalternativen i hög grad påverkas av det beroendeöverträdelsemönster som koden presenterar. Vi koncentrerar vår analys i de algoritmer där beroenden är mindre benägna att visas när utförandet fortskrider. Särskilt fokuserar vi på randomiserade inkrementella algoritmer, som ofta används som en mycket effektivare lösning på många problem än deras deterministiska motsvarigheter. Dessa viktiga algoritmer är i allmänhet svåra att parallellisera för hand och utgör en utmaning för alla automatiska parallelliseringsscheman. Vår analys ledde oss till utvecklingen av MESETA, en ny schemaläggningsstrategi som tar hänsyn till sannolikheten för en beroendeöverträdelse för att bestämma antalet iterationer som planeras. MESETA jämförs med befintliga tekniker, inklusive Fixed-Size Chunking (FSC), det enda schemaläggningsalternativ som hittills använts i samband med spekulativ parallellisering. Våra experimentella resultat visar en 5,5 procent till 36,25 procent speedup förbättring över FSC, vilket leder till en bättre extraktion av parallellismen inneboende till randomiserade inkrementella algoritmer. Dessutom, när kostnaderna för missbruk av beroende är för höga för att få upp farten, så kurrar MESETA försämringen av prestandan. Index Terms-Parallelism och samstämmighet, lastbalansering och uppgiftstilldelning, schemaläggning och uppgiftspartitionering, geometriska problem och beräkningar.
Llanos och andra använder sannolikheter för ett beroendeöverträdelse för att styra slingan schemaläggning av randomiserade inkrementella algoritmer i samband med spekulativ parallellisering REF.
New Scheduling Strategies for Randomized Incremental Algorithms in the Context of Speculative Parallelization
{'venue': 'IEEE Transactions on Computers', 'journal': 'IEEE Transactions on Computers', 'mag_field_of_study': ['Computer Science']}