I gaffel-join parallellism, ett sekventiellt program är uppdelad i en riktad acyklisk graf av uppgifter kopplade till riktade beroende kanter, och uppgifterna utförs, eventuellt parallellt, i en ordning som överensstämmer med deras beroenden. Ett populärt och effektivt sätt att utvidga gaffel-join parallellism är att tillåta trådar att skapa framtider. En tråd skapar en framtid för att hålla resultaten av en beräkning, som kan eller inte kan utföras parallellt. Detta resultat kommer tillbaka när en tråd vidrör den framtiden och vid behov blockerar den tills resultatet är klart. Den senaste tidens forskning har visat att även om framtiden naturligtvis kan öka parallellismen på ett strukturerat sätt, kan de ha en skadlig inverkan på cachelokaliteten. I värsta fall kan futures ådra sig  och (P T ∞ + tT ∞ ) avvikelser, vilket innebär att  och (CP T ∞ + CtT ∞ ) ytterligare cache missar, där C är antalet cache linjer, P är antalet processorer, t är antalet touchs, och T ∞ är beräkning spännvidden. Eftersom cachelokaliseringen har stor inverkan på mjukvarans prestanda på moderna multicores, är detta resultat oroande. I den här tidningen visar vi dock att om framtiden används på ett enkelt, disciplinerat sätt, då är situationen mycket bättre: om varje framtid bara vidrörs en gång, antingen av tråden som skapade den, eller av en senare ättling av tråden som skapade den, då kan parallella avrättningar med arbete stjälas som mest O(CP T 2 ❌ ) ytterligare cache missar, en betydande förbättring. Denna strukturerade användning av terminer är karakteristisk för många (men inte alla) parallella tillämpningar.
För att lindra detta problem föreslår Herlihy och Liu Ref att cachelokaliteten för framtidsparallellprogram med work-stealing kan förbättras genom att begränsa programmen till att använda "välstrukturerade framtider": varje framtid berörs bara en gång, antingen av tråden som skapade den, eller av en senare ättling till tråden som skapade den.
Well-structured futures and cache locality
{'venue': "PPoPP '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}