Transcript Slide Presentation - Carleton University

Parallel Buffer Trees and
Searching
Cory Fraser
School of Computer Science
Carleton University, Ottawa, Canada
http://people.scs.carleton.ca/~cfraser3/
COMP 5704 Project Presentation
Outline
• Computational Model
• Parallel Buffer Trees
• Implementation
• Results
COMP 5704 Project Presentation
Computational Model
• Sequential Buffer Tree operated in the External
Memory Model.
• Minimizes transfers from hard disk -> RAM.
• Parallel Buffer Tree operates in the Parallel
External Memory Model.
• Minimizes transfers from RAM -> CPU cache.
COMP 5704 Project Presentation
Related Search Data Structures
• Binary Search Trees
• Usually analyzed in RAM/PRAM model.
• O(nlogn) build time, O(logn) operation time.
• B-trees
• Analyzed in EM / PEM model.
• O(nlogBn) build time, O(logBn) operation time.
• Buffer Tree has O((n/B) logB(n/B)) build time.
COMP 5704 Project Presentation
What is a Parallel Buffer Tree?
• An offline data structure.
• An (a,b)-tree variant.
• Performs tree operations in batches to reduce
I/Os.
• Good when there’s a continual large flow of
operations to execute.
COMP 5704 Project Presentation
Parallel Buffer Tree Complexity
• For sequences of N insert/delete/find(/range)
operations:
• O(sortP(N)) I/Os without range search
• O(sortP(N) + K/PB) I/Os with range searches.
• sortP(N) = O(N/PB logBN/B) I/Os
• Parallel B-tree needs O(N/PlogBN) I/Os.
COMP 5704 Project Presentation
Required Parallel Algorithms
• Parallel sorting for batch operations.
• Parallel merge sort used.
• Parallel prefix sums
• Needed for range query support.
• Distributes batched operations in buckets.
COMP 5704 Project Presentation
Implementation Overview
• Intel Cilk++ SDK with GCC used.
• Available at http://software.intel.com/enus/articles/download-intel-cilk-sdk
• Parallel merge sort from class used.
• Range query extension not implemented.
COMP 5704 Project Presentation
Implementation Details
• Buffer tree is an (a,b)-tree, a=f/4, b=f, f>= PB
• Each leaf stores up to B elements.
• Each non-leaf has a buffer of size 2fB.
• Internal nodes have k-1 routing elements to
direct values to children. k = num. of children
COMP 5704 Project Presentation
Implementation Details - Operations
• Tree builds up batches of PB operations before
executing them.
• An operation is its type, value, and timestamp.
• The PB batches operations are split into P
blocks and sent to the root in parallel.
COMP 5704 Project Presentation
Emptying Non-fringe buffers
• Sort the buffer by value and timestamp.
• Answer Find operations with matching Insert/Delete operations.
• Cancel out matching Insert/Deleting operations.
• Distribute buffer elements to children based on the routing
elements.
• Recursively empty children buffers with more than fB operations.
COMP 5704 Project Presentation
Emptying Fringe Buffers
• Convert all values within children nodes into
insert operations with negative infinity
timestamp.
• Sort the buffer by value and timestamp.
• Answer Find operations, cancel out
Insert/Deletes.
• Based on remaining operations:
• If <= fB then remake child nodes.
• If > fB then create new siblings for each fB/2 operations.
Tree rebalancing may be required.
COMP 5704 Project Presentation
Node Rebalancing
COMP 5704 Project Presentation
Results
• Test System Specs:
• Quad-core running Fedora 16.
• 12 GB of RAM.
• Sequential comparison structures:
• C++ std::set
• online structure
• Parallel Buffer Tree with 1 worker.
COMP 5704 Project Presentation
Results So Far – Build Times
COMP 5704 Project Presentation
Conclusions
• Parallel speedup vs sequential version is high
with enough input.
• Performance is not competitive against
equivalent online data structures thus far.
• Would need about 12 cores to match std::set.
• May be practical for high volume external
memory applications.
COMP 5704 Project Presentation
Questions
• What is an offline data structure?
• What kind of I/O operations is the Parallel
External Memory (PEM) model concerned with?
• Why can a Buffer tree be loaded with N
elements faster than a B-tree according to bigO?
COMP 5704 Project Presentation
References
• N. Sitchinava, N. Zeh, A Parallel Buffer Tree http://dl.acm.org/citation.cfm?id=2312046
• L. Arge, External Memory Data Structures http://www.itc.dk/research/algorithms/Kurser/AA/2002F/Uge
11/handbook.pdf
• http://opendatastructures.org
COMP 5704 Project Presentation