论文标题
新的并发订单维护数据结构
New Concurrent Order Maintenance Data Structure
论文作者
论文摘要
\ emph {order-Maintenance}（OM）数据结构维护插入，删除和比较项目的总订单列表。作为基本数据结构，OM具有许多应用程序，例如在图形中维持拓扑顺序，核心数和桁架，并以统一建模语言（UML）规范维护有序集。多功能机器的患病率表明将这种基本数据结构并行。本文提出了一种新的并行OM数据结构，该结构支持并行插入，删除和比较。具体而言，通过有效使用锁定，并行插入和删除可以同步，最高$ 7 $ x和$ 5.6 $ x的速度，$ 64美元的工人。一个很大的优势是，比较是无锁的，因此它们可以与其他插入和删除同行执行，这些插入和删除可达到高达$ 34.4 $ x的速度，而$ 64美元的工人。典型的真实应用程序维护订单列表，这些订单列表总是比插入和删除的比较部分要大得多。例如，在核心维护中，与某些图中的插入和删除相比，比较数量高297倍。这就是为什么无锁订单比较是实践中的突破的原因。
The \emph{Order-Maintenance} (OM) data structure maintains a total order list of items for insertions, deletions, and comparisons. As a basic data structure, OM has many applications, such as maintaining the topological order, core numbers, and truss in graphs, and maintaining ordered sets in Unified Modeling Language (UML) Specification. The prevalence of multicore machines suggests parallelizing such a basic data structure. This paper proposes a new parallel OM data structure that supports insertions, deletions, and comparisons in parallel. Specifically, parallel insertions and deletions are synchronized by using locks efficiently, which achieve up to $7$x and $5.6$x speedups with $64$ workers. One big advantage is that the comparisons are lock-free so that they can execute highly in parallel with other insertions and deletions, which achieve up to $34.4$x speedups with $64$ workers. Typical real applications maintain order lists that always have a much larger portion of comparisons than insertions and deletions. For example, in core maintenance, the number of comparisons is up to 297 times larger compared with insertions and deletions in certain graphs. This is why the lock-free order comparison is a breakthrough in practice.
