Email
wwei9 (at) lsu.edu

Address
2126 Digital Media Center
340 E Parker Blvd
Baton Rouge, LA, 70803

Google Summer of Code: Lock-free data structure meets HPX runtime system

August 20, 2020

I am proud and excited that this year I got selected as student contributor in Google Summer of Code project: Concurrent Data Structure. The project idea I proposed is to add user-level lightweight threads provided by HPX runtime system to LibCDS (a Concurrent Data Structures library). Both libraries are implemented in modern  C++ fashion. One of the most significant contributions out of this three-month long project is that, now we can use hazard pointer based lock-free data structure (i.e. concurrent map) in LibCDS using HPX threads! 

 

Here is a bit background about my work. Hazard pointer has been discussed in C++ standard communities for years (i.e. C++ proposal p1121r0), and has been implemented in Facebook Folly, LibCDS, and other C++ libraries. HPX is a C++ Standard Library for Concurrency and Parallelism, and is a Asynchronous Many-Task System. Currently, HPX uses boost lock-free queue to schedule tasks. It will be great to have another lock-free backend to compare and look for potential performance improvement. LibCDS is a good candidate due its mature implementation in lock-free data structure and can be easily modularized (it already has threading backends to support different platforms). So it will be good fit for us to explore integrating HPX and LibCDS.

 

I believe I have a fruitful summer throughout this project, as this work has the following results and impacts:

  1. Media story:

  2. YouTube Seminars

    • ​After 1st month of GSoC project, I gave a talk at host organization (STE||AR group)'s 2020 Summer Symposium to share about the overview of this project and report my coding progress: https://youtu.be/1c9XG053VOU  

  3. ​Monthly reports:

  4. Multiple merged pull requests where contains my own commits and discussions with the team

 

I wrote documentation that wraps up GSoC project and will be useful for future contribution: https://github.com/STEllAR-GROUP/hpx/blob/libcds-module/libs/libcds/docs/index.rst#libcds. In short, the hazard-pointer related containers in LibCDS now can use HPX threading. In the future, we are considering to have more SMR (i.e. dynamic hazard pointer, RCU) support in HPX threading, also have LibCDS data structure in HPX internal scheduler. 

 

One of the most technical challenging in this project I've learned is that, finding all thread-private data (thread_local) and kernel-level synchronization primitives (i.e. mutex) in LibCDS project. These features are key to the success of this project. With all these findings, I am able to move forward and replace these threading features in kernel-level to HPX user-level. One of the most joyful parts is to read hazard pointer related papers, which provide theoretical foundation of my work. I read through most of Maged Michael (creator of HP) talks and papers and also relevant C++ proposals. It is a pleasure to see how HP concepts are involved over the years and how it is implemented in modern C++. Lastly, I have learned that communication and leadership is extremely important in this project. I am the lead coder in this project and work with people from various background. It is critical to not only code but also express the impact of my code to the team to make sure everyone is on the same page. 

 

Over the summer, I collaborate with two teams STE||AR group and LibCDS team (9 people in total). Participants are very diverse and are located in different timezone and countries (United States, Switzerland, Russia, etc.). We host weekly Zoom meeting to discuss features implemented and to-do, and use Slack and IRC for rapid discussion and development. I would like deeply thank all of my mentors and teammates John, Mickael, Hartmut, Auriane, Alex, Evgeny, Max. Without their supports and guidance, I could not achieve such results. Overall, I believe we have a very pleasure journey of working together and embrace such diversity! I look forward to the future development of HPX-LibCDS!

 

 

 

 

 

 

Share on Facebook
Share on Twitter
Please reload

Weile WEI

LSU | C++ | HPC | Future SWE

  • ghat
  • Black LinkedIn Icon
  • Black Tumblr Icon
  • Black YouTube Icon
Copyright @ 2017 Weile Wei
This site was designed with the
.com
website builder. Create your website today.
Start Now