You are here: Home projects

Projects

  • Software-Improved Hardware Lock Elision.  Software extension mechanisms that considerably improve the concurrency and speedup levels attained by lock based programs using HTM-based lock elision.
  • Consistency Oblivious Programming.  A methodology to design data structures with TM, both in hardware and in the compiler, so as to yield good performance and scalability in programs where TM alone had not previously been useful.
  • Fast concurrent queues for x86 processors.  We show how to rely on fetch-and-add (F&A), a weak synchronization primitive that is available on x86 processors, to construct a nonblocking (lock-free) linearizable concurrent FIFO queue which, despite the F&A being a contended hot spot, outperforms prior FIFO queue implementations.
  • Flat combining. Traditional data-structure designs, whether lock-based or lock-free, provide parallelism via fine grained synchronization among threads. We introduce a new synchronization paradigm based on coarse locking, which we call flat-combining.
  • Fast and scalable rendezvous. In an asymmetric rendezvous system, such as an unfair synchronous queue and an elimination array, threads of two types, consumers and producers, show up and are matched, each with a unique thread of the other type. We present a new highly scalable, high throughput asymmetric rendezvous system that outperforms prior synchronous queue and elimination array implementations under both symmetric and asymmetric workloads (more operations of one type than the other).
  • Elimination-Diffraction trees. There are three common ways to implement concurrent pools in the Java JDK6.0: the SynchronousQueue, the LinkedBlockingQueue, and the ConcurrentLinkedQueue. Unfortunately, most pool implementations, including the ones in the JDK, are based on centralized structures like a queue or a stack, and thus are limited in their scalability.  The ED-Tree is a distributed pool structure based on a combination of the elimination-tree and diffracting-tree paradigms, allows high degrees of parallelism with reduced contention.
  • Deuce STM. A powerful open source java support for software transactional memory. Deuce lets you develop highly concurrent applications without worrying about concurrency. Deuce is an extensible framework, which allows developers to develop/extend their own STM algorithms
  • Interrupting snapshots. Highly scalable wait-free implementation of a concurrent size() operation based on a new lock-free interrupting snapshots algorithm for the classical atomic snapshot problem.
  • C++ Concurrency Package. C++ multi-platform memory-model solution, with Java orientation. Accompanied by C++ and Java Algorithms. Developed by Ms. Moran Tzafrir.
  • Hopscotch hashing. New class of resizable sequential and concurrent hash map algorithms directed at both uni-processor and multicore machines.
  • VMF & VMSTM.  In the spirit of the new trend towards hardware assited STMs (HASTMs), we show how one can add a simple hardware element, the virtual memory filter (VMF) that provides dynamic identification and execution of STM functions on transactionally shared locations.  VMSTM is a software transactional memory system that provides VMF-like capabilities by leveraging virtual memory hardware available in contemporary hardware.
  • Union find.  Highly efficient and flexible algorithms for the union-find and union-find-delete problems.