Externt minnesalgoritm - External memory algorithm

Vid beräkning , externa minnesalgoritmer eller out-of-core algoritmer är algoritmer som är utformade för processdata som är för stora för att passa in i en dators huvudminne på en gång. Sådana algoritmer måste optimeras för att effektivt hämta och komma åt data som lagras i långsam bulkminne ( hjälpminne ) såsom hårddiskar eller bandstationer , eller när minnet finns i ett datanätverk . Externa minnesalgoritmer analyseras i modellen för externt minne .

Modell

Cachen till vänster innehåller block av storlek vardera för totalt M- objekt. Det externa minnet till höger är obegränsat. ${\ displaystyle {\ tfrac {M} {B}}}$${\ displaystyle B}$

Externa minnesalgoritmer analyseras i en idealiserad beräkningsmodell som kallas externt minnesmodell (eller I / O-modell eller diskåtkomstmodell ). Den externa minnesmodellen är en abstrakt maskin som liknar RAM-maskinens modell , men med en cache förutom huvudminnet . Modellen fångar det faktum att läs- och skrivoperationer är mycket snabbare i en cache än i huvudminnet , och att läsning av långa sammanhängande block är snabbare än att läsa slumpmässigt med hjälp av ett läs-och-skrivhuvud . Den gångtid av en algoritm i det externa minnet modell definieras av antalet läsningar och skrivningar till minne som krävs. Modellen introducerades av Alok Aggarwal och Jeffrey Vitter 1988. Den externa minnesmodellen är relaterad till den cache-glömska modellen , men algoritmer i den externa minnesmodellen kan känna till både blockstorleken och cachestorleken . Av denna anledning kallas modellen ibland för den cache-medvetna modellen .

Modellen består av en processor med ett internt minne eller cache i storlek M , ansluten till ett obegränsat externt minne. Både den interna och externa minnet är uppdelade i block av storlek B . En ingång / utgång eller minnesöverföringsoperation består i att förflytta ett block av B intilliggande element från extern till internminnet, och den gångtid av en algoritm bestäms av antalet av dessa ingångs / utgångsoperationer.

Algoritmer

Algoritmer i modellen för externt minne utnyttjar det faktum att hämtning av ett objekt från externt minne hämtar ett helt storleksblock . Den här egenskapen kallas ibland lokalitet. ${\ displaystyle B}$

Att söka efter ett element bland objekt är möjligt i den externa minnesmodellen med hjälp av ett B-träd med förgreningsfaktor . Med hjälp av ett B-träd kan sökning, insättning och radering uppnås i tid (i Big O-notering ). Teoretisk information är detta den minsta möjliga körtiden för dessa operationer, så användning av ett B-träd är asymptotiskt optimalt . ${\ displaystyle N}$${\ displaystyle B}$${\ displaystyle O (\ log _ {B} N)}$

Extern sortering är sortering i en extern minnesinställning. Extern sortering kan göras via distributionssortering, som liknar quicksort , eller via en -way merge sort . Båda varianterna uppnår den asymptotiskt optimala körtiden för att sortera N- objekt. Denna gräns gäller också för den snabba Fourier-transformationen i det externa minnesmodellen. ${\ displaystyle {\ tfrac {M} {B}}}$${\ displaystyle O ({\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} {B}})}$

Permutationsproblemet är att ordna om element till en specifik permutation . Detta kan antingen göras antingen genom att sortera, vilket kräver ovanstående sorteringstid, eller infoga varje element i ordning och ignorera fördelarna med lokalitet. Således kan permutering göras i tid. ${\ displaystyle N}$${\ displaystyle O (\ min (N, {\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} {B}}))}$

Applikationer

Den externa minnesmodellen fångar minneshierarkin , som inte modelleras i andra vanliga modeller som används för att analysera datastrukturer , till exempel maskinen för slumpmässig åtkomst , och är användbar för att bevisa lägre gränser för datastrukturer. Modellen är också användbar för analys av algoritmer som fungerar på datamängder som är för stora för att passa in i internminnet.

Ett typiskt exempel är geografiska informationssystem , särskilt digitala höjdmodeller , där hela datamängden lätt överstiger flera gigabyte eller till och med terabyte data.

Denna metod sträcker sig utöver allmänna processorer och inkluderar även GPU- beräkning såväl som klassisk digital signalbehandling . I allmänna datorer på grafikprocessorenheter (GPGPU) används kraftfulla grafikkort (GPU) med lite minne (jämfört med det mer välbekanta systemminnet, som oftast kallas helt enkelt RAM ) med relativt långsam CPU-till- GPU-minneöverföring (jämfört med beräkningsbandbredd).

Historia

En tidig användning av termen "out-of-core" som adjektiv är 1962 med hänvisning till enheter som är andra än kärnminnet i en IBM 360 . En tidig användning av termen "out-of-core" med avseende på algoritmer förekommer 1971.

Se även

• Extern sortering
• Online-algoritm
• Strömmande algoritm
• Cache-omedveten algoritm
• Parallellt externt minne
• Externt minnesdiagramgenomgång

Referenser

externa länkar

• Av Core SVD och QR
• Av kärngrafik
• Scalapack design