How cmuparlay/pam works
Project Type and Purpose
• Type: C++ parallel library (open-source tool) providing sequence, ordered set/map, and augmented-map interfaces with multiple balancing schemes.
• Purpose: Expose a header-only (plus optional compiled interface) library that clients link against, supporting highly parallel algorithms via join-based tree operations. Includes examples, tests, and benchmarks to illustrate and validate functionality.
File Structure
Top level:
– CMakeLists.txt, Makeheader, .gitmodules → Build and submodule setup
– include/pam/… → Public library headers
– benchmark/ → Performance tests
– examples/ → Sample applications in domains (interval, range_query, segment, rectangle, index, tpch)
– tests/ → Unit and parallel tests
Key patterns:
• Header-only API living under include/pam
• Modular tree implementations (avl_tree, treap, red_black_tree, weight_balanced_tree)
• Utility modules (gc, parsing, timing)
• Examples organized by algorithm/domain
• Dependence on ParlayLib (git submodule)
README for Insights
– Architecture described in papers: join-based balanced trees + prefix structures
– External dependency: ParlayLib for parallel primitives (sorting, scan, scheduler)
– Build via CMake with option to download ParlayLib
– Runtime options for scheduler backends (Cilk, OpenMP, TBB, sequential)
Main Components and Their Interactions
a. Components:
1. Client Applications
• examples/…
• tests/
• benchmark/
2. PAM Public API (include/pam/pam.h and friends)
3. PAM Core Modules
• Tree Data Structures: avl_tree, red_black_tree, treap, weight_balanced_tree
• Augmentation & Sequence Ops: augmented_ops, sequence_ops, map_ops, build
• Utilities: gc (garbage collection), get_time, parse_command_line, utils
4. Third-Party Library
• ParlayLib (parallel algorithms, scheduler)
5. Build System
• CMake + Makeheader + git submodule
6. Hardware / Runtime
• Multicore CPU, 128-bit CMPXCHG
b. Relationships and Data Flow:
– Client code invokes PAM Public API
– Public API delegates to Core Modules (tree operations, augmentation, sequence ops)
– Core Modules perform parallel algorithms by calling ParlayLib routines
– ParlayLib issues tasks to the scheduler and uses low-level atomic operations/HW
– Build system orchestrates compilation and configuration (including optional download of ParlayLib)
c. Architectural Patterns & Principles:
– Layered architecture (clients → API → core modules → external library → hardware)
– Modular: pluggable balancing schemes via templates
– Join-based divide-and-conquer parallelism
– Header-only design for ease of integration (with optional compiled library)
– Extensible augmentation via user-provided entry struct
d. Key Technologies & Frameworks:
– C++17 templates and inline implementations
– CMake for cross-platform builds
– ParlayLib for parallel primitives
– Optional backends: Cilk Plus, OpenMP, TBB
Elements
– API calls from clients to public API
– Internal calls from API to core modules
– Calls from core modules to ParlayLib
– Data flow from hardware back up through layers (for timing, GC)
– Library code (e.g., blue rectangles)
– Applications/tests (e.g., green rectangles)
– External dependencies (e.g., orange rectangles)
– Build/configuration (e.g., gray parallelograms)
Detailed Breakdown of Components
1. Client Layer:
– examples/index, examples/interval, examples/range_query, etc.
– tests/*.cpp, benchmark/timeOps.cpp
2. API Layer:
– include/pam/pam.h (entry point)
– pam_map, pam_set typedefs
3. Core Module Layer:
– Data structures: avl_tree.h, red_black_tree.h, treap.h, weight_balanced_tree.h
– Augmentation: augmented_map.h, augmented_node.h, augmented_ops.h
– Sequence operations: sequence_ops.h
– Build utilities: build.h, map_ops.h
– Support: gc.h, parse_command_line.h, get_time.h, utils.h
4. External Parallel Primitives:
– parlaylib submodule
5. Build & Deploy:
– CMakeLists.txt (+ subdirectories), .gitmodules, Makeheader
6. Hardware: