Vi tillhandahåller en konkurrenskraftig analysram för online ptefetching och bufferthanteringsalgoritmer i parallella I/O-system, med hjälp av en read-once-modell av blockreferenser. Detta har utbredd tillämplighet på viktiga I/O-bundna program såsom extern sammanslagning och samtidig uppspelning av flera videoströmmar. Två realistiska lookahead-modeller, globala lookahead och lokala lookahead, är definierade. Algoritmer NOM och GREED baserat på dessa två former av lookahead analyseras för delad buffert och distribuerade buffertkonfigurationer, som båda förekommer ofta i befintliga system. En viktig aspekt av vårt arbete är att vi visar hur vi kan implementera båda modellerna av lookahead i praktiken med hjälp av enkla tekniker för prognostisering och spolning. Den ökande obalansen mellan processorers och I/O-enheters hastigheter har lett till att I/O-delsystemet blivit en flaskhals i många tillämpningar. Användningen av flera diskar för att bygga ett parallellt I/O-delsystem har förespråkats för att förbättra i/prestanda och systemtillgänglighet [3], och de flesta nuvarande högpresterande system innehåller någon form av parallell I/O. Med tanke på ett D-disk parallellt I/O-system och en globalt delad I/O-buffert som kan hålla upp till M-diskblock, härleder vi en lägre gräns för Q(a) på konkurrensförhållandet för alla deterministiska online-förhämtningsalgoritmer med O(M) lookahead. NOM visas matcha den nedre gränsen med global M-block lookahead. Att endast använda locallookahead resulterar däremot i ett Q(D) konkurrenskraftigt förhållande. När bufferten fördelas i D-delar av M/D-block var och en, visas algoritmen GREED baserad på lokal lookahead vara optimal, och NOM ligger inom en konstant faktor för optimal. Således ger vi en teoretisk grund för intuitionen att global lookahead är mer värdefull för pmfetching i fallet med en delad buffert konfiguration medan det är tillräckligt för att ge lokal lookaheadin fall av den distribuerade konfigurationen. Slutligen analyserar vi prestandan hos dessa algoritmer för referenssträngar som genereras av en enhetligtrandom stokastisk process och vi visar att de uppnår det minsta förväntade antalet UOs. Dessa resultat ger också gränser på det värsta-fall förväntade prestanda av algoritmer som använder randomisering i datalayouten Ptefetching är en kraftfull teknik för att minska JfO latency ses av ett program. Detta gäller särskilt i ett parallellt I/O-system där prefetching effektivt kan användas för att få parallellism i diskåtkomst, så att diskarna används mest effektivt. För att till fullo utnyttja denna potential är det viktigt att utforma och implementera algoritmer för förhämtning och bufferthantering som säkerställer att de mest användbara blocken hämtas och behålls i I/O-bufferten. Vi anser att ett parallellt l/O-system består av D oberoende diskar som kan nås parallellt [12]. Uppgifterna för beräkningen sprids ut bland diskarna i blockenheter. Ett block är åtkomstenheten från en disk När det gäller I/O kännetecknas beräkningen av en referenssträng som består av en ordnad sekvens av block som beräkningsåtkomsten. I allmänhet kan referenssträngen som motsvarar en beräkning bestå av en godtycklig interleaving av referenssträngar av flera samtidiga applikationer. För att beräkna för att framgångsrikt få tillgång till en datablockering bör den vara bosatt i datorsystemets interna minne. Genom att betjäna en referenssträng hänvisar vi till handlingen att utföra en serie UO-operationer som gör det möjligt för beräkningen att komma åt block i den ordning som anges av referenssträngen. En färsk studie [6] fokuserade på off-line problemet med att tjäna en godtycklig men fullt känd referenssträng av block spridda över D parallella, oberoende diskar med parallell prefetchmg i samband med sidan ersättning t. Författarna presenterade och analyserade en mycket smart men något komplicerad approximation algoritm för detta problem. Den praktiska frågan om att utarbeta en online-algoritm inom ramen för en konkurrensanalys [9] för samma problem togs dock inte upp. Tillstånd att göra digitalnlihnrd kopior av alla eller en del av denna nmtcrial tbr pcrsonnl eller klassrum användning beviljas utan l>c tillhandahålls 111:tt tltc cop& nrc inte görs eller distribueras för vinst eller connncrcinl ndvnn~agc. 111~ upphovsrättsligt meddelande, titeln på 1111: publicering och dess dntc nppcnr. och meddelande ges lbnt copyrigh1 är med tillstånd av lhc ACAI. Inc. Kopiera olltcnvise, återpublicera, posta på scnvrs eller till rcdistribtnl: till listor. rcquircs specical pemiission nndIor avgift Copyright 19.97 ACM U-89731~9GG-1/97/l I..$3.50 Prestanda av parallella versioner av LRU och MIN [2] analyserades i [l 11. Modellering av ett distribuerat parallellt Y/O-system, med oberoende diskar och en partitionerad I/O-buffert, de definierade en parallell version av MIN, och visade att det är optimalt. Prestanda hos onlinealgoritmer i ett tätare kopplat system där bufferten kan delas av de olika diskarna beaktades inte. I detta dokument presenterar vi ett konkurrenskraftigt analysramverk för parallella förhämtningsalgoritmer på parallella disksystem för en re-'Notera attnplacementbeslutenberöms av det faktum atttbeUOffer bara kan hålla ett visst fast nummer, säger M. av sidor.
Problemet med online schemaläggning av read-once referenssträngar i ett multi-disk system togs först upp i REF.
Competitive parallel disk prefetching and buffer management
{'venue': "IOPADS '97", 'journal': None, 'mag_field_of_study': ['Computer Science']}