Non-blocking algorithms are a class of algorithms that provide guarantees of progress within a system. These progress guarantees come from the fine-grained synchronization techniques incorporated into their design. There are a number of various non-blocking designs and implementations of concurrent algorithms. However, trade-offs between performance and non-blocking algorithm design decisions are poorly understood. The most common method to measure the performance of non-blocking algorithms is to analyze the number of operations completed over a period of time. Unfortunately, this coarse-grained approach for performance analysis is unable to capture and explain many of the nuances of the behavior of non-blocking algorithms. This can result in a flawed perception of such algorithms, which may lead to a misguided use of them. This work provides a fine-grained approach for the analysis of the design and use of non-blocking algorithms. To support this analysis, we introduce a methodology that enables a user to simulate an application's use of an arbitrary non-blocking algorithm and extract insightful information from the performance results. To better understand the behavior of non-blocking algorithms, we present metrics to measure the effectiveness of the key synchronization and memory management techniques used in non-blocking algorithms. Our analysis combines these new metrics with several well-known hardware metrics to explain key behaviors and develop new insights. To demonstrate the effectiveness of the proposed methodology, we integrate it within the Tervel framework and analyzed Tervel's vector in various use cases. Our experiments show that helping mechanisms negatively impact throughput by increasing misaligned data cache accesses. Furthermore, by studying the correlations between different metrics, we are able to observe the effect of thread interference on the CPU instructions and instruction cache invalidation, and then link the decrease in work completed to this effect. In addition to the provided information, these metrics revealed implementation errors that did not affect correctness but caused increased thread congestion.

The vector is a fundamental data structure, which provides constant-time access to a dynamically-resizable range of elements. Currently, there exist no wait-free vectors. The only non-blocking version supports only a subset of the sequential vector API and exhibits significant synchronization overhead caused by supporting opposing operations. Since many applications operate in phases of execution, wherein each phase only a subset of operations are used, this overhead is unnecessary for the majority of the application. To address the limitations of the non-blocking version, we present a new design that is wait-free, supports more of the operations provided by the sequential vector, and provides alternative implementations of key operations. These alternatives allow the developer to balance the performance and functionality of the vector as requirements change throughout execution. Compared to the known non-blocking version and the concurrent vector found in Intel's TBB library, our design outperforms or provides comparable performance in the majority of tested scenarios. Over all tested scenarios, the presented design performs an average of 4.97 times more operations per second than the non-blocking vector and 1.54 more than the TBB vector. In a scenario designed to simulate the filling of a vector, performance improvement increases to 13.38 and 1.16 times. This work presents the first ABA-free non-blocking vector. Unlike the other non-blocking approach, all operations are wait-free and bounds-checked and elements are stored contiguously in memory.

Identifying design patterns that limit the performance of multi-core algorithms is a challenging task. There are many known methods by which threads synchronize their actions and each method may exhibit different behavior in different use cases. These use cases may vary in regards to the workload being executed, number of parallel tasks, dependencies between these tasks, and the behavior of the system scheduler. Restructuring algorithms to overcome performance limitations requires intimate knowledge on how these algorithms utilize the hardware. In our experience, we have found a lack of adequate tools to gain such knowledge. To address this, we have enhanced and implemented additional data sampler modules for OVIS's Lightweight Distributed Metric Service (LDMS) to enable scalable distributed collection of hardware performance counter data. These modules provide an interface by which LDMS can utilize the PAPI library, Linux perf tools, and RAPL to collect hardware performance data of interest. Using these samplers, we plan to monitor the intra-node behavior, including contention for node level shared resources, of multi-core applications for a diverse set of use cases. We are currently exploring how the values reported are affected by the level of concurrency, the synchronization methodologies, and progress guarantees. We hope to use this information to identify ways to restructure algorithms to increase their performance.