Memory \(M\), block size \(B\), problem size \(N\)

basic operations:

• Scanning: \(O(N/B)\)

• reversing an array: \(O(N/B)\)

matrix operations

• \(N\times N\) matrix

• Add?

  • need to decide on representation

  • use row-major dense representation

  • add is linear scan

• Multiply?

• How externalize standard algorithm?

  • Row major

    • scan rows of first and columns of second

    • so need \(N\) reads to get each column entry from second matrix

    • and \(N^2\) items to read

    • so \(N^3\) over all

  • Column major

    • What if could somehow transpose second matrix?

    • Now only need \(N/B\) reads per output value

    • So \(N^3/B\)

    • Still wasteful. How?

    • Many output values rely on same column

    • So we read the same rows repeatedly

    • How avoid?

  • Block layout

    • Think of matrix as array of smaller matrices

    • Multiply main matrix as sum of products of smaller matrices

    • We’ve seen addition is linear

    • Bigger blocks will help

    • But the limit: need block to fit in memory

    • so size \(\sqrt{M} \times \sqrt{M}\)

    • so need to read \(N/\sqrt{M}\) blocks to produce an output block

    • time per block is \(M/B\) since block size \(M\)

    • \(N^2/M\) output blocks

    • so total time is product \(N^3/B\sqrt{M}\)

• Can improve this by starting with better sequential matrix multiply—e.g Strassen.

  • get to \(N^{2.376}\) sequential

  • can extend to external memory

Linked list

• operations insert, delete, traverse

• insert and delete cost \(O(1)\)

• must traversing \(k\) items cost \(O(k)\)?

• keep segments of list in blocks

• keep each block half full

• now can traverse \(B/2\) items on one read

• so \(O(K/B)\) to traverse \(K\) items

• on insert: if block overflows, split into two half-full blocks

• on delete:

  • if block less than half full, check next block

  • if it is more than half full, redistribute items

  • now both blocks are at least half full

  • otherwise, merge items from both blocks, drop empty block

• Note: can also insert and delete while traversing at cost \(1/B\) per operation

• so, e.g., can hold \(O(1)\) “fingers” in list and insert/delete at fingers.

Search trees:

• binary tree cost \(O(\log n)\) memory transfers

• wastes effort because only getting one useful item per block read

• Instead use \((B+1)\)-ary tree; block has \(B\) splitters

• Require all leaves at same depth

• ensures balanced

• So depth \(O(\log_B N)\), much better

• Need to keep balanced while insert/delete:

  • require every block but root to be at least half full (so degree \(\ge B/2\))

  • also ensures depth \(\log_B N\)

  • on insert, if block is full, split into two blocks and pass up a splitter to insert in parent

  • may overflow parent, forcing recursive splits

  • on delete, if block half empty, merge as for linked lists

  • may empty parent, force recursive merges

• optimal in comparison model:

  • Reading a block reveals position of query among \(B\) splitters

  • i.e. \(\log B\) bits of information

  • Need \(\log N\) bits.

  • so \(\log N/\log B\) queries needed.

Sorting:

• Tree sort?

  • \(N\) inserts into \(B\)-tree, then scan

  • time \(O(N\log_B N)\).

• Standard merge sort based on linear scans: \(T(N)=2T(N/2) + O(N/B)=O((N/B)\log N)\)

• (Better than tree sort: \(\log B \rightarrow B\).

• Can do better by using more memory

• \(M/B\)-way merge

• keep head block of each of \(M/B\) lists in memory

• keep emitting smallest item

• when emit \(B\) items, write a block

• when block empties, read next block of that list

• \(T(M) = O(N/B)+(M/B)T(N/(M/B)) = O((N/B)\log_{M/B}N/B)\)

Optimal for comparison sort:

• Assume each block starts and is kept sorted (only strengthens lower bound)

• loading a block reveals placement of \(B\) sorted items among \(M\) in memory

• \(\binom{M+B}{B} \approx (eM/B)^B\) possibilities

• so \(\log() \approx B\log M/B\) bits of info

• need \(N\log N\) bits of info about sort,

• except in each of \(N/B\) blocks \(B\log B\) bits are redundant (sorted blocks)

• total \(N\log B\) redundant i.e. \(N\log N/B\) needed.

• now divide by bits per block load

Buffer Trees

Mismatch:

• In memory binary search tree can sort in \(O(n\log n)\) (optimal) using inserts and deletes

• But sorting with \(B\)-tree costs \(N\log_B N\)

• So inserts are individually optimal, but not “batch optimal”

• Basic problem: writing one item costs 1, but writing \(B\) items together only costs 1, i.e. \(1/B\) per item

• Is there a data structure that gives “batch optimality”?

• Yes, but if inserts/queries are to happen in batches, sometimes you will have to wait for an answer until your batch is big enough

• Can achieve optimum throughput, but must sacrifice latency.

Basic idea:

• Focus on supporting \(N\) inserts and then doing inorder traversal

• Idea: keep buffer in memory, push into \(B\)-tree when we have a block’s worth

• Problem: different items push into different children, no longer a block’s worth going down

• Solution: keep a buffer at each internal node

• Still a problem: writing one item into the child buffer costs 1 instead of \(1/B\)

• Solution: make buffers huge, so most children get whole blocks written

Details:

• make buffer “as big as possible”: size \(M\)

• increase tree degree to \(M/B\)

• but still B items per leaf node—tree over individual blocks

• basic operation: pushing overflowing buffer down to children

  • invariant: arriving overflow items are sorted

  • buffer had \(M\)

  • sort \(M\) items

  • merge with sorted incoming \(X\) in time \(O(M/B+X/B)\) (write to external)

  • write sorted contiguous elements to proper children

  • check for child overflow, recurse

  • cost is at most 1 partial block per child (\(M/B\) children) plus 1 block per \(B\) items (\(K/B\)) so \(M/B+K/B < 2K/B\).

  • since at least \(M\) items, account as \(1/B\) per item

• on insert, put item in root buffer (in memory, so free)

• when a buffer fills, flush

• may fill child buffers. flush recursively

• when flush reaches leaves, store items using standard \(B\)-tree ops (split leaf nodes, possibly recursing splits)

  • cost of splits dominated by buffer flushing

  • how handle buffers when split leaves?

  • no problem: they are empty on root-leaf path because we have just flushed to leaves.

• cost of flushes:

  • buffer flush costs \(1/B\) per item

  • but each flushed item descends a level

  • total levels \(\log_{M/B} N/B\)

  • So cost per item is \((1/B)\log_{M/B} N/B\)

  • So cost to insert \(N\) is optimal sort cost

“Flush” operation

• empties all buffers so can directly query structure

• full buffers already accounted

• unfull buffers cost \(M/B\) per internal node

• but number of internal nodes is \((N/B)/(M/B)\) (\(N/B\) leaf blocks divided among \(M/B\) leaf-blocks per parent)

• so total cost \(N/B\)

• so can sort in \(N/B\log_{M/B} N/B\)

Extensions

• search: “insert” query, look for closest match as flushes down

• delete: insert “hole” that triggers when it catches up to target item

• delete-min: extra buffer of \(M\) minimum elements in memory. when empties, flush left path and extract leftmost items to refill

• range search: insert range, push to all matching children on flush

• all ops take \(1/B \log_{M/B}N/B\) (plus range output)

Cache Oblivious Algorithms

In practice, don’t want to consider \(B\) and \(M\)

• hard-coding them makes your algorithm non-portable

• and, with multi-level memory hierarchies, unclear where bottleneck is, i.e. which \(B\) and \(M\) you use

• without knowing \(B\) and \(M\), how can we tune for them?

• surprisingly often, you can

• key: divide and conquer algorithms

• these tend to be sequentially optimal

• and rapidly shrink subproblems to where they fit on one page

• regardless of the size of that page

Assumption: optimal memory management

• so we can assume whatever page eviction policy works for us

• because we know e.g. LRU with double memory is 2-competitive against optimal management

• and we are ignoring constant factors

Example: scanning contiguous array

• \(N/B\)

• without knowing \(B\)!

Matrix Multiply

Adding matrices is easy

• \(N \times N\) arrays

• treat as vectors and scan to add

• time \(N^2/B\)

Standard sequential algorithm

• \(N \times N\) arrays

• \(N^3\) time

• row major order

• so scanning a row is very cheap

• but scanning a column is super expensive

• unless \(N \times N < M\), evict rows on every column

• so \(N^3\) external memory accesses!

• can we do better?

store second matrix column major?

• One output now requires \(N/B\) reads

• So \(N^3/B\), an improvement

• problem: what if next have to multiply in other order?

• need fast transpose operation!

• and turns out still not optimal—not leveraging large \(M\)

Divide and conquer

• mentally partition \(A\) and \(B\) into four blocks

• solve 8 matrix-multiply subproblems

• add up the pieces

• sequentially, \(T(N)=8T(N/2) + N^2 = O(N^3)\) (same as standard)

• external memory: \(T(N)=8T(N/2) + N^2/B = O(N^3/B)\) (same as column major)

• because at level \(i\) of recurrence do \(2^iN^2/B\) fetches

• wait, at size \(N=\sqrt{M}\), whole matrix fits in memory

• no more recursions. \(T(c\sqrt{M}) = O(M/B)\)

• this is at level \(i\) such that \(N/2^i = \sqrt{M}\), ie \(i=\log N/\sqrt{M}\)

• so runtime \(2^iN^2/B= N^3/B\sqrt{M}\)

Binary Search Trees

\(B\)-trees are optimal, but you need to know \(B\)

Divide and conquer

• We generally search an array by binary search

• We query one value and cut problem in half

• bad in external memory, because only halve on one fetch

• \(B\)-tree is better, divides by \(B\) on one fetch

• but we don’t know \(B\)

Van Emde Boas insight

• use new degree parameter \(d\) to avoid confusion

• problem of finding right child among \(d\) in page is same problem

• before, we set \(d=B\) and ignored it because “in memory”

• now we don’t know \(B\) but can still set a \(d\)

• recurrence: \(T(N) = T(d) + T(n/d)\)

• Balance: set \(d=\sqrt{N}\)

• \(T(N) = 2T(\sqrt{N}) = 2^{\log\log N} = \log N\) (still sequentially optimal)

• Wait, when \(N=B\) we get the whole array in memory and finish in \(O(1)\)

• so, stop at \(i\) such that \(N^{(1/2)^i}=B\), ie \(B^{2^i}=N\) so \(2^i = (\log N)/\log B =\log_B N\)

• so runtime \(\log_B N\)

• draw a picture

• see how you get a chain of \(\log B\) items all on same page.

• yields speedup

Generalizations:

• Dynamic

• Buffer Trees

Linked Lists

Want \(O(1)\) insert/delete but \(O(1/B\) scan

• Cache aware, we used dynamic splitting/merging of contiguous “runs” to limit fragmentation

• How without \(B\)?

• Need to combat fragmentation without knowing whether it exists

• idea: defragment while scanning

• all scanned items become unfragmented

• use potential function (amount of fragmentation) to pay for defrag

Solution:

• on delete, just leave a hole

• on insert, append to end of external memory

• on scan, append all scanned items in order to end of memory

Analysis

• potential function: number of contiguous “runs” of elements in sequence on block

• equals number of “jumps” of pointers from one block to another

• suppose traverse \(K\) items in \(r\) runs

• the cost is at most \(K/B+r\)

• scanned items written to end

• eliminates all but first and last run:

• reduces runs by \(r-2\)

• so amortized cost \(O(K/B)\)

Controlling size

• all operations including traversal increase size of data structure

• solution: after \(N/B\) work, scan whole list

• amortized cost \(N/B\)

• but now list is sorted/contiguous

• all previous blocks become free/irrelevant