2015 · 110 citations · 40 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureData StructuresParallel ComputingConcurrent ProgrammingData ParallelismData SynchronizationScalable Algorithm DesignAsynchronous ExecutionConcurrency ModelsEvaluation
We introduce "asynchronized concurrency (ASCY)," a paradigm consisting of four complementary programming patterns. ASCY calls for the design of concurrent search data structures (CSDSs) to resemble that of their sequential counterparts. We argue that ASCY leads to implementations which are portably scalable: they scale across different types of hardware platforms, including single and multi-socket ones, for various classes of workloads, such as read-only and read-write, and according to different performance metrics, including throughput, latency, and energy. We substantiate our thesis through the most exhaustive evaluation of CSDSs to date, involving 6 platforms, 22 state-of-the-art CSDS algorithms, 10 re-engineered state-of-the-art CSDS algorithms following the ASCY patterns, and 2 new CSDS algorithms designed with ASCY in mind. We observe up to 30% improvements in throughput in the re-engineered algorithms, while our new algorithms out-perform the state-of-the-art alternatives.
40
Andrew Baumann, Paul Barham, Pierre-Évariste Dagand et al. · 2009 · 797 citations
Rajesh Nishtala, Hans Fugal, Steven Grimm et al. · Networked Systems Design and Implementation · 2013 · 597 citations