Multi-combining : exploring the batching-parallelism trade-off
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Diese Arbeit untersucht die effiziente Synchronisation von gleichzeitigen Operationen auf AVL-Bäumen in Multi-Core-Umgebungen. Während AVL-Bäume Laufzeitgarantien im logarithmischen Bereich bieten, erfordert der parallele Zugriff eine Synchronisation, die häufig zu Konflikten und Skalierungsengpässen führt. Delegationsbasierte Synchronisationsmethoden wie Flat Combining verringern diese Konflikte durch das Bündeln von Operationen, führen jedoch aufgrund der Abhängigkeit von einem einzelnen Combiner-Thread selbst zu einem neuen Engpass.
Zur Überwindung dieser Einschränkung wird in dieser Arbeit ein Multi Combining-Ansatz vorgeschlagen, der den Engpass durch die Aufteilung der Operationsbündel auf mehrere Combiner entschärft. Das Design nutzt die strukturellen Eigenschaften von AVL-Bäumen, indem die Arbeitslast entlang des Wurzelknotens partitioniert und separate Combiner für Operationen auf dem linken und rechten Teilbaum verwendet werden. Um den Synchronisationsaufwand zu reduzieren, der typischerweise durch häufige Aktualisierungen an der Wurzel entsteht, verwendet das System ein relaxiertes AVL-Baum-Design, bei dem das Rebalancing bis zum Erreichen eines bestimmten Schwellenwerts aufgeschoben wird.
Umfassende Evaluationen zeigen, dass Multi Combining sowohl traditionelle Locking-Mechanismen als auch Flat Combining-Ansätze durchgehend übertrifft. In einfüge- und löschintensiven Workloads wird bis zu die doppelte Durchsatzrate im Vergleich zu konkurrierenden Methoden erreicht, während leseintensive Workloads von der parallelen Ausführung von Suchanfragen profitieren. Insgesamt zeigen die Ergebnisse, dass Multi Combining das Zusammenspiel von Batching und Parallelisierung wirksam ausbalanciert und eine skalierbare Synchronisationsstrategie für parallele, balancierte Bäume bietet.
This thesis investigates the efficient synchronization of concurrent operations on AVL trees in multicore environments. While AVL trees offer logarithmic-time guarantees, concurrent access requires synchronization, which often leads to contention and scalability bottlenecks. Delegation-based synchronization methods, such as Flat Combining, address contention by batching operations but introduce a new bottleneck due to their reliance on a single combiner thread. To overcome this limitation, this thesis proposes a Multi Combining approach that alleviates the bottleneck by partitioning operation batches across multiple combiners. The design leverages the structural properties of AVL trees by partitioning the workload based on the root node, dedicating separate combiners for operations on the left and right subtrees. To minimize the synchronization overhead that is typically required for frequent root updates, the system utilizes a relaxed AVL tree design, which defers rebalancing until a specific threshold is reached. Extensive evaluation shows that Multi Combining consistently outperforms both traditional locking and Flat Combining approaches. Insertion- and removal-heavy workloads achieve up to double the throughput compared to competing methods, while read-heavy workloads benefit from parallel execution of lookups. Overall, the results demonstrate that Multi Combining effectively balances batching and parallelism, providing a scalable synchronization strategy for concurrent balanced trees.
This thesis investigates the efficient synchronization of concurrent operations on AVL trees in multicore environments. While AVL trees offer logarithmic-time guarantees, concurrent access requires synchronization, which often leads to contention and scalability bottlenecks. Delegation-based synchronization methods, such as Flat Combining, address contention by batching operations but introduce a new bottleneck due to their reliance on a single combiner thread. To overcome this limitation, this thesis proposes a Multi Combining approach that alleviates the bottleneck by partitioning operation batches across multiple combiners. The design leverages the structural properties of AVL trees by partitioning the workload based on the root node, dedicating separate combiners for operations on the left and right subtrees. To minimize the synchronization overhead that is typically required for frequent root updates, the system utilizes a relaxed AVL tree design, which defers rebalancing until a specific threshold is reached. Extensive evaluation shows that Multi Combining consistently outperforms both traditional locking and Flat Combining approaches. Insertion- and removal-heavy workloads achieve up to double the throughput compared to competing methods, while read-heavy workloads benefit from parallel execution of lookups. Overall, the results demonstrate that Multi Combining effectively balances batching and parallelism, providing a scalable synchronization strategy for concurrent balanced trees.