Externspeicher-Algorithmen:Teil 2

Petra Mutzel Technische Universität Wien

Institut für Computergraphik und Algorithmen

Algorithmen und Datenstrukturen 2

Robert E. Bixby:Solving Linear and Integer Programs

Montag, 7. April 2003, 17 Uhr s.t.Informatik-Kolloquium

Zemanek-Hörsaal, Favoritenstraße

Externe Array-Heaps

Lemma 1: li+1=li (μ+1)

μ=(cM/B)-1

L1

L2

L3

l2

li=(cM)i/Bi-1

μ μ

L Schichten Li

Slots:enthaltensortierte Folgeoder sind leer

c=1/7L<=4

I/O Schranken

Theorem:

Annahme: cM>3B und 0<c<1/3 und N<=B(cM/B)1/c-3

In einer Folge von N Operationen der Art Insert und

Del_Min benötigt

– Insert amortisiert 18/B(log cM/B(N/B)) I/O´s und

– Del_Min 7/B amortisierte I/O´s.

Beweis: Amortisierte Analyse (1)

• Insert: 18/B(log cM/B(N/B)) >= 18L/B I/O´s

• Del_Min 7/B amortisierte I/O´s.

• Bankkonto-Methode:

– Jedes Element erhält beim Einfügen ein Guthaben von 18L/B

– Wir zeigen: es werden höchstens 18/B benötigt um von einer zur

anderen Schicht zu wandern

– Beim Entfernen werden 7/B Einheiten im Heap belassen

Beweis: Amortisierte Analyse (2)

• Insert mit Overflow kostet 6li+1/B, denn:

– Merge_level(i,S;S´): kostet 3li+1/B und Store(i+1,S´): kostet 3li+1/B

• Wie können diese Kosten bezahlt werden?

• Fall1: 1. Overflow zur Schicht L1:

• Jedes Element, das mittels nun bewegt wird, gibt von ihrem Bakkonto

jeweils 12/B Einheiten dafür ab; da Schicht L2 mindestens zur Hälfte gefüllt

ist, kommen so (12/B) (l2/2)=6l2 / B Einheiten zusammen.

• (Interpretation: stellen Sie sich vor, jedes Element erhält beim Einfügen

(anfangs) 18L/B Einheiten; nun möchten die Elemente in die Schicht L2

wechseln, das kostet aber insgesamt 6l2/B. Diese können dadurch

aufgebracht werden, indem alle bewegten Elemente jeweils 12/B Einheiten

von ihrem momentanen Bankkonto abgeben.)

Beweis: Amortisierte Analyse (2)

• Insert mit Overflow kostet 6li+1/B, denn:

– Merge_level(i,S;S´): kostet 3li+1/B und Store(i+1,S´): kostet 3li+1/B

• Fall2: Overflow von Schicht Li nach Li+1:

• Jedes Element hatte ja anfangs 18L/B Einheiten zur Verfügung; das sind

für jede Schicht (also auch für Schicht i) genau 18/B Einheiten, die das

Element verbrauchen kann. Da Schicht Li mindestens zur Hälfte gefüllt

ist, können diese Kosten (genauso wie im 1. Fall) durch 12/B Einheiten

von den Bankkonten der bewegten Elemente genommen werden.

• Beobachtung: Damit hat jedes Element nach der Merge_level() und

Store()-Operation noch 6/B Einheiten pro Schicht übrig.

Beweis: Amortisierte Analyse (2)

• Invariante: Zu jedem nicht-leeren Slot j der Schicht Li gehört ein Deposit

Di,j von 6x/B, wobei x die Anzahl der freien Felder in j entspricht.

• Das heisst: Um die Invariante zu erfüllen, muss jedes durch den Store()

Aufruf nach Schicht Li+1 bewegte Element 6/B Einheiten an Di,j abgeben

• Insgesamt: kostet also eine Merge_Level() und eine Store() Operation

pro Overflow (Schicht) 18/B Einheiten per Element.

Beweis: Amortisierte Analyse (3)

• Beim Entfernen werden 7/B=(1+6)/B Einheiten im Heap belassen

• Eine Load()-Operation wird durch das Nehmen von B(1/B)=1 Einheiten

aus dem Heap bezahlt.

• Diese Einheiten kamen jeweils durch die letzten (aus Slot j) B

entfernten Elemente zustande.

• Die restlichen B(6/B)=6 Einheiten dieser entfernten Elemente werden

dem Di,j zugeordnet, auf dem Load() operiert hat (denn danach sind

es dort B Einheiten weniger, es werden also 6*B/B=6 Einheiten mehr

in Di,j benötigt).

• Insgesamt: sind das 7/B Einheiten für die Load() Operation

Beweis: Amortisierte Analyse (4)

• Es bleibt: die Bezahlung für Compact(i): 3li/B

• Dies wird durch die Deposits Di,j an den slots j1 und j2, die kompaktiert

werden, bezahlt:

• Die Gesamtanzahl der leeren Plätze in den slots j1 und j2 ist

mindestens li.

• Dafür gibt es in den Deposits Di,j1 und Di,j2 zusammen mindestens 6l i/B

Einheiten.

• Nach dem Mischen gibt es in Di,j1 höchstens li/2 freie Slots, d.h. für das

neue Di,j1 werden nur 3li/2 Einheiten benötigt

• Die anderen 3li/2 Einheiten werden für Compact(i) ausgegeben.

Literatur

Andreas Crauser: LEDA-SM: External Memory Algorithms and Data

Structures in Theory and Praxis. Dissertation, Max-Planck-Institut für

Informatik, Saarbrücken, 2001. Kapitel 4: Priority Queues;

http://www.mpi-sb.mpg.de/~crauser/degrees.html

Klaus Brengel, Andreas Crauser, Paolo Ferragina, Ulrich Meyer: An

Experimental Study of Priority Queues in External Memory, Proc. of

the Workshop on Algorithmic Engineering (WAE ´99), Lecture Notes in

Computer Science 1668, 345-359, Springer-Verlag, 1999

Die Vorlesung hält sich eng an:

When this book was first written, magnetic tapes were abundant and disk drives were expensive. But disks became enormously better during the 1980s,... . Therefore the once-crucial topic of patterns for tape merging has become of limited relevance to current needs. Yet many of the patterns are quite beautiful, and the associated algorithms reflect some of the best research done in computer science during ist early years;

The techniques are just too nice to be discarded abruptly onto the rubbish heap of history. ...

Therefore merging patterns are discussed carefully and completely below, in what may be their last grand appearance before they accept a final curtain call.

Donald E. Knuth: The Art of Computer Programming 1967 (Neuauflage 1998):

Pavel Curtis in Knuth:``The Art of Computer Programming´´ 1967 (Neuauflage 1998):

For all we know now, these techniques may well become crucial once again.

Cache-Optimale Algorithmen

Teil 2:

CPUCache

Kapazität Z

Arbeits-Speicher

KapazitätM

Extern-speicher

Faktor 100 schneller als

Hierarchisches Speichermodell moderner Computer

Hits vs. Cache misses

L = Anzahl der Elemente, die in eine Zeile passen

Auch zur Cache-Optimierung könnte EM-Seichermodell verwendet werden

Problem: Speicherhierarchie, alle mit anderer Block-größe und Kapazität

B = Anzahl der Elemente, die in einen Block passen

Lösung: ``Cache-oblivious´´ Speichermodell

• Blockgröße B und Kapazität M sind unbekannt• Eine Algorithmen-Analyse muss für alle

Blockgrößen und Kapazitäten gelten ---also auch für alle Speicherhierarchie-Ebenen

• Dies erhöht die Portabilität von Programmen:• eben nicht für festes B und M entwickelt

• Dies garantiert optimale Speicherzugriffe auf jeder Speicherhierarchie-Ebene.

Z/L Cache-Zeilender Länge L

L = Anzahl der Wörter, die in eine Cache- Zeile passen

CPU

Arbeits-speicher

beliebiggroß

Das ``ideal-cache´´-Modell von Frigo et al. 1999

Kapazität: Z Bytes

2-Ebenen Speicherhierarchie

Annahme: Z=Ω(L2): ``Cache ist hoch´´

Cache-misses

Das ``ideal-cache´´-Modell von Frigo et al. 1999

• CPU kann nur Wörter bearbeiten, die sich im Cache befinden

• Wenn sich ein referenziertes Wort im Cache befindet: Cache-Hit

• Sonst: Cache miss: Zeile muss erst in den Cache gebracht werden.

• Falls der Cache voll ist, muß eine Cache-Zeile vorher entfernt werden. Der ideale Cache entfernt diejenige off-line optimale Zeile, die zuletzt (zeitlich) wieder benötigt wird.

Praxis: least recently used

``Cache-oblivious´´ Analyse

• Cache-Komplexität Q(n,Z.L): die Anzahl der Cache-Misses, abhängig von Z und L (n Eingabegröße der Instanz).

• Die Anzahl der ausgeführten CPU-Operationen im RAM Modell T(n)

• Ein Algorithmus heisst ``Cache-Aware´´ (Cache-bewußt), wenn er Parameter enthält, mit denen die Cache-Komplexität für gegebenes Z und L optimiert werden kann.

• Andernfalls heißt der Algorithmus ``Cache-oblivious´´ (Cache-ignorierend).

• Ein optimaler ``Cache-oblivious´´ Algorithmus für 2 Ebenen, ist auch für mehrere Ebenen optimal.

Beispiel: Matrix-MultiplikationCache-Aware Algorithmus

• Annahme: s ist Teiler von n• Insgesamt: Θ(1+n2/L+(n/√Z)3(Z/L))=Θ(1+n2/L+n3√Z/L)

Algorithmus BLOCK_MULT(A,B,C,n)Für i=1 bis n/s Für j=1 bis n/s

Für k=1 bis n/s MULT(Aik,Bkj,Cij,s);

MULT(A,B,C,s) ist die Standard-Prozedur, die C=C+AB auf sxs Untermatrizen in Zeit O(s3) berechnet.

• s sei der größte Wert, so dass die drei Untermatrizen zusammen in den Cache passen.

• Eine sxs Untermatrix benötigt ((s+s2)/L) Cache Zeilen.• Der Cache besitzt Z/L Cache Zeilen.• Cahe hat Größe Z: 3s2<=Z: s=Θ(√Z).• Jeder Aufruf von MULT() benötigt höchstens Z/L=Θ(s2/L)=Θ(Z/L)

Cache-Misses, um die drei Untermatrizen in den Cache zu bringen.

Cache-Oblivious Algorithmus

Idee: Divide & Conquer Prinzip

A: mxn Matrix, B: nxp Matrix

• Fall 1: m>= max{n,p}: splitte A horizontal in A1 und A2 mit jeweils m/2 Zeilen; es folgen 2 Aufrufe der Form A1B und A2B. Denn es gilt:

BA

BAB

A

A

2

1

2

1

• Fall 2: n>= max{m,p}: splitte A vertikal in A1 und A2 mit jeweils n/2 Spalten und B horizontal in B1 und B2 mit jeweils n/2 Zeilen. Denn es gilt

BABAB

BAA 21

2

121,

Cache-Oblivious Algorithmus

Idee: Divide & Conquer Prinzip

A: mxn Matrix, B: nxp Matrix

• Fall 3: p>= max{m,n}: splitte B vertikal in B1 und B2 mit jeweils p/2 Spalten. Denn es gilt: 2121 ,, BABABBA

• Fall 4: Falls m=n=p=1 gilt, dann werden die beiden Elemente multipliziert und zur resultierenden Matrix C hinzuaddiert.

Analyse des Cache-Oblivious Algorithmus

Theorem: Der Algorithmus benötigt Θ(mnp) Zeit im RAM Modell. Die Cache Komplexität beträgt Θ(m+n+p+(mn+np+mp)/L+mnp√Z/L) Cache-Misses.

Theorem: Zur Multiplikation zweier nxn Matrizen benötigt der Algorithmus REC_MULT Θ(n3) Zeit im RAM Modell und Θ(n+n2/L+n3√Z/L) Cache-Komplexität.

Gegenüberstellung BLOCK_MULT:

Θ(1+n2/L+(n/√Z)3(Z/L))=Θ(1+n2/L+n3√Z/L)

Analyse des Cache-Oblivious Algorithmus

Intuitiv benutzt der Algorithmus den Cache effektiv, denn: sobald ein Unterproblem ganz in den Cache passt, können dessen Unterprobleme ohne einen einzigen Cache-Miss gelöst werden.

Deswegen sind Divide&Conquer Verfahren grundsätzlich sehr gut für große Datenmengen geeignet.

Divide&Conquer Verfahren sind grundsätzlich gute Kandidaten für Cache-optimale Algorithmen.

Algorithmus mit besserer Laufzeit

Verfahren von Strassen (1986) zur Matrixmultiplikation

Auch ein Divide&Conquer Verfahren: jede Untermatrix wird in 4 Viertel der Höhe und Länge jeweils ungefähr n/2 zerlegt

RAM-Komplexität: Θ(N log 7)=Θ(N2,81)

Cache-Komplexität: Θ(n+n2/L+n log 7 √Z/L)

In Praxis: sehr aufwändig zu implementieren

Für n<=1.000.000 noch ungefähr genauso langsam wie REC_MULT

Offenes Problem! Eher theoretischer, aber

überraschender Beitrag

Weiterführende Literatur

Frigo, Leiserson, Prokop, Ramachandran:

Cache-Oblivious Algorithms, MIT, Cambridge

IEEE Transactions, 1999

Ende von External Memory 2

Vielen Dank