Relaxing Concurrent Data-structure Semantics for Increasing Performance: A Multi-structure 2D Design Framework
Adones Rukundo, Aras Atalar and Philippas Tsigas
在文献中提出了大量工作,建议语义放松并发数据结构,以提高可扩展性和性能。 通过放松数据结构的语义,更大的设计空间,允许较弱的同步和更有用的并行性,已经揭幕。 调查新的数据结构设计,能够交易语义,以单调的方式获得更好的性能,是该领域的一个重大挑战。 为了应对这一挑战,我们提出了高效的无锁、并发数据结构设计框架,用于超序语义放松。 我们的框架引入了一种新的二维算法设计,它使用给定数据结构实现的多个实例。 我们设计的第一个维度是将操作扩展到的数据结构实例的数量,以便通过不连接的内存访问实现更高的并行性。 第二个维度是单个线程的连续操作次数,可以保持在同一数据结构实例中,以便从数据定位中受益。 我们的设计可以灵活地探索这个二维空间,通过在紧密的确定性放松约束内放松,实现单调地提高吞吐量性能的特性,正如我们在论文中证明的那样。 我们展示了我们的框架如何实例化无锁的超序队列,堆栈,计数器和队列。 实验评估表明,我们的二维数据结构:i)在可扩展性和吞吐量性能方面明显优于之前受人尊敬的数据结构,并且ii)随着放松的增加而单调地增加吞吐量。
There has been a significant amount of work in the literature proposing semantic relaxation of concurrent data structures for improving scalability and performance. By relaxing the semantics of a data structure, a bigger design space, that allows weaker synchronization and more useful parallelism, is unveiled. Investigating new data structure designs, capable of trading semantics for achieving better performance in a monotonic way, is a major challenge in the area. We algorithmically address thi...
