På moderna datorsystem beror en applikations minnesprestanda på dess plats. För en enda körning har lokala korrelerade åtgärder som genomsnittlig felfrekvens eller arbetsmängdsstorlek länge analyserats med hjälp av återanvändningsavstånd – antalet olika platser som nås mellan på varandra följande åtkomster till en given plats. Denna artikel behandlar analys problemet på programnivå, där storleken på data och lokaliseringen av utförandet kan ändras avsevärt beroende på indata. Artikeln presenterar två tekniker som förutsäger hur lokaliseringen av ett program förändras med dess ingång. Den första är ungefärlig återanvändning-distansmätning, som är asymptotiskt snabbare än exakta metoder samtidigt som den ger en garanterad precision. Den andra är statistisk förutsägelse av lokalitet i alla utföranden av ett program baserat på analysen av några avrättningar. Förutsägelseprocessen har tre steg: att dela dataåtkomst i grupper, att hitta åtkomstmönster i varje grupp och att bygga parameteriserade modeller. Den förutsägelse som blir följden kan användas on-line med hjälp av avståndsbaserad provtagning. Vid utvärdering på femton referensapplikationer, de nya teknikerna förutspådde programlokalitet med god noggrannhet, även för test utföranden som är storleksordningar större än utbildning utföranden. De två metoderna är bland de första för att möjliggöra kvantitativ analys av hela programlokaliteten i allmän sekventiell kod. Dessa resultat utgör grunden för en enhetlig förståelse av programmet Tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior visar detta meddelande på första sidan eller första skärmen av en skärm tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Behörighet kan begäras från publikationsavdelningen, ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, eller behörigheter@acm.org. Lokalitet och dess många facetter. Avslutande delar av artikeln presenterar en taxonomi av relaterad litteratur längs fem dimensioner av lokalitet och diskutera rollen av återanvändning avstånd i prestandamodellering, programoptimering, cache och virtuell minneshantering, och nätverkstrafik analys.
Skalträdsalgoritmen för återanvändning av distansanalys REF är anpassad för att använda en enda nod under en dvalasperiod.
Program locality analysis using reuse distance
{'venue': 'TOPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}