• Binary Fork Join Model
  • Assume each processor shares memory
  • Threads may perform a fork operation
  • Later performs a join operation for sync

• Represent algorithm's computation as a DAG
  • Each node represents tasks, each edge is a dependency
• Work: Total number of nodes in the graph
• Span: Longest path within the graph

• Modern computers typically bottlenecked by memory accesses
  • Captured sequentially by the External Memory Model
  • PRAM has the parallel equivalent, PEM
  • Binary Fork Join model does not

• Natural extension of Binary Fork-Join Model
  • All threads share external memory
  • Each thread may access a block of data in a single memory access
  • Each fork and join spawns and syncs at most threads

• Join-based framework
  • Supports efficient set operations on search trees
  • Core operations are the Join and Split operations

• Multi-way cache efficient self-balancing tree
• Each node in the tree contains keys and subtrees
• We seek to extend Join to B-way Join
  • Eventually develop Multi-way Join

• General steps for the algorithm
  • Grouping
  • Recurse and Subtree Replace
  • Concatenate and Rebalance

Theorem 1

Let be a set of B-trees, with the largest tree height and the shortest tree height , and be a set of separator keys, where . The join operation can be performed in I/O span and I/O work.

• Leads to a span-inefficient solution
• Union with above primitive leads to I/O Span

• Grouping
• Fuse within Groups
• Divide Large Nodes
• Divide Smaller Nodes
• Concatenate and Rebalance

• Do not recurse into subgroups of tall trees
  • Fuse keys and nodes at their heights directly
• Maintain list of pointers along the left and right spines
• Finding the node a root merges with takes I/O span

• Divide node if contains keys
  • Any node contains at most keys
• After, each node contains at most keys
  • Each subsequent dividing of nodes will push up at most 1 key

Theorem 2

We can join B-trees and keys together in parallel with I/O span and I/O work, where is in the Fork-Join I/O model.

Theorem 3

We can split a B-tree by keys in parallel with I/O span and I/O work, where is in the Fork-Join I/O Model.

• Divide each tree into sections
  • Use the Multi-way Split operation
• Perform a union on each pair of subtrees
• Use Multi-way Join to combine all elements in the tree
  • Minor modifications may be made to Multi-way Join to get Intersection and Difference operations

Theorem 4

Given two B-trees with sizes and , there exists a parallel algorithm that returns a new B-tree containing the union, intersection, and set difference of the two input trees in and I/O work, I/O span, where is the block size.

• Turning to
• Removing factor entirely
• Apply algorithm to adaptive sorting settings
• Use Fork-Join I/O model on other algorithms