Emne: I den første forelæsning om External Memory Algorithms (20. marts), blev der gennemgået de dele af

The Input/Output Complexity of Sorting and Related Problems
Alok Aggarwal and Jeffrey Scott Vitter
Communications of the ACM, 31(9):1116-1127, 1988

der omhandlede flette sortering og permutation. Afsnitene omhandlende "FFT", "Permutation networks", "Matrix transposition" og "Distribution sort" blev ikke gennemgået.

Den anden forelæsning (27. marts) omhandler B-træer, som er I/O effektive søgetræer. B-træer er den fundamentale data struktur anvendt i mange database systemer. Forelæsningen tager udgangspunkt i nedenstående to manuskripter. En mere grundlæggende introduktion til B-træer findes i (Cormen et al, Kapitel 19).

Tekst:
Amortized Analysis of (a,b)-Trees
Gerth Stølting Brodal and Rolf Fagerberg
Note, 4 pages, 2000
[ps,pdf]

Cache-Oblivious B-Trees
Michael A. Bender, Erik Demain, and Martin Farach-Colton
In Proc. 41th Annual Symposium on Foundations of Computer Science,
399-409, 2000
Note 2

Slides fra forelæsningen d. 20 marts [pdf,ps]

Bemærk den sidste opgave er den obligatoriske opgave

Opgave 1)

a) I bedes overveje hvordan man eksperimentielt kan bestemme hukommelses hierakiet på en konkret maskine, f.eks.

* Antallet af forskellige hukommelses nivauer (L1 cache, L2 cache, DRAM, virtual memory)

* Størrelsen af de forskellige hukommelses niveauer

* Blok størrelsen

* Tilgangstider tider (Hit time, Miss penalty)

Hint: Mål udførselstiden af løkker der systematisk tilgår hukommelsen.

b) Afprøv evt. jeres overvejelser i praksis. Opnås de ønskede resultater ?

Hvorfor/hvorfor ikke ?

Opgave 2)

I denne opgave betragtes bunke sortering ("Heap sort", Cormen et al., Kapitel 7). Det antages at M>=B^2.

a) Argumenter for at det kræver O(N/B) I/Oer at bygge en bunke med N Heapify operationer.

Hint: CPU tiden er O(N). Betragt de 2log B nedeste niveuaer og de øverste log N-2log B niveauer adskilt.

b) Hvor mange I/Oer kræver det at fjern det mindste element fra bunken ?

c) Argumenter uformelt hvor mange I/Oer det kræver at udtage alle N elementer fra en bunke.

d) Er bunke sortering I/O effektiv ?

Opgave 3)

I forelæsningen blev det gennemgået hvorledes man opnår en I/O effektiv flette sorterings algorithme, hvis man kender parameterne B,N, M. I denne opgave antager vi at disse parametre ikke er kendt og at I/O sker automatisk af en virtuel hukommelses mekanisme der anvender LRU. Betragt følgende to varianter (pseudo kode) af binær flette sortering: I) Rekursiv variant

        proc Sort(X[1..N])
          if N>2 then
            Sort(X[1..N/2])
            Sort(X[N/2+1..N])
            X := Merge(X[1..N/2],X[N/2+1..N)

   
        proc Sort(X[1..N])
          i:=1
          while (i < N)
            for j=1 to N-i step 2*i
              k := min(j+2*i-1,N)
              X[j..k] := Merge(X[j..j+i-1],X[j+i..k]
            i:=2*i

a) Hvor mange I/O foretager algoritmerne hvis N<=M/2 ?

b) Hvor mange I/O foretager algoritmerne hvis N=M+1 ?

c) Hvilken af de to varianter af flette sortering er at foretrække i I/O modellen ? Bemærk at jeres argumenter vil gælde for alle niveau i hukommelses hierakiet.

d) Verificer evt. jeres udsagn fra c) eksperimentielt.

Denne opgave omhandler permutations algoritmer til flere diske.

a) Giv en permutations algoritme i Aggarwal-Vitter modellen der bruger O(N/P) I/Oer.

b) Giv en permutations algoritme i I/O modellen der bruger O(N/D) I/Oer når D<=B. Det antages at input og output er ligeligt fordelt på diskene.