Lock-free Multiway Search Trees as Priority Queues in Parallel Branch and Bound Applications

Report
Authors:Spiegel, Michael, Department of Computer ScienceUniversity of Virginia Reynolds, Paul, Department of Computer ScienceUniversity of Virginia
Abstract:

The lock-free skip tree is a cache-conscious concurrent data structure for many-core systems that shows significant performance improvements over the state of the art in concurrent data structure designs for those applications that must contend with the deleterious effects of the memory wall. In a previous study using a series of synthetic benchmarks, the lock-free skip tree was found to improve peak throughput by x1.8 to x2.3 relative to a state of the art lock-free skip list implementation when the working set exceeds chache size. In this work, we study a class of application benchmarks that can be used to characterize the relative merits of the lock-free skip tree as compared to the lock-free skip list. In a series of four parallel branch-and-bound applications, two of the applications are x2.3 and x3.1 faster when using the skip tree as a concurrent priority queue as compared to the lock-free skip list priority queue. On a shared-memory supercomputer architecture the two branch-and-bound applications are x1.6 and x2.1 faster with the skip tree versus the skip list running at 80 hardware threads. Based on the four application benchmarks and a synthetic branch-and-bound application, a set of guidelines is offered for selecting the lcok-free skip tree to use as a centralized priority queue in parallel branch-and-bound applications. This technical report is an extended version of a manuscript of the same title that has been submitted for publication.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Spiegel, Michael, and Paul Reynolds. "Lock-free Multiway Search Trees as Priority Queues in Parallel Branch and Bound Applications." University of Virginia Dept. of Computer Science Tech Report (2011).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
2011