A transactional approach to lock scalability
Most software transactional memory implementations execute code using fine-grained optimistic concurrency control. This does not perform well with low contention data structures where fine grained conflict detection means manipulating metadata for every object touched and optimistic concurrency control imposes the overhead of making thread private shadow copies. Also, a purely optimistic approach does not coexist naturally with legacy code that is either already concurrent using locks or does IO operations that cannot be revoked. We try to address these problems by presenting a new form of the reader writer locks used by the vast majority of concurrent code today. Along with the traditional lock/unlock operations, these new locks support STM-like management of shadow versions that can be used when desired by the programmer. We show how existing lock based code can be scaled to perform as well as an STM, with few changes to the existing code base. We also show as a corollary that our design allows construction of data structures that retain strict fairness between threads, while simultaneously allowing disjoint access parallelism.

title: A runtime system for software lock elision
abstract: The advent of multi-core processors means that exploiting parallelism is key to increasing the performance of programs. Many researchers have studied the use of atomic blocks as a way to simplify the construction of scalable parallel programs. However, there is a large body of existing lock-based code, and typically it is incorrect to simply replace lock-based critical sections with atomic blocks. Some problems include the need to do IO within critical sections; the use of primitives such as condition variables; and the sometime reliance on underlying lock properties such as fairness or priority inheritance.
 In this paper we investigate an alternative: a software runtime system that allows threads to speculatively execute lock-based critical sections in parallel. Execution proceeds optimistically, dynamically detecting conflicts between accesses by concurrent threads. However, if there are frequent conflicts, or if there are attempts to perform operations that cannot be done speculatively, then execution can fall back to acquiring a lock. Conversely, implementations of atomic blocks must typically serialise all operations that cannot be performed speculatively.
 Our runtime system has been designed with the requirements of systems code in mind: in particular it does not require that programs be written in type-safe languages, nor does it require any form of garbage collection. Furthermore, we never require a thread holding a lock to wait for a thread that has speculatively acquired it. This lets us retain any useful underlying properties of a given lock implementation, e.g. fairness or priority inheritance.

title: Fast and Generalized Polynomial Time Memory Consistency Verification
abstract: The problem of verifying multi-threaded execution against the memory consistency model of a processor is known to be an NP hard problem. However polynomial time algorithms exist that detect almost all failures in such execution. These are often used in practice for microprocessor verification. We present a low complexity and fully parallelized algorithm to check program execution against the processor consistency model. In addition our algorithm is general enough to support a number of consistency models without any degradation in performance. An implementation of this algorithm is currently used in practice to verify processors in the post silicon stage for multiple architectures.

title: Improved Probabilistic Models for 802.11 Protocol Verification
abstract: The IEEE 802.11 protocol is a popular standard for wireless local area networks. Its medium access control layer (MAC) is a carrier sense multiple access with collision avoidance (CSMA/CA) design and includes an exponential backoff mechanism that makes it a possible target for probabilistic model checking. In this work, we identify ways to increase the scope of application of probabilistic model checking to the 802.11 MAC. Current techniques model only specialized cases of minimum size. To work around this problem, we identify properties of the protocol that can be used to simplify the models and make verification feasible. Using these observations, we present generalized probabilistic timed automata models that are independent of the number of stations. We optimize these through a novel abstraction technique while preserving probabilistic reachability measures. We substantiate our claims of a significant reduction due to our optimization with results from using the probabilistic model checker PRISM.

title: Scalable Probabilistic Models for 802.11 Protocol Verification
abstract: The IEEE 802.11 protocol is a popular standard for wireless local area networks. Its medium access control layer (MAC) is a carrier sense multiple access with collision avoidance (CSMA/CA) design and includes an exponential backoff mechanism that makes it a possible target for probabilistic model checking. In this work, we identify ways to increase the scope of application of probabilistic model checking to the 802.11 MAC. Current techniques do not scale to networks of even moderate size. To work around this problem, we identify properties of the protocol that can be used to simplify the models and make verification feasible. Using these observations, we directly optimize the probabilistic timed automata models while preserving probabilistic reachability measures. We substantiate our claims of significant reduction by our results from using the probabilistic model checker PRISM.