Leveraging Hardware Message Passing for Efficient Thread Synchronization

As the level of parallelism in manycore processors keeps increasing, providing efficient mechanisms for thread syn-chronization in concurrent programs is becoming a ma-jor concern. On cache-coherent shared-memory processors, synchronization efficiency is ultimately limited by the per-formance of the underlying cache coherence protocol. This paper studies how hardware support for message passing can improve synchronization performance. Considering the ubiquitous problem of mutual exclusion, we adapt two state-of-the-art solutions used on shared-memory processors, namely the server approach and the combining approach, to leverage the potential of hardware message passing. We propose HYBCOMB, a novel combining algorithm that uses both message passing and shared memory features of emerg-ing hybrid processors. We also introduce MP-SERVER, a straightforward adaptation of the server approach to hard-ware message passing. Evaluation on Tilera’s TILE-Gx pro-cessor shows that MP-SERVER can execute contended criti-cal sections with unprecedented throughput, as stalls related to cache coherence are removed from the critical path. HYB-COMB can achieve comparable performance, while avoiding the need to dedicate server cores. Consequently, our queue and stack implementations, based on MP-SERVER and HYB-COMB, largely outperform their most efficient pure-shared-memory counterparts