Previous slide
Next slide
Toggle fullscreen
Open presenter view
Adaptive Parallel Joinable B-Trees
Presented By: Ryuto Kitagawa
Joint Work: Michael Goodrich, Yan Gu, Yihan Sun
University of California, Irvine
Parallel Joinable Binary Search Trees
Framework for parallelizing binary search trees
External Memory Model
Traditionally analyze algorithms RAM model
Instead consider having two layers of memory
B-Tree
Each node contains between
and
keys
All leaf nodes are at the exact same level
Height:
Binary Fork Join Model
Begin the algorithm with a single thread (processor)
fork
and
sync
operations
fork
spawns an extra thread
sync
joins two threads together
Analysis in terms of span and work
Span: Longest time taken by a single thread
Work: Sum time taken across all threads
External Fork Join Model
Natural extension of the fork join model
Each thread has their own cached memory
Threads may retrieve chunks of memory
External Fork Join Model
In addition to the cache
multifork
spawns
threads
multisync
joins
threads
Joinable B-Tree
Two crucial operations:
Join: Given
trees and
separator keys, output a combined tree
Split: Given a tree
and
keys,
trees separated by the keys
Given these two operations, all other set operations are trivial
Mainly focusing on the union operation
Operation Performance
Algorithm
Span
Work
Union Algorithm
Given two trees
and
Check if either tree is empty, if so output the other
Split
with the values from the root of
, outputs
Union across all
and the children of
Output a set of trees
Join across
and the root of
Union Algorithm: Analysis
For every join operation, there is a split operation
Span and work of union is dominated by the split operation
Adaptive Algorithms
The more "well-behaved" our input is, the more efficient it should be
Recall insertion sort and inversions
Potential flaws with this metric
Measures of Disorder
Techniques For Adaptive Algorithms
Many techniques for adaptive sorting in sequential
Skip-List/Level-Linked-Tree Sort
Tree Sort
Tim Sort
Parallel Tree Sort
Span:
Work:
Adapting Joinable B-Tree
Goal
Span:
Work:
Conclusion
Current Work
Prove that split still dominates the cost in the union algorithm
Show that the disorder metric does not affect the analysis
Future Work
Taking advantage of the size of cache memory
Analyze across various disorder metrics
Make span also adaptive to the disorder metric