Scalable Consistency in the Multi-core Era

The advent of heterogeneous many-core systems has increased the spectrum of achievable performance from multi-threaded programming. As the processor components become more distributed, the cost of synchronization and communication needed to access the shared resources increases. Concurrent linearizable access to shared objects can be prohibitively expensive in a high contention workload. Though there are various mechanisms (e.g., lock-free data structures) to circumvent the synchronization overhead in linearizable objects, it still incurs performance overhead for many concurrent data types. Moreover, many applications do not require linearizable objects and apply ad-hoc techniques to eliminate synchronous atomic updates. In this thesis, we propose the Global-Local View Model. This programming model exploits the heterogeneous access latencies in many-core systems. In this model, each thread maintains different views on the shared object: a thread-local view and a global view. As the thread-local view is not shared, it can be updated without incurring synchronization costs. The local updates become visible to other threads only after the thread-local view is merged with the global view. This scheme improves the performance at the expense of linearizability. Besides the weak operations on the local view, the model also allows strong operations on the global view. Combining operations on the global and the local views, we can build data types with customizable consistency semantics on the spectrum between sequential and purely mergeable data types. Thus the model provides a framework that captures the semantics of Multi-View Data Types. We discuss a formal operational semantics of the model. We also introduce a verification method to verify the correctness of the implementation of several multi-view data types. Frequently, applications require updating shared objects in an “all-or-nothing” manner. Therefore, the mechanisms to synchronize access to individual objects are not sufficient. Software Transactional Memory (STM) is a mechanism that helps the programmer to correctly synchronize access to multiple mutable shared data by serializing the transactional reads and writes. But under high contention, serializable transactions incur frequent aborts and limit parallelism, which can lead to severe performance degradation. Mergeable Transactional Memory (MTM), proposed in this thesis, allows accessing multi-view data types within a transaction. Instead of aborting and re-executing the transaction, MTM merges its changes using the data-type specific merge semantics. Thus it provides a consistency semantics that allows for more scalability even under contention. The evaluation of our prototype implementation in Haskell shows that mergeable transactions outperform serializable transactions even under low contention while providing a structured and type-safe interface